On the state complexity of reversals of regular languages
From MaRDI portal
Publication:596099
DOI10.1016/j.tcs.2004.02.032zbMath1068.68078OpenAlexW2025521996MaRDI QIDQ596099
Arto Salomaa, Derick Wood, Sheng Yu
Publication date: 10 August 2004
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.032
Related Items (36)
Closure properties and descriptional complexity of deterministic regular expressions ⋮ Undecidability of State Complexities Using Mirror Images ⋮ State Complexity of Boundary of Prefix-Free Regular Languages ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ On the State and Computational Complexity of the Reverse of Acyclic Minimal DFAs ⋮ State complexity of combined operations for suffix-free regular languages ⋮ Prefix-free languages: left and right quotient and reversal ⋮ On the minimal faithful degree of Rhodes semisimple semigroups ⋮ Operational state complexity revisited: the contribution of monsters and modifiers ⋮ Binary coded unary regular languages ⋮ State complexity of cyclic shift ⋮ Concatenation of regular languages and descriptional complexity ⋮ An alternating hierarchy for finite automata ⋮ Reversal of binary regular languages ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ Magic numbers in the state hierarchy of finite automata ⋮ IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES ⋮ State complexity of basic language operations combined with reversal ⋮ Lower Bound Methods for the Size of Nondeterministic Finite Automata Revisited ⋮ Operational state complexity of nested word automata ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ State Complexity of Four Combined Operations Composed of Union, Intersection, Star and Reversal ⋮ Note on Reversal of Binary Regular Languages ⋮ State complexity of deletion and bipolar deletion ⋮ State Complexity of Combined Operations for Prefix-Free Regular Languages ⋮ State Complexity of Catenation Combined with Union and Intersection ⋮ Descriptional complexity of iterated uniform finite-state transducers ⋮ Unnamed Item ⋮ Concatenation of Regular Languages and Descriptional Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ State complexity of basic operations on suffix-free regular languages ⋮ Descriptional complexity of regular languages ⋮ Primitivity, uniform minimality, and state complexity of Boolean operations ⋮ COMPLEXITY OF ATOMS OF REGULAR LANGUAGES ⋮ Undecidability of state complexity ⋮ State Complexity of k-Union and k-Intersection for Prefix-Free Regular Languages
Cites Work
This page was built for publication: On the state complexity of reversals of regular languages
