Technical Report: DCC-2013-12

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},
July 2013


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.