Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

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

(1) , (2) , (3)
1
2
3
Yo-Sub Han
  • Function : Author
  • PersonId : 1024595
Kai Salomaa
  • Function : Author
  • PersonId : 1022715

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).
Fichier principal
Vignette du fichier
480958_1_En_12_Chapter.pdf (123.12 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02387306 , version 1 (29-11-2019)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

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⟩
35 View
8 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More