On the enlargement of the class of regular languages by the shuffle closure

DOI10.1016/0020-0190(83)90023-6zbMATH Open0555.68043OpenAlexW2102729777MaRDI QIDQ760799FDOQ760799

Authors: Joanna Jȩdrzejowicz 

Publication date: 1983

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(83)90023-6

Recommendations

• scientific article; zbMATH DE number 1222104
• On the itarated shuffle of some regular languages
• SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES
• Shuffle product of regular languages: results and open problems
• The commutative closure of shuffle languages over group languages is regular
• scientific article; zbMATH DE number 3974328
• Commutative Regular Shuffle Closed Languages, Noetherian Property, and Learning Theory
• On the State Complexity of the Shuffle of Regular Languages
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages

zbMATH Keywords

shuffleregular expressionscontext-sensitive languagesrecursively enumerable languagesflow expressionspseudo- flow languagesshuffle closure

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Parallel program schemata
• Optimization of LR(k) parsers
• Software Descriptions with Flow Expressions
• Vector addition systems and regular languages
• Flow languages equal recursively enumerable languages

Cited In (13)

• On the State Complexity of the Shuffle of Regular Languages
• Insertion languages
• Extending regular expressions with iterated shuffle
• Regularity conditions for iterated shuffle on commutative regular languages
• Shuffle languages are in P
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
• Infinite hierarchy of shuffle expressions over a finite alphabet
• Lower Space Bounds for Accepting Shuffle Languages
• A P-complete language describable with iterated shuffle
• Nesting of shuffle closure is important
• Infinite hierarchy of expressions containing shuffle closure operator
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: On the enlargement of the class of regular languages by the shuffle closure

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