Lower Space Bounds for Accepting Shuffle Languages

DOI10.1051/ITA:1999119MaRDI QIDQ4718896zbMATH OpenOpenAlexFDO

Authors Andrzej Szepietowski

Publication date 18 December 2000

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/222065, https://semanticscholar.org/paper/0b893f38dab32184400bf5f5626dd027c9e3e9ab

zbMATH Keywords

shuffle languages

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• Shuffle languages are in P
• scientific article; zbMATH DE number 1916664
• scientific article; zbMATH DE number 992018
• Remarks on languages acceptable in log log n space
• On the State Complexity of the Shuffle of Regular Languages

Cites work

• Extending regular expressions with iterated shuffle
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• Nesting of shuffle closure is important
• On the complexity of iterated shuffle
• On the enlargement of the class of regular languages by the shuffle closure
• Shuffle languages, Petri nets, and context-sensitive grammars
• Software Descriptions with Flow Expressions
• Turing machines with sublogarithmic space

Cited in

(1)

• scientific article; zbMATH DE number 1916664 (Why is no real title available?)

This page was built for publication: Lower Space Bounds for Accepting Shuffle Languages

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