Complexity of some problems concerningL systems

DOI10.1007/BF01744286zbMath0449.68038MaRDI QIDQ3896507

Neil D. Jones, Sven Skyum

Publication date: 1979

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

zbMATH Keywords

membershipemptinessL systemsinfiniteness

Mathematics Subject Classification ID

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

Related Items (11)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Complexity of some problems concerningL systems