Separability by piecewise testable languages and downward closures beyond subwords

DOI10.1145/3209108.3209201zbMATH Open1497.68281OpenAlexW2810848820MaRDI QIDQ5145372FDOQ5145372

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

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

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)

Cited In (5)

• A Note on Decidable Separability by Piecewise Testable Languages
• Existential Definability over the Subword Ordering
• Title not available (Why is that?)
• Separability by piecewise testable languages is \textsc{PTime}-complete
• 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)