On the k-reversibility of finite automata

Loading...
Thumbnail Image

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

It is a famous result of Angluin (1982 [1]) that there exists a time polynomial and space linear algorithm to identify the canonical automata of k- reversible languages by using characteristic sample sets. This result has several applications. In this paper we characterise the class of all automata for which her method is not applicable. In particular, the aim of this paper is to characterise the family of finite automata which are not k-reversible for any non-negative integer k.

Description

Citation

Endorsement

Review

Supplemented By

Referenced By