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

downward closurespiecewise testable languagesseparabilitywell-quasi-orderings

Mathematics Subject Classification ID

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

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

(19)

• Separability by piecewise testable languages is \textsc{PTime}-complete
• On separation by locally testable and locally threshold testable languages
• 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
• Regular separability of well-structured transition systems
• The height of piecewise-testable languages with applications in logical complexity
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• Existential Definability over the Subword Ordering
• k-universality of regular languages revisited
• Directed regular and context-free languages
• Regular separators for VASS coverability languages
• Priority downward closures
• Separability and non-determinizability of WSTS
• Dot-depth three, return of the j-class
• Verifying unboundedness via amalgamation
• Generalized Parikh matrices for tracking subsequence occurrences
• On the piecewise complexity of words
• Subsequence matching and analysis problems for formal 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)