A Simple Extension to Finite Tree Automata for Defining Sets of Labeled, Connected Graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F19%3A00335631" target="_blank" >RIV/68407700:21230/19:00335631 - isvavai.cz</a>
Result on the web
<a href="https://link.springer.com/chapter/10.1007/978-3-030-23679-3_10" target="_blank" >https://link.springer.com/chapter/10.1007/978-3-030-23679-3_10</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-030-23679-3_10" target="_blank" >10.1007/978-3-030-23679-3_10</a>

Result language
angličtina
Original language name
A Simple Extension to Finite Tree Automata for Defining Sets of Labeled, Connected Graphs
Original language description
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.
Czech name
—
Czech description
—

Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA19-21198S" target="_blank" >GA19-21198S: Complex prediction models and their learning from weakly annotated data</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)