6533b853fe1ef96bd12ad3a1

RESEARCH PRODUCT

Transition Function Complexity of Finite Automata

Maris Valdats

subject

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESState complexityFinite-state machineTheoretical computer scienceGeneral Computer ScienceComputer scienceTransition functionValue (computer science)MinificationMeasure (mathematics)Computer Science::Formal Languages and Automata TheoryAutomaton

description

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.

yearjournalcountryeditionlanguage
2019-01-01Baltic Journal of Modern Computing
https://doi.org/10.22364/bjmc.2019.7.3.02