Finite Automata and Their Decision Problems

Keywords

Automaton, Deterministic automaton, Two-way deterministic finite automaton, ω-automaton, Timed automaton

References

• The Reduction of Two-Way Automata to One-Way AutomataJ. C. Shepherdson — 1959
• Linear automaton transformationsAnil Nerode — 1958
• A variant of a recursively unsolvable problemEmil L. Post — 1946
• Gedanken-Experiments on Sequential MachinesE. F. Moore — 1956
• Representation of Events in Nerve Nets and Finite AutomataS. Kleene — 1951

Cited by

• Hardware acceleration of network intrusion detection and preventionBrendan Cronin — 2014
• On the State Hierarchy of Exploding AutomataMatthew Maly — 2010
• CONTRIBUTIONS TO THE THEORY OF FINITE-STATE BASED GRAMMARSAnssi Yli-Jyrä — 2005
• Algorithms for testing equivalence of finite automata, with a grading tool for JFLAPD.S. Norton — 2009
• Fault Equivalence in Sequential Machines.Raymond Boute, E.J. McCluskey — 1971
• Generating Deterministic ω-Automata for most LTL Formulas by the Breakpoint ConstructionAndreas Morgenstern, Klaus Schneider, Sven Lamberti — 2008
• Loops in automata and HDTOL relationsKarel Čulík, Juhani Karhumäki — 1990
• Tight bounds on the number of states of DFAs that are equivalent to n-state NFAsKazuo Iwama, Yahiko Kambayashi, Kazuya Takaki — 2000
• Complete System of Equivalent Transformations for Multitape AutomataV. É. Khachatryan — 2004
• Boolean language operations on nondeterministic automata with a pushdown of constant heightZuzana Bednárová, Viliam Geffert, Carlo Mereghetti — 2013
• ProGram: a grammar-based method for specification and hardware synthesis of communication protocolsJohnny Öberg — 1999
• Descriptional Complexity of Finite Automata: Concepts and Open ProblemsJuraj Hromkovič — 2002
• Advanced Topics on State Complexity of Combined OperationsYuan Gao — 2010
• Design and Analysis of Randomized Algorithms - Introduction to Design ParadigmsJuraj Hromkovič — 2010
• Exploratives Lernen mit partiell generierter Lehr- und LernsoftwareAndreas Kerren — 2003
• Finite-State Parsing of Phrase-Structure Languages and the Status of Readjustment Rules in GrammarD. Terence Langendoen — 2010
• Foundations of Computational LinguisticsRoland Hausser — 2001
• Quantum Automata Theory - A ReviewMika Hirvensalo — 2011
• On a Subclass of Infinite-Regular LanguagesIvan Mezník — 1988
• Erweiterungen von DendrogrammatikenWolfram-Manfred Lippe — 1980

Related papers

• Characterization of Finite State AutomatonBumpei Nakano, Yasuo Kuwata, Yasuhiko Takahara — 1981
• Decomposing a kind of weakly invertible finite automata with delay 2Gang Yao — 2003
• Complexity of control on finite automataJean‐Charles Delvenne, Vincent D. Blondel — 2006
• Operation-Preserving Functions and Autononous Factors of Finite AutomataJerzy W. Grzymala‐Busse — 1971
• Decomposing a Kind of Weakly Invertible Finite Automata with Delay 2YAOGang — 2003