Article ID Journal Published Year Pages File Type
428782 Information Processing Letters 2008 5 Pages PDF
Abstract

Quasi-reversible automata is a suitable representation for reversible languages. In this work a method is proposed to obtain such an automaton for any given reversible language represented by its minimal DFA. Our method runs in polynomial time respect to the size of the minimal DFA and improves a previous exponential method. Previous bound for the size of quasi-reversible automata is also reduced.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics