K+1 Heads are Better Than K
There are languages which can be recognized by a deterministic (k+1)-headed one-way 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 w...
Main Authors: | Yao, Andrew C., Rivest, Ronald L. |
---|---|
Published: |
2023
|
Online Access: | https://hdl.handle.net/1721.1/148903 |
Similar Items
-
Merdeka Curriculum Better than K13 Curriculum?
by: Zahirotul Kamiliyah, et al.
Published: (2023-09-01) -
From the Editors: Two heads are better than one?
by: Tim Stokes, et al.
Published: (2022-01-01) -
An examination of ambiguity aversion: Are two heads better than one?
by: L. Robin Keller, et al.
Published: (2007-12-01) -
k-Cut: A Simple Approximately-Uniform Method for Sampling Ballots in Post-election Audits
by: Sridhar, Mayuri, et al.
Published: (2022) -
Are Two Heads Better Than One for Computer-Aided Design?
by: Phadnis, Vrushank Shripad, et al.
Published: (2021)