|
DesCo: a Knowledge Based System for Descriptional
Complexity of Formal Languages
Nelma Moreira, Davide Nabais, Rogério Reis
DCC-FC & CMUP, Universidade do Porto
e-mail: {nam,dnabais,rvr}@dcc.fc.up.pt,
July 2013
Abstract
Recently the descriptional complexity of formal languages has been
extensively researched. One of the most studied complexity measures
for regular languages is the number of states of its minimal
automaton (state complexity of the language). Other measures can be
related to other structural components and other models of
computation. The complexity of a language operation is the
complexity of the resulting language seen as a function of the
complexities of the operation arguments. This proliferous research
gave origin to a multitude of results scattered over a few hundred
articles, with the inevitable lack of unified terminology and
notation. This makes it very difficult for an interested researcher
to have a global perspective of this field and realize what is the
current coverage achieved in order to know where to allocate more
research efforts. In this paper we present a first step towards the
development of a knowledge base and a Web interface where
descriptional complexity results can be structurally introduced,
queried, and viewed. We also show how the system can interact with
formal language symbolic manipulators in order to obtain
examples and perform experimental tests. Moreover the system enables
the user to easily customize queries in order to get novel views
over the existing results.
|