\(\varepsilon\)-productions in context-free grammars

DOI10.1007/BF00289308zbMath0452.68082OpenAlexW2078130239MaRDI QIDQ1148693

Leslie M. Goldschlager

Publication date: 1981

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00289308

zbMATH Keywords

context-free languagemembership problemspace complexityemptiness problemepsilon-productionsfiniteness problems

Mathematics Subject Classification ID

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

Related Items (3)

The maximum flow problem is log space complete for P ⋮ Prediction-preserving reducibility ⋮ The parallel complexity of two problems on concurrency

Cites Work

• Unnamed Item
• Unnamed Item
• A space efficient algorithm for the monotone planar circuit value problem
• An observation on time-storage trade off
• Complete problems for deterministic polynomial time
• Linear programming is log-space hard for P
• A unified approach to models of synchronous parallel machines

This page was built for publication: \(\varepsilon\)-productions in context-free grammars