𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Complete formal systems for equivalence problems

✍ Scribed by Géraud Sénizergues

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
181 KB
Volume
231
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We describe four complete and recursively enumerable formal systems S0; D0; H0; B0. Each one of them proves the decidability of some equivalence problem for some class of automata: namely the language equivalence problem for simple automata, the language equivalence problem for deterministic pushdown automata, the function equivalence problem for deterministic pushdown transducers with outputs in an abelian group, the bisimulation equivalence problem for loop-free pushdown automata.

📜 SIMILAR VOLUMES

On feedback equivalence and completion p
On feedback equivalence and completion problems
✍ Fernando C. Silva 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 508 KB

In 1987, I. Zaballa characterized the possible similarity classes of a square matrix with some prescribed rows. In 1988, the same author characterized the possible feedback equivalence classes of [ A B ], where A is a fixed square matrix and B varies. Firstly, in this paper, we observe that these re