Results 21 to 30 of about 6,057,560 (362)
The logical strength of B\"uchi's decidability theorem [PDF]
Logical Methods in Computer Science, 2019 We study the strength of axioms needed to prove various results related to automata on infinite words and B\"uchi's theorem on the decidability of the MSO theory of $(N, {\le})$.
Leszek Kołodziejczyk +3 more
doaj +1 more source
Improved Undecidability Results for Reachability Games on Recursive Timed Automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We study reachability games on recursive timed automata (RTA) that generalize Alur-Dill timed automata with recursive procedure invocation mechanism similar to recursive state machines. It is known that deciding the winner in reachability games on RTA is
Shankara Narayanan Krishna +2 more
doaj +1 more source
Mathematics, 2020 In this paper, which is based on a real-life motivation, we present an algebraic theory of automata and multi-automata. We combine these (multi-)automata using the products introduced by W.
Štěpán Křehlík
doaj +1 more source
Determinising Parity Automata [PDF]
, 2014 Parity word automata and their determinisation play an important role in automata and game theory. We discuss a determinisation procedure for nondeterministic parity automata through deterministic Rabin to deterministic parity automata. We prove that the
Schewe, Sven, Varghese, Thomas
core +1 more source
Handbook of Automata Theory [PDF]
Handbook of Automata Theory, 2015 This text is devoted to the theory of varieties, which provides an important tool, based in universal algebra, for the classification of regular languages.
Howard Straubing, Pascal Weil
semanticscholar +1 more source
Minimization via duality [PDF]
, 2012 We show how to use duality theory to construct minimized versions of a wide class of automata. We work out three cases in detail: (a variant of) ordinary automata, weighted automata and probabilistic automata.
A. Beimel +9 more
core +2 more sources
Symbolic Algorithms for Language Equivalence and Kleene Algebra with Tests [PDF]
, 2014 We first propose algorithms for checking language equivalence of finite automata over a large alphabet. We use symbolic automata, where the transition function is compactly represented using a (multi-terminal) binary decision diagrams (BDD). The key idea
Bouajjani A. +10 more
core +5 more sources
On Learning Nominal Automata with Binders [PDF]
Electronic Proceedings in Theoretical Computer Science, 2019 We investigate a learning algorithm in the context of nominal automata, an extension of classical automata to alphabets featuring names. This class of automata captures nominal regular languages; analogously to the classical language theory, nominal ...
Yi Xiao, Emilio Tuosto
doaj +1 more source
Quantum cellular automata and free quantum field theory [PDF]
Frontiers of Physics, 2016 In a series of recent papers [1–4] it has been shown how free quantum field theory can be derived without using mechanical primitives (including space-time, special relativity, quantization rules, etc.), but only considering the easiest quantum algorithm
G. D’Ariano, P. Perinotti
semanticscholar +1 more source
On structure of isomorphisms of universal graphic automata [PDF]
Известия Саратовского университета. Новая серия: Математика. Механика. ИнформатикаAutomata theory is one of the branches of mathematical cybernetics, that studies information transducers that arise in many applied problems. The major objective of automata theory is to develop methods by which one can describe and analyze the dynamic ...
Molchanov, Vladimir Aleksandrovich +1 more
doaj +1 more source