Efficient separability of regular languages by subsequences and suffixes
From MaRDI portal
Abstract: When can two regular word languages K and L be separated by a simple language? We investigate this question and consider separation by piecewise- and suffix-testable languages and variants thereof. We give characterizations of when two languages can be separated and present an overview of when these problems can be decided in polynomial time if K and L are given by nondeterministic automata.
Recommendations
- Separating regular languages by piecewise testable and unambiguous languages
- Separability by piecewise testable languages is \textsc{PTime}-complete
- Separability by short subsequences and subwords
- Separating regular languages by locally testable and locally threshold testable languages
- On separation by locally testable and locally threshold testable languages
Cited in
(31)- Separability by piecewise testable languages is \textsc{PTime}-complete
- Learning algorithms
- Certifying DFA bounds for recognition and separation
- Certifying inexpressibility
- On the height of towers of subsequences and prefixes
- A sufficient condition to polynomially compute a minimum separating DFA
- On the index of Simon's congruence for piecewise testability
- Quantifier alternation for infinite words
- Separating regular languages by piecewise testable and unambiguous languages
- On upper and lower bounds on the length of alternating towers
- A Note on Decidable Separability by Piecewise Testable Languages
- Separating regular languages by locally testable and locally threshold testable languages
- Efficient algorithms for membership in Boolean hierarchies of regular languages
- scientific article; zbMATH DE number 3856432 (Why is no real title available?)
- Efficient Enumeration of Regular Languages
- Separating regular languages with two quantifier alternations
- The covering problem
- Regular separability of one counter automata
- Partially ordered automata and piecewise testability
- Regular separability of well-structured transition systems
- The Complexity of Separation for Levels in Concatenation Hierarchies
- Regular separability of Parikh automata
- Separation for dot-depth two
- Remarks on separating words
- Covering and separation for logical fragments with modular predicates
- Separability by short subsequences and subwords
- Weak separation problem for tree languages
- The amazing mixed polynomial closure and its applications to two-variable first-order logic
- Timed games and deterministic separability
- Regular separators for VASS coverability languages
- Dot-depth three, return of the j-class
This page was built for publication: Efficient separability of regular languages by subsequences and suffixes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5327430)
