Deciding path size of nondeterministic (and input-driven) pushdown automata

被引：2

作者：

Han, Yo-Sub ^{[1
]}

Ko, Sang-Ki ^{[2
]}

Salomaa, Kai ^{[3
]}

机构：

[1] Yonsei Univ, Dept Comp Sci, Seoul, South Korea

[2] Kangwon Natl Univ, Dept Comp Sci & Engn, Chunchon, South Korea

[3] Queens Univ, Sch Comp, Kingston, ON, Canada

来源：

THEORETICAL COMPUTER SCIENCE | 2023年 / 939卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Measures of nondeterminism; Path size; Ambiguity; Input-driven pushdown automaton; Decidability; FINITE AUTOMATA; COMPLEXITY; AMBIGUITY;

D O I：

10.1016/j.tcs.2022.10.023

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The degree of ambiguity (respectively, the path size) of a nondeterministic automaton, on a given input, measures the number of accepting computations (respectively, the number of all computations). It is known that deciding the finiteness of the degree of ambiguity of a nondeterministic pushdown automaton is undecidable. Also, it is undecidable for a given k >= 3 to decide whether the path size of a nondeterministic pushdown automaton is bounded by k.As the main result, we show that deciding the finiteness of the path size of a nondeterministic pushdown automaton can be done in polynomial time. Also, we show that the k -path problem for nondeterministic input-driven pushdown automata (respectively, for nondeterministic finite automata) is complete for exponential time (respectively, complete for polynomial space).(c) 2022 Elsevier B.V. All rights reserved.

引用

页码：170 / 181

页数：12

共 34 条

[1]

Alur R., 2004, Proc. of the Thirty-sixth Annual ACM Symposium on Theory of Computing, P202, DOI DOI 10.1145/1007352.1007390

[2] Adding Nesting Structure to Words [J].

Alur, Rajeev ;

Madhusudan, P. .

JOURNAL OF THE ACM, 2009, 56 (03)

[3]

[Anonymous], 1979, Introduction to Automata Theory, Languages and Computation

[4] The tractability frontier for NFA minimization [J].

Bjorklund, Henrik ;

Martens, Wim .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2012, 78 (01) :198-210

[5]

Caralp M, 2012, LECT NOTES COMPUT SC, V7410, P226, DOI 10.1007/978-3-642-31653-1_21

[6]

Carotenuto D, 2007, LECT NOTES COMPUT SC, V4588, P132

[7]

CHAN TH, 1983, THEOR COMPUT SCI, V23, P95, DOI 10.1016/0304-3975(88)90012-6

[8] Problems on finite automata and the exponential time hypothesis [J].

Fernau H. ;

Krebs A. .

Algorithms, 2017, 10 (01)

[9]

Gecseg F., 2015, ARXIV

[10] Measuring nondeterminism in pushdown automata [J].

Goldstine, J ;

Leung, H ;

Wotschke, D .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2005, 71 (04) :440-466

← 1 2 3 4 →