Complexity of some problems concerningL systems

DOI10.1007/BF01744286zbMath0449.68038MaRDI QIDQ3896507

Sven Skyum, Neil D. Jones

Publication date: 1979

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

membership; emptiness; L systems; infiniteness

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

Complexity of E0L structural equivalence, Structural equivalence and ET0L grammars, Completeness results concerning systolic tree automata and E0L languages, Recurrent words and simultaneous growth in T0L systems, Concerning two-adjacent context-free languages, Decidability of the finiteness of ranges of tree transductions, The Euclidean traveling salesman problem and a space-filling curve, Extending regular expressions with homomorphic replacement

Cites Work

• The membership question for ETOL-languages is polynomially complete
• General context-free recognition in less than cubic time
• The tape-complexity of context-independent developmental languages
• Complete problems for deterministic polynomial time
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• Recognition of deterministic ETOL languages in logarithmic space
• Recognition and parsing of context-free languages in time n3
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item