Theoretical Aspects of Symbolic Automata
| Autor: | Margus Veanes, Hellis Tamm |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Finite-state machine Theoretical computer science Generalization Computer science Symbolic automata 0102 computer and information sciences 02 engineering and technology Nonlinear Sciences::Cellular Automata and Lattice Gases 01 natural sciences Automaton Set (abstract data type) Nondeterministic algorithm TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES 010201 computation theory & mathematics ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION 0202 electrical engineering electronic engineering information engineering Computer Science::Symbolic Computation 020201 artificial intelligence & image processing Boolean combination Computer Science::Formal Languages and Automata Theory Hardware_LOGICDESIGN |
| Zdroj: | SOFSEM 2018: Theory and Practice of Computer Science ISBN: 9783319731162 SOFSEM |
| DOI: | 10.1007/978-3-319-73117-9_30 |
| Popis: | Symbolic finite automata extend classical automata by allowing infinite alphabets given by Boolean algebras and having transitions labeled by predicates over such algebras. Symbolic automata have been intensively studied recently and they have proven useful in several applications. We study some theoretical aspects of symbolic automata. Especially, we study minterms of symbolic automata, that is, the set of maximal satisfiable Boolean combinations of predicates of automata. We define canonical minterms of a language accepted by a symbolic automaton and show that these minterms can be used to define symbolic versions of some known classical automata. Also we show that canonical minterms have an important role in finding minimal nondeterministic symbolic automata. We show that Brzozowski’s double-reversal method for minimizing classical deterministic automata as well as its generalization is applicable for symbolic automata. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|