Separability by piecewise testable languages and downward closures beyond subwords

DOI10.1145/3209108.3209201zbMATH Open1497.68281OpenAlexW2810848820MaRDI QIDQ5145372FDOQ5145372

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)

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

   Recommendations

• A Note on Decidable Separability by Piecewise Testable Languages 👍 👎
• Title not available (Why is that?) 👍 👎
• Separability by piecewise testable languages is \textsc{PTime}-complete 👍 👎
• On Languages Piecewise Testable in the Strict Sense 👍 👎
• Title not available (Why is that?) 👍 👎
• 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 👍 👎

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)