Name
Abstract | ||
|---|---|---|
Finite automata whose computations can be reversed, at any point, by knowing the last k symbols read from the input, for a fixed k, are considered. These devices and their accepted languages are called k-reversible automata and k-reversible languages, respectively. The existence of k-reversible languages which are not (k - 1)-reversible is known, for each k > 1. This gives an infinite hierarchy of weakly irreversible languages, i.e., languages which are k-reversible for some k. Conditions characterizing the class of k-reversible languages, for each fixed k, and the class of weakly irreversible languages are obtained. From these conditions, a procedure that given a finite automaton decides if the accepted language is weakly or strongly (i.e., not weakly) irreversible is described. Furthermore, a construction which allows to transform any finite automaton which is not k-reversible, but which accepts a k-reversible language, into an equivalent k-reversible finite automaton, is presented. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.4204/EPTCS.252.15 | ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE |
DocType | Volume | Issue |
Journal | 252 | 252 |
ISSN | Citations | PageRank |
2075-2180 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Giovanna J. Lavado | 1 | 0 | 0.34 |
| Giovanni Pighizzini | 2 | 434 | 41.18 |
| Luca Prigioniero | 3 | 0 | 2.03 |