In search of most complex regular languages
From MaRDI portal
Publication:5401550
DOI10.1142/S0129054113400133zbMATH Open1410.68199OpenAlexW2786516640MaRDI QIDQ5401550FDOQ5401550
Authors: Janusz Brzozowski 
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
Recommendations
regular languageatomfinite automatonstate complexitysyntactic semigroupwitnessquotient complexitycomplexity of operation
Cites Work
- The state complexities of some basic operations on regular languages
- On the state complexity of reversals of regular languages
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- State complexity of combined operations
- State complexity of two combined operations: catenation-star and catenation-reversal
- State complexity of union and intersection of star on \(k\) regular languages
- State complexity of combined operations with two basic operations
- State complexity of basic language operations combined with reversal
Cited In (30)
- Primitivity, uniform minimality, and state complexity of Boolean operations
- Complexity of proper prefix-convex regular languages
- Combination of roots and Boolean operations: an application to state complexity
- Most complex non-returning regular languages
- State complexity of combined operations involving catenation and binary Boolean operations: beyond the Brzozowski conjectures
- In Search of Most Complex Regular Languages
- What is a complex regular language?
- Towards a theory of complexity of regular languages
- Syntactic complexity of regular ideals
- New tools for state complexity
- State complexity of overlap assembly
- Operational state complexity revisited: the contribution of monsters and modifiers
- Complexity of bifix-free regular languages
- Complexity of bifix-free regular languages
- Kleene closure and state complexity
- Large aperiodic semigroups
- Title not available (Why is that?)
- Prefix-free languages: left and right quotient and reversal
- Complexity of left-ideal, suffix-closed and suffix-free regular languages
- Title not available (Why is that?)
- Complexity of proper prefix-convex regular languages
- Most Complex Regular Right-Ideal Languages
- On the interplay between Černý and Babai's conjectures
- Syntactic complexity of bifix-free regular languages
- Descriptional complexity of regular languages
- Syntactic complexity of bifix-free languages
- Complexity of suffix-free regular languages
- Complexity of suffix-free regular languages
- Unrestricted state complexity of binary operations on regular languages
- State complexity of catenation combined with a Boolean operation: a unified approach
This page was built for publication: In search of most complex regular languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5401550)
