Cycle Height of Finite Automata - Archive ouverte HAL Access content directly
Conference Papers Year : 2018

Cycle Height of Finite Automata

(1) , (1)
1
Chris Keeler
  • Function : Author
  • PersonId : 1024582
Kai Salomaa
  • Function : Author
  • PersonId : 1022715

Abstract

A nondeterministic finite automaton (NFA) A has cycle height $$\mathcal {K}$$ if any computation of A can visit at most $$\mathcal {K}$$ cycles, and A has finite cycle height if it has cycle height $$\mathcal {K}$$ for some $$\mathcal {K}$$. We give a polynomial time algorithm to decide whether an NFA has finite cycle height and, in the positive case, to compute its optimal cycle height. Nondeterministic finite automata of finite cycle height recognize the polynomial density regular languages.
Fichier principal
Vignette du fichier
470153_1_En_17_Chapter.pdf (313.84 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01905622 , version 1 (26-10-2018)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Chris Keeler, Kai Salomaa. Cycle Height of Finite Automata. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.200-211, ⟨10.1007/978-3-319-94631-3_17⟩. ⟨hal-01905622⟩
46 View
86 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More