Exponential time analysis of confluent and boundary eNCE graph languages

DOI10.1007/3-540-59071-4_47MaRDI QIDQ6184368zbMATH OpenOpenAlexFDO

Authors Konstantin Skodinis, Egon Wanke

Publication date 5 January 2024

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59071-4_47

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Emptiness problems of eNCE graph languages
• The bounded degree problem for eNCE graph grammars
• Boundary graph grammars with dynamic edge relabeling
• Linear graph grammars: Power and complexity
• scientific article; zbMATH DE number 17539

Cites work

• Algorithms for graph problems on BNLC structured garphs
• Alternation
• Boundary graph grammars with dynamic edge relabeling
• Efficient decision procedures for graph properties on context-free graph languages
• Graph grammars and their application to computer science. 4th international workshop, Bremen, Germany, March 5-9, 1990. Proceedings
• Graph grammars with neighbourhood-controlled embedding
• 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
• Graph-grammars and their application to computer science. 3rd International Workshop, Warrenton, Virginia, USA, December 2-6, 1986
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 3943061 (Why is no real title available?)
• scientific article; zbMATH DE number 4049100 (Why is no real title available?)
• scientific article; zbMATH DE number 4049101 (Why is no real title available?)
• Hyperedge replacement: grammars and languages
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

This page was built for publication: Exponential time analysis of confluent and boundary eNCE graph languages

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