Piecewise testable languages and nondeterministic automata

DOI10.4230/LIPICS.MFCS.2016.67MaRDI QIDQ4608630zbMATH OpenFDO

Authors Tomáš Masopust

Publication date 21 March 2018

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

zbMATH Keywords

\(k\)-piecewise testabilityautomatalanguageslogicsnondeterminism

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of k-piecewise testability and the depth of automata
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Alternative automata characterization of piecewise testable languages
• On Boolean combinations forming piecewise testable languages
• scientific article; zbMATH DE number 1839456

Cited in

(14)

• Separability by piecewise testable languages is \textsc{PTime}-complete
• On shuffle products, acyclic automata and piecewise-testable languages
• Testing language containment for \(\omega\)-automata using BDDs
• Complexity of universality and related problems for partially ordered NFAs
• On Boolean combinations forming piecewise testable languages
• Alternating complexity of counting first-order logic for the subword order
• Piecewise directable automata
• A Note on Decidable Separability by Piecewise Testable Languages
• On the complexity of k-piecewise testability and the depth of automata
• scientific article; zbMATH DE number 6125212 (Why is no real title available?)
• Partially ordered automata and piecewise testability
• Complexity of counting first-order logic for the subword order
• Alternative automata characterization of piecewise testable languages
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)

This page was built for publication: Piecewise testable languages and nondeterministic automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608630)