Column Representation of Sturmian Words in Cellular Automata

被引：1

作者：

Dolce, Francesco ^{[1
]}

Tahay, Pierre-Adrien ^{[2
]}

机构：

[1] Czech Tech Univ, FIT, Prague, Czech Republic

[2] Czech Tech Univ, FNSPE, Prague, Czech Republic

来源：

DEVELOPMENTS IN LANGUAGE THEORY (DLT 2022) | 2022年 / 13257卷

关键词：

Sturmian words; Cellular automata; Quadratic numbers; Continued fraction expansion;

D O I：

10.1007/978-3-031-05578-2_10

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We prove that, given a Sturmian word w with quadratic slope, it is possible to construct a one-dimensional cellular automaton such that w is represented in a chosen column in its space-time diagram. Our proof is constructive and use the continued fraction expansion of the slope of the word.

引用

页码：127 / 138

页数：12

共 20 条

[1] STURMIAN JUNGLE (OR GARDEN?) ON MULTILITERAL ALPHABETS [J].

Balkova, L'ubomira ;

Pelantova, Edita ;

Starosta, Stepan .

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2010, 44 (04) :443-470

[2] Rigidity and Substitutive Dendric Words [J].

Berthe, V ;

Dolce, F. ;

Durand, F. ;

Leroy, J. ;

Perrin, D. .

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2018, 29 (05) :705-720

[3] Acyclic, connected and tree sets [J].

Berthe, Valerie ;

De Felice, Clelia ;

Dolce, Francesco ;

Leroy, Julien ;

Perrin, Dominique ;

Reutenauer, Christophe ;

Rindone, Giuseppina .

MONATSHEFTE FUR MATHEMATIK, 2015, 176 (04) :521-550

[4] Language complexity of rotations and Sturmian sequences [J].

Blanchard, F ;

Kurka, P .

THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :179-193

[5]

Coven EM, 1973, Math Syst Theory, V7, P138

[6]

Dolce Francesco, 2021, Language and Automata Theory and Applications. 15th International Conference, LATA 2021. Proceedings. Lecture Notes in Computer Science (LNCS 12638), P293, DOI 10.1007/978-3-030-68195-1_23

[7] Eventually dendric shift spaces [J].

DOLCE, F. R. A. N. C. E. S. C. O. ;

PERRIN, D. O. M. I. N. I. Q. U. E. .

ERGODIC THEORY AND DYNAMICAL SYSTEMS, 2021, 41 (07) :2023-2048

[8] GENERATION OF PRIMES BY A 1-DIMENSIONAL REAL-TIME ITERATIVE ARRAY [J].

FISCHER, PC .

JOURNAL OF THE ACM, 1965, 12 (03) :388-&

[9]

Hedlund G. A., 1969, MATH SYST THEORY, V3, P320, DOI DOI 10.1007/BF01691062

[10]

Hubert P, 2000, THEOR COMPUT SCI, V242, P91, DOI 10.1016/S0304-3975(98)00202-3

← 1 2 →