La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata Automates finis multi-têtes non déterministes et auto-vérifiés de Las Vegas

Katsushi INOUE, Yasunori TANAKA, Akira ITO, Yue WANG

  • Vues en texte intégral

    0

  • Citer

Résumé:

Cet article concerne une étude comparative des pouvoirs d'acceptation des automates finis multi-têtes déterministes, de Las Vegas, auto-vérifiants non déterministes et non déterministes (simples). Nous montrons que (1) pour chaque k 2, déterministe à sens unique k-tête (resp., simple k-head) les automates finis sont moins puissants que Las Vegas à sens unique k-tête (resp., simple k-head) automates finis, (2) il existe un langage accepté par un automate fini simple à 2 têtes non déterministe à vérification automatique unidirectionnelle, mais non accepté par aucun automate fini multi-têtes simple déterministe unidirectionnel, (3) il existe un langage accepté par un automate fini unidirectionnel non déterministe à 2 têtes (resp., simple 2 têtes), mais non accepté par un automate fini unidirectionnel non déterministe à vérification automatique (resp., simple multitête), (4) pour chaque k 1, aller-retour Las Vegas k-tête (resp., simple k-head) les automates finis ont les mêmes pouvoirs d'acceptation que les auto-vérifications non déterministes bidirectionnelles k-tête (resp., simple k-head) les automates finis, et (5) les automates finis simples à 2 têtes bidirectionnels de Las Vegas sont plus puissants que les automates finis simples déterministes bidirectionnels à 2 têtes.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1094-1101
Date de publication
2001/05/01
Publicisé
ISSN en ligne
DOI
Type de manuscrit
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Catégories

Auteurs

Mots-clés

Table des matières