On Boolean combinations forming piecewise testable languages
From MaRDI portal
Publication:2358689
DOI10.1016/j.tcs.2017.01.017zbMath1371.68158OpenAlexW2582563599MaRDI QIDQ2358689
Tomáš Masopust, Michaël Thomazo
Publication date: 15 June 2017
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01637057/file/Tcs_bool.pdf
Related Items
Unnamed Item ⋮ Alternating complexity of counting first-order logic for the subword order ⋮ On shuffle products, acyclic automata and piecewise-testable languages ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Piecewise testable languages via combinatorics on words
- Finite-automaton aperiodicity is PSPACE-complete
- The method of forced enumeration for nondeterministic automata
- Intersection and union of regular languages and state complexity
- Games, equations and the dot-depth hierarchy
- On the index of Simon's congruence for piecewise testability
- On the State Complexity of the Reverse of ${\mathcal R}$ - and ${\mathcal J}$ -Trivial Regular Languages
- Succinctness of the Complement and Intersection of Regular Expressions
- On the Complexity of k-Piecewise Testability and the Depth of Automata
- Complexity of some problems from the theory of automata
- Nondeterministic Space is Closed under Complementation
- Computational Parallels between the Regular and Context-Free Languages
- SYNTACTIC COMPLEXITY OF ℛ- AND 𝒥-TRIVIAL REGULAR LANGUAGES
- The Height of Piecewise-Testable Languages with Applications in Logical Complexity
- Alternative Automata Characterization of Piecewise Testable Languages
