Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428782 | Information Processing Letters | 2008 | 5 Pages |
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