title | Nondeterminism and the size of two-way finite automata |
---|---|

authors | William J. Sakoda, Michael F. Sipser |

meeting | Symposium on Theory of Computing |

year | 1978 |

pages | 275-286 |

topics | complexity, asymptotics, and exact trade-offs; general alphabet; one-way, rotating, and two-way heads; deterministic and nondeterministic modes |

features |
1D is closed under $\leq_\text{h}$ 1N is closed under $\leq_\text{h}$ 2D is closed under $\leq_\text{h}$ 2N is closed under $\leq_\text{h}$ co-1D $\subseteq$ 1D co-1N $\nsupseteq$ 1N compact one-way liveness $\notin$ co-1N one-way liveness $\in$ 2 ^{1D}one-way liveness $\in$ 1N one-way liveness $\notin$ 1D one-way liveness $\notin$ co-1N one-way liveness is hard for 1N under $\leq^\text{t}_\text{h}$ separability is hard for 1N under $\leq^\text{t}_\text{h}$ two-way liveness $\in$ 2 ^{1D}two-way liveness $\in$ 2N two-way liveness is hard for 2N under $\leq^\text{t}_\text{h}$ |

doi | 10.1145/800133.804357 |