State complexity of cyclic shift

DOI10.1051/ita:2007038zbMath1144.68033OpenAlexW2011242982MaRDI QIDQ3515466

Alexander Okhotin, Galina Jirásková

Publication date: 29 July 2008

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/246037

Mathematics Subject Classification ID

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

Related Items (20)

A Study of a Simple Class of Modifiers: Product Modifiers ⋮ Operations on Permutation Automata ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ Operational complexity and pumping lemmas ⋮ Counting (Watson-Crick) palindromes in Watson-Crick conjugates ⋮ Nondeterministic operational complexity in subregular languages ⋮ Further Remarks on the Operational Nonterminal Complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Block reversal on finite words ⋮ Further closure properties of input-driven pushdown automata ⋮ Language operations with regular expressions of polynomial size ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Unnamed Item ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages ⋮ Undecidability of state complexity ⋮ Combination of roots and Boolean operations: an application to state complexity ⋮ Maximal state complexity and generalized de Bruijn words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the state complexity of reversals of regular languages
• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• State complexity of some operations on binary regular languages
• State complexity of combined operations
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS
• Magic Numbers in the State Hierarchy of Finite Automata

This page was built for publication: State complexity of cyclic shift