Results 21 to 30 of about 1,641 (261)

A Myhill-Nerode theorem for automata with advice [PDF]

open access: yesElectronic Proceedings in Theoretical Computer Science, 2012
An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with ...
Alex Kruckman   +3 more
doaj   +1 more source

Alternating register automata on finite words and trees [PDF]

open access: yesLogical Methods in Computer Science, 2012
We study alternating register automata on data words and data trees in relation to logics. A data word (resp. data tree) is a word (resp. tree) whose every position carries a label from a finite alphabet and a data value from an infinite domain.
Diego Figueira
doaj   +1 more source

Weighted DAG Automata for Semantic Graphs [PDF]

open access: yesComputational Linguistics, 2018
Graphs have a variety of uses in natural language processing, particularly as representations of linguistic meaning. A deficit in this area of research is a formal framework for creating, combining, and using models involving graphs that parallels the ...
David Chiang   +4 more
doaj   +2 more sources

Automata for unordered trees

open access: yesInformation and Computation, 2017
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Boiret, Adrien   +3 more
openaire   +3 more sources

A Finite Exact Representation of Register Automata Configurations [PDF]

open access: yesElectronic Proceedings in Theoretical Computer Science, 2014
A register automaton is a finite automaton with finitely many registers ranging from an infinite alphabet. Since the valuations of registers are infinite, there are infinitely many configurations.
Yu-Fang Chen, Bow-Yaw Wang, Di-De Yen
doaj   +1 more source

On automata on infinite trees

open access: yesTheoretical Computer Science, 1992
It is well-known the importance of the theory of automata on infinite objects in the study of decision problems and in logic of programs, in particular when dealing with nonterminating computations. In this paper the infinite objects are infinite trees and the authors are interested in the relationship between Büchi and Muller automata (on infinite ...
Bonizzoni, P, Mauri, G
openaire   +4 more sources

Emptiness Problems for Distributed Automata [PDF]

open access: yesElectronic Proceedings in Theoretical Computer Science, 2017
We investigate the decidability of the emptiness problem for three classes of distributed automata. These devices operate on finite directed graphs, acting as networks of identical finite-state machines that communicate in an infinite sequence of ...
Antti Kuusisto, Fabian Reiter
doaj   +1 more source

Efficient Implementation for Deterministic Finite Tree Automata Minimization

open access: yesJournal of Computing and Information Technology, 2016
We address the problem of deterministic finite tree automata (DFTA) minimization. We describe a new alternative to implement both standard and incremental tree automata minimization using a well-defined graph representing the automaton to be minimized ...
Younes Guellouma, Hadda Cherroun
doaj   +1 more source

Minimisation of Multiplicity Tree Automata [PDF]

open access: yesLogical Methods in Computer Science, 2017
We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic.
Stefan Kiefer   +2 more
doaj   +1 more source

Algorithms for Converting Finite Automata Corresponding to Infinite Iterative Trees

open access: yesСовременные информационные технологии и IT-образование, 2021
In this paper, we work with some different variants of finite automata, each of which corresponds to an infinite iterative tree constructed for some given morphism.
Mikhail Abramyan, Boris Melnikov
doaj   +1 more source

Home - About - Disclaimer - Privacy