Complexity in union-free regular languages

DOI10.1142/S0129054111008933MaRDI QIDQ2909101zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

descriptional complexityfinite automatonclosure propertiesone-cycle-free-path automatonunion-free regular language

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• A lower bound technique for the size of nondeterministic finite automata
• Descriptional and computational complexity of finite automata -- a survey
• Intersection and union of regular languages and state complexity
• On equations for union-free regular languages
• On the state complexity of reversals of regular languages
• Partial orders on words, minimal elements of regular languages, and state complexity
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• State complexity of basic operations on suffix-free regular languages
• State complexity of cyclic shift
• State complexity of power
• State complexity of some operations on binary regular languages
• Succinct representation of regular languages by Boolean automata
• The state complexities of some basic operations on regular languages
• The state complexity of \(L^{2}\) and \(L^k\)

Cited in

(26)

• Isometries on positive operators of unit norm
• Nondeterministic complexity in subclasses of convex languages
• On Union-Free and Deterministic Union-Free Languages
• Most complex deterministic union-free regular languages
• On classes of tractable unrestricted regular expressions
• Complexity in Union-Free Regular Languages
• On equations for union-free regular languages
• Power, positive closure, and quotients on convex languages
• Closure properties of subregular languages under operations
• Nondeterministic operational complexity in subregular languages
• Union-freeness, deterministic union-freeness and union-complexity
• Languages, Decidability, and Complexity
• On a structural property in the state complexity of projected regular languages
• Nondeterministic complexity of operations on closed and ideal languages
• Operations on subregular languages and nondeterministic state complexity
• Union-complexities of Kleene plus operation
• Operational union-complexity
• 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
• Nondeterministic complexity of operations on free and convex languages
• Concatenation-free languages
• Descriptional complexity of the forever operator
• Expressive capacity of concatenation freeness
• Union-Freeness Revisited — Between Deterministic and Nondeterministic Union-Free Languages
• Operations on Permutation Automata
• Minimal Union-Free Decompositions of Regular Languages

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)