State complexity and approximation

DOI10.1142/S0129054112400461MaRDI QIDQ4902894zbMATH OpenFDO

Authors Yuan Gao, Sheng Yu

Publication date 18 January 2013

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

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

zbMATH Keywords

approximationcombined operationsfinite automataregular languagesstate complexityundecidability

Mathematics Subject Classification ID

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

Recommendations

• State complexity research and approximation
• scientific article; zbMATH DE number 7301304
• scientific article; zbMATH DE number 2182451
• On the State Complexity of Combined Operations
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION

Cites work

• Enumeration and generation with a string automata representation
• Estimation of state complexity of combined operations
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 572102 (Why is no real title available?)
• scientific article; zbMATH DE number 3307592 (Why is no real title available?)
• Lower bounds for the transition complexity of NFAs
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On the average state and transition complexity of finite languages
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• State complexity of combined operations
• State complexity of two combined operations: catenation-union and catenation-intersection
• Synchronization expressions with extended join operation
• The state complexities of some basic operations on regular languages
• Transition complexity of language operations

Cited in

(15)

• State complexity of unique rational operations
• State complexity of pseudocatenation
• Primitivity, uniform minimality, and state complexity of Boolean operations
• State Complexity of Deletion
• State complexity of cyclic shift
• scientific article; zbMATH DE number 2182451 (Why is no real title available?)
• scientific article; zbMATH DE number 7315090 (Why is no real title available?)
• scientific article; zbMATH DE number 7453075 (Why is no real title available?)
• scientific article; zbMATH DE number 7301304 (Why is no real title available?)
• State complexity research and approximation
• State-complexity of finite-state devices, state compressibility and incompressibility
• Operational State Complexity under Parikh Equivalence
• State complexity of deletion and bipolar deletion
• Length of the state trace: a method for partitioning model complexity
• The state complexity of \(L^{2}\) and \(L^k\)

This page was built for publication: State complexity and approximation

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