Non-definability of Languages by Generalized First-order Formulas over (N,+)

DOI10.1109/LICS.2012.55zbMath1361.68101arXiv1204.6179OpenAlexW2075225990MaRDI QIDQ2986821

Andreas Krebs, A. V. Sreejith

Publication date: 16 May 2017

Published in: 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.6179

zbMATH Keywords

descriptive complexitylogic on wordsCrane-Beach conjectureextended first-order logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (1)

Unnamed Item

This page was built for publication: Non-definability of Languages by Generalized First-order Formulas over (N,+)