DesCo: a Web-base Knowledge System for Descriptional Complexity of Formal Languages
Davide Nabais · Open Repository of the University of Porto (University of Porto) · 2013
Descriptional complexity of formal languages studies the measures of descriptions of languages in terms of their accepting models of computation. For example, the state complexity of a regular language L is the minimal number of states in any deterministic finite automaton accepting L. The proliferous research in the field of descriptional complexity in recent years has given origin to a large collection of results dispersed along a few hundred articles. It is becoming increasingly difficult to have a general idea of all the work done in this field of research. DesCo, a web-based knowledge system for descriptional complexity results, was created to compensate for this, as well as, to provide some features that could be of help to the researchers, when looking for new results. In this thesis we describe the key concepts involved with descriptional complexity, and how they can be represented in some way so that they can be manipulated in order to aid the research community in finding new results. We also describe the tools used in the creation of the knowledge base and web interface, and the functionality of the system.