About DesCo
hide
Descriptional complexity studies the measures of complexity of
languages and operations. Usually, the descriptional complexity of an
object is its shortest description which can be analyzed in the worst
or average case. For each measure, it is important to know the size
of the smallest representation for a given language and how the size
varies when several such representations are combined or transformed.
These studies are motivated by the need to have good estimates of the
amount of resources required to manipulate those representations.
This is crucial in new applied areas where automata and other models
of computation are used, for instance, for pattern matching in
bioinformatics or network security, or for model checking or security
certificates in formal verification systems. In general, having
succinct objects will improve our control on software, which may become
smaller, more efficient and easier to certify.
Among formal languages, regular languages are fundamental structures
in Computer Science. One of the most studied complexity measures for
regular languages is the number of states of its minimal deterministic
finite automaton (state complexity of the language). The state
complexity of an operation over languages is the complexity of the
resulting language as a function of the complexities of its arguments.
Both concepts can be extended to other models of computation
(e.g. nondeterministic automata, two-way automata, regular
expressions, grammars, etc.), other measures (number of transitions,
number of symbols, etc.) and other classes of languages (classes of
sub-regular languages, context-free languages, recursive languages,
etc).
DesCo is a Web based information system for descriptional complexity
results. Currently most of the data is related with the operational
complexity of regular or subregular languages.
Authors:
Nelma Moreira
Davide Nabais
Rogério Reis
Contact:
desco at dcc.fc.up.pt
