Standard

On stateless multihead automata: Hierarchies and the emptiness problem. / Ibarra, Oscar H.; Karhumäki, Juhani; Okhotin, Alexander.

LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. 2008. стр. 94-105 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 4957 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование

Harvard

Ibarra, OH, Karhumäki, J & Okhotin, A 2008, On stateless multihead automata: Hierarchies and the emptiness problem. в LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 4957 LNCS, стр. 94-105, 8th Latin American TheoreticalINformatics Symposium, LATIN 2008, Buzios, Бразилия, 7/04/08. https://doi.org/10.1007/978-3-540-78773-0_9

APA

Ibarra, O. H., Karhumäki, J., & Okhotin, A. (2008). On stateless multihead automata: Hierarchies and the emptiness problem. в LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings (стр. 94-105). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 4957 LNCS). https://doi.org/10.1007/978-3-540-78773-0_9

Vancouver

Ibarra OH, Karhumäki J, Okhotin A. On stateless multihead automata: Hierarchies and the emptiness problem. в LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. 2008. стр. 94-105. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-78773-0_9

Author

Ibarra, Oscar H. ; Karhumäki, Juhani ; Okhotin, Alexander. / On stateless multihead automata: Hierarchies and the emptiness problem. LATIN 2008: Theoretical Informatics - 8th Latin American Symposium, Proceedings. 2008. стр. 94-105 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{0fb03bc8943346a9bfd472b647674dd7,
title = "On stateless multihead automata: Hierarchies and the emptiness problem",
abstract = "We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition moves each head one cell left or right, or instructs it to stay. We show that stateless (k∈+∈4)-head two-way automata are more powerful than stateless k-head two-way automata. In the one-way case, we prove a tighter result: stateless (k∈+∈1)-head one-way automata are more powerful than stateless k-head one-way automata. Finally, we show that the emptiness problem for stateless 2-head two-way automata is undecidable.",
author = "Ibarra, {Oscar H.} and Juhani Karhum{\"a}ki and Alexander Okhotin",
year = "2008",
doi = "10.1007/978-3-540-78773-0_9",
language = "English",
isbn = "3540787720",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "94--105",
booktitle = "LATIN 2008",
note = "8th Latin American TheoreticalINformatics Symposium, LATIN 2008 ; Conference date: 07-04-2008 Through 11-04-2008",

}

RIS

TY - GEN

T1 - On stateless multihead automata: Hierarchies and the emptiness problem

AU - Ibarra, Oscar H.

AU - Karhumäki, Juhani

AU - Okhotin, Alexander

PY - 2008

Y1 - 2008

N2 - We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition moves each head one cell left or right, or instructs it to stay. We show that stateless (k∈+∈4)-head two-way automata are more powerful than stateless k-head two-way automata. In the one-way case, we prove a tighter result: stateless (k∈+∈1)-head one-way automata are more powerful than stateless k-head one-way automata. Finally, we show that the emptiness problem for stateless 2-head two-way automata is undecidable.

AB - We look at stateless multihead finite automata in their two-way and one-way, deterministic and nondeterministic variations. The transition of a k-head automaton depends solely on the symbols currently scanned by its k heads, and every such transition moves each head one cell left or right, or instructs it to stay. We show that stateless (k∈+∈4)-head two-way automata are more powerful than stateless k-head two-way automata. In the one-way case, we prove a tighter result: stateless (k∈+∈1)-head one-way automata are more powerful than stateless k-head one-way automata. Finally, we show that the emptiness problem for stateless 2-head two-way automata is undecidable.

UR - http://www.scopus.com/inward/record.url?scp=43049111773&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78773-0_9

DO - 10.1007/978-3-540-78773-0_9

M3 - Conference contribution

AN - SCOPUS:43049111773

SN - 3540787720

SN - 9783540787723

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 94

EP - 105

BT - LATIN 2008

T2 - 8th Latin American TheoreticalINformatics Symposium, LATIN 2008

Y2 - 7 April 2008 through 11 April 2008

ER -

ID: 78926861