Separating regular languages with two quantifier alternations

DOI10.23638/LMCS-14(4:16)2018OpenAlexW2952682936MaRDI QIDQ4558789

Thomas Place

Publication date: 30 November 2018

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

zbMATH Keywords

wordsfirst-order logicseparationregular languagesmembershipconcatenation hierarchiesquantifier alternation

Mathematics Subject Classification ID

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

Related Items (8)

Unnamed Item ⋮ Living without Beth and Craig: Definitions and Interpolants in Description and Modal Logics with Nominals and Role Inclusions ⋮ The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies ⋮ Unnamed Item ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies ⋮ 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
• Factorization forests for infinite words and applications to countable scattered linear orderings
• Factorization forests of finite height
• First-order logic and star-free sets
• Semigroups and languages of dot-depth two
• 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
• Finite semigroup varieties of the form V*D
• Concatenation hierarchies: new bottle, old wine
• 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
• The Height of Factorization Forests
• Factorization Forests
• Separating Regular Languages with Two Quantifiers Alternations
• The Dot-Depth Hierarchy, 45 Years Later
• 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

This page was built for publication: Separating regular languages with two quantifier alternations