Deux propriétés décidables des suites récurrentes linéaires
Bulletin de la Société Mathématique de France, Tome 104 (1976), pp. 175-184. 
@article{BSMF_1976__104__175_0,
     author = {Berstel, Jean and Mignotte, Maurice},
     title = {Deux propri\'et\'es d\'ecidables des suites r\'ecurrentes lin\'eaires},
     journal = {Bulletin de la Soci\'et\'e Math\'ematique de France},
     pages = {175--184},
     publisher = {Soci\'et\'e math\'ematique de France},
     volume = {104},
     year = {1976},
     doi = {10.24033/bsmf.1823},
     mrnumber = {54 #2576},
     zbl = {0329.10009},
     language = {fr},
     url = {https://numdam.org/articles/10.24033/bsmf.1823/}
}
TY  - JOUR
AU  - Berstel, Jean
AU  - Mignotte, Maurice
TI  - Deux propriétés décidables des suites récurrentes linéaires
JO  - Bulletin de la Société Mathématique de France
PY  - 1976
SP  - 175
EP  - 184
VL  - 104
PB  - Société mathématique de France
UR  - https://numdam.org/articles/10.24033/bsmf.1823/
DO  - 10.24033/bsmf.1823
LA  - fr
ID  - BSMF_1976__104__175_0
ER  - 
%0 Journal Article
%A Berstel, Jean
%A Mignotte, Maurice
%T Deux propriétés décidables des suites récurrentes linéaires
%J Bulletin de la Société Mathématique de France
%D 1976
%P 175-184
%V 104
%I Société mathématique de France
%U https://numdam.org/articles/10.24033/bsmf.1823/
%R 10.24033/bsmf.1823
%G fr
%F BSMF_1976__104__175_0
Berstel, Jean; Mignotte, Maurice. Deux propriétés décidables des suites récurrentes linéaires. Bulletin de la Société Mathématique de France, Tome 104 (1976), pp. 175-184. doi : 10.24033/bsmf.1823. https://numdam.org/articles/10.24033/bsmf.1823/

[1] Benzaghou (B.). - Algèbres de Hadamard, Bull. Soc. math. France, t. 98, 1970, p. 209-252. | Numdam | MR | Zbl

[2] Berstel (J.). - Factorisation de fractions rationnelles et de suites récurrentes, Acta Arithmetica, t. 30, 1976, p. 5-17. | MR | Zbl

[3] Eilenberg (S.). - Automata, languages and machines. Vol. A : Foundations. - New York, Academic Press, 1973 (Pure and applied Mathematics Series, 59). | MR | Zbl

[4] Lech (C.). - A note on recurring series, Arkiv der Math., t. 2, 1953, p. 417-421. | MR | Zbl

[5] Lewis (D. J.). - Diophantine equations, p-adic methods, “Studies in Number Theory”, [W. J. LE VEQUE, ed.], p. 25-75. - New York, Prentice Hall, 1969 (MAA Studies in Mathematics, 6). | MR | Zbl

[6] Mahler. (K.). - Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen, Koninkl. Akad. Wetensch. Amsterdam, Proc., t. 38, 1935, p. 50-60. | JFM | Zbl

[7] Mignotte (M.). - A note on linear recursive series, J. Austr. math. Soc (à paraître). | Zbl

[8] Mignotte (M.). - Suites récurrentes linéaires, Séminaire Delange-Pisot-Poitou: Groupe d'études de théorie des nombres, 15e année, 1973/1974, n° G 14, 9 p. | Numdam | Zbl

[9] Mignotte (M.). - Algorithmes relatifs à la décomposition des polynômes, “Theoretical Computer Science” (à paraître). | Zbl

[10] Picon (P. A.). - Sur les termes nuls d'une suite récurrente cubique, R.A.I.R.O., 8e année, R-3, 1974, p. 47-61. | Numdam | MR | Zbl

[11] Pisot (C.). - Quelques aspects de la théorie des entiers algébriques. - Montréal, les Presses Universitaires de Montréal, 1963 (Séminaire de Mathématiques supérieures. été 1963, 5). | MR | Zbl

[12] Pólya (G.). - Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen, J. reine und ang. Math., t. 151, 1921, p. 1-31. | JFM

[13] Pólya (G.) et Szegö (G.). - Aufgaben und Lehrsätze aus der Analysis, 3te Auflage. -. Berlin, Springer-Verlag, 1964 (Heidelberger Taschenbücher, 73, 74).

[14] Rosser (J. B.) and Schoenfeld (L.). - Approximate formulas for some functions of prime numbers, Illinois J. Math., t. 6, 1962, p. 64-94. | MR | Zbl

[15] Siegel (C. L.). - Über die Koeffizienten in der Taylorentwicklung rationaler Funktionen, Tôhoku math. J., t. 20, 1921, p. 26-31. | JFM

[16] Shapiro. (H. N.) - On a theorem concerning exponential polynomials, Comm. pure and appl. Math., t. 12, 1959, p. 487-500. | MR | Zbl

[17] Skolem (T.). - Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen, "Comptes Rendus du 8e Congrès des Mathématiciens scandinaves, Stockholm 1934", p. 163-188. - Lund, Håkan Ohlssons, 1935. | JFM | Zbl

[18] Smiley (M. F.). - On the zeros of a cubic recurrence, Amer. math. Monthly, t. 63, 1956, p. 171-172. | MR | Zbl

[19] Ward (M.). - Note on an arithmetical property of recurring series, Math. Z., t. 39, 1934, p. 211-224. | JFM | Zbl

  • Arzhakova, Elizaveta; Lind, Douglas; Schmidt, Klaus; Verbitskiy, Evgeny Decimation limits of principal algebraic ℤd-actions, Israel Journal of Mathematics, Volume 265 (2025) no. 1, p. 255 | DOI:10.1007/s11856-024-2676-z
  • Berthé, Valérie; Karimov, Toghrul; Nieuwveld, Joris; Ouaknine, Joël; Vahanwala, Mihir; Worrell, James The monadic theory of toric words, Theoretical Computer Science, Volume 1025 (2025), p. 114959 | DOI:10.1016/j.tcs.2024.114959
  • Vahanwala, Mihir Skolem and positivity completeness of ergodic Markov chains, Information Processing Letters, Volume 186 (2024), p. 106481 | DOI:10.1016/j.ipl.2024.106481
  • García, Jonathan; Gómez, Carlos A.; Luca, Florian Solving Skolem's problem for the k–generalized Fibonacci sequence with negative indices, Journal of Number Theory, Volume 257 (2024), p. 273 | DOI:10.1016/j.jnt.2023.10.017
  • Scoones, Andrew On the abcabc conjecture in algebraic number fields, Mathematika, Volume 70 (2024) no. 1 | DOI:10.1112/mtk.12230
  • Bell, Jason P.; Smertnig, Daniel, 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (2023), p. 1 | DOI:10.1109/lics56636.2023.10175691
  • Jiménez-Pastor, Antonio; Nuspl, Philipp; Pillwein, Veronika An extension of holonomic sequences: C2-finite sequences, Journal of Symbolic Computation, Volume 116 (2023), p. 400 | DOI:10.1016/j.jsc.2022.10.008
  • Chonev, Ventsislav; Ouaknine, Joel; Worrell, James On the Zeros of Exponential Polynomials, Journal of the ACM, Volume 70 (2023) no. 4, p. 1 | DOI:10.1145/3603543
  • Macintyre, Angus J. Between the Rings Z/pnZ and the Ring Zp: Issues of Axiomatizability, Definability and Decidability, Mathematics Going Forward, Volume 2313 (2023), p. 389 | DOI:10.1007/978-3-031-12244-6_27
  • Kauers, Manuel; Nuspl, Philipp; Pillwein, Veronika, Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation (2023), p. 389 | DOI:10.1145/3597066.3597070
  • Neumann, Eike On the Complexity of Robust Eventual Inequality Testing for C-Finite Functions, Reachability Problems, Volume 14235 (2023), p. 98 | DOI:10.1007/978-3-031-45286-4_8
  • Bravo, Eric F.; Bravo, Jhon J.; Luca, Florian On the Multiplicities of Padovan-Type Sequences, Bulletin of the Brazilian Mathematical Society, New Series, Volume 53 (2022) no. 4, p. 1519 | DOI:10.1007/s00574-022-00315-7
  • Ostafe, Alina; Shparlinski, Igor E. On the Skolem problem and some related questions for parametric families of linear recurrence sequences, Canadian Journal of Mathematics, Volume 74 (2022) no. 3, p. 773 | DOI:10.4153/s0008414x21000080
  • Luca, Florian; Ouaknine, Joël; Worrell, James Algebraic Model Checking for Discrete Linear Dynamical Systems, Formal Modeling and Analysis of Timed Systems, Volume 13465 (2022), p. 3 | DOI:10.1007/978-3-031-15839-1_1
  • Karimov, Toghrul; Kelmendi, Edon; Ouaknine, Joël; Worrell, James What’s Decidable About Discrete Linear Dynamical Systems?, Principles of Systems Design, Volume 13660 (2022), p. 21 | DOI:10.1007/978-3-031-22337-2_2
  • Melczer, Stephen Generating Functions and Analytic Combinatorics, Algorithmic and Symbolic Combinatorics (2021), p. 21 | DOI:10.1007/978-3-030-67080-1_2
  • Jiménez-Pastor, Antonio; Nuspl, Philipp; Pillwein, Veronika, Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation (2021), p. 217 | DOI:10.1145/3452143.3465529
  • Almagor, Shaull; Karimov, Toghrul; Kelmendi, Edon; Ouaknine, Joël; Worrell, James Deciding ω-regular properties on linear recurrence sequences, Proceedings of the ACM on Programming Languages, Volume 5 (2021) no. POPL, p. 1 | DOI:10.1145/3434329
  • García, Jonathan; Gómez, Carlos A.; Luca, Florian On the zero-multiplicity of the k-generalized Fibonacci sequence, Journal of Difference Equations and Applications, Volume 26 (2020) no. 11-12, p. 1564 | DOI:10.1080/10236198.2020.1857749
  • Kenison, George; Lipton, Richard; Ouaknine, Joël; Worrell, James, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation (2020), p. 289 | DOI:10.1145/3373207.3404036
  • Andrica, Dorin; Bagdasar, Ovidiu Higher Order Linear Recurrent Sequences, Recurrent Sequences (2020), p. 195 | DOI:10.1007/978-3-030-51502-7_6
  • Bilotta, S.; Pergola, E.; Pinzani, R.; Rinaldi, S. Recurrence relations, succession rules and the positivity problem, Journal of Computer and System Sciences, Volume 104 (2019), p. 102 | DOI:10.1016/j.jcss.2016.09.006
  • Sha, Min Effective results on the Skolem Problem for linear recurrence sequences, Journal of Number Theory, Volume 197 (2019), p. 228 | DOI:10.1016/j.jnt.2018.08.012
  • Dubickas, Artūras Roots of unity as quotients of two conjugate algebraic numbers, Glasnik Matematicki, Volume 52 (2017) no. 2, p. 235 | DOI:10.3336/gm.52.2.03
  • Chonev, Ventsislav; Ouaknine, Joël; Worrell, James On the Complexity of the Orbit Problem, Journal of the ACM, Volume 63 (2016) no. 3, p. 1 | DOI:10.1145/2857050
  • Chonev, Ventsislav; Ouaknine, Joël; Worrell, James, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (2016), p. 515 | DOI:10.1145/2933575.2934548
  • Biscaia, M.; Henriques, D.; Mateus, P. Decidability of Approximate Skolem Problem and Applications to Logical Verification of Dynamical Properties of Markov Chains, ACM Transactions on Computational Logic, Volume 16 (2015) no. 1, p. 1 | DOI:10.1145/2666772
  • Bilotta, Stefano; Pergola, Elisa; Pinzani, Renzo; Rinaldi, Simone Recurrence Relations, Succession Rules, and the Positivity Problem, Language and Automata Theory and Applications, Volume 8977 (2015), p. 499 | DOI:10.1007/978-3-319-15579-1_39
  • Ouaknine, Joël; Worrell, James On the Positivity Problem for Simple Linear Recurrence Sequences,, Automata, Languages, and Programming, Volume 8573 (2014), p. 318 | DOI:10.1007/978-3-662-43951-7_27
  • Ouaknine, Joël; Worrell, James Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences, Automata, Languages, and Programming, Volume 8573 (2014), p. 330 | DOI:10.1007/978-3-662-43951-7_28
  • Honkala, Juha The sequence equivalence problem for primitive D0L systems, Journal of Computer and System Sciences, Volume 79 (2013) no. 1, p. 101 | DOI:10.1016/j.jcss.2012.05.013
  • DUBICKAS, ARTŪRAS ROOTS OF UNITY AS QUOTIENTS OF TWO ROOTS OF A POLYNOMIAL, Journal of the Australian Mathematical Society, Volume 92 (2012) no. 2, p. 137 | DOI:10.1017/s1446788712000183
  • Ouaknine, Joël; Worrell, James Decision Problems for Linear Recurrence Sequences, Reachability Problems, Volume 7550 (2012), p. 21 | DOI:10.1007/978-3-642-33512-9_3
  • Cipu, Mihai; Diouf, Ismaïla; Mignotte, Maurice Testing degenerate polynomials, Applicable Algebra in Engineering, Communication and Computing, Volume 22 (2011) no. 4, p. 289 | DOI:10.1007/s00200-011-0150-8
  • Bell, Paul C.; Delvenne, Jean-Charles; Jungers, Raphaël M.; Blondel, Vincent D. The continuous Skolem-Pisot problem, Theoretical Computer Science, Volume 411 (2010) no. 40-42, p. 3625 | DOI:10.1016/j.tcs.2010.06.005
  • Laohakosol, Vichian; Tangsupphathawat, Pinthira Positivity of third order linear recurrence sequences, Discrete Applied Mathematics, Volume 157 (2009) no. 15, p. 3239 | DOI:10.1016/j.dam.2009.06.021
  • Hainry, Emmanuel Reachability in Linear Dynamical Systems, Logic and Theory of Algorithms, Volume 5028 (2008), p. 241 | DOI:10.1007/978-3-540-69407-6_28
  • Ruohonen, Keijo D0L sequence equivalence is inPfor fixed alphabets, RAIRO - Theoretical Informatics and Applications, Volume 42 (2008) no. 2, p. 361 | DOI:10.1051/ita:2007037
  • Hainry, Emmanuel Computing Omega-Limit Sets in Linear Dynamical Systems, Unconventional Computing, Volume 5204 (2008), p. 83 | DOI:10.1007/978-3-540-85194-3_9
  • Halava, Vesa; Harju, Tero; Hirvensalo, Mika Positivity of second order linear recurrent sequences, Discrete Applied Mathematics, Volume 154 (2006) no. 3, p. 447 | DOI:10.1016/j.dam.2005.10.009
  • Bostan, Alin; Flajolet, Philippe; Salvy, Bruno; Schost, Éric Fast computation of special resultants, Journal of Symbolic Computation, Volume 41 (2006) no. 1, p. 1 | DOI:10.1016/j.jsc.2005.07.001
  • Honkala, Juha An n2-bound for the ultimate equivalence problem of certain D0L systems over an n-letter alphabet, Journal of Computer and System Sciences, Volume 71 (2005) no. 4, p. 506 | DOI:10.1016/j.jcss.2005.05.003
  • Ruohonen, Keijo Explicit test sets for iterated morphisms in free monoids and metabelian groups, Theoretical Computer Science, Volume 330 (2005) no. 1, p. 171 | DOI:10.1016/j.tcs.2004.09.017
  • Harju, Tero Decision Questions on Integer Matrices, Developments in Language Theory, Volume 2295 (2002), p. 57 | DOI:10.1007/3-540-46011-x_5
  • Blondel, Vincent D.; Portier, Natacha Le problème de la réalisation minimale dans le demi-anneau max-plus et le problème de Pisot sont NP-durs, Comptes Rendus de l'Académie des Sciences - Series I - Mathematics, Volume 333 (2001) no. 12, p. 1127 | DOI:10.1016/s0764-4442(01)02192-9
  • HONKALA, JUHA RESULTS CONCERNING THINNESS OF D0L LANGUAGES, International Journal of Algebra and Computation, Volume 10 (2000) no. 02, p. 209 | DOI:10.1142/s0218196700000054
  • Honkala, Juha On D0L power series, Theoretical Computer Science, Volume 244 (2000) no. 1-2, p. 117 | DOI:10.1016/s0304-3975(98)00338-7
  • Bezivin, Jean-Paul Sur les suites récurrentes à coefficients polynômes, Journal of Number Theory, Volume 66 (1997) no. 2, p. 282 | DOI:10.1006/jnth.1997.2157
  • Yokoyama, K. A modular method for computing the Galois groups of polynomials, Journal of Pure and Applied Algebra, Volume 117-118 (1997), p. 617 | DOI:10.1016/s0022-4049(97)00030-3
  • Gourdon, Xavier; Salvy, Bruno Effective asymptotics of linear recurrences with rational coefficients, Discrete Mathematics, Volume 153 (1996) no. 1-3, p. 145 | DOI:10.1016/0012-365x(95)00133-h
  • van der Poorten, A. J.; Shparlinski, I. E. On linear recurrence sequences with polynomial coefficients, Glasgow Mathematical Journal, Volume 38 (1996) no. 2, p. 147 | DOI:10.1017/s0017089500031372
  • Myerson, G.; van der Poorten, A. J. Some Problems Concerning Recurrence Sequences, The American Mathematical Monthly, Volume 102 (1995) no. 8, p. 698 | DOI:10.1080/00029890.1995.12004645
  • Litow, B. On Rat ∔, ACM SIGACT News, Volume 23 (1992) no. 3, p. 98 | DOI:10.1145/141914.141916
  • Vereshchagin, N. K. Occurrence of zero in a linear recursive sequence, Mathematical Notes of the Academy of Sciences of the USSR, Volume 38 (1985) no. 2, p. 609 | DOI:10.1007/bf01156238
  • Karpinski, Marek Decidability of “Skolem matrix emptiness problem” entails constructability of exact regular expression, Theoretical Computer Science, Volume 17 (1982) no. 1, p. 99 | DOI:10.1016/0304-3975(82)90134-7
  • Pansiot, J. J. A decidable property of iterated morphisms, Theoretical Computer Science, Volume 104 (1981), p. 152 | DOI:10.1007/bfb0017307
  • Ruohonen, Keijo On the decidability of the OL-DOL equivalence problem, Information and Control, Volume 40 (1979) no. 3, p. 301 | DOI:10.1016/s0019-9958(79)90797-6
  • Ruohonen, Keijo On some decidability problems for HDOL systems with nonsingular Parikh matrices, Theoretical Computer Science, Volume 9 (1979) no. 3, p. 377 | DOI:10.1016/0304-3975(79)90037-9
  • Mignotte, Maurice Some effective results about linear recursive sequences, Automata, Languages and Programming, Volume 62 (1978), p. 322 | DOI:10.1007/3-540-08860-1_23
  • Mignotte, M. Intersection des images de certaines suites récurrentes linéaires, Theoretical Computer Science, Volume 7 (1978) no. 1, p. 117 | DOI:10.1016/0304-3975(78)90043-9
  • Ruohonen, K. A note on equal powers of word morphisms, RAIRO. Informatique théorique, Volume 11 (1977) no. 3, p. 207 | DOI:10.1051/ita/1977110302071
  • Ruohonen, Keijo Zeros of Z-rational functions and D0L equivalence, Theoretical Computer Science, Volume 3 (1976) no. 3, p. 283 | DOI:10.1016/0304-3975(76)90047-5

Cité par 62 documents. Sources : Crossref