State complexity of basic language operations combined with reversal

DOI10.1016/j.ic.2008.03.018zbMath1154.68073OpenAlexW2066620717MaRDI QIDQ948089

Arto Salomaa, Guangwu Liu, Sheng Yu, Carlos Martín-Vide

Publication date: 8 October 2008

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

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

zbMATH Keywords

regular languagesstate complexityfinite state automatacombined operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

State Complexity of Catenation Combined with a Boolean Operation: A Unified Approach ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-STAR AND CATENATION-REVERSAL ⋮ State complexity of star of union and square of union on \textit{k} regular languages ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION ⋮ The exact state complexity for the composition of root and reversal ⋮ State complexity of union and intersection of star on \(k\) regular languages ⋮ State complexity of the concatenation of regular tree languages ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ State complexity of combined operations with two basic operations ⋮ IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Estimation of state complexity of combined operations ⋮ State complexity of union and intersection of square and reversal on \(k\) regular languages ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ State Complexity of Catenation Combined with Union and Intersection ⋮ State complexity of power ⋮ Undecidability of state complexity

Cites Work

• On the state complexity of reversals of regular languages
• The state complexities of some basic operations on regular languages
• Multiple-entry finite automata
• State complexity of combined operations
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: State complexity of basic language operations combined with reversal