QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES

DOI10.1142/S0129054112400515zbMath1272.68206OpenAlexW1501444314MaRDI 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

complexitylanguageregularstate complexityquotientautomatonoperationaperiodicstar-free

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items (9)

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

This page was built for publication: QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES