Nondeterministic Moore Automata and Brzozowski’s Algorithm
作者： Giusi Castiglione , Antonio Restivo , Marinella Sciortino
DOI: 10.1007/978-3-642-22256-6_9
关键词: Büchi automaton 、 Algorithm 、 Two-way deterministic finite automaton 、 Nondeterministic finite automaton 、 DFA minimization 、 Mathematics 、 Deterministic automaton 、 Discrete mathematics 、 Powerset construction 、 Nondeterministic algorithm 、 Deterministic finite automaton
摘要: Moore automata represent a model that has many applications. In this paper we define notion of coherent nondeterministic automaton (NMA) and show such the same computational power classical deterministic automaton. We consider also problem constructing minimal equivalent to given NMA. propose an algorithm is variant Brzozowski's in sense it essentially structured as reverse operation subset construction performed twice.
core.ac.uk
springer.com
sci-hub.st 参考文章(27)
Elena Calude, Marjo Lipponen, Minimal Deterministic Incomplete Automata Journal of Universal Computer Science. ,vol. 3, pp. 1180- 1193 ,(1997)
J. A. Brzozowski, Canonical regular expressions and minimal state graphs for definite events Princeton University. ,(1962)
Jaya Yadav, Shruti Shukla, Kanika Sharma, Nupur Soni, Shruti Agarwal, Prabhash Chandra Pathak, Frontiers in Artificial Intelligence and Applications IOS Press. ,(2009)
Corinna Cortes, Mehryar Mohri, Learning with Weighted Transducers finite-state methods and natural language processing. pp. 14- 22 ,(2009) , 10.3233/978-1-58603-975-2-14
Pavlos Antoniou, Jan Holub, Costas S. Iliopoulos, Bořivoj Melichar, Pierre Peterlongo, Finding Common Motifs with Gaps Using Finite Automata Implementation and Application of Automata. ,vol. 4094, pp. 69- 77 ,(2006) , 10.1007/11812128_8
Deian Tabakov, Moshe Y. Vardi, Experimental evaluation of classical automata constructions international conference on logic programming. pp. 396- 411 ,(2005) , 10.1007/11591191_28
Pedro García, José Ruiz, Antonio Cano, Gloria Alvarez, None, Inference improvement by enlarging the training set while learning DFAs iberoamerican congress on pattern recognition. pp. 59- 70 ,(2005) , 10.1007/11578079_7
Ian Hodkinson, Frank Wolter, Michael Zakharyaschev, Monodic fragments of first-order temporal logics: 2000-2001 A.D international conference on logic programming. pp. 1- 23 ,(2001) , 10.1007/3-540-45653-8_1
Giusi Castiglione, Cyril Nicaud, Marinella Sciortino, A challenging family of automata for classical minimization algorithms international conference on implementation and application of automata. ,vol. 6482, pp. 251- 260 ,(2010) , 10.1007/978-3-642-18098-9_27
Galina Jirásková, Giovanni Pighizzini, Optimal simulation of self-verifying automata by deterministic automata Information & Computation. ,vol. 209, pp. 528- 535 ,(2011) , 10.1016/J.IC.2010.11.017