Lambert, J. L. The local catenativity of D0L-sequences in free commutative monoids is decidable in the binary case. (English) Zbl 0768.68078 RAIRO, Inform. Théor. Appl. 26, No. 5, 425-438 (1992). Summary: Given a matrix \(A\in\mathbb{Z}^{2\times 2}\) and a vector \(V_ 0\in\mathbb{Z}^ 2\) we determine if there exists an integer \(m\) and \(m\) positive integers \(a_{m-1}\dots a_ 0\) such that \(A^ m V_ 0=\sum_{i=0}^{m-1} a_ i A^ i V_ 0\). When such an \(m\) exists, we compute the smallest one and \(m\) positive integers \(a_{m-1}\dots a_ 0\) that satisfy the relation. MSC: 68Q45 Formal languages and automata 20M35 Semigroups in automata theory, linguistics, etc. 15B36 Matrices of integers 20M05 Free semigroups, generators and relations, word problems 20M14 Commutative semigroups Keywords:free monoid; decidability × Cite Format Result Cite Review PDF Full Text: DOI EuDML References: [1] 1 C. CHOFFRUT, Iterated substitutions and locally catenative Systems: a decidability result in the binary case, private communication. · Zbl 0765.68069 [2] 2 S. LANG, Algebra, Addison Wesley 1965. Zbl0193.34701 MR197234 · Zbl 0193.34701 [3] 3 A. LINDENMAYER, G. ROZENBERG, Developmental Systems with locally catenative formulas, Acta Informatica, 2, 1973, pp. 214-248. Zbl0304.68076 MR331883 · Zbl 0304.68076 · doi:10.1007/BF00289079 [4] 4 WEBER, SEIDL, On finite generated monoids of matrices with entries in N, RAIRO, Inf Theor. Appl., 25, 1991, pp. 19-38. Zbl0721.20042 MR1104408 · Zbl 0721.20042 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.