On the Complexity of k-Piecewise Testability and the Depth of Automata

DOI10.1007/978-3-319-21500-6_29zbMath1434.68277OpenAlexW1145240173MaRDI QIDQ3451116

Tomáš Masopust, Michaël Thomazo

Publication date: 10 November 2015

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-21500-6_29

Mathematics Subject Classification ID

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

Related Items (6)

On Boolean combinations forming piecewise testable languages ⋮ On the Complexity of k-Piecewise Testability and the Depth of Automata ⋮ On the Simon's congruence neighborhood of languages ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Finite-automaton aperiodicity is PSPACE-complete
• The method of forced enumeration for nondeterministic automata
• Equations and monoid varieties of dot-depth one and two
• On the index of Simon's congruence for piecewise testability
• Invariant Theoretical Interpretation of Interaction
• On the Complexity of k-Piecewise Testability and the Depth of Automata
• Alternative Automata Characterization of Piecewise Testable Languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Complexity of k-Piecewise Testability and the Depth of Automata