A Simple Extension to Finite Tree Automata for Defining Sets of Labeled, Connected Graphs
| Autor: | Daniel Průša, Akio Fujiyoshi |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Infinite set TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Spanning tree Computer science Structure (category theory) 020206 networking & telecommunications 0102 computer and information sciences 02 engineering and technology Nonlinear Sciences::Cellular Automata and Lattice Gases 01 natural sciences Simple extension Automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Automata theory Tree automaton Finite set Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Implementation and Application of Automata ISBN: 9783030236786 CIAA |
| DOI: | 10.1007/978-3-030-23679-3_10 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|