The variable membership problem: Succinctness versus complexity

DOI10.1007/3-540-57785-8_174MaRDI QIDQ4942630zbMATH OpenFDO

Authors Gerhard Buntrock, Krzysztof Loryś

Publication date 16 March 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57785-8_174

zbMATH Keywords

completenesscontext-sensitive grammarsgrowingquasi-context-sensitive grammarsquasigrowing rule in a grammar

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)

Cited in

(4)

• Growing context-sensitive languages and Church-Rosser languages
• The Church-Rosser languages are the deterministic variants of the growing context-sensitive languages
• Lower bound technique for length-reducing automata
• Learning correction grammars

This page was built for publication: The variable membership problem: Succinctness versus complexity

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