A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Ambiguity, Nondeterminism and State Complexity of Finite Automata
Tekijät: Yo-Sub Han, Arto Salomaa, Kai Salomaa
Kustantaja: UNIV SZEGED, FAC SCIENCE
Julkaisuvuosi: 2017
Journal: Acta Cybernetica
Tietokannassa oleva lehden nimi: ACTA CYBERNETICA
Lehden akronyymi: ACTA CYBERN
Vuosikerta: 23
Numero: 1
Aloitussivu: 141
Lopetussivu: 157
Sivujen määrä: 17
ISSN: 0324-721X
DOI: https://doi.org/10.14232/actacyb.23.1.2017.9
Tiivistelmä
The degree of ambiguity counts the number of accepting computations of a nondeterministic finite automaton (NFA) on a given input. Alternatively, the nondeterminism of an NFA can be measured by counting the amount of guessing in a single computation or the number of leaves of the computation tree on a given input. This paper surveys work on the degree of ambiguity and on various nondeterminism measures for finite automata. In particular, we focus on state complexity comparisons between NFAs with quantified ambiguity or nondeterminism.
The degree of ambiguity counts the number of accepting computations of a nondeterministic finite automaton (NFA) on a given input. Alternatively, the nondeterminism of an NFA can be measured by counting the amount of guessing in a single computation or the number of leaves of the computation tree on a given input. This paper surveys work on the degree of ambiguity and on various nondeterminism measures for finite automata. In particular, we focus on state complexity comparisons between NFAs with quantified ambiguity or nondeterminism.
Turun yliopiston Tutkimustietojärjestelmän portaali