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

Some Observations on 1-Inkdot Alternating Multi-Counter Automata with Sublinear Space Quelques observations sur des automates multi-compteurs alternés à 1 point d'encre avec espace sublinéaire

Tsunehiro YOSHINAGA, Jianliang XU, Katsushi INOUE

  • Vues en texte intégral

    0

  • Citer

Résumé:

Cet article étudie certaines propriétés fondamentales des automates multi-compteurs alternés à 2 voies (2amca) avec uniquement des états existentiels (universels) qui ont un espace sublinéaire et 1 point d'encre. On montre que pour toute fonction s(n) enregistrer n tel que le journal s(n)=o(Journal n), s(n) Les 1amca à 2 point d'encre limités dans l'espace avec uniquement des états existentiels sont incomparables avec ceux avec uniquement des états universels, et ceux avec uniquement des états existentiels (universels) ne sont pas fermés par complémentation.

Publication
IEICE TRANSACTIONS on Information Vol.E83-D No.2 pp.285-290
Date de publication
2000/02/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
LETTER
Catégories
Théorie des automates, théorie du langage formel

Auteurs

Mots-clés

Table des matières