QUOTIENT COMPLEXITY OF STAR-FREE LANGUAGES
From MaRDI portal
Publication:4923279
DOI10.1142/S0129054112400515zbMath1272.68206MaRDI QIDQ4923279
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
complexity; language; regular; state complexity; quotient; automaton; operation; aperiodic; star-free
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