article

Free access

k + 1 Heads Are Better than k

Authors:

Andrew C. Yao,

Ronald L. RivestAuthors Info & Claims

Journal of the ACM (JACM), Volume 25, Issue 2

Pages 337 - 340

https://doi.org/10.1145/322063.322076

Published: 01 April 1978 Publication History

PDF eReader

References

[1]

FLOYD, R W Review 14,352 (of paper by Rosenberg {5}) Comptng Rev. 9, 5 (May 1968), 280

Google Scholar

[2]

IB~,~, O H., A~qD KIM, C E On 3-head versus 2-head fimte automata. Acta Informatzca 4 (1975), 193-200

Google Scholar

[3]

NELSON, C G One-way automata on bounded languages Tech. Rep TR14-76, Harvard Ctr for Res and Comptng, July 1976.

Google Scholar

[4]

PIATKOWSKI, T F N-head finite state machines Ph D Th., U of M~ch~gan, Ann Arbor, Mlch, 1963

Google Scholar

[5]

ROSENBER(;, A L On multi-head fimte automata IBM J Res. and Develop 10 (1966), 388-394

Google Scholar

[6]

ROSErqBERG, A L Nonwrmng extensions of fimte automata Ph D Th, Rep No. BL-39, Comput Lab, Harvard U., Cambridge, Mass, 1965

Google Scholar

[7]

SODaOROUGH, I H One-way multlhead writing fimte automata Inform. and Control 30 (1976), 1-20

Google Scholar

[8]

SODBO~OUGH, I H Computation by multi-head writing finite automata Ph.D Th, Pennsylvania State U, Umvers~ty Park, Pa, 1971

Crossref

Google Scholar

Cited By

View all

Kutrib MWendlandt M(2024)Variants of string assembling systemsNatural Computing: an international journal10.1007/s11047-022-09918-x23:1(131-156)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11047-022-09918-x
Gezer MDolu ÖErsoy NSay A(2023)Real-time, constant-space, constant-randomness verifiersTheoretical Computer Science10.1016/j.tcs.2023.114155976(114155)Online publication date: Oct-2023
https://doi.org/10.1016/j.tcs.2023.114155
Dolu ÖErsoy NGezer MSay A(2022)Real-Time, Constant-Space, Constant-Randomness VerifiersImplementation and Application of Automata10.1007/978-3-031-07469-1_17(212-224)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-07469-1_17
Show More Cited By

Index Terms

k + 1 Heads Are Better than k
1. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages

Recommendations

Listening heads
ZiF'06: Proceedings of the Embodied communication in humans and machines, 2nd ZiF research group international conference on Modeling communication with robots and virtual humans

In [1] we discussed functions of head movements and gaze. In this paper, we will go into more depth in the classification of various head movements: how they are distinguished in both formal and functional terms. We look at the distribution of a ...
Animated faces for robotic heads: gaze and beyond
COST'10: Proceedings of the 2010 international conference on Analysis of Verbal and Nonverbal Communication and Enactment

We introduce an approach to using animated faces for robotics where a static physical object is used as a projection surface for an animation. The talking head is projected onto a 3D physical head model.

In this chapter we discuss the different benefits ...
Better Than You Think: Head Gestures for Mid Air Input
Human-Computer Interaction – INTERACT 2015
Abstract
This paper presents a systematical comparison of pointing gestures in the context of controlling home appliances in smart homes. The pointing gestures were conducted with head, hand, arm and a computer mouse serving as baseline. To the best of our ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 25, Issue 2

April 1978

164 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322063

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1978

Published in JACM Volume 25, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

94
Total Citations
View Citations
693
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)3

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kutrib MWendlandt M(2024)Variants of string assembling systemsNatural Computing: an international journal10.1007/s11047-022-09918-x23:1(131-156)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11047-022-09918-x
Gezer MDolu ÖErsoy NSay A(2023)Real-time, constant-space, constant-randomness verifiersTheoretical Computer Science10.1016/j.tcs.2023.114155976(114155)Online publication date: Oct-2023
https://doi.org/10.1016/j.tcs.2023.114155
Dolu ÖErsoy NGezer MSay A(2022)Real-Time, Constant-Space, Constant-Randomness VerifiersImplementation and Application of Automata10.1007/978-3-031-07469-1_17(212-224)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-07469-1_17
Burjons EFrei FRaszyk MGorla D(2021)From finite-valued nondeterministic transducers to deterministic two-tape automataProceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science10.1109/LICS52264.2021.9470688(1-13)Online publication date: 29-Jun-2021
https://dl.acm.org/doi/10.1109/LICS52264.2021.9470688
Ganguly DChatterjee KRay K(2021)Watson–Crick quantum finite automataActa Informatica10.1007/s00236-020-00370-x58:3(231-240)Online publication date: 1-Jun-2021
https://dl.acm.org/doi/10.1007/s00236-020-00370-x
Ganguly DChatterjee KRay K(2021)Multi-head Watson–Crick Quantum Finite AutomataEmerging Technologies in Data Mining and Information Security10.1007/978-981-15-9927-9_60(615-620)Online publication date: 29-Jun-2021
https://doi.org/10.1007/978-981-15-9927-9_60
Ďuriš PKrálovič RPardubská D(2020)Tight hierarchy of data-independent multi-head automataJournal of Computer and System Sciences10.1016/j.jcss.2020.06.005114(126-136)Online publication date: Dec-2020
https://doi.org/10.1016/j.jcss.2020.06.005
Ibarra OMcQuillan I(2019)On Store Languages and ApplicationsInformation and Computation10.1016/j.ic.2019.03.003Online publication date: Mar-2019
https://doi.org/10.1016/j.ic.2019.03.003
Kutrib MWendlandt M(2019)Multi-stranded String Assembling SystemsSOFSEM 2019: Theory and Practice of Computer Science10.1007/978-3-030-10801-4_23(285-297)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1007/978-3-030-10801-4_23
Kutrib MMalcher A(2017)One-way reversible multi-head finite automataTheoretical Computer Science10.1016/j.tcs.2016.11.006682(149-164)Online publication date: Jun-2017
https://doi.org/10.1016/j.tcs.2016.11.006
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Listening heads

Animated faces for robotic heads: gaze and beyond

Better Than You Think: Head Gestures for Mid Air Input

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations