Reversible multi-head finite automata characterize reversible logarithmic space

Holger Bock Axelsen

doi:10.1007/978-3-642-28332-1_9

Reversible multi-head finite automata characterize reversible logarithmic space

Holger Bock Axelsen

Department of Computer Science

12 Citations (Scopus)

Abstract

Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (RMFAs), and posed the question of whether RMFAs characterize reversible logarithmic space as well. Here, we resolve the question affirmatively, by exhibiting a clean RMFA simulation of logarithmic space reversible Turing machines. Indirectly, this also proves that reversible and deterministic multi-head finite automata recognize the same languages.

Original language	English
Title of host publication	Language and Automata Theory and Applications : 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings
Editors	Adrian-Horia Dediu, Carlos Martín-Vide
Number of pages	11
Publisher	Springer
Publication date	2012
Pages	95–105
ISBN (Print)	978-3-642-28331-4
ISBN (Electronic)	978-3-642-28332-1
DOIs	https://doi.org/10.1007/978-3-642-28332-1_9
Publication status	Published - 2012
Event	6th International Conference on Language and Automata Theory and Applications - A Coruña, Spain Duration: 5 Mar 2012 → 9 Mar 2012 Conference number: 6

Conference

Conference	6th International Conference on Language and Automata Theory and Applications
Number	6
Country/Territory	Spain
City	A Coruña
Period	05/03/2012 → 09/03/2012

Series	Lecture notes in computer science
Volume	7183
ISSN	0302-9743

Access to Document

10.1007/978-3-642-28332-1_9

Cite this

Axelsen, H. B. (2012). Reversible multi-head finite automata characterize reversible logarithmic space. In A-H. Dediu, & C. Martín-Vide (Eds.), Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings (pp. 95–105). Springer. Lecture notes in computer science Vol. 7183 https://doi.org/10.1007/978-3-642-28332-1_9

Reversible multi-head finite automata characterize reversible logarithmic space. / Axelsen, Holger Bock.

Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings. ed. / Adrian-Horia Dediu; Carlos Martín-Vide. Springer, 2012. p. 95–105 (Lecture notes in computer science, Vol. 7183).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Axelsen, HB 2012, Reversible multi-head finite automata characterize reversible logarithmic space. in A-H Dediu & C Martín-Vide (eds), Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings. Springer, Lecture notes in computer science, vol. 7183, pp. 95–105, 6th International Conference on Language and Automata Theory and Applications, A Coruña, Spain, 05/03/2012. https://doi.org/10.1007/978-3-642-28332-1_9

Axelsen HB. Reversible multi-head finite automata characterize reversible logarithmic space. In Dediu A-H, Martín-Vide C, editors, Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings. Springer. 2012. p. 95–105. (Lecture notes in computer science, Vol. 7183). doi: 10.1007/978-3-642-28332-1_9

@inproceedings{938f74adb9a74db197a6ecdd12d7623c,

title = "Reversible multi-head finite automata characterize reversible logarithmic space",

abstract = "Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (RMFAs), and posed the question of whether RMFAs characterize reversible logarithmic space as well. Here, we resolve the question affirmatively, by exhibiting a clean RMFA simulation of logarithmic space reversible Turing machines. Indirectly, this also proves that reversible and deterministic multi-head finite automata recognize the same languages.",

author = "Axelsen, {Holger Bock}",

year = "2012",

doi = "10.1007/978-3-642-28332-1_9",

language = "English",

isbn = "978-3-642-28331-4",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "95–105",

editor = "Adrian-Horia Dediu and Carlos Mart{\'i}n-Vide",

booktitle = "Language and Automata Theory and Applications",

note = "6th International Conference on Language and Automata Theory and Applications, LATA 2012 ; Conference date: 05-03-2012 Through 09-03-2012",

}

TY - GEN

T1 - Reversible multi-head finite automata characterize reversible logarithmic space

AU - Axelsen, Holger Bock

N1 - Conference code: 6

PY - 2012

Y1 - 2012

N2 - Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (RMFAs), and posed the question of whether RMFAs characterize reversible logarithmic space as well. Here, we resolve the question affirmatively, by exhibiting a clean RMFA simulation of logarithmic space reversible Turing machines. Indirectly, this also proves that reversible and deterministic multi-head finite automata recognize the same languages.

AB - Deterministic and non-deterministic multi-head finite automata are known to characterize the deterministic and non- deterministic logarithmic space complexity classes, respectively. Recently, Morita introduced reversible multi-head finite automata (RMFAs), and posed the question of whether RMFAs characterize reversible logarithmic space as well. Here, we resolve the question affirmatively, by exhibiting a clean RMFA simulation of logarithmic space reversible Turing machines. Indirectly, this also proves that reversible and deterministic multi-head finite automata recognize the same languages.

U2 - 10.1007/978-3-642-28332-1_9

DO - 10.1007/978-3-642-28332-1_9

M3 - Article in proceedings

SN - 978-3-642-28331-4

T3 - Lecture notes in computer science

SP - 95

EP - 105

BT - Language and Automata Theory and Applications

A2 - Dediu, Adrian-Horia

A2 - Martín-Vide, Carlos

PB - Springer

T2 - 6th International Conference on Language and Automata Theory and Applications

Y2 - 5 March 2012 through 9 March 2012

ER -

Reversible multi-head finite automata characterize reversible logarithmic space

Abstract

Conference

Access to Document

Fingerprint

Cite this