The string generating power of context-free hypergraph grammars
From MaRDI portal
Publication:1176107
DOI10.1016/0022-0000(91)90018-ZzbMath0776.68075OpenAlexW2060300993MaRDI QIDQ1176107
Joost Engelfriet, Linda Heyker
Publication date: 25 June 1992
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(91)90018-z
string languagescontext-free hypergraph grammarscrossing number of transducerdeterministic tree-walking transducersnumber of tentacles of the nonterminals
Related Items
Monadic second-order definable graph transductions: a survey ⋮ Handle-rewriting hypergraph grammars ⋮ The translation power of top-down tree-to-graph transducers ⋮ Context-free graph languages of bounded degree are generated by apex graph grammars ⋮ Synthesized and inherited functions. A new computational model for syntax-directed semantics ⋮ Unnamed Item ⋮ Independent parallelism in finite copying parallel rewriting systems ⋮ Uniform \textit{vs.} nonuniform membership for mildly context-sensitive languages: a brief survey ⋮ Concatenation of graphs ⋮ The monadic second-order logic of graphs. VII: Graphs as relational structures ⋮ Multiple context-free tree grammars: lexicalization and characterization ⋮ Context-free hypergraph grammars have the same term-generating power as attribute grammars ⋮ Second-order abstract categorial grammars as hyperedge replacement grammars ⋮ A Greibach normal form for context-free graph grammars ⋮ Unnamed Item ⋮ Trading independent for synchronized parallelism in finite copying parallel rewriting systems ⋮ The Pumping Lemma for Well-Nested Multiple Context-Free Languages ⋮ The generating power of total deterministic tree transducers ⋮ Macro tree transducers, attribute grammars, and MSO definable tree translations. ⋮ Hypergraph languages of bounded degree
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A comparison of boundary graph grammars and context-free hypergraph grammars
- Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
- An axiomatic definition of context-free rewriting and its application to NLC graph grammars
- Tree transducers, L systems, and two-way machines
- One way finite visit automata
- Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
- Linear graph grammars: Power and complexity
- Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- Absolutely parallel grammars and two-way finite-state transducers
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Graph expressions and graph rewritings
- Passes and paths of attribute grammars
- Linear and Context-Free Graph Grammars
- Translations on a context free grammar
