Abstract | ||
---|---|---|
We study deterministic finite automata (DFA) with recursive calls, that is, finite sequences of component DFAs that can call each other recursively. DFAs with recursive calls are akin to recursive state machines and unrestricted hierarchic state machines. We show that they are language equivalent to deterministic pushdown automata (DPDA). |
Year | DOI | Venue |
---|---|---|
2003 | 10.1016/S0020-0190(03)00281-3 | Inf. Process. Lett. |
Keywords | Field | DocType |
deterministic finite automaton,pushdown automaton,component dfas,language equivalent,state machine,finite sequence,unrestricted hierarchic state machine,recursive call,deterministic finite automata,formal language,pushdown automata,formal languages | Deterministic context-free grammar,Discrete mathematics,Quantum finite automata,Deterministic automaton,Nested word,Deterministic finite automaton,Computer science,Deterministic pushdown automaton,Algorithm,Recursive language,Theoretical computer science,DFA minimization | Journal |
Volume | Issue | ISSN |
87 | 4 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 12 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jean H. Gallier | 1 | 749 | 111.86 |
Salvatore La Torre | 2 | 912 | 52.42 |
supratik mukhopadhyay | 3 | 267 | 39.44 |