Skip to Main content Skip to Navigation
Conference papers

Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity

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

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387306
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:36:33 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

Yo-Sub Han, Sang-Ki Ko, Kai Salomaa. Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.158-170, ⟨10.1007/978-3-030-23247-4_12⟩. ⟨hal-02387306⟩

Share

Metrics

Record views

88