Affordable Access

Loops in automata and HDTOL relations

Authors
Publication Date
Disciplines
  • Mathematics

Abstract

Loops in automata and HDTOL relations INFORMATIQUE THÉORIQUE ET APPLICATIONS KARELCULIK II JUHANIKARHUMÄKI Loops in automata andHDTOL relations Informatique théorique et applications, tome 24, no 4 (1990), p. 327- 337. <http://www.numdam.org/item?id=ITA_1990__24_4_327_0> © AFCET, 1990, tous droits réservés. L’accès aux archives de la revue « Informatique théorique et applications » im- plique l’accord avec les conditions générales d’utilisation (http://www.numdam. org/legal.php). Toute utilisation commerciale ou impression systématique est constitutive d’une infraction pénale. Toute copie ou impression de ce fichier doit contenir la présente mention de copyright. Article numérisé dans le cadre du programme Numérisation de documents anciens mathématiques http://www.numdam.org/ Informatique théorique et Applications/Theoretical Informaties and Applications (vol. 24, n° 4, 1990, p. 327 à 337) LOOPS IN AUTOMATA AND HDTOL RELATIONS (*) by Karel CULIK II (x) and Juhani KARHUMÂKI (2) Communicated by J. E. PIN Abstract. — We show that n-tape automata containing only simple loops, i. e. no state is involved in two loops, have several properties which gênerai n-tape automata, or even automata wiîh parallel loops only, do not have. In particular, the intersection of relations dejïned by two simple n-tape automata is so called HDTOL relation. This implies several old and new decidability resuit s for simple n-tape automata. Résumé. — Nous montrons que les automates à n bandes contenant seulement des boucles simples, c'est-à-dire pour lesquels aucun état n'appartient à deux boucles, possèdent différentes propriétés que les automates généraux à n bandes ou même les automates possédant seulement des boucles parallèles ne partagent pas. En particulier l'intersection de relations définies par deux automates à n bandes ayant seulement des boucles simples est ce que l'on appelle une relation HDTOL. Ceci implique plusieurs résultats de décidabilité anciens et nouveaux concernant les

There are no comments yet on this publication. Be the first to share your thoughts.