Name
Abstract | ||
|---|---|---|
In this paper, we propose a reduction of the minimization problem for a bottom-up deterministic tree automaton (DFTA), making the latter a minimization of a string deterministic finite automaton (DFA). To achieve this purpose, we proceed first by the transformation of the tree automaton into a particular string automaton, followed by minimizing this string automaton. In addition, we show that for our transformation, the minimization of the resulting string automaton coincides with the minimization of the original tree automaton. Finally, we discuss the complexity of our proposal for different types of tree automata, namely: standard, acyclic, incremental, and incrementally constructed tree automata. |
Year | DOI | Venue |
|---|---|---|
2018 | https://doi.org/10.1007/s00224-017-9815-4 | Theory Comput. Syst. |
Keywords | Field | DocType |
Tree automata,Tree languages,Finite automata,Minimization | Discrete mathematics,Two-way deterministic finite automaton,Combinatorics,Deterministic automaton,Nondeterministic finite automaton,Timed automaton,DFA minimization,Pushdown automaton,Tree automaton,Mathematics,Büchi automaton | Journal |
Volume | Issue | ISSN |
62 | 5 | 1432-4350 |
Citations | PageRank | References |
0 | 0.34 | 17 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Younes Guellouma | 1 | 0 | 1.01 |
| Hadda Cherroun | 2 | 21 | 11.14 |
| Djelloul Ziadi | 3 | 197 | 29.12 |
| Bruce W. Watson | 4 | 338 | 53.24 |