Results 21 to 30 of about 1,641 (261)
A Myhill-Nerode theorem for automata with advice [PDF]
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]
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]
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
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]
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
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]
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
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]
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
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

