Digitale Bibliotheek
Sluiten Bladeren door artikelen uit een tijdschrift
<< vorige    volgende >>
     Tijdschrift beschrijving
       Alle jaargangen van het bijbehorende tijdschrift
         Alle afleveringen van het bijbehorende jaargang
           Alle artikelen van de bijbehorende aflevering
                                       Details van artikel 9 van 18 gevonden artikelen
  Minimization and Characterizations for Biautomata
Titel: Minimization and Characterizations for Biautomata
Auteur: Holzer, Markus
Jakobi, Sebastian
Verschenen in: Fundamenta informaticae
Paginering: Jaargang 136 (2015) nr. 1-2 pagina's 113-137
Jaar: 2015-02-06
Inhoud: We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the biautomaton under consideration. Biautomata were recently introduced in [O. KLÍMA, L. POLÁK: On biautomata. RAIRO—Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first use the recently introduced notion of nondeterminism for biautomata [M. HOLZER, S. JAKOBI: Nondeterministic Biautomata and Their Descriptional Complexity. In: 15th DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward- and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.
Uitgever: IOS Press
Bronbestand: Elektronische Wetenschappelijke Tijdschriften

                             Details van artikel 9 van 18 gevonden artikelen
<< vorige    volgende >>
 Koninklijke Bibliotheek - Nationale Bibliotheek van Nederland