IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
From MaRDI portal
Publication:5401550
DOI10.1142/S0129054113400133zbMath1410.68199OpenAlexW2786516640MaRDI QIDQ5401550
Publication date: 10 March 2014
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054113400133
atomregular languagefinite automatonstate complexitysyntactic semigroupwitnessquotient complexitycomplexity of operation
Related Items
State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach ⋮ Syntactic complexity of bifix-free languages ⋮ Complexity of suffix-free regular languages ⋮ Complexity of Suffix-Free Regular Languages ⋮ Kleene closure and state complexity ⋮ Prefix-free languages: left and right quotient and reversal ⋮ Large Aperiodic Semigroups ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ Unnamed Item ⋮ On the Interplay Between Černý and Babai’s Conjectures ⋮ Complexity of Left-Ideal, Suffix-Closed and Suffix-Free Regular Languages ⋮ Syntactic complexity of regular ideals ⋮ Most Complex Non-Returning Regular Languages ⋮ Complexity of proper prefix-convex regular languages ⋮ Complexity of bifix-free regular languages ⋮ Complexity of proper prefix-convex regular languages ⋮ Complexity of bifix-free regular languages ⋮ Unnamed Item ⋮ Unrestricted State Complexity of Binary Operations on Regular Languages ⋮ Syntactic complexity of bifix-free regular languages ⋮ Descriptional complexity of regular languages ⋮ Primitivity, uniform minimality, and state complexity of Boolean operations ⋮ State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures ⋮ State Complexity of Overlap Assembly ⋮ Combination of roots and Boolean operations: an application to state complexity
Cites Work
- State complexity of union and intersection of star on \(k\) regular languages
- State complexity of combined operations with two basic operations
- On the state complexity of reversals of regular languages
- State complexity of basic language operations combined with reversal
- The state complexities of some basic operations on regular languages
- State complexity of combined operations
- STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-STAR AND CATENATION-REVERSAL
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
This page was built for publication: IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES
