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

DOI10.1145/151261.151268zbMATH Open0768.68085OpenAlexW1968017594MaRDI QIDQ5286167FDOQ5286167

Authors: 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

Recommendations

• scientific article; zbMATH DE number 4060749
• scientific article; zbMATH DE number 4060748
• On the decidability of certain integer subgraph problems on context-free graph languages
• The complexity of connectivity problems on context-free graph languages

zbMATH Keywords

complexitydecision procedurecombinatorial algorithmscontext-free graph grammarscellular graph grammarhyperedge replacement systems

Mathematics Subject Classification ID

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

Cited In (12)

• Decision problems for edge grammars
• Title not available (Why is that?)
• Node replacements in embedding normal form.
• A structural/temporal query language for business processes
• Set of memories of a D-graph
• Exponential time analysis of confluent and boundary eNCE graph languages
• Context-free graph languages of bounded degree are generated by apex graph grammars
• Logical description of context-free graph languages
• Bounded tree-width and LOGCFL
• The complexity of connectivity problems on context-free graph languages
• Title not available (Why is that?)
• Title not available (Why is that?)

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

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