Ambiguity, nondeterminism and state complexity of finite automata

Yo Sub Han, Arto Salomaa, Kai Salomaa

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)141-157
Number of pages17
JournalActa Cybernetica
Issue number1
Publication statusPublished - 2017

Bibliographical note

Funding Information:
Han was supported by the Basic Science Research Program through NRF funded by MEST (2015R1D1A1A01060097) and the Yonsei University Future-leading Research Initiative of 2016. K. Salomaa was supported by the Natural Sciences and Engineering Research Council of Canada Grant OGP0147224.

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science (miscellaneous)
  • Computer Vision and Pattern Recognition
  • Management Science and Operations Research
  • Information Systems and Management
  • Electrical and Electronic Engineering


Dive into the research topics of 'Ambiguity, nondeterminism and state complexity of finite automata'. Together they form a unique fingerprint.

Cite this