Ambiguity, Nondeterminism and State Complexity of Finite Automata | Zendy

Yo-Sub Han | Zendy; Arto Salomaa | Zendy; Kai Salomaa | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Ambiguity, Nondeterminism and State Complexity of Finite Automata

Author(s) -

Yo-Sub Han,

Arto Salomaa,

Kai Salomaa

Publication year - 2017

Publication title -

acta cybernetica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.143

H-Index - 18

eISSN - 2676-993X

pISSN - 0324-721X

DOI - 10.14232/actacyb.23.1.2017.9

Subject(s) - nondeterministic finite automaton , ambiguity , nondeterministic algorithm , computation , automaton , finite state machine , computer science , deterministic finite automaton , degree (music) , tree (set theory) , theoretical computer science , mathematics , algorithm , discrete mathematics , automata theory , combinatorics , programming language , physics , acoustics

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 content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research