The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
본 논문에서는 그래프 선형 표기법과 이를 정규식으로 확장한 방법을 제안합니다. 그래프 선형 표기법은 레이블이 지정된 일반 그래프를 나타내는 문자열 집합입니다. 특정 유도된 하위 그래프의 선택 및 반복을 위해 선택된 부분을 지정하여 그래프 세트를 나타내기 위해 정규 표현식으로 확장됩니다. 그래프 선형 표기법과 레이블이 지정된 일반 그래프 간의 변환 방법이 표시됩니다. 그래프 정규식에 대한 멤버십 문제의 NP-완전성이 입증되었습니다.
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.
부
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
부
@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},}
부
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 -