Descriptional complexity studies the measures of complexity of languages and operations. These studies are motivated by the need to have good estimates of the amount of resources required to manipulate the smallest representation for a given language. In general, having succinct objects will improve our control on software, which may become smaller and more efficient.
Among formal languages, regular languages constitutes a fundamental class in Computer Science, and its descriptional complexity has recently been extensively investigated. One of the most studied complexity measures for regular languages is the number of states of its minimal (complete) deterministic finite automaton, the state complexity of the language. Because the transition function, in these models, is a total function it is obvious that the transition complexity is the product of the alphabet size by the state complexity. However, in nondeterministic finite automata (NFA) the study of the transition complexity is often preferred as a much more significant measure of descriptional complexity. In regular languages for non-necessarily complete deterministic finite automata (DFA), when the transition function can be partial, the transition complexity is also a more expressive descriptional measure.
These models are convenient in many applications where very sparse transition functions take place. The state (transition) complexity of an operation over languages is the complexity of the resulting language as a function of the complexities and other measures of its arguments. The study of the transition complexity of operations on regular languages based on non-necessarily complete DFAs is very recent, and only a few results were found.
In this talk we present tight upper bounds for the operational state and transition complexity of boolean operations, concatenation, Kleene star and reversal, over regular languages based on DFAs.
This is joint work with Nelma Moreira and Rogério Reis.