Double Greibach operator grammars
type: Item
instance of: scholarly article
title: Double Greibach operator grammars
zbMATH Open document ID: 0952.68074
DOI: 10.1016/S0304-3975(99)00138-3
author: R. Smith
published in: Theoretical Computer Science
publication date: 2000-12-12T00:00:00Z
review text: Every context-free grammar can be transformed into one in double Greibach operator form, that satisfies both double Greibach form and operator form. Examination of the expressive power of various well-known subclasses of context-free grammars in double Greibach and/or operator form yields an extended hierarchy of language classes. Basic decision properties such as equivalence can be stated in stronger forms via new classes of languages in this hierarchy.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 1542267
zbMATH Keywords: formal languages
zbMATH Keywords: context-free grammars
zbMATH Keywords: normal forms
zbMATH Keywords: hierarchy
zbMATH Keywords: decision properties
MaRDI profile type: Publication
cites work: Handle-rewriting hypergraph grammars
cites work: An elementary proof of double Greibach normal form
cites work: Context-free graph languages of bounded degree are generated by apex graph grammars
cites work: Linear graph grammars: Power and complexity
cites work: Apex graph grammars and attribute grammars
cites work: Boundary graph grammars with dynamic edge relabeling
cites work: Syntactic Analysis and Operator Precedence
cites work: A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
cites work: Q4198075
cites work: Q5592246
cites work: On Equivalence and Containment Problems for Formal Languages
cites work: A hierarchy of eNCE families of graph languages
cites work: Efficient recognition algorithms for boundary and linear eNCE graph languages
cites work: HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
cites work: Separating \(k\)-separated eNCE graph languages
cites work: Node replacement graph languages squeezed with chains, trees, and forests
cites work: Matrix Equations and Normal Forms for Context-Free Grammars
cites work: Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
cites work: Q5678435
cites work: On Greibach normal form construction
full work available at URL: s0304-3975(99)00138-3
OpenAlex ID: W2090256263
description: scientific article; zbMATH DE number 1542267