ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION

DOI10.1142/S0129054107004917MaRDI QIDQ3503086zbMATH OpenOpenAlexFDO

Authors Kai Salomaa, Sheng Zu

Publication date 20 May 2008

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054107004917

zbMATH Keywords

regular languagesestimation methodsnondeterministic state complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the State Complexity of Combined Operations
• Estimation of state complexity of combined operations
• State complexity of combined operations
• State complexity of two combined operations: catenation-union and catenation-intersection
• State complexity of two combined operations: catenation-star and catenation-reversal

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 107464 (Why is no real title available?)
• scientific article; zbMATH DE number 3307592 (Why is no real title available?)
• IMPROVED BOUNDS ON THE NUMBER OF AUTOMATA ACCEPTING FINITE LANGUAGES
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• Partial orders on words, minimal elements of regular languages, and state complexity
• STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION
• 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\)
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

Cited in

(23)

• State complexity of combined operations for suffix-free regular languages
• Combination of roots and Boolean operations: an application to state complexity
• On the State Complexity of Combined Operations
• The state complexity of \(L^{2}\) and \(L^k\)
• State complexity of basic language operations combined with reversal
• State complexity of power
• State Complexity of Combined Operations for Prefix-Free Regular Languages
• State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
• A survey on operational state complexity
• State complexity and approximation
• Operational State Complexity under Parikh Equivalence
• Estimation of state complexity of combined operations
• State complexity of boundary of prefix-free regular languages
• State complexity of combined operations
• State complexity of unique rational operations
• State complexity of regular tree languages for tree matching
• Operational state complexity of subtree-free regular tree languages
• State complexity of inversion operations
• Undecidability of state complexities using mirror images
• State complexity research and approximation
• Composition and orbits of language operations: finiteness and upper bounds
• State Complexity of Nested Word Automata
• Undecidability of state complexity

This page was built for publication: ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION

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