Separating regular languages with first-order logic

DOI10.2168/LMCS-12(1:5)2016MaRDI QIDQ2794672zbMATH OpenOpenAlexFDO

Authors Thomas Place, Marc Zeitoun

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

zbMATH Keywords

Ehrenfeucht-Fraïssé gamesexpressive powerfirst-order logicinfinite wordsregular languagessemigroupsseparationwords

Mathematics Subject Classification ID

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

Recommendations

• Separating regular languages with first-order logic
• Separating regular languages by piecewise testable and unambiguous languages
• Separating regular languages with two quantifiers alternations
• Separating regular languages by locally testable and locally threshold testable languages
• On separation by locally testable and locally threshold testable languages

Cited in

(38)

• Classifying regular languages by a split game
• The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages
• Certifying DFA bounds for recognition and separation
• Measuring power of locally testable languages
• Recognizing pro-\(\mathrm{R}\) closures of regular languages
• Certifying inexpressibility
• Reducibility of pointlike problems
• Pointlike sets for varieties determined by groups
• Quantifier alternation for infinite words
• Separating regular languages by piecewise testable and unambiguous languages
• Separation and the successor relation
• Separating regular languages by locally testable and locally threshold testable languages
• Minimal consistent DFA revisited
• Merge decompositions, two-sided Krohn-Rhodes, and aperiodic pointlikes
• Separating regular languages with two quantifier alternations
• The covering problem
• Separating regular languages with first-order logic
• A survey on difference hierarchies of regular languages
• AN APPLICATION OF FIRST-ORDER LOGIC TO THE STUDY OF RECOGNIZABLE LANGUAGES
• Regular separability of one counter automata
• Regular separability of well-structured transition systems
• Recursive axiomatisations from separation properties
• The Complexity of Separation for Levels in Concatenation Hierarchies
• On All Things Star-Free
• Separating the words of a language by counting factors
• Covering and separation for logical fragments with modular predicates
• Separability by short subsequences and subwords
• 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
• Timed games and deterministic separability
• Deciding the existence of interpolants and definitions in first-order modal logic
• Closing star-free closure
• Regular separators for VASS coverability languages
• Problems of algorithmic decidability and axiomatizability of finite subset algebra for binary operations
• Deterministic and game separability for regular languages of infinite trees
• Modal separation of fixpoint formulae
• Pointlike sets and separation: a personal perspective

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2794672)