Efficient decision procedures for graph properties on context-free graph languages

DOI10.1145/151261.151268zbMath0768.68085OpenAlexW1968017594MaRDI QIDQ5286167

Thomas Lengauer, Egon Wanke

Publication date: 29 June 1993

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/151261.151268

zbMATH Keywords

complexitycombinatorial algorithmsdecision procedurecontext-free graph grammarscellular graph grammarhyperedge replacement systems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Grammars and rewriting systems (68Q42) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

Node replacements in embedding normal form. ⋮ The complexity of connectivity problems on context-free graph languages ⋮ Context-free graph languages of bounded degree are generated by apex graph grammars ⋮ Logical description of context-free graph languages ⋮ Decision problems for edge grammars ⋮ A structural/temporal query language for business processes ⋮ Exponential time analysis of confluent and boundary eNCE graph languages ⋮ Bounded tree-width and LOGCFL

This page was built for publication: Efficient decision procedures for graph properties on context-free graph languages