NEW RESULTS ON COMPUTABILITY OF RECURRENCE EQUATIONS

DOI10.1142/S0129054198000179zbMath1319.68086OpenAlexW2034103477MaRDI QIDQ5248978

Yannick Saouter, Hervé Le Verge

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054198000179

zbMATH Keywords

Turing machinesunbounded domainscomputabilitysystems of uniform recurrence equationsparametrized recurrent systemssystem of affine recurrence equations

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Undecidability and degrees of sets of sentences (03D35) Parallel algorithms in computer science (68W10) Mathematical problems of computer architecture (68M07) Distributed algorithms (68W15) Notions of recurrence and recurrent behavior in topological dynamical systems (37B20)

Cites Work

• Simple termination is difficult
• Parallel program schemata
• On the Analysis and Synthesis of VLSI Algorithms
• Formal verification of parallel programs
• Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
• The Organization of Computations for Uniform Recurrence Equations