A P-complete language describable with iterated shuffle

DOI10.1016/0020-0190(92)90165-RzbMath0780.68087OpenAlexW1989896950MaRDI QIDQ1197969

Takayoshi Shoudai

Publication date: 16 January 1993

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

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90165-r

zbMATH Keywords

computational complexityformal language\(P\)-complete language

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (2)

Unshuffling a square is NP-hard ⋮ String shuffle: circuits and graphs

Cites Work

• On the enlargement of the class of regular languages by the shuffle closure
• On the complexity of iterated shuffle
• Extending regular expressions with iterated shuffle
• Flow languages equal recursively enumerable languages
• The power of synchronizing operations on strings
• Software Descriptions with Flow Expressions

This page was built for publication: A P-complete language describable with iterated shuffle