A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Ambiguity, Nondeterminism and State Complexity of Finite Automata




TekijätYo-Sub Han, Arto Salomaa, Kai Salomaa

KustantajaUNIV SZEGED, FAC SCIENCE

Julkaisuvuosi2017

JournalActa Cybernetica

Tietokannassa oleva lehden nimiACTA CYBERNETICA

Lehden akronyymiACTA CYBERN

Vuosikerta23

Numero1

Aloitussivu141

Lopetussivu157

Sivujen määrä17

ISSN0324-721X

DOIhttps://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.



Last updated on 2024-26-11 at 21:40