On Half Iterates of Functions Defined on Finite Sets
Institute of Mathematics University of Silesia
Katowice Bankowa 14, 40-007 Katowice, Poland
E-mail: pawel_m_kozyra@wp.pl
Received:
Received: 30 April 2018; revised: 28 August 2018; accepted: 30 August 2018; published online: 30 September 2018
DOI: 10.12921/cmst.2018.0000027
Abstract:
Four algorithms determining all functional square roots (half iterates) and seven algorithms finding one functional square root of any function f : X → X defined on a finite set X, if these square roots exist, are presented herein. Time efficiency of these algorithms depending on the complexity of examined functions is compared and justification of correctness is given. Moreover, theorems which make finding half iterates possible in some cases or facilitate this task are formulated.
Key words:
References:
[1] J. Gross, J. Yellen, Handbook of Graph Theory, CRC Press, 2003.
[2] M.N.S. Swamy, K. Thulasiraman, Graphs: Theory and Algo- rithms. Wiley,1992.
[3] Kneser, H. Reelle analytische Lösungen der Gleichung Φ(Φ(x)) = ex und verwandter Funktionalgleichungen. Jour- nal fur die reine und angewandte Mathematik. 187, 56–67 (1950).
[4] Gray J., Parshall, K. Episodes in the History of Modern Al- gebra (1800–1950), American Mathematical Society, ISBN 978-0-8218-4343-7, 2007.
[5] E. Schröder, Über iterirte Functionen. Mathematische Annalen, 3 (2), 296–322 (1870).
[6] G. Szekeres, Regular iteration of real and complex functions Acta Mathematica 100, (3–4) 361–376 (1958).
[7] T. Curtright, C. Zachos, X. Jin, Approximate solutions of func- tionalequations, JournalofPhysicsA44(40):405205(2011). [8] M.C. Zdun, On iterative roots of homeomorphisms of the circle, Bull. Pol. Acad. Sci. Math 48 (2), 203-213.
Four algorithms determining all functional square roots (half iterates) and seven algorithms finding one functional square root of any function f : X → X defined on a finite set X, if these square roots exist, are presented herein. Time efficiency of these algorithms depending on the complexity of examined functions is compared and justification of correctness is given. Moreover, theorems which make finding half iterates possible in some cases or facilitate this task are formulated.
Key words:
References:
[1] J. Gross, J. Yellen, Handbook of Graph Theory, CRC Press, 2003.
[2] M.N.S. Swamy, K. Thulasiraman, Graphs: Theory and Algo- rithms. Wiley,1992.
[3] Kneser, H. Reelle analytische Lösungen der Gleichung Φ(Φ(x)) = ex und verwandter Funktionalgleichungen. Jour- nal fur die reine und angewandte Mathematik. 187, 56–67 (1950).
[4] Gray J., Parshall, K. Episodes in the History of Modern Al- gebra (1800–1950), American Mathematical Society, ISBN 978-0-8218-4343-7, 2007.
[5] E. Schröder, Über iterirte Functionen. Mathematische Annalen, 3 (2), 296–322 (1870).
[6] G. Szekeres, Regular iteration of real and complex functions Acta Mathematica 100, (3–4) 361–376 (1958).
[7] T. Curtright, C. Zachos, X. Jin, Approximate solutions of func- tionalequations, JournalofPhysicsA44(40):405205(2011). [8] M.C. Zdun, On iterative roots of homeomorphisms of the circle, Bull. Pol. Acad. Sci. Math 48 (2), 203-213.
