Regularity Conditions for Iterated Shuffle on Commutative Regular Languages

DOI10.1142/S0129054123430037MaRDI QIDQ6070751zbMATH OpenOpenAlexFDO

Authors Stefan Hoffmann

Publication date 24 November 2023

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054123430037

zbMATH Keywords

closure propertiescommutative languagesfinite automataiterated shufflepositive varietiesregularity-preserving operationsshuffle closuresuperalphabet closure

Mathematics Subject Classification ID

Semigroups (20Mxx) Computer science (68-XX) Theory of computing (68Qxx)

Recommendations

• Regularity conditions for iterated shuffle on commutative regular languages
• Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages
• On the itarated shuffle of some regular languages
• The commutative closure of shuffle languages over group languages is regular
• scientific article; zbMATH DE number 1222104

Cites work

• A hierarchy of languages with catenation and shuffle
• Algebraic Theory of Automata and Languages
• An algorithm to decide whether a rational subset of \({\mathbb{N}}^ k\) is recognizable
• An approach to software system behavior description
• Automata for regular expressions with shuffle
• Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages
• Bounded Regular Sets
• Characterization and complexity results on jumping finite automata
• Commutative one-counter languages are regular
• Commutative Positive Varieties of Languages
• Commutative regular languages -- properties and state complexity
• Constrained synchronization and commutativity
• Extending regular expressions with iterated shuffle
• Extensions to minimal synchronizing words
• Flow languages equal recursively enumerable languages
• scientific article; zbMATH DE number 992018 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3463159 (Why is no real title available?)
• scientific article; zbMATH DE number 3514949 (Why is no real title available?)
• scientific article; zbMATH DE number 1222104 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• Location automata for synchronised shuffle expressions
• Modeling literal morphisms by shuffle
• On finite monoids having only trivial subgroups
• On regularity of context-free languages
• On the Chinese Remainder Theorem
• On the complexity of iterated shuffle
• On the enlargement of the class of regular languages by the shuffle closure
• On the shuffle of star-free languages
• On the State Complexity of the Shuffle of Regular Languages
• Permutation automata
• Process Algebra
• Properties of Languages with Catenation and Shuffle
• Regularity conditions for iterated shuffle on commutative regular languages
• Shuffle languages are in P
• Shuffle languages, Petri nets, and context-sensitive grammars
• Shuffle on positive varieties of languages
• Shuffled languages -- representation and recognition
• Software Descriptions with Flow Expressions
• State complexity of projection on languages recognized by permutation automata and commuting letters
• String shuffle: circuits and graphs
• The complexity of logical theories
• The expressive power of the shuffle product
• The loop complexity of pure-group events
• The power of synchronizing operations on strings
• The Shuffle Product: New Research Directions
• The universe problem for unrestricted flow languages
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Unshuffling a square is NP-hard
• Variétés de langages et opérations

Cited in

(8)

• Regularity conditions for iterated shuffle on commutative regular languages
• The commutative closure of shuffle languages over group languages is regular
• Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages
• scientific article; zbMATH DE number 1222104 (Why is no real title available?)
• State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages
• Subset mapping problems in solvable automata
• The n-ary initial literal and literal shuffle
• On the enlargement of the class of regular languages by the shuffle closure

This page was built for publication: Regularity Conditions for Iterated Shuffle on Commutative Regular Languages

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