scientific article; zbMATH DE number 7407796

MaRDI QIDQ5155687

Thomas Place, Marc Zeitoun

Publication date: 8 October 2021

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

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

zbMATH Keywords

wordsfirst-order logicseparationregular languagesmembershipconcatenation hierarchiesquantifier alternation

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Related Items

Measuring power of locally testable languages, First-order separation over countable ordinals, The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies, Characterizing level one in group-based concatenation hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Discrete algebraic methods. Arithmetic, cryptography, automata and groups
• First-order logic and star-free sets
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• Classifying regular events in symbolic logic
• The dot-depth hierarchy of star-free languages is infinite
• Polynomial closure and unambiguous product
• Generic results for concatenation hierarchies
• Dot-depth of star-free events
• Separating Regular Languages by Piecewise Testable and Unambiguous Languages
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Separating regular languages with two quantifier alternations
• Adding Successor
• Going Higher in First-Order Quantifier Alternation Hierarchies on Words
• An Explicit Formula for the Intersection of Two Polynomials of Regular Languages
• Efficient Separability of Regular Languages by Subsequences and Suffixes
• On finite monoids having only trivial subgroups