The Inverse of Ackermann Function is Computable in Linear Time

• Autorzy: Sureson Claude

Identyfikatory

DOI

10.3233/FI-2021-2077

• Języki publikacji: EN

Abstrakty

EN

We propose a detailed proof of the fact that the inverse of Ackermann function is computable in linear time.

Słowa kluczowe

EN

recursive functions; complexity of computation

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2021
• Tom: Vol. 182, nr 4
• Strony: 345--361
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Sureson Claude

• Université Paris

Bibliografia

• [1] Ackermann W. Zum Hilbertschen Aufbau der reellen Zahlen. Math. Ann., 1928. 99:118–133. doi:10.1007/BF01459088.
• [2] Tarjan RE. Efficiency of a good but not linear set union algorithm. J. Assoc. Comput. Mach., 1975. 22:215–225. doi:10.1145/321879.321884.
• [3] Chazelle B. A minimum spanning tree algorithm with inverse-ackermann type complexity. J. ACM, 2000. 47:1028–1047. doi:10.1145/355541.355562.
• [4] Nivasch G. Inverse Ackermann without pain. Accessed: 2019-10-7.URL http://www.gabrielnivasch.org/fun/inverse-ackermann.
• [5] Seidel R. Understanding the inverse Ackermann function. 22nd European Workshop on Computational Geometry, 2006. URL http://cgi.di.uoa.gr/~ewcg06/invited/Seidel.pdf.
• [6] Seidel R, Sharir M. Top-down analysis of path compression. SIAM J. Comput., 2005. 34(3):515–525. doi:10.1137/S0097539703439088.
• [7] Sureson C. Subcomputable Hausdorff Function Dimension. To appear in the J. Theor. Comput. Science, 2021. doi:10.1016/j.tcs2021.08.27.
• [8] Tran L, Mohan A, Hobor A. A functional Proof Pearl: Inverting the Ackermann Hierarchy. CCP 2020: Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs: 2020 pp. 129–142. https://doi.org/10.1145/3372885.3373837.
• [9] Tourlakis G. Theory of computation. Hoboken, NJ: John Wiley & Sons, 2012. ISBN:978-1-118-01478-3, 978-1-118-31536-1.
• [10] Arora S, Barak B. Computational complexity. A modern approach. Cambridge: Cambridge University Press, 2009. ISBN:978-0-521-42426-4.
• [11] Cori R, Lascar D. Mathematical logic. A course with exercises. Part II. Recursion theory, G¨odel’s theorems, set theory, model theory. Translated from the 1993 French original by Donald H. Pelletier. Oxford: Oxford University Press, 2001. ISBN-10:0198500505, 13:978-0198500506.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023). (PL)