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

De Mol, Liesbeth

Document type :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1016/j.tcs.2010.08.026

Title :

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

Author(s) :

De Mol, Liesbeth [Auteur]

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

Journal title :

Theoretical Computer Science

Pages :

97-112

Publisher :

Elsevier

Publication date :

2011

ISSN :

0304-3975

HAL domain(s) :

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

English abstract : [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 ...
Show more >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.Show less >

Language :

Anglais

Popular science :

Non

Collections :

Savoirs, Textes, Langage (STL) - UMR 8163

Source :

Harvested from HAL

Files

https://hal.univ-lille.fr/hal-01396517/document
Open access
Access the document

https://doi.org/10.1016/j.tcs.2010.08.026
Open access
Access the document

https://doi.org/10.1016/j.tcs.2010.08.026
Open access
Access the document

https://hal.univ-lille.fr/hal-01396517/document
Open access
Access the document

https://doi.org/10.1016/j.tcs.2010.08.026
Open access
Access the document

https://doi.org/10.1016/j.tcs.2010.08.026
Open access
Access the document

document
Open access
Access the document

TCS_CSP_minor_revision.pdf
Open access
Access the document

j.tcs.2010.08.026
Open access
Access the document

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

Files

On the complex behavior of simple tag ...

BibTeX

CSV

Excel

RIS