Generalization of the Double-Reversal Method of Finding a Canonical Residual Finite State Automaton
Autor: | Hellis Tamm |
---|---|
Rok vydání: | 2015 |
Předmět: |
Discrete mathematics
Büchi automaton Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Reversible cellular automaton Combinatorics Deterministic finite automaton Regular language Deterministic automaton Probabilistic automaton Computer Science::Programming Languages Two-way deterministic finite automaton Nondeterministic finite automaton Computer Science::Formal Languages and Automata Theory Mathematics |
Zdroj: | Descriptional Complexity of Formal Systems ISBN: 9783319192246 DCFS |
DOI: | 10.1007/978-3-319-19225-3_23 |
Popis: | Residual finite state automata (RFSA) are a subclass of nondeterministic finite automata with the property that every state of an RFSA defines a residual language (a left quotient) of the language accepted by the RFSA. Every regular language has a unique canonical RFSA which is a minimal RFSA accepting the language. We study the relationship of RFSAs with atoms of regular languages. We generalize the double-reversal method of finding a canonical RFSA, presented by Denis, Lemay, and Terlutte. |
Databáze: | OpenAIRE |
Externí odkaz: |
načítá se...