Graph Linear Notations with Regular Expressions

被引：0

作者：

Mimura, Ren ^{[1
]}

Miyamoto, Kengo ^{[1
]}

Fujiyoshi, Akio ^{[1
]}

机构：

[1] Ibaraki Univ, Grad Sch Sci & Engn, Hitachi 3168511, Japan

来源：

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS | 2024年 / E107D卷 / 03期

关键词：

key linear notation; formal language theory; graph theory; regular expressions; NP-completeness;

D O I：

10.1587/transinf.2023FCP0006

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper proposes graph linear notations and an extension of them with regular expressions. Graph linear notations are a set of strings to represent labeled general graphs. They are extended with regular expressions to represent sets of graphs by specifying chosen parts for selections and repetitions of certain induced subgraphs. Methods for the conversion between graph linear notations and labeled general graphs are shown. The NP -completeness of the membership problem for graph regular expressions is proved.

引用

页码：312 / 319

页数：8

共 10 条

[1]

Bondy JA, 1976, Graph Theory

[2] A Simple Extension to Finite Tree Automata for Defining Sets of Labeled, Connected Graphs [J].

Fujiyoshi, Akio ;

Prusa, Daniel .

IMPLEMENTATION AND APPLICATION OF AUTOMATA (CIAA 2019), 2019, 11601 :121-132

[3]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[4]

GLUSHKOV VM, 1961, RUSS MATH SURV, V16, P1, DOI [10.1070/RM1961v016n05ABEH004112, DOI 10.1070/RM1961V016N05ABEH004112]

[5]

James C.A., 2023, OpenSMILES

[6] A Proposal of Chemical Structure Search Using a Regular Expression Extension for SMILES [J].

Sakamoto, Masashi ;

Fujiyoshi, Akio .

JOURNAL OF COMPUTER CHEMISTRY-JAPAN, 2018, 17 (05) :193-195

[7]

Sipser M., 2006, Introduction to the Theory of Computation, V2nd

[8]

Ullman, 1979, ADDISON WESLEY SERIE

[9] SMILES, A CHEMICAL LANGUAGE AND INFORMATION-SYSTEM .1. INTRODUCTION TO METHODOLOGY AND ENCODING RULES [J].

WEININGER, D .

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1988, 28 (01) :31-36

[10]

World Anti-Doping Agency, 2023, PROH LIST

← 1 →