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

De Mol, Liesbeth

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1016/j.tcs.2010.08.026

Titre :

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

Auteur(s) :

De Mol, Liesbeth [Auteur]

Savoirs, Textes, Langage (STL) - UMR 8163 [STL]

Titre de la revue :

Theoretical Computer Science

Pagination :

97-112

Éditeur :

Elsevier

Date de publication :

2011

ISSN :

0304-3975

Discipline(s) HAL :

Informatique [cs]/Théorie et langage formel [cs.FL]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

Savoirs, Textes, Langage (STL) - UMR 8163

Source :

Harvested from HAL

Fichiers

https://hal.univ-lille.fr/hal-01396517/document
Accès libre
Accéder au document

https://doi.org/10.1016/j.tcs.2010.08.026
Accès libre
Accéder au document

https://doi.org/10.1016/j.tcs.2010.08.026
Accès libre
Accéder au document

https://hal.univ-lille.fr/hal-01396517/document
Accès libre
Accéder au document

https://doi.org/10.1016/j.tcs.2010.08.026
Accès libre
Accéder au document

https://doi.org/10.1016/j.tcs.2010.08.026
Accès libre
Accéder au document

document
Accès libre
Accéder au document

TCS_CSP_minor_revision.pdf
Accès libre
Accéder au document

j.tcs.2010.08.026
Accès libre
Accéder au document

On the complex behavior of simple tag ... BibTeX CSV Excel RIS

Fichiers

On the complex behavior of simple tag ...

BibTeX

CSV

Excel

RIS