Separating regular languages with first-order logic

DOI10.1145/2603088.2603098zbMath1401.68165arXiv1402.3277OpenAlexW2004710041MaRDI QIDQ4635660

Thomas Place, Marc Zeitoun

Publication date: 23 April 2018

Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

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

zbMATH Keywords

wordssemigroupsfirst-order logicseparationexpressive powerregular languagesinfinite wordsEhrenfeucht-Fraïssé games

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (8)

Pointlike sets and separation: a personal perspective ⋮ On Upper and Lower Bounds on the Length of Alternating Towers ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Conelikes and ranker comparisons ⋮ Unnamed Item ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ Learning algorithms ⋮ Profinite topologies

This page was built for publication: Separating regular languages with first-order logic