From Tree Automata to String Automata Minimization
| Autor: | Djelloul Ziadi, Bruce W. Watson, Younes Guellouma, Hadda Cherroun |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Timed automaton Pushdown automaton Büchi automaton 0102 computer and information sciences 02 engineering and technology Nonlinear Sciences::Cellular Automata and Lattice Gases 01 natural sciences Theoretical Computer Science TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Computational Theory and Mathematics DFA minimization 010201 computation theory & mathematics Deterministic automaton 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Two-way deterministic finite automaton Tree automaton Nondeterministic finite automaton Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | Theory of Computing Systems. 62:1203-1222 |
| ISSN: | 1433-0490 1432-4350 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink