A Note on Decidable Separability by Piecewise Testable Languages
From MaRDI portal
Recommendations
- A characterization for decidable separability by piecewise testable languages
- Separability by piecewise testable languages and downward closures beyond subwords
- Deciding piecewise testable separability for regular tree languages
- Separability by piecewise testable languages is \textsc{PTime}-complete
- On languages piecewise testable in the strict sense
- Separating regular languages by piecewise testable and unambiguous languages
- On separation by locally testable and locally threshold testable languages
- Piecewise testable languages and nondeterministic automata
- A proof of Simon's theorem on piecewise testable languages
- Piecewise testable languages via combinatorics on words
Cites work
- A note on undecidable properties of formal languages
- Algebra for Infinite Forests with an Application to the Temporal Logic EF
- Algebraic decision procedures for local testability
- An Algorithm for the General Petri Net Reachability Problem
- An approach to computing downward closures
- Deciding twig-definability of node selecting tree automata
- Efficient separability of regular languages by subsequences and suffixes
- Factorization forests of finite height
- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
- scientific article; zbMATH DE number 4035179 (Why is no real title available?)
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3483582 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 3628412 (Why is no real title available?)
- scientific article; zbMATH DE number 798167 (Why is no real title available?)
- Indexed Grammars—An Extension of Context-Free Grammars
- Locally testable languages
- Model checking vector addition systems with one zero-test
- Noncanonical Extensions of Bottom-Up Parsing Techniques
- On Context-Free Languages
- On finite monoids having only trivial subgroups
- On the Decidability of Grammar Problems
- Parikh's theorem: a simple and direct automaton construction
- Piecewise testable tree languages
- Polynomial closure and unambiguous product
- Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
- Semigroups and languages of dot-depth two
- Semigroups, Presburger formulas, and languages
- Separability by short subsequences and subwords
- Separating regular languages by locally testable and locally threshold testable languages
- Separating regular languages by piecewise testable and unambiguous languages
- Separating regular languages with first-order logic
- The general vector addition system reachability problem by Presburger inductive invariants
Cited in
(19)- Separability by piecewise testable languages is \textsc{PTime}-complete
- On Boolean combinations forming piecewise testable languages
- A complete refinement procedure for regular separability of context-free languages
- Complexity assessments for decidable fragments of Set Theory. III: Testers for crucial, polynomial-maximal decidable Boolean languages
- On separation by locally testable and locally threshold testable languages
- Recursion schemes and the WMSO+U logic
- scientific article; zbMATH DE number 3978421 (Why is no real title available?)
- A characterization for decidable separability by piecewise testable languages
- Deciding piecewise testable separability for regular tree languages
- Regular separability of one counter automata
- Intersection types for unboundedness problems
- Recursion schemes, the MSO logic, and the \textsf{U} quantifier
- The Complexity of the Diagonal Problem for Recursion Schemes
- Separability by piecewise testable languages and downward closures beyond subwords
- scientific article; zbMATH DE number 7056230 (Why is no real title available?)
- Cost Automata, Safe Schemes, and Downward Closures
- Timed games and deterministic separability
- Cost automata, safe schemes, and downward closures
- Deterministic and game separability for regular languages of infinite trees
This page was built for publication: A Note on Decidable Separability by Piecewise Testable Languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947878)
