Cycle Height of Finite Automata

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905622
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:00:56 AM
Last modification on : Friday, October 26, 2018 - 8:05:10 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:46:01 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

40