6533b853fe1ef96bd12ad4a4

RESEARCH PRODUCT

Transition Function Complexity of Finite Automata

Maris Valdats

subject

Discrete mathematicsAverage-case complexityTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESFinite-state machineDFA minimizationContinuous spatial automatonAutomata theoryQuantum finite automataDescriptive complexity theoryω-automatonComputer Science::Formal Languages and Automata TheoryMathematics

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
2011-01-01
https://doi.org/10.1007/978-3-642-22600-7_24