%0 Conference Proceedings
%T Nondeterminism Growth and State Complexity
%+ School of computing [Kingston]
%A Keeler, Chris
%A Salomaa, Kai
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Košice, Slovakia
%Y Michal Hospodár
%Y Galina Jirásková
%Y Stavros Konstantinidis
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-11612
%P 210-222
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_16
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387283/document
%2 https://inria.hal.science/hal-02387283/file/480958_1_En_16_Chapter.pdf
%L hal-02387283
%U https://inria.hal.science/hal-02387283
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612