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)
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) First-order arithmetic and fragments (03F30) Descriptive complexity and finite models (68Q19) Hierarchies of computability and definability (03D55)
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