Polynomial graph transformability

被引：1

作者：

Kreowski, Hans-Joerg ^{[1
]}

Kuske, Sabine ^{[1
]}

机构：

[1] Univ Bremen, Dept Comp Sci, D-28334 Bremen, Germany

来源：

THEORETICAL COMPUTER SCIENCE | 2012年 / 429卷

关键词：

Graph transformation; Polynomial graph transformation unit; Satisfiability problem; NP-completeness; Reduction;

D O I：

10.1016/j.tcs.2011.12.039

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we introduce and study polynomial graph transformability as a graph-transformational counterpart of the satisfiability problem of the propositional calculus. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：193 / 201

页数：9

共 16 条

[1]

[Anonymous], 1999, Handbook of graph grammars and computing by graph transformation

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[3] Bounded model checking [J].

Biere, Armin .

Frontiers in Artificial Intelligence and Applications, 2009, 185 (01) :457-481

[4]

Corradini A., HDB GRAPH GRAMMARS C, P163

[5]

Corradini A, 2002, LECT NOTES COMPUTER, V2505

[6]

Corradini A., 2006, LECT NOTES COMPUTER, V4178

[7]

Ehrig H., 2010, LECT NOTES COMPUTER, V6372

[8]

Ehrig H., 1999, Handbook of Graph Grammars and Computing by Graph Transformation: Applications, Languages and Tools, V2

[9]

Ehrig H., 2008, LECT NOTES COMPUTER, V5214

[10]

Ehrig H., 2004, LECT NOTES COMPUTER, V3256

← 1 2 →