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 条

[1] DECIDABILITY OF BISIMULATION EQUIVALENCE FOR PROCESSES GENERATING CONTEXT-FREE LANGUAGES [J].

BAETEN, JCM ;

BERGSTRA, JA ;

KLOP, JW .

JOURNAL OF THE ACM, 1993, 40 (03) :653-682

[2] Bisimilarity of Pushdown Automata is Nonelementary [J].

Benedikt, Michael ;

Goeller, Stefan ;

Kiefer, Stefan ;

Murawski, Andrzej S. .

2013 28TH ANNUAL IEEE/ACM SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2013, :488-497

[3]

Broadbent C., 2012, LEIBNIZ INT P INF, V18, P160, DOI DOI 10.4230/LIPICS.FSTTCS.2012.160

[4]

Burkart O., 1995, Mathematical Foundations of Computer Science 1995. 20th International Symposium, MFCS '95. Proceedings, P423

[5]

Caucal D., 1995, CSLI LECT NOTES, V53, P85

[6]

Courcelle Bruno, 1990, HDB THEORETICAL COMP, P459

[7]

Czerwinski W., 2010, LIPICS, V8

[8] A polynomial algorithm for deciding bisimilarity of normed context-free processes [J].

Hirshfeld, Y ;

Jerrum, M ;

Moller, F .

THEORETICAL COMPUTER SCIENCE, 1996, 158 (1-2) :143-159

[9]

Jancar P., 2013, LOG METH COMPUT SCI, V9, P1

[10] Undecidability of bisimilarity by defender's forcing [J].

Jancar, Petr ;

Srba, Jiri .

JOURNAL OF THE ACM, 2008, 55 (01)

← 1 2 3 →