QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES

DOI10.1142/S0129054112400515zbMath1272.68206MaRDI QIDQ4923279

Bo Liu, Janusz A. Brzozowski

Publication date: 6 June 2013

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054112400515

zbMATH Keywords

complexity; language; regular; state complexity; quotient; automaton; operation; aperiodic; star-free

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

Related Items

Operations on Permutation Automata, Nondeterministic State Complexity of Star-Free Languages, Large Aperiodic Semigroups, Operational complexity in subregular classes, Descriptional complexity of regular languages, State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages, Nondeterministic complexity in subclasses of convex languages, Primitivity, uniform minimality, and state complexity of Boolean operations, Complexity of suffix-free regular languages

Cites Work

• Finite-automaton aperiodicity is PSPACE-complete
• State complexity of basic operations on suffix-free regular languages
• The state complexities of some basic operations on regular languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• On finite monoids having only trivial subgroups