STATE COMPLEXITY AND APPROXIMATION

DOI10.1142/S0129054112400461zbMath1255.68094MaRDI QIDQ4902894

Yuan Gao, Sheng Yu

Publication date: 18 January 2013

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

zbMATH Keywords

undecidability; approximation; finite automata; regular languages; state complexity; combined operations

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

Related Items

State complexity of deletion and bipolar deletion, Primitivity, uniform minimality, and state complexity of Boolean operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for the transition complexity of NFAs
• Synchronization expressions with extended join operation
• The state complexities of some basic operations on regular languages
• Estimation of state complexity of combined operations
• State complexity of combined operations
• Enumeration and generation with a string automata representation
• Transition complexity of language operations
• On the average state and transition complexity of finite languages
• STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES