A Note on Decidable Separability by Piecewise Testable Languages
From MaRDI portal
Publication:2947878
DOI10.1007/978-3-319-22177-9_14zbMath1434.68242OpenAlexW2113283923MaRDI QIDQ2947878
Lorijn van Rooijen, Wim Martens, Wojciech Czerwiński, Marc Zeitoun
Publication date: 29 September 2015
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-22177-9_14
Related Items
Unnamed Item, Recursion Schemes and the WMSO+U Logic, Cost Automata, Safe Schemes, and Downward Closures, Separability by piecewise testable languages is \textsc{PTime}-complete, Unnamed Item, Unnamed Item, The Complexity of the Diagonal Problem for Recursion Schemes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deciding twig-definability of node selecting tree automata
- Factorization forests of finite height
- Semigroups and languages of dot-depth two
- Polynomial closure and unambiguous product
- Parikh's theorem: a simple and direct automaton construction
- Semigroups, Presburger formulas, and languages
- Locally testable languages
- The General Vector Addition System Reachability Problem by Presburger Inductive Invariants
- Separating Regular Languages by Piecewise Testable and Unambiguous Languages
- Model Checking Vector Addition Systems with one zero-test
- Regular tree languages definable in FO and in FO mod
- Separating Regular Languages by Locally Testable and Locally Threshold Testable Languages
- Piecewise testable tree languages
- Algebra for Infinite Forests with an Application to the Temporal Logic EF
- An Approach to Computing Downward Closures
- An Algorithm for the General Petri Net Reachability Problem
- On the Decidability of Grammar Problems
- Noncanonical Extensions of Bottom-Up Parsing Techniques
- Separating regular languages with first-order logic
- Algebraic decision procedures for local testability
- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
- Efficient Separability of Regular Languages by Subsequences and Suffixes
- On finite monoids having only trivial subgroups
- On Context-Free Languages
- A note on undecidable properties of formal languages
- Indexed Grammars—An Extension of Context-Free Grammars
