Lower Space Bounds for Accepting Shuffle Languages
From MaRDI portal
Publication:4718896
DOI10.1051/ita:1999119zbMath0951.68067MaRDI QIDQ4718896
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
68Q45: Formal languages and automata
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Unnamed Item
- 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
- Nesting of shuffle closure is important
- Turing machines with sublogarithmic space
- Shuffle languages, Petri nets, and context-sensitive grammars
- Software Descriptions with Flow Expressions