Accéder directement au contenu Accéder directement à la navigation
Article dans une revue

On the complex behavior of simple tag systems: An experimental approach

Abstract : It is a well-known fact that apparently simple systems can give rise to complex behavior. But why exactly does a given system behave in a complex manner? There are two main approaches to tackle this and other related questions. One can take on a theoretical approach or else start from a more experimental study of the behavior of such systems with the help of a computer. In this paper, the experimental approach is applied to tag systems with a very small program size. After a discussion of some of the main theoretical results on tag systems, several results from a computer-assisted and experimental study on tag systems are analyzed. Special attention is given to the well-known example studied by Post with only 2 symbols and a deletion number v = 3. These results are combined with some theoretical results on tag systems in order to gain more insight into the computational power of simple tag systems.
Type de document :
Article dans une revue
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.univ-lille.fr/hal-01396517
Contributeur : Liesbeth de Mol <>
Soumis le : lundi 14 novembre 2016 - 15:24:45
Dernière modification le : mercredi 1 juillet 2020 - 03:10:45
Document(s) archivé(s) le : lundi 20 mars 2017 - 21:39:19

Fichier

TCS_CSP_minor_revision.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Liesbeth de Mol. On the complex behavior of simple tag systems: An experimental approach. Theoretical Computer Science, Elsevier, 2011, 412 (1-2), pp.97-112. ⟨10.1016/j.tcs.2010.08.026⟩. ⟨hal-01396517⟩

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

524