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

Yo Sub Han; Sang Ki Ko; Kai Salomaa

doi:10.1007/978-3-030-23247-4_12

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

Yo Sub Han, Sang Ki Ko, Kai Salomaa

College of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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).

Original language	English
Title of host publication	Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings
Editors	Michal Hospodár, Galina Jirásková, Stavros Konstantinidis
Publisher	Springer Verlag
Pages	158-170
Number of pages	13
ISBN (Print)	9783030232467
DOIs	https://doi.org/10.1007/978-3-030-23247-4_12
Publication status	Published - 2019
Event	21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 - Košice, Slovakia Duration: 2019 Jul 17 → 2019 Jul 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11612 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019
Country/Territory	Slovakia
City	Košice
Period	19/7/17 → 19/7/19

Bibliographical note

Publisher Copyright:
© 2019, IFIP International Federation for Information Processing.

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-23247-4_12

Cite this

Han, Y. S., Ko, S. K., & Salomaa, K. (2019). Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity. In M. Hospodár, G. Jirásková, & S. Konstantinidis (Eds.), Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings (pp. 158-170). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11612 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-23247-4_12

Han, Yo Sub ; Ko, Sang Ki ; Salomaa, Kai. / Limited Nondeterminism of Input-Driven Pushdown Automata : Decidability and Complexity. Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. editor / Michal Hospodár ; Galina Jirásková ; Stavros Konstantinidis. Springer Verlag, 2019. pp. 158-170 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9ef5a56475a34dd1a29b4f001f6dc07c,

title = "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).",

keywords = "Ambiguity, Input-driven pushdown automata, Nondeterminism, Tree width",

author = "Han, {Yo Sub} and Ko, {Sang Ki} and Kai Salomaa",

note = "Publisher Copyright: {\textcopyright} 2019, IFIP International Federation for Information Processing.; 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 ; Conference date: 17-07-2019 Through 19-07-2019",

year = "2019",

doi = "10.1007/978-3-030-23247-4_12",

language = "English",

isbn = "9783030232467",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "158--170",

editor = "Michal Hospod{\'a}r and Galina Jir{\'a}skov{\'a} and Stavros Konstantinidis",

booktitle = "Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings",

address = "Germany",

}

Han, YS, Ko, SK & Salomaa, K 2019, Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity. in M Hospodár, G Jirásková & S Konstantinidis (eds), Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11612 LNCS, Springer Verlag, pp. 158-170, 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019, Košice, Slovakia, 19/7/17. https://doi.org/10.1007/978-3-030-23247-4_12

Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity. / Han, Yo Sub; Ko, Sang Ki; Salomaa, Kai.
Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. ed. / Michal Hospodár; Galina Jirásková; Stavros Konstantinidis. Springer Verlag, 2019. p. 158-170 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11612 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Limited Nondeterminism of Input-Driven Pushdown Automata

T2 - 21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019

AU - Han, Yo Sub

AU - Ko, Sang Ki

AU - Salomaa, Kai

PY - 2019

Y1 - 2019

N2 - 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).

AB - 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).

KW - Ambiguity

KW - Input-driven pushdown automata

KW - Nondeterminism

KW - Tree width

UR - http://www.scopus.com/inward/record.url?scp=85069543333&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85069543333&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-23247-4_12

DO - 10.1007/978-3-030-23247-4_12

M3 - Conference contribution

AN - SCOPUS:85069543333

SN - 9783030232467

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 170

BT - Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings

A2 - Hospodár, Michal

A2 - Jirásková, Galina

A2 - Konstantinidis, Stavros

PB - Springer Verlag

Y2 - 17 July 2019 through 19 July 2019

ER -

Han YS, Ko SK, Salomaa K. Limited Nondeterminism of Input-Driven Pushdown Automata: Decidability and Complexity. In Hospodár M, Jirásková G, Konstantinidis S, editors, Descriptional Complexity of Formal Systems - 21st IFIP WG 1.02 International Conference, DCFS 2019, Proceedings. Springer Verlag. 2019. p. 158-170. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-23247-4_12

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

Abstract

Publication series

Conference

Bibliographical note

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this