|
| << previous |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 12 of 12 found articles
| Title: |
Series-Parallel Automata and Short Regular Expressions |
| Author: |
Moreira, Nelma Reis, Rogério |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 91 (2009) nr. 3-4 pages 611-629 |
| Year: |
2009-05-28 |
| Contents: |
Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n^{2} log n) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 12 of 12 found articles
| << previous |