• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Ambiguity, Non-Determinism and State Complexity of Finite Automata

Yo-Sub Han, Arto Salomaa, Kai Salomaa, Ambiguity, Non-Determinism and State Complexity of Finite Automata. Acta Cybernetica 23, 141–157, 2017.

Abstract:

The degree of ambiguity counts the number of accepting computations of a non-deterministic finite automaton (NFA) on a given input. Alternatively, the non-determinism 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 non-determinism measures for finite automata. In particular, we focus on state complexity comparisons between NFAs with quantified ambiguity or non-determinism.

BibTeX entry:

@ARTICLE{jHaSaSa17a,
  title = {Ambiguity, Non-Determinism and State Complexity of Finite Automata},
  author = {Han, Yo-Sub and Salomaa, Arto and Salomaa, Kai},
  journal = {Acta Cybernetica},
  volume = {23},
  pages = {141–157},
  year = {2017},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication