%0 Conference Proceedings
%T Cycle Height of Finite Automata
%+ Queen's University [Kingston, Canada]
%A Keeler, Chris
%A Salomaa, Kai
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 200-211
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_17
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905622/document
%2 https://inria.hal.science/hal-01905622/file/470153_1_En_17_Chapter.pdf
%L hal-01905622
%U https://inria.hal.science/hal-01905622
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952