State complexity of basic language operations combined with reversal

DOI10.1016/J.IC.2008.03.018MaRDI QIDQ948089zbMATH OpenOpenAlexFDO

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

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

finite state automataregular languagescombined operationsstate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• State complexity of combined operations with union, intersection, star and reversal
• State complexity of four combined operations composed of union, intersection, star and reversal
• The state complexity of two combined operations: star of catenation and star of reversal
• State complexity of catenation combined with star and reversal
• State complexity of combined operations with two basic operations

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1084695 (Why is no real title available?)
• scientific article; zbMATH DE number 1773072 (Why is no real title available?)
• scientific article; zbMATH DE number 2182451 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3222931 (Why is no real title available?)
• An introduction to formal languages and automata.
• Multiple-entry finite automata
• ON THE STATE COMPLEXITY OF COMBINED OPERATIONS AND THEIR ESTIMATION
• On the state complexity of reversals of regular languages
• State complexity of combined operations
• State complexity of regular languages
• The state complexities of some basic operations on regular languages

Cited in

(25)

• State complexity of inversion operations
• State complexity of star of union and square of union on \textit{k} regular languages
• Estimation of state complexity of combined operations
• Undecidability of state complexity
• The range of state complexities of languages resulting from the cut operation
• State complexity of the concatenation of regular tree languages
• On the state complexity of reversals of regular languages
• State complexity of union and intersection of star on \(k\) regular languages
• The state complexity of two combined operations: star of catenation and star of reversal
• State complexity of two combined operations: catenation-union and catenation-intersection
• Limitations of lower bound methods for deterministic nested word automata
• State complexity of four combined operations composed of union, intersection, star and reversal
• State complexity of union and intersection of square and reversal on \(k\) regular languages
• State complexity of power
• Operational state complexity revisited: the contribution of monsters and modifiers
• State complexity of combined operations with union, intersection, star and reversal
• State complexity of reversals of deterministic finite automata with output
• The exact state complexity for the composition of root and reversal
• State complexity of combined operations with two basic operations
• State complexity of inversion operations
• State complexity of catenation combined with union and intersection
• Universal witnesses for state complexity of basic operations combined with reversal
• State complexity of two combined operations: catenation-star and catenation-reversal
• In search of most complex regular languages
• State complexity of catenation combined with a Boolean operation: a unified approach

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

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