Separability by piecewise testable languages is \textsc{PTime}-complete

DOI10.1016/j.tcs.2017.11.004zbMath1386.68094arXiv1704.07856OpenAlexW2963728259MaRDI QIDQ1698734

Tomáš Masopust

Publication date: 16 February 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

complexityseparabilitypiecewise testable languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (3)

Unnamed Item ⋮ On the height of towers of subsequences and prefixes ⋮ The Complexity of Separation for Levels in Concatenation Hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finite-automaton aperiodicity is PSPACE-complete
• Kernel methods for learning languages
• Characterizations of some classes of regular events
• The method of forced enumeration for nondeterministic automata
• A generalization of the Schützenberger product of finite monoids
• Classification of finite monoids: the language approach
• The dot-depth hierarchy of star-free languages is infinite
• Finite semigroup varieties of the form V*D
• Pointlike sets with respect to R and J.
• Relationships between nondeterministic and deterministic tape complexities
• Dot-depth of star-free events
• Separating Regular Languages by Piecewise Testable and Unambiguous Languages
• A Note on Decidable Separability by Piecewise Testable Languages
• An Algebraic Characterization of Strictly Piecewise Languages
• Piecewise testable tree languages
• On Decidability of Intermediate Levels of Concatenation Hierarchies
• On the Complexity of k-Piecewise Testability and the Depth of Automata
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• On Languages Piecewise Testable in the Strict Sense
• Complexity of some problems from the theory of automata
• Nondeterministic Space is Closed under Complementation
• On the Decidability of Grammar Problems
• The pseudovariety $J$ is hyperdecidable
• Deciding Piecewise Testable Separability for Regular Tree Languages
• AROUND DOT-DEPTH ONE
• Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
• Alternative Automata Characterization of Piecewise Testable Languages
• Cognitive and Sub-regular Complexity
• Efficient Separability of Regular Languages by Subsequences and Suffixes
• Machines, Computations, and Universality

This page was built for publication: Separability by piecewise testable languages is \textsc{PTime}-complete