On Boolean combinations forming piecewise testable languages

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

zbMATH Keywords

complexityautomatalanguages\(k\)-piecewise testability

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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