K + 1 heads are better than K+

Andrew C. Yao; Ronald L. Rivest

doi:10.1109/SFCS.1976.4567888

K + 1 heads are better than K⁺

Andrew C. Yao
, Ronald L. Rivest

Faculty of Electronic and Information Engineering

Research output: Contribution to journal › Conference article › peer-review

3 Scopus citations

Abstract

There are languages which can be recognized by a deterministic (k + 1)-headed oneway finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, there is a language accepted by a 2-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton.

Original language	English
Article number	4567888
Pages (from-to)	67-70
Number of pages	4
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume	1976-October
DOIs	https://doi.org/10.1109/SFCS.1976.4567888
State	Published - 1976
Event	17th Annual Symposium on Foundations of Computer Science, SFCS 1976 - Houston, United States Duration: 25 Oct 1976 → 27 Oct 1976

Keywords

Multihead finite automata

Access to Document

10.1109/SFCS.1976.4567888

Cite this

@article{67c50a4112874a6283d70aaa4dc2ae6b,

title = "K + 1 heads are better than K+",

abstract = "There are languages which can be recognized by a deterministic (k + 1)-headed oneway finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, there is a language accepted by a 2-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton.",

keywords = "Multihead finite automata",

author = "Yao, \{Andrew C.\} and Rivest, \{Ronald L.\}",

note = "Publisher Copyright: {\textcopyright} 1976 Institute of Electrical and Electronics Engineers, Inc.; 17th Annual Symposium on Foundations of Computer Science, SFCS 1976 ; Conference date: 25-10-1976 Through 27-10-1976",

year = "1976",

doi = "10.1109/SFCS.1976.4567888",

language = "英语",

volume = "1976-October",

pages = "67--70",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

publisher = "IEEE Computer Society",

}

TY - JOUR

T1 - K + 1 heads are better than K+

AU - Yao, Andrew C.

AU - Rivest, Ronald L.

PY - 1976

Y1 - 1976

N2 - There are languages which can be recognized by a deterministic (k + 1)-headed oneway finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, there is a language accepted by a 2-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton.

AB - There are languages which can be recognized by a deterministic (k + 1)-headed oneway finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, there is a language accepted by a 2-headed nondeterministic finite automaton which is accepted by no k-headed deterministic finite automaton.

KW - Multihead finite automata

UR - https://www.scopus.com/pages/publications/84938008034

U2 - 10.1109/SFCS.1976.4567888

DO - 10.1109/SFCS.1976.4567888

M3 - 会议文章

AN - SCOPUS:84938008034

SN - 0272-5428

VL - 1976-October

SP - 67

EP - 70

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 4567888

T2 - 17th Annual Symposium on Foundations of Computer Science, SFCS 1976

Y2 - 25 October 1976 through 27 October 1976

ER -

K + 1 heads are better than K⁺

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this