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

电子与信息学部

Massachusetts Institute of Technology
Laboratory for Computer Science

科研成果: 期刊稿件 › 会议文章 › 同行评审

3 引用（Scopus）

摘要

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.

源语言	英语
期刊论文编号	4567888
页（从-至）	67-70
页数	4
期刊	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
卷	1976-October
DOI	https://doi.org/10.1109/SFCS.1976.4567888
出版状态	已出版 - 1976
活动	17th Annual Symposium on Foundations of Computer Science, SFCS 1976 - Houston, 美国期限: 25 10月 1976 → 27 10月 1976

访问文件

10.1109/SFCS.1976.4567888

其它文件与链接

链接到 Scopus 的出版物

引用此

@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+

摘要

访问文件

其它文件与链接

学术指纹

引用此

K + 1 heads are better than K⁺