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

Datalogisk Institut

12 Citationer (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.

Originalsprog	Engelsk
Titel	Language and Automata Theory and Applications : 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings
Redaktører	Adrian-Horia Dediu, Carlos Martín-Vide
Antal sider	11
Forlag	Springer
Publikationsdato	2012
Sider	95–105
ISBN (Trykt)	978-3-642-28331-4
ISBN (Elektronisk)	978-3-642-28332-1
DOI	https://doi.org/10.1007/978-3-642-28332-1_9
Status	Udgivet - 2012
Begivenhed	6th International Conference on Language and Automata Theory and Applications - A Coruña, Spanien Varighed: 5 mar. 2012 → 9 mar. 2012 Konferencens nummer: 6

Konference

Konference	6th International Conference on Language and Automata Theory and Applications
Nummer	6
Land/Område	Spanien
By	A Coruña
Periode	05/03/2012 → 09/03/2012

Navn	Lecture notes in computer science
Vol/bind	7183
ISSN	0302-9743

Adgang til dokumentet

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

Citationsformater

Axelsen, H. B. (2012). Reversible multi-head finite automata characterize reversible logarithmic space. I A-H. Dediu, & C. Martín-Vide (red.), Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings (s. 95–105). Springer. Lecture notes in computer science Bind 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. red. / Adrian-Horia Dediu; Carlos Martín-Vide. Springer, 2012. s. 95–105 (Lecture notes in computer science, Bind 7183).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Axelsen, HB 2012, Reversible multi-head finite automata characterize reversible logarithmic space. i A-H Dediu & C Martín-Vide (red), 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, bind 7183, s. 95–105, 6th International Conference on Language and Automata Theory and Applications, A Coruña, Spanien, 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. I Dediu A-H, Martín-Vide C, red., Language and Automata Theory and Applications: 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings. Springer. 2012. s. 95–105. (Lecture notes in computer science, Bind 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

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater