scientific article; zbMATH DE number 6917945

DOI10.23638/LMCS-14(3:1)2018zbMath1448.03026arXiv1707.03370MaRDI QIDQ4580330

Thomas Place, Marc Zeitoun

Publication date: 15 August 2018

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

first-order logicmembership problemregular languagescovering problemseparation problemdecidable characterization

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05)

Related Items

Pointlike sets and separation: a personal perspective, Unnamed Item, Conelikes and ranker comparisons, First-order separation over countable ordinals, The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies, Unnamed Item, Separating regular languages with two quantifier alternations, On All Things Star-Free, Generic results for concatenation hierarchies, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial closure and unambiguous product
• Graph congruences and wreath products
• Locally testable languages
• Characterizations of locally testable events
• Separating Regular Languages with First-Order Logic
• Separating Regular Languages by Piecewise Testable and Unambiguous Languages
• On Separation by Locally Testable and Locally Threshold Testable Languages
• Green’s Relations and Their Use in Automata Theory
• Regular Languages of Words over Countable Linear Orderings
• Theme and Variations on the Concatenation Product
• Weak Second‐Order Arithmetic and Finite Automata
• Decision Problems of Finite Automata Design and Related Arithmetics
• Separating regular languages with first-order logic
• Separating Regular Languages with Two Quantifiers Alternations
• Definability equals recognizability for graphs of bounded treewidth
• The Dot-Depth Hierarchy, 45 Years Later
• Algebraic decision procedures for local testability
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Efficient Separability of Regular Languages by Subsequences and Suffixes
• On finite monoids having only trivial subgroups
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Decidability of Second-Order Theories and Automata on Infinite Trees