The Complexity of Separation for Levels in Concatenation Hierarchies

DOI10.4230/LIPIcs.FSTTCS.2018.47OpenAlexW2963128734MaRDI QIDQ5090988

Thomas Place, Marc Zeitoun

Publication date: 21 July 2022

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

zbMATH Keywords

complexityseparationregular languagesconcatenation hierarchies

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Finite-automaton aperiodicity is PSPACE-complete
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Generic results for concatenation hierarchies
• Dot-depth of star-free events
• On the structure of semigroups
• Separating Regular Languages with First-Order Logic
• Separating Regular Languages by Piecewise Testable and Unambiguous Languages
• Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages
• Separating regular languages with two quantifier alternations
• Separating regular languages with first-order logic
• The Dot-Depth Hierarchy, 45 Years Later
• Adding Successor
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Efficient Separability of Regular Languages by Subsequences and Suffixes

This page was built for publication: The Complexity of Separation for Levels in Concatenation Hierarchies