A Simple Extension to Finite Tree Automata for Defining Sets of Labeled, Connected Graphs
A Simple Extension to Finite Tree Automata for Defining Sets of Labeled, Connected Graphs
复制标题
用于定义标记连通图集的有限树自动机的简单扩展
DOI：
10.1007/978-3-030-23679-3_10
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Prusa Daniel
中科院分区：
文献类型：
--
作者：
Fujiyoshi Akio;Prusa Daniel
本文介绍了生成树自动机（ST自动机）可用于定义一组标记，连接图。该自动机简单地通过将普通的自顶向下有限树自动机扩展到标记有序树而得到。它表明，ST自动机可以定义任何有限集的标记，连通图，也可以定义一些子类的无限集的图，可以表示化学分子的结构。虽然ST自动机的成员问题是NP完全的，一个有效的软件开发，支持ST自动机在化学信息学以及在其他领域的实际应用。
This paper introduces spanning tree automata (ST automata) usable for defining sets of labeled, connected graphs. The automata are simply obtained by extending ordinary top-down finite tree automata for labeled, ordered trees. It is shown that ST automata can define any finite set of labeled, connected graphs, and also some subclasses of infinite sets of graphs that can represent the structure of chemical molecules. Although the membership problem for ST automata is NP-complete, an efficient software was developed which supports a practical use of ST automata in chemoinformatics as well as in other fields.