Equivalence of pushdown automata via first-order grammars

Autor: Petr Jancar
Rok vydání: 2021
Předmět:
FOS: Computer and information sciences
Computer Science - Logic in Computer Science
Formal Languages and Automata Theory (cs.FL)
Computer Networks and Communications
Computer science
Computer Science - Formal Languages and Automata Theory
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Deterministic pushdown automaton
Rule-based machine translation
020204 information systems
0202 electrical engineering
electronic engineering
information engineering
Equivalence (formal languages)
Discrete mathematics
Applied Mathematics
Pushdown automaton
Novelty
Bisimulation equivalence
First order
Logic in Computer Science (cs.LO)
Decidability
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Computational Theory and Mathematics
010201 computation theory & mathematics
TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS
Computer Science::Formal Languages and Automata Theory
Zdroj: Journal of Computer and System Sciences. 115:86-112
ISSN: 0022-0000
DOI: 10.1016/j.jcss.2020.07.004
Popis: A decidability proof for bisimulation equivalence of first-order grammars is given. It is an alternative proof for a result by S\'enizergues (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.
Comment: version accepted to JCSS
Databáze: OpenAIRE
Externí odkaz: