The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E107-D No.3 pp.312-319

- Publication Date
- 2024/03/01

- Publicized
- 2023/10/11

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2023FCP0006

- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science — Foundations of Computer Science and their New Trends —)

- Category

Ren MIMURA

Ibaraki University

Kengo MIYAMOTO

Ibaraki University

Akio FUJIYOSHI

Ibaraki University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Ren MIMURA, Kengo MIYAMOTO, Akio FUJIYOSHI, "Graph Linear Notations with Regular Expressions" in IEICE TRANSACTIONS on Information,
vol. E107-D, no. 3, pp. 312-319, March 2024, doi: 10.1587/transinf.2023FCP0006.

Abstract: 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2023FCP0006/_p

Copy

@ARTICLE{e107-d_3_312,

author={Ren MIMURA, Kengo MIYAMOTO, Akio FUJIYOSHI, },

journal={IEICE TRANSACTIONS on Information},

title={Graph Linear Notations with Regular Expressions},

year={2024},

volume={E107-D},

number={3},

pages={312-319},

abstract={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.},

keywords={},

doi={10.1587/transinf.2023FCP0006},

ISSN={1745-1361},

month={March},}

Copy

TY - JOUR

TI - Graph Linear Notations with Regular Expressions

T2 - IEICE TRANSACTIONS on Information

SP - 312

EP - 319

AU - Ren MIMURA

AU - Kengo MIYAMOTO

AU - Akio FUJIYOSHI

PY - 2024

DO - 10.1587/transinf.2023FCP0006

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E107-D

IS - 3

JA - IEICE TRANSACTIONS on Information

Y1 - March 2024

AB - 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.

ER -