Results 21 to 30 of about 1,576 (262)
Alternating register automata on finite words and trees [PDF]
Logical 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
CoRR, 2015 This is a reissue of the book Tree Automata by F. Gécseg and M. Steinby originally published in 1984 by Akadémiai Kiadó, Budapest. Some mistakes have been corrected and a few obscure passages have been clarified. Moreover, some more recent contributions and current lines of research are reviewed in an appendix that also contains several new references.
Ferenc Gécseg, Magnus Steinby
openaire +2 more sources
Emptiness Problems for Distributed Automata [PDF]
Electronic 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
Determinization and Minimization of Automata for Nested Words Revisited
Algorithms, 2021 We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions (NREs) from the usual XPath benchmark to nested word automata (NWAs).
Joachim Niehren, Momar Sakho
doaj +1 more source
Theoretical 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 +3 more sources
Weighted DAG Automata for Semantic Graphs [PDF]
Computational 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
Information and Computation, 2017 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Boiret, Adrien +3 more
openaire +2 more sources
Efficient Implementation for Deterministic Finite Tree Automata Minimization
Journal 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
Interpolant Tree Automata and their Application in Horn Clause Verification [PDF]
Electronic Proceedings in Theoretical Computer Science, 2016 This paper investigates the combination of abstract interpretation over the domain of convex polyhedra with interpolant tree automata, in an abstraction-refinement scheme for Horn clause verification.
Bishoksan Kafle, John P. Gallagher
doaj +1 more source
Theoretical Computer Science, 1984 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Karel Culík II, Sheng Yu 0001
openaire +1 more source