Equivalence of pushdown automata via first-order grammars

被引：2

作者：

Jancar, Petr ^{[1
]}

机构：

[1] Palacky Univ Olomouc, Fac Sci, Dept Comp Sci, Olomouc, Czech Republic

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2021年 / 115卷 / 115期

关键词：

Pushdown automata; First-order grammars; Bisimulation equivalence; DECIDABILITY; BISIMILARITY;

D O I：

10.1016/j.jcss.2020.07.004

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

A decidability proof for bisimulation equivalence of first-order grammars is given. It is an alternative proof for a result by Senizergues (1998, 2005) that subsumes his affirmative solution of the famous decidability question for deterministic pushdown automata. The presented proof is conceptually simpler, and a particular novelty is that it is not given as two semidecision procedures but it provides an explicit algorithm that might be amenable to a complexity analysis. (C) 2020 Elsevier Inc. All rights reserved.

引用

页码：86 / 112

页数：27

共 27 条

[11] Bisimulation Equivalence of First-Order Grammars is ACKERMANN-Complete [J].

Jancar, Petr ;

Schmitz, Sylvain .

2019 34TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2019,

[12] Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence [J].

Jancar, Petr .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2020, 109 :22-44

[13]

Jancar P, 2014, LECT NOTES COMPUT SC, V8412, P1

[14]

Jancar P, 2014, LECT NOTES COMPUT SC, V8573, P232

[15] Decidability of DPDA Language Equivalence via First-Order Grammars [J].

Jancar, Petr .

2012 27TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2012, :415-424

[16] BPA bisimilarity is EXPTIME-hard [J].

Kiefer, Stefan .

INFORMATION PROCESSING LETTERS, 2013, 113 (04) :101-106

[17]

Milner R., 1989, Communication and concurrency

[18] Higher-Order Model Checking: An Overview [J].

Ong, Luke .

2015 30TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2015, :1-15

[19] Complexity Hierarchies beyond Elementary [J].

Schmitz, Sylvain .

ACM TRANSACTIONS ON COMPUTATION THEORY, 2016, 8 (01)

[20] The bisimulation problem for equational graphs of finite out-degree [J].

Sénizergues, G .

SIAM JOURNAL ON COMPUTING, 2005, 34 (05) :1025-1106

← 1 2 3 →