Separability by piecewise testable languages is \textsc{PTime}-complete
From MaRDI portal
Publication:1698734
Abstract: Piecewise testable languages form the first level of the Straubing-Th'erien hierarchy. The membership problem for this level is decidable and testing if the language of a DFA is piecewise testable is NL-complete. The question has not yet been addressed for NFAs. We fill in this gap by showing that it is PSpace-complete. The main result is then the lower-bound complexity of separability of regular languages by piecewise testable languages. Two regular languages are separable by a piecewise testable language if the piecewise testable language includes one of them and is disjoint from the other. For languages represented by NFAs, separability by piecewise testable languages is known to be decidable in PTime. We show that it is PTime-hard and that it remains PTime-hard even for minimal DFAs.
Recommendations
- A Note on Decidable Separability by Piecewise Testable Languages
- A characterization for decidable separability by piecewise testable languages
- Separability by piecewise testable languages and downward closures beyond subwords
- Deciding piecewise testable separability for regular tree languages
- On languages piecewise testable in the strict sense
- Separating regular languages by piecewise testable and unambiguous languages
- Piecewise testable languages via combinatorics on words
- On separation by locally testable and locally threshold testable languages
- Piecewise testable languages and nondeterministic automata
- A proof of Simon's theorem on piecewise testable languages
Cites work
- A generalization of the Schützenberger product of finite monoids
- A Note on Decidable Separability by Piecewise Testable Languages
- A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
- Alternative automata characterization of piecewise testable languages
- An Algebraic Characterization of Strictly Piecewise Languages
- Around dot-depth one
- Characterizations of some classes of regular events
- Classification of finite monoids: the language approach
- Cognitive and sub-regular complexity
- Complexity of some problems from the theory of automata
- Deciding piecewise testable separability for regular tree languages
- Dot-depth of star-free events
- Efficient separability of regular languages by subsequences and suffixes
- Finite semigroup varieties of the form V*D
- Finite-automaton aperiodicity is PSPACE-complete
- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
- scientific article; zbMATH DE number 5595162 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1839456 (Why is no real title available?)
- scientific article; zbMATH DE number 784042 (Why is no real title available?)
- scientific article; zbMATH DE number 2206109 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- Kernel methods for learning languages
- Machines, Computations, and Universality
- Nondeterministic Space is Closed under Complementation
- On decidability of intermediate levels of concatenation hierarchies
- On languages piecewise testable in the strict sense
- On the complexity of k-piecewise testability and the depth of automata
- On the Decidability of Grammar Problems
- Piecewise testable languages and nondeterministic automata
- Piecewise testable tree languages
- Pointlike sets with respect to R and J.
- Relationships between nondeterministic and deterministic tape complexities
- Separability by short subsequences and subwords
- Separating regular languages by piecewise testable and unambiguous languages
- Separation and the successor relation
- The dot-depth hierarchy of star-free languages is infinite
- The method of forced enumeration for nondeterministic automata
- The pseudovariety J is hyperdecidable
Cited in
(13)- On the height of towers of subsequences and prefixes
- Separating regular languages by piecewise testable and unambiguous languages
- A Note on Decidable Separability by Piecewise Testable Languages
- On the complexity of k-piecewise testability and the depth of automata
- On languages piecewise testable in the strict sense
- A characterization for decidable separability by piecewise testable languages
- Deciding piecewise testable separability for regular tree languages
- Piecewise testable languages and nondeterministic automata
- Partially ordered automata and piecewise testability
- The Complexity of Separation for Levels in Concatenation Hierarchies
- Separability by piecewise testable languages and downward closures beyond subwords
- Efficient separability of regular languages by subsequences and suffixes
- Regular separators for VASS coverability languages
This page was built for publication: Separability by piecewise testable languages is \textsc{PTime}-complete
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1698734)
