Abstract
Newton’s forward difference equation gives an expression of a function from \({\mathbb {N}}\) to \({\mathbb {Z}}\) in terms of the initial value of the function and the powers of the forward difference operator. An extension of this formula to functions from \(A^*\) to \({\mathbb {Z}}\) was given in 2008 by P. Silva and the author. In this paper, the formula is further extended to functions from \(A^*\) into the free group over \(B\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Therefore, the notation \(FG(M)\) and \(FG[M]\) refer to the same set, but to different structures: the free group on \(M\) in the first case, the free near semiring on \(M\) in the latter case.
References
Almeida, J.: Finite semigroups and universal algebra. World Scientific Publishing Co., River Edge (1994). Translated from the 1992 Portuguese original and revised by the author
Banaschewski, B., Nelson, E.: On the non-existence of injective near-ring modules. Can. Math. Bull. 20(1), 17–23 (1977)
Berstel, J., Boasson, L., Carton, O., Petazzoni, B., Pin, J.É.: Operations preserving recognizable languages. Theor. Comput. Sci. 354, 405–420 (2006)
Droste, M., Zhang, G.Q.: On transformations of formal power series. Inf. Comput. 184(2), 369–383 (2003)
Eilenberg, S.: Automata, Languages and Machines, vol. B. Academic Press, New York (1976)
Fröhlich, A.: On groups over a d.g. near-ring. I. Sum constructions and free \(R\)-groups. Q. J. Math. Oxf. Ser. (2) 11, 193–210 (1960)
Fröhlich, A.: On groups over a d.g. near-ring. II. Categories and functors. Q. J. Math. Oxf. Ser. (2) 11, 211–228 (1960)
Kosaraju, S.R.: Regularity preserving functions. SIGACT News 6(2), 16–17 (1974)
Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1997)
Pin, J.É., Sakarovitch, J.: Operations and transductions that preserve rationality. In: Cremers, A.B., Kriegel, H.-P. (eds.) Theoretical Computer Science. LNCS, vol. 145, pp. 617–628. Springer, Heidelberg (1982)
Pin, J.É., Sakarovitch, J.: Une application de la représentation matricielle des transductions. Theor. Comput. Sci. 35, 271–293 (1985)
Pin, J.É., Silva, P.V.: A topological approach to transductions. Theor. Comput. Sci. 340, 443–456 (2005)
Pin, J.É., Silva, P.V.: A Mahler’s theorem for functions from words to integers. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), pp. 585–596. Internationales Begegnungs- Und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany (2008)
Pin, J.É., Silva, P.V.: On profinite uniform structures defined by varieties of finite monoids. Int. J. Algebr. Comput. 21, 295–314 (2011)
Pin, J.É., Silva, P.V.: A noncommutative extension of Mahler’s theorem on interpolation series. Eur. J. Comb. 36, 564–578 (2014)
Pin, J.É., Weil, P.: Uniformities on free semigroups. Int. J. Algebr. Comput. 9, 431–453 (1999)
Reutenauer, C., Schützenberger, M.P.: Variétés et fonctions rationnelles. Theor. Comput. Sci. 145(1–2), 229–240 (1995)
Seiferas, J.I., McNaughton, R.: Regularity-preserving relations. Theor. Comp. Sci. 2, 147–154 (1976)
Stearns, R.E., Hartmanis, J.: Regularity preserving modifications of regular expressions. Inf. Control 6, 55–69 (1963)
Acknowlegements
I would like to thank the anonymous referees for their valuable comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Pin, JÉ. (2015). Newton’s Forward Difference Equation for Functions from Words to Words. In: Beckmann, A., Mitrana, V., Soskova, M. (eds) Evolving Computability. CiE 2015. Lecture Notes in Computer Science(), vol 9136. Springer, Cham. https://doi.org/10.1007/978-3-319-20028-6_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-20028-6_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-20027-9
Online ISBN: 978-3-319-20028-6
eBook Packages: Computer ScienceComputer Science (R0)