A characterization for decidable separability by piecewise testable languages

MaRDI QIDQ4560219zbMATH OpenFDO

Authors Wojciech Czerwiński, Wim Martens, Lorijn Van Rooijen, Georg Zetzsche, Marc Zeitoun

Publication date 10 December 2018

Full work available at URL https://arxiv.org/abs/1410.1042, https://dmtcs.episciences.org/4131/pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• A Note on Decidable Separability by Piecewise Testable Languages
• Separability by piecewise testable languages and downward closures beyond subwords
• Deciding piecewise testable separability for regular tree languages
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Separating regular languages by piecewise testable and unambiguous languages

Cited in

(15)

• Regular separators for VASS coverability languages
• Separability and non-determinizability of WSTS
• Verifying unboundedness via amalgamation
• A Note on Decidable Separability by Piecewise Testable Languages
• Cost Automata, Safe Schemes, and Downward Closures
• scientific article; zbMATH DE number 7559472 (Why is no real title available?)
• Separability by piecewise testable languages and downward closures beyond subwords
• Cost automata, safe schemes, and downward closures
• On the height of towers of subsequences and prefixes
• Extending the WMSO+U logic with quantification over tuples
• Unboundedness problems for languages of vector addition systems
• Learning algorithms
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Deciding piecewise testable separability for regular tree languages
• On separation by locally testable and locally threshold testable languages

This page was built for publication: A characterization for decidable separability by piecewise testable languages

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