One-way simple multihead finite automata

DOI 被引用文献9件 オープンアクセス

この論文をさがす

説明

AbstractThe first half of this paper investigates the accepting powers of various types of simple one-way multihead finite automata. It is shown that(1)for each k⩾1, simple one-way (k+1)-head finite automata are more powerful than simple one-way k-head finite automata.(2)for each k⩾2, nondeterministic simple one-way k-head finite automata are more powerful than deterministic ones, and(3)for each k⩾2, sensing simple one-way k-head finite automata are more powerful than non-sensing ones.In the latter half, closure properties for various types of simple one-way multihead finite automata are investigated.Finally, we demonstrate that languages accepted by nondeterministic sensing simple one-way 2-head finite automata are related to some open problem concerning deterministic and nondeterministic tape-bounded Turing computations.

収録刊行物

被引用文献 (9)*注記

もっと見る

キーワード

詳細情報 詳細情報について

  • CRID
    1570291226247538176
  • NII論文ID
    30006150702
  • DOI
    10.1016/0304-3975(79)90033-1
  • ISSN
    03043975
  • データソース種別
    • CiNii Articles
    • OpenAIRE

問題の指摘

ページトップへ