On weak growing context-sensitive grammars

DOI10.1007/3-540-59175-3_88MaRDI QIDQ5096331zbMATH OpenOpenAlexFDO

Authors Gerhard Buntrock, Gundula Niemann

Publication date 16 August 2022

Published in LATIN '95: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59175-3_88

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Recommendations

• scientific article; zbMATH DE number 1332661
• scientific article; zbMATH DE number 929620
• The complexity of membership for deterministic growing context-sensitive grammars^∗
• Inferring Grammars for Mildly Context Sensitive Languages in Polynomial-Time
• scientific article; zbMATH DE number 3958759
• Membership for growing context-sensitive grammars is polynomial
• Some results on contextual grammars^∗
• scientific article; zbMATH DE number 2150279
• Growing grammars and length-reducing automata

Cites work

• scientific article; zbMATH DE number 3936519 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3230262 (Why is no real title available?)
• Classes of languages and linear-bounded automata
• Membership for growing context-sensitive grammars is polynomial
• Normal forms for context-sensitive grammars
• On Computable Numbers, with an Application to the Entscheidungsproblem
• On certain formal properties of grammars
• On growing context-sensitive languages
• On the Tape Complexity of Deterministic Context-Free Languages
• On the complexity of formal grammars
• Studies in abstract families of languages
• Tree-size bounded alternation

Cited in

(1)

• On the Mild Context-Sensitivity of k-Tree Wrapping Grammar

This page was built for publication: On weak growing context-sensitive grammars

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