Separating Regular Languages with First-Order Logic
From MaRDI portal
Publication:2794672
DOI10.2168/LMCS-12(1:5)2016zbMath1448.68273OpenAlexW2004710041MaRDI QIDQ2794672
Publication date: 11 March 2016
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2168/lmcs-12(1:5)2016
wordssemigroupsfirst-order logicseparationexpressive powerregular languagesinfinite wordsEhrenfeucht-Fraïssé games
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Algebraic theory of languages and automata (68Q70) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items
Reducibility of pointlike problems, Pointlike sets and separation: a personal perspective, A Survey on Difference Hierarchies of Regular Languages, Minimal consistent DFA revisited, Pointlike sets for varieties determined by groups, Certifying DFA bounds for recognition and separation, Measuring power of locally testable languages, Unnamed Item, Recognizing pro-\(\mathrm{R}\) closures of regular languages, Living without Beth and Craig: Definitions and Interpolants in Description and Modal Logics with Nominals and Role Inclusions, First-order separation over countable ordinals, Measuring power of generalised definite languages, Unnamed Item, Certifying inexpressibility, Separating the Words of a Language by Counting Factors, The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages, Unnamed Item, Quantifier Alternation for Infinite Words, Unnamed Item, The Complexity of Separation for Levels in Concatenation Hierarchies, On All Things Star-Free, Merge Decompositions, Two-sided Krohn–Rhodes, and Aperiodic Pointlikes
