Separating regular languages by piecewise testable and unambiguous languages
From MaRDI portal
Abstract: Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by a set from a smaller class. We discuss the separation problem for regular languages. We give a Ptime algorithm to check whether two given regular languages are separable by a piecewise testable language, that is, whether a sentence can witness that the languages are disjoint. The proof refines an algebraic argument from Almeida and the third author. When separation is possible, we also express a separator by saturating one of the original languages by a suitable congruence. Following the same line, we show that one can as well decide whether two regular languages can be separated by an unambiguous language, albeit with a higher complexity.
Recommendations
- Efficient separability of regular languages by subsequences and suffixes
- Separability by piecewise testable languages is \textsc{PTime}-complete
- Separating regular languages with first-order logic
- Separating regular languages by locally testable and locally threshold testable languages
- On separation by locally testable and locally threshold testable languages
Cited in
(37)- Uniformisation of regular relations in first-order logic with two variables
- Verifying unboundedness via amalgamation
- All about unambiguous polynomial closure
- A Note on Decidable Separability by Piecewise Testable Languages
- scientific article; zbMATH DE number 3856432 (Why is no real title available?)
- Separating regular languages with two quantifier alternations
- On upper and lower bounds on the length of alternating towers
- On the index of Simon's congruence for piecewise testability
- Reducibility of pointlike problems
- Covering and separation for logical fragments with modular predicates
- The word problem for omega-terms over the Trotter-Weil hierarchy
- Regular separability of well-structured transition systems
- The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
- Une critique de la notion de test de processus fondée sur la non séparabilité de certaines classes de langages
- Weak separation problem for tree languages
- Classifying regular languages by a split game
- scientific article; zbMATH DE number 7559472 (Why is no real title available?)
- Separability by piecewise testable languages and downward closures beyond subwords
- Separating regular languages with first-order logic
- Regular separability of one counter automata
- Timed games and deterministic separability
- On the height of towers of subsequences and prefixes
- scientific article; zbMATH DE number 7407796 (Why is no real title available?)
- The Complexity of Separation for Levels in Concatenation Hierarchies
- Measuring power of locally testable languages
- The amazing mixed polynomial closure and its applications to two-variable first-order logic
- Efficient separability of regular languages by subsequences and suffixes
- Separating regular languages by locally testable and locally threshold testable languages
- Regular separability of Parikh automata
- Learning algorithms
- Separability by piecewise testable languages is \textsc{PTime}-complete
- Deciding piecewise testable separability for regular tree languages
- Quantifier alternation for infinite words
- A characterization for decidable separability by piecewise testable languages
- Separability by short subsequences and subwords
- The covering problem
- Separating regular languages with first-order logic
This page was built for publication: Separating regular languages by piecewise testable and unambiguous languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2849957)
