Descriptional Complexity of Regular Languages

 
Researchers

Marco Almeida, Nelma Moreira, Rogério Reis

  Since May 2007 this research is part of the ASA (Automata,semigroups and applications) FCT project (PTDC/MAT/65481/2006).

•   Enumeration and Random Generation
  

  The enumeration of languages based on their model representations are useful for several language characterization, and for random generation and average case analysis. Based on a compact canonical form for deterministic finite automata (DFA) some new results were obtained for enumeration, random generation and state-complexity minimality characterization [1,2,3]. Also,a canonical form for minimal acyclic deterministic finite automata was developed, which provided for the first time in the literature the exact enumeration of this kind of automata [4]. 
  
  Ongoing and future work:

  • to pursue in a deeper study of the density of minimal DFA's and obtain some graph characterizations of state-complexity non-minimality
  • the characterize the normal forms of other specific classes of automata and infer its enumerative consequences;to obtain similar representations for (representative) classes of non-deterministic automata (NFA) and apply them for enumerative and random generation, and other characterizations.

     

  [1] R. Reis, N. Moreira and M. Almeida, On the Representation of Finite Automata. DCFS05. pp 269-276, 2005.

  [2]M. Almeida, N. Moreira, and R. Reis. Aspects of enumeration and generation with a string representation. DCFS06, pp 58-69,NMSU-CS-2006-001, 2006.

  [3] M. Almeida, N. Moreira, and R. Reis. Enumeration and Generation with a String Automata Representation. Theor. Comp. Sci., 387, 2, pp 93-102, 2007.

  [4] M. Almeida, N. Moreira, and R. Reis. Exact generation of minimal acyclic deterministic finite automata, Proc. DCFS07,pp 57-68, 2007.

  [5] R. Reis. Autómatos finitos: manipulação e geração. Phd, Univ. do Porto, 2007 (in portuguese)

•   Conversion between finite automata and regular expressions
  

  One of the goals is to characterise classes of finite automata for which it is easy to find a small regular expression, as well as to relate the usual algebraic properties of regular expression with automata transformations that preserve equivalence. We identified a class of acyclic automata for which it is possible to obtain in time O(n^2logn) an equivalent regular expression of size O(n). This class of automata is characterized by the properties of the underlying graphs that correspond to the series-parallel digraphs class (SP automata). Using this last characterization, we developed an exact generation algorithm and presented an enumerative formula [5,6].  
  
  Ongoing and future work:

  • to extend the notion of SP automata to acyclic automata with several final states and some restricted classes of cyclic automata
  • to define a set of transformations between graphs of equivalent automata, based on basic equivalences between regular expressions
  • to explore the possible relationships between the descriptional complexities (state, transition, etc.) of automata and of the corresponding measures for regular expressions

  [6] J. J. Morais, N. Moreira and R. Reis. Acyclic Automata with easy-to-find short regular expressions. CIAA 2005, LNCS 3845, pp. 349-350. SV. 2006

  J. J. Morais. Computing small regular expressions from finite automata. MSc in Informatics, DCC-FCUP, 2005.

•   Equivalence and small representations of regular expressions
  

  For regular expressions there are no standard measure for small normal forms and equivalence of regular expressions is PSPACE-complete. This problem is normally solved by transforming each regular expression to equivalent nondeterministic finite automata; convert those automata into equivalent deterministic ones, and finally minimise both deterministic finite automata, and determine if the resulting automata are isomorphic. Antimirov and Mosses presented a rewrite system for deciding the equivalence of two (extended) regular expressions and argued that this method could lead to a better average-case algorithm than those based on the comparison of the equivalent minimal dfas. We implemented their method and although being a refutation method, our preliminary results lead to the conclusion that indeed this method is feasible and it is, almost always, faster than the classical methods [7].  
  
  Ongoing and future work:

  • a better theoretical understanding of relationships between the two approaches would be helpful towards the characterization of their average-case complexity
  • study if the sets of partial derivatives of a regular expression can be used to improve the rewrite system described above
  • identify sets of rewrite rules for the simplification of regular expressions and analyse their computational properties.

     

  [7] M. Almeida, N. Moreira, and R. Reis. Antimirov and Mosses's rewrite system revisited. CIAA 2008

•   High-performance software library for the symbolic manipulation of automata
  

  Computational symbolic manipulation environments for formal languages and algebraic structures are now widely recognized as important tools for supporting theoretical research. In LIACC ,it is in progress the development of the [FAdo] system which intends to provide a set of tools for formal languages manipulation, and currently includes most standard operations for the manipulation of regular languages [5,8], a Turing machine simulator and parsing tools for context-free languages.  
  
  Ongoing and future work: an open source extensible high-performance software library for the symbolic manipulation of automata and other models of computation; tools for automatic drawing of automata diagrams that respect, as far as possible, common accepted aesthetics principles, allow user interaction and provide output diagrams in standard formats; a modular graphical user interface for the manipulation of automata and other models of computation and that will include interactive visualization of algorithms, based on a formal description.

  [8] N. Moreira and R. Reis. Interactive Manipulation of Regular Objects with FAdo.ITICSE 2005,pp 335-339, ACM, 2005.