arXiv Open Access 2017

Reversible Languages Having Finitely Many Reduced Automata

Kitti Gelle Szabolcs Iván

Lihat Sumber

Abstrak

Reversible forms of computations are often interesting from an energy efficiency point of view. When the computation device in question is an automaton, it is known that the minimal reversible automaton recognizing a given language is not necessarily unique, moreover, there are languages having arbitrarily large reversible recognizers possessing no nontrivial reversible congruence. However, the exact characterization of this class of languages was open. In this paper we give a forbidden pattern capturing the reversible regular languages having only finitely many reduced reversible automata, allowing an efficient (NL) decision procedure.

Topik & Kata Kunci

cs.FL

Penulis (2)

Kitti Gelle

Szabolcs Iván

Format Sitasi

APA MLA BibTeX

Gelle, K., Iván, S. (2017). Reversible Languages Having Finitely Many Reduced Automata. https://arxiv.org/abs/1705.10533

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2017
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓