Skip to Main content Skip to Navigation
Conference papers

Nondeterminism Growth and State Complexity

Abstract : Tree width (respectively, string path width) measures the maximal number of partial (respectively, complete) computations of a nondeterministic finite automaton (NFA) on an input of given length. We study the growth rate of the tree width and string path width measures. As the main result we show that the degree of the polynomial bounding the tree width of an NFA differs by at most one from the degree of the polynomial bounding the string path width. Also we show that for $$m \ge 4$$ there exists an m-state NFA with finite string path width such that any equivalent finite tree width NFA needs $$2^{m-2} + 1$$ states.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387283
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:35:23 PM
Last modification on : Monday, December 7, 2020 - 9:44:02 AM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-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. Nondeterminism Growth and State Complexity. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.210-222, ⟨10.1007/978-3-030-23247-4_16⟩. ⟨hal-02387283⟩

Share

Metrics

Record views

125