Separability by piecewise testable languages and downward closures beyond subwords

DOI10.1145/3209108.3209201MaRDI QIDQ5145372zbMATH OpenOpenAlexFDO

Authors Georg Zetzsche

Publication date 20 January 2021

Published in Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3209108.3209201

zbMATH Keywords

separabilitypiecewise testable languageswell-quasi-orderingsdownward closures

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics of partially ordered sets (06A07) Logic in computer science (03B70)

Recommendations

• A Note on Decidable Separability by Piecewise Testable Languages
• A characterization for decidable separability by piecewise testable languages
• Separability by piecewise testable languages is \textsc{PTime}-complete
• On languages piecewise testable in the strict sense
• scientific article; zbMATH DE number 7056230
• 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
• Deciding piecewise testable separability for regular tree languages
• Hierarchies of Piecewise Testable Languages

Cited in

(9)

• The height of piecewise-testable languages with applications in logical complexity
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Regular separability of well-structured transition systems
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• Existential Definability over the Subword Ordering
• A Note on Decidable Separability by Piecewise Testable Languages
• A characterization for decidable separability by piecewise testable languages
• Deciding piecewise testable separability for regular tree languages
• On separation by locally testable and locally threshold testable languages

This page was built for publication: Separability by piecewise testable languages and downward closures beyond subwords

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