A CHARACTERIZATION OF THE ARITHMETICAL HIERARCHY BY LANGUAGE EQUATIONS
From MaRDI portal
Publication:5704378
DOI10.1142/S012905410500342XzbMath1090.68062MaRDI QIDQ5704378
Publication date: 14 November 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03F30: First-order arithmetic and fragments
68Q19: Descriptive complexity and finite models
03D55: Hierarchies of computability and definability
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the number of nonterminals in linear conjunctive grammars
- Characterizations and computational complexity of systolic trellis automata
- Reversal-bounded multipushdown machines
- Conjunctive grammars and systems of language equations
- Boolean grammars
- Number of variables is equivalent to space
- On the equivalence of linear conjunctive grammars and trellis automata
- Some classifications of context-free languages