Automata and minimization
| Autor: | Daniela Petrişan, Thomas Colcombet |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Microbiology (medical)
Theoretical computer science Nested word Immunology Timed automaton ω-automaton Nonlinear Sciences::Cellular Automata and Lattice Gases Mobile automaton DFA minimization Continuous spatial automaton Immunology and Allergy Quantum finite automata Automata theory Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | ACM SIGLOG News. 4:4-27 |
| ISSN: | 2372-3491 |
| DOI: | 10.1145/3090064.3090066 |
| Popis: | Already in the seventies, strong results illustrating the intimate relationship between category theory and automata theory have been described and are still investigated. In this column, we provide a uniform presentation of the basic concepts that underlie minimization results in automata theory. We then use this knowledge for introducing a new model of automata that is an hybrid of deterministic finite automata and automata weighted over a field. These automata are very natural, and enjoy minimization result by design. The presentation of this paper is indeed categorical in essence, but it assumes no prior knowledge from the reader. It is also non-conventional in that it is neither algebraic, nor co-algebraic oriented. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|