Sofic and almost of finite type tree-shifts

Nathalie Aubrun; Marie Pierre Béal

doi:10.1007/978-3-642-13182-0_2

Sofic and almost of finite type tree-shifts

Nathalie Aubrun
, Marie Pierre Béal

Université Paris-Est

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique minimal deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Shannon cover of the tree-shift. We define the notion of almost finite type tree-shift which is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Shannon cover of an almost finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type.

Original language	English
Title of host publication	Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings
Pages	12-24
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-642-13182-0_2
Publication status	Published - 20 Jul 2010
Externally published	Yes
Event	5th International Computer Science Symposium in Russia, CSR 2010 - Kazan, Russian Federation Duration: 16 Jun 2010 → 20 Jun 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6072 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Computer Science Symposium in Russia, CSR 2010
Country/Territory	Russian Federation
City	Kazan
Period	16/06/10 → 20/06/10

Access to Document

10.1007/978-3-642-13182-0_2

Cite this

Aubrun, N., & Béal, M. P. (2010). Sofic and almost of finite type tree-shifts. In Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings (pp. 12-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6072 LNCS). https://doi.org/10.1007/978-3-642-13182-0_2

@inproceedings{1766a8596e334a8aa7e12aead0b764b6,

title = "Sofic and almost of finite type tree-shifts",

abstract = "We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique minimal deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Shannon cover of the tree-shift. We define the notion of almost finite type tree-shift which is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Shannon cover of an almost finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type.",

author = "Nathalie Aubrun and B{\'e}al, \{Marie Pierre\}",

year = "2010",

month = jul,

day = "20",

doi = "10.1007/978-3-642-13182-0\_2",

language = "English",

isbn = "3642131816",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "12--24",

booktitle = "Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings",

note = "5th International Computer Science Symposium in Russia, CSR 2010 ; Conference date: 16-06-2010 Through 20-06-2010",

}

Aubrun, N & Béal, MP 2010, Sofic and almost of finite type tree-shifts. in Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6072 LNCS, pp. 12-24, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russian Federation, 16/06/10. https://doi.org/10.1007/978-3-642-13182-0_2

Sofic and almost of finite type tree-shifts. / Aubrun, Nathalie; Béal, Marie Pierre.
Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. p. 12-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6072 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Sofic and almost of finite type tree-shifts

AU - Aubrun, Nathalie

AU - Béal, Marie Pierre

PY - 2010/7/20

Y1 - 2010/7/20

N2 - We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique minimal deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Shannon cover of the tree-shift. We define the notion of almost finite type tree-shift which is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Shannon cover of an almost finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type.

AB - We introduce the notion of sofic tree-shifts which corresponds to symbolic dynamical systems of infinite trees accepted by finite tree automata. We show that, contrary to shifts of infinite sequences, there is no unique minimal deterministic irreducible tree automaton accepting an irreducible sofic tree-shift, but that there is a unique synchronized one, called the Shannon cover of the tree-shift. We define the notion of almost finite type tree-shift which is a meaningful intermediate dynamical class in between irreducible finite type tree-shifts and irreducible sofic tree-shifts. We characterize the Shannon cover of an almost finite type tree-shift and we design an algorithm to check whether a sofic tree-shift is almost of finite type.

U2 - 10.1007/978-3-642-13182-0_2

DO - 10.1007/978-3-642-13182-0_2

M3 - Conference contribution

AN - SCOPUS:77954573746

SN - 3642131816

SN - 9783642131813

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 12

EP - 24

BT - Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings

T2 - 5th International Computer Science Symposium in Russia, CSR 2010

Y2 - 16 June 2010 through 20 June 2010

ER -

Aubrun N, Béal MP. Sofic and almost of finite type tree-shifts. In Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. p. 12-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-13182-0_2

Sofic and almost of finite type tree-shifts

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this