Cellular automata between sofic tree shifts. (English) Zbl 1301.68185
Summary: We study the sofic tree shifts of \(A^{\Sigma^\ast}\), where \(\Sigma^\ast\) is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if \(X\subset A^{\Sigma^\ast}\) is a sofic tree shift, then the configurations in \(X\) whose orbit under the shift action is finite are dense in \(X\), and, as a consequence of this, we deduce that every injective cellular automata \(\tau:X\to X\) is surjective. Moreover, a characterization of sofic tree shifts in terms of general Rabin automata is given.
We present an algorithm for establishing whether two unrestricted Rabin automata accept the same sofic tree shift or not. This allows us to prove the decidability of the surjectivity problem for cellular automata between sofic tree shifts. We also prove the decidability of the injectivity problem for cellular automata defined on a tree shift of finite type.
We present an algorithm for establishing whether two unrestricted Rabin automata accept the same sofic tree shift or not. This allows us to prove the decidability of the surjectivity problem for cellular automata between sofic tree shifts. We also prove the decidability of the injectivity problem for cellular automata defined on a tree shift of finite type.
Keywords:
free monoid; regular rooted tree; tree shift; subshift; shift of finite type; sofic shift; unrestricted Rabin automaton; cellular automaton; surjectivity problem; injectivity problemReferences:
| [1] | Amoroso, S.; Patt, Y. N., Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures, J. Comput. System Sci., 6, 448-464 (1972) · Zbl 0263.94019 |
| [2] | Aubrun, N., Dynamique symbolique des systèmes 2D et des arbres infinis (2011), Université Paris-Est, PhD thesis |
| [3] | Aubrun, N.; Béal, M.-P., Sofic and almost of finite type tree-shifts, (CSR 2010. CSR 2010, Lecture Notes in Comput. Sci., vol. 6072 (2010), Springer: Springer Berlin), 12-24 · Zbl 1285.68078 |
| [4] | Aubrun, N.; Béal, M.-P., Sofic tree-shifts, Theory Comput. Syst. (2013), in press · Zbl 1293.68195 |
| [5] | Ax, J., The elementary theory of finite fields, Ann. Math., 88, 239-271 (1968) · Zbl 0195.05701 |
| [6] | Ceccherini-Silberstein, T.; Coornaert, M., Cellular Automata and Groups (2010), Springer Monographs in Mathematics: Springer Monographs in Mathematics Berlin · Zbl 1218.37004 |
| [7] | Ceccherini-Silberstein, T.; Coornaert, M., A Garden of Eden theorem for linear subshifts, Ergodic Theory Dyn. Syst., 32, 81-102 (2012) · Zbl 1254.37013 |
| [8] | Ceccherini-Silberstein, T.; Coornaert, M., On the density of periodic configurations in strongly irreducible subshifts, Nonlinearity, 25, 2119-2131 (2012) · Zbl 1269.37008 |
| [9] | Ceccherini-Silberstein, T.; Coornaert, M., The Myhill property for strongly irreducible subshifts over amenable groups, Monatsh. Math., 165, 155-172 (2012) · Zbl 1283.37022 |
| [11] | Ceccherini-Silberstein, T.; Coornaert, M.; Fiorenzi, F.; Šunić, Z., Cellular automata on regular rooted trees, (CIAA 2012. CIAA 2012, Lecture Notes in Comput. Sci., vol. 7381 (2012), Springer: Springer Berlin), 101-112 · Zbl 1297.68175 |
| [12] | Ceccherini-Silberstein, T.; Machì, A.; Scarabotti, F., Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble), 49, 673-685 (1999) · Zbl 0920.43001 |
| [13] | Comon, H.; Dauchet, M.; Gilleron, R.; Löding, C.; Jacquemard, F.; Lugiez, D.; Tison, S.; Tommasi, M., Tree automata techniques and applications, Available on: |
| [14] | de Bruijn, N., A combinatorial problem, Nederl. Akad. Wet., Proc., 49, 758-764 (1946) · Zbl 0060.02701 |
| [15] | Doner, J., Tree acceptors and some of their applications, J. Comput. Syst. Sci., 4, 406-451 (1970) · Zbl 0212.02901 |
| [16] | Fici, G.; Fiorenzi, F., Topological properties of cellular automata on trees, (Formenti, E., Proceedings 18th International Workshop on Cellular Automata and Discrete Complex Systems and 3rd International Symposium Journées Automates Cellulaires. Proceedings 18th International Workshop on Cellular Automata and Discrete Complex Systems and 3rd International Symposium Journées Automates Cellulaires, La Marana, Corsica, September 19-21, 2012. Proceedings 18th International Workshop on Cellular Automata and Discrete Complex Systems and 3rd International Symposium Journées Automates Cellulaires. Proceedings 18th International Workshop on Cellular Automata and Discrete Complex Systems and 3rd International Symposium Journées Automates Cellulaires, La Marana, Corsica, September 19-21, 2012, Electronic Proceedings in Theoretical Computer Science, vol. 90 (2012), Open Publishing Association), 255-266 · Zbl 1466.37012 |
| [17] | Fiorenzi, F., Cellular automata and finitely generated groups (2000), University of Rome “La Sapienza”, PhD thesis |
| [18] | Fiorenzi, F., Cellular automata and strongly irreducible shifts of finite type, Theoret. Comput. Sci., 299, 477-493 (2003) · Zbl 1042.68077 |
| [19] | Fiorenzi, F., Semi-strongly irreducible shifts, Adv. in Appl. Math., 32, 421-438 (2004) · Zbl 1058.37009 |
| [20] | Fiorenzi, F., Periodic configurations of subshifts on groups, Internat. J. Algebra Comput., 19, 315-335 (2009) · Zbl 1205.37026 |
| [21] | Good, I., Normal recurring decimals, J. Lond. Math. Soc., 21, 167-169 (1946) · Zbl 0060.02702 |
| [22] | Gottschalk, W., Some general dynamical notions, (Recent Advances in Topol. Dynamics, Proc. Conf. Topol. Dynamics. Recent Advances in Topol. Dynamics, Proc. Conf. Topol. Dynamics, Yale University, 1972. Recent Advances in Topol. Dynamics, Proc. Conf. Topol. Dynamics. Recent Advances in Topol. Dynamics, Proc. Conf. Topol. Dynamics, Yale University, 1972, Lect. Notes Math., vol. 318 (1973), Springer), 120-125 · Zbl 0255.54035 |
| [23] | Gromov, M., Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS), 1, 109-197 (1999) · Zbl 0998.14001 |
| [24] | Kari, J., Reversibility of 2D cellular automata is undecidable, Physica D, 45, 1-3, 379-385 (1990) · Zbl 0729.68058 |
| [25] | Kari, J., The nilpotency problem of one-dimensional cellular automata, SIAM J. Comput., 21, 571-586 (1992) · Zbl 0761.68067 |
| [26] | Kari, J., Reversibility and surjectivity problems of cellular automata, J. Comput. System Sci., 48, 149-182 (1994) · Zbl 0802.68090 |
| [27] | Lind, D. A.; Marcus, B. H., An Introduction to Symbolic Dynamics and Coding (1995), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1106.37301 |
| [28] | Margenstern, M., The injectivity of the global function of a cellular automaton in the hyperbolic plane is undecidable, Fund. Inform., 94, 63-99 (2009) · Zbl 1191.68421 |
| [29] | Muller, D. E.; Schupp, P. E., Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems, Bull. Amer. Math. Soc. (N. S.), 4, 331-334 (1981) · Zbl 0484.03019 |
| [30] | Muller, D. E.; Schupp, P. E., The theory of ends, pushdown automata, and second-order logic, Theoret. Comput. Sci., 37, 51-75 (1985) · Zbl 0605.03005 |
| [31] | Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Trans. Am. Math. Soc., 141, 1-35 (1969) · Zbl 0221.02031 |
| [32] | Richardson, D., Tesselations with local transformations, J. Comput. Syst. Sci., 6, 373-388 (1972) · Zbl 0246.94037 |
| [33] | Thatcher, J. W.; Wright, J. B., Generalized finite automata theory with an application to a decision problem of second-order logic, Math. Syst. Theory, 2, 57-81 (1968) · Zbl 0157.02201 |
| [34] | Weiss, B., Sofic groups and dynamical systems, Sankhyā, Ser. A, 62, 350-359 (2000) · Zbl 1148.37302 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
