Paper Info
Title
Transition function complexity of finite automata
Abstract
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.
Year
DOI
Venue
2011
10.1007/978-3-642-22600-7_24
DCFS
Keywords
Field
DocType
state complexity,new measure,finite automaton,interesting minimization property,different complexity,descriptional complexity,complexity value,superpolynomial increase,transition function complexity
Quantum finite automata,Average-case complexity,Discrete mathematics,Automata theory,Continuous spatial automaton,Finite-state machine,DFA minimization,Descriptive complexity theory,Mathematics,ω-automaton
Conference
Citations 
PageRank 
References 
0
0.34
2
Authors
1
Name
Order
Citations
PageRank
Maris Valdats1201.64