On the State Complexity of the Shuffle of Regular Languages

DOI10.1007/978-3-319-41114-9_6zbMath1476.68127arXiv1512.01187OpenAlexW3105230796MaRDI QIDQ2829972

Galina Jirásková, Aayush Rajasekaran, Bo Liu, Marek Szykuła, Janusz A. Brzozowski

Publication date: 9 November 2016

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1512.01187

zbMATH Keywords

shuffleupper boundregular languagestate complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (13)

State complexity of permutation on finite languages over a binary alphabet ⋮ A Study of a Simple Class of Modifiers: Product Modifiers ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Descriptional Complexity of the Forever Operator ⋮ Most Complex Non-Returning Regular Languages ⋮ Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation ⋮ Commutative regular languages with product-form minimal automata ⋮ State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages ⋮ Combination of roots and Boolean operations: an application to state complexity ⋮ The commutative closure of shuffle languages over group languages is regular

Uses Software

• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Quotient complexity of ideal languages
• On the State Complexity of Scattered Substrings and Superstrings

This page was built for publication: On the State Complexity of the Shuffle of Regular Languages