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

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item