%0 Conference Proceedings
%T Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity
%+ Yonsei University
%+ Korea Electronics Technology Institute [Seongnam-si] (KETI)
%+ Queen's University [Kingston, Canada]
%A Han, Yo-Sub
%A Ko, Sang-Ki
%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 158-170
%8 2019-07-17
%D 2019
%R 10.1007/978-3-030-23247-4_12
%K Nondeterminism
%K Tree width
%K Ambiguity
%K Input-driven pushdown automata
%Z Computer Science [cs]Conference papers
%X We study the decidability and computational complexity for several decision problems related to limited nondeterminism of finite-state automata equipped with a pushdown stack. Ambiguity and tree width are two measures of nondeterminism considered in the literature. As a main result, we prove that the problem of deciding whether or not the tree width of a nondeterministic pushdown automaton is finite is decidable in polynomial time. We also prove that the k-tree width problem for nondeterministic input-driven pushdown automata (respectively, nondeterministic finite automata) is complete for exponential time (respectively, for polynomial space).
%G English
%Z TC 1
%Z WG 1.02
%2 https://inria.hal.science/hal-02387306/document
%2 https://inria.hal.science/hal-02387306/file/480958_1_En_12_Chapter.pdf
%L hal-02387306
%U https://inria.hal.science/hal-02387306
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-11612