Operational union-complexity

DOI10.1016/J.IC.2021.104692MaRDI QIDQ2113386zbMATH OpenOpenAlexFDO

Authors Benedek Nagy

Publication date 14 March 2022

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2021.104692

zbMATH Keywords

regular languagesregular operationsunion-complexityunion-free languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Complexity in union-free regular languages
• Complexity in Union-Free Regular Languages
• Union-freeness, deterministic union-freeness and union-complexity
• Most complex deterministic union-free regular languages
• State complexity of star of union and square of union on \textit{k} regular languages

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 2229032 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• A survey on operational state complexity
• Algorithms for determining relative star height and star height
• Complexity in union-free regular languages
• Incomplete operational transition complexity of regular languages
• Isometries on positive operators of unit norm
• Minimal Union-Free Decompositions of Regular Languages
• Most complex deterministic union-free regular languages
• On Union-Free and Deterministic Union-Free Languages
• On equations for union-free regular languages
• On the number of accepting states of finite automata
• Structure and Complexity of Some Subregular Language Families
• The ranges of accepting state complexities of languages resulting from some operations
• Transition complexity of incomplete DFAs
• Union-freeness, deterministic union-freeness and union-complexity

Cited in

(3)

• Union-complexities of Kleene plus operation
• Union-Freeness Revisited — Between Deterministic and Nondeterministic Union-Free Languages
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages

This page was built for publication: Operational union-complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113386)