A comparison of compatible, finite, and inductive graph properties

DOI10.1016/0304-3975(93)90354-VzbMath0771.68079MaRDI QIDQ1812942

Annegret Habel, Clemens Lautemann, Hans-Joerg Kreowski

Publication date: 25 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

decision problemshyperedge-replacementcontext-free graph grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42)

Related Items (5)

Recognizable sets of graphs: equivalent definitions and closure properties ⋮ Recognizable languages of arrows and cospans ⋮ Decision problems for edge grammars ⋮ Process specification and verification ⋮ Bottom-up unranked tree-to-graph transducers for translation into semantic graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• Monadic second-order evaluations on tree-decomposable graphs
• Metatheorems for decision problems on hyperedge replacement graph languages
• Plex languages
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• Graph expressions and graph rewritings

This page was built for publication: A comparison of compatible, finite, and inductive graph properties