|
| << vorige |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 12 van 12 gevonden artikelen
| Titel: |
Series-Parallel Automata and Short Regular Expressions |
| Auteur: |
Moreira, Nelma Reis, Rogério |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 91 (2009) nr. 3-4 pagina's 611-629 |
| Jaar: |
2009-05-28 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 12 van 12 gevonden artikelen
| << vorige |