Transition Function Complexity of Finite Automata
| Autor: | Maris Valdats |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
State complexity Finite-state machine Theoretical computer science General Computer Science Computer science Transition function Value (computer science) Minification Measure (mathematics) Computer Science::Formal Languages and Automata Theory Automaton |
| Zdroj: | Baltic Journal of Modern Computing. 7 |
| ISSN: | 2255-8950 |
| DOI: | 10.22364/bjmc.2019.7.3.02 |
| Popis: | State complexity of finite automata in some cases gives the same complexity value for automata which intuitively seem to have completely different complexities. In this paper we consider a new measure of descriptional complexity of finite automata -- BC-complexity. Comparison of it with the state complexity is carried out here as well as some interesting minimization properties are discussed. It is shown that minimization of the number of states can lead to a superpolynomial increase of BC-complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|