Complexity in union-free regular languages
From MaRDI portal
Publication:2909101
DOI10.1142/S0129054111008933zbMATH Open1252.68148OpenAlexW1980726210MaRDI QIDQ2909101FDOQ2909101
Authors: Galina Jirásková, Tomáš Masopust 
Publication date: 29 August 2012
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054111008933
Recommendations
- Complexity in Union-Free Regular Languages
- Most complex deterministic union-free regular languages
- Complexity of suffix-free regular languages
- Complexity of suffix-free regular languages
- scientific article; zbMATH DE number 7315105
- On equations for union-free regular languages
- Complexity of bifix-free regular languages
- Complexity of bifix-free regular languages
- Intersection and union of regular languages and state complexity
- Minimal Union-Free Decompositions of Regular Languages
descriptional complexityfinite automatonclosure propertiesone-cycle-free-path automatonunion-free regular language
Cites Work
- The state complexities of some basic operations on regular languages
- On the state complexity of reversals of regular languages
- Title not available (Why is that?)
- Descriptional and computational complexity of finite automata -- a survey
- A lower bound technique for the size of nondeterministic finite automata
- State complexity of power
- State complexity of basic operations on suffix-free regular languages
- State complexity of some operations on binary regular languages
- STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
- The state complexity of \(L^{2}\) and \(L^k\)
- Intersection and union of regular languages and state complexity
- Partial orders on words, minimal elements of regular languages, and state complexity
- Succinct representation of regular languages by Boolean automata
- On equations for union-free regular languages
- State complexity of cyclic shift
Cited In (26)
- Complexity in Union-Free Regular Languages
- Union-freeness, deterministic union-freeness and union-complexity
- On classes of tractable unrestricted regular expressions
- Operations on subregular languages and nondeterministic state complexity
- Union-complexities of Kleene plus operation
- Operational union-complexity
- Union-Freeness Revisited — Between Deterministic and Nondeterministic Union-Free Languages
- State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
- A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
- Languages, Decidability, and Complexity
- Descriptional complexity of the forever operator
- On a structural property in the state complexity of projected regular languages
- Concatenation-free languages
- On equations for union-free regular languages
- Power, positive closure, and quotients on convex languages
- Closure properties of subregular languages under operations
- Nondeterministic complexity of operations on free and convex languages
- Nondeterministic complexity in subclasses of convex languages
- On Union-Free and Deterministic Union-Free Languages
- Expressive capacity of concatenation freeness
- Most complex deterministic union-free regular languages
- Nondeterministic operational complexity in subregular languages
- Minimal Union-Free Decompositions of Regular Languages
- Isometries on positive operators of unit norm
- Nondeterministic complexity of operations on closed and ideal languages
- Operations on Permutation Automata
This page was built for publication: Complexity in union-free regular languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909101)
