In Pattern Recognition and Image Analysis, pages 49–61, 1992.
FINITE STATE OTOMATA UPDATE
Inferring regular languages in polynomial update time. American Mathematical Society, volume 9, pages 541–544, 1958. Finite automata and the representation of events. McCarthy, editors, Automata Studies, Annals of Math. Representation of events in nerve nets and finite automata. Introduction to Automata Theory, Languages, and Computation. Characteristic sets for polynomial grammatical inference. Complexity of automaton identification from given data. Computers and Intractability, a Guide to the Theory of NP-Completness. Apprentissage de langages réguliers á l’aide d’automates non déterministes. Technical report, Laboratoire de Calcul de la Faculté des Sciences de l’Université de Lille, 1970.į. On the minimalization of non-deterministic automaton.
In Mathematical Theory of Automata, volume 12 of MRI Symposia Series, pages 52–561. Canonical regular expressions and minimal state graphs for definite events. A note about minimal non-deterministic automata. This process is experimental and the keywords may be updated as the learning algorithm improves.Ī. These keywords were added by machine and not by the authors. We study the complexity of several decision and construction problems linked to the class of RFSA: most of them are PSPACE-complete.
We provide an algorithm that computes the canonical RFSA equivalent to a given NFA. Moreover, this canonical RFSA may be exponentially smaller than the equivalent minimal DFA but it also may have the same number of states as the equivalent minimal DFA, even if minimal equivalent NFA are exponentially smaller. We prove that for every regular language L, there exists a unique RFSA that recognizes L and which has both a minimal number of states and a maximal number of transitions. We introduce a subclass of non deterministic finite automata (NFA) that we call Residual Finite State Automata (RFSA): a RFSA is a NFA all the states of which define residual languages of the language it recognizes.
0 kommentar(er)
