Automata in Chinese Remainder Theorem

Authors

DOI:

https://doi.org/10.26713/cma.v13i1.1704

Keywords:

Automata, Cartesian product of DFA, Chinese Remainder Theorem

Abstract

. Automaton is a system that spontaneously gives an output from an input. The input may
be energy, information, materials, etc. The system works without the intervention of man. Simply
automaton (plural: automata or automatons) is a self–operating machine. Its synonym is ROBOT.
In this paper, an attempt has been made to exhibit the relation between linear congruence and
automata theory. Also, an effort has been put to solve certain problems of the Chinese Remainder
theorem using the Cartesian product of finite automata theory. In deterministic finite automata, the
acceptable strings give the solutions of the Chinese Remainder Theorem (CRT). The main result of the
paper is that residue classes can be recognized by finite automaton. This is the novelty of the article.
Finally, we conclude with certain examples and non-examples alike!

Downloads

Download data is not yet available.

References

B. Adamczewski and J. Bell, Automata in Number Theory (Chapter 25), CNRS and University of Waterloo (2018), URL: https://adamczewski.perso.math.cnrs.fr/Chapter25.pdf.

J.P. Allouche, Cellular automata, finite automata, and number theory, in: Cellular Automata, pp. 321 – 330, (1999), Mathematics and Its Applications book series (MAIA, Vol. 460), Springer, Dordrecht, DOI: 10.1007/978-94-015-9153-9_13.

D.M. Burton, Elementary Number Theory, Tata McGraw-Hill Education (2006).

C. Ding, D. Pei and A. Salomaa, Chinese Remainder Theorem: Applications in Computing, Coding, Cryptography, World Scientific Publishing Co. Pte. Ltd., Singapore (1996), DOI: 10.1142/3254.

W. Dörfler, The cartesian product of automata, Mathematical System Theory 11 (1978), 239 – 257, DOI: 10.1007/BF01768479.

V.M. Glushkov, The abstract theory of automata, Russian Mathematical Surveys (Uspekhi Matematicheskikh Nauk) 16(5) (1961), 3 – 62, URL: http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=6668&option_lang=eng (in Russian).

J. Hartmanis and H. Shank, On the recognition of primes by automata, Journal of the ACM 15(3) (1968), 382 – 389, DOI: 10.1145/321466.321470.

W.M.L. Holcombe, Algebraic Automata Theory, in: Cambridge Studies in Mathematics series, Vol. 1, Cambridge University Press (1981), URL: https://www.ioc.ee/~jaan/Algebraic_automata/Holcombe/Holcombe1.PDF

J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, languages, and computation, ACM SIGACT News 32(1) (2001), 60 – 65, DOI: 10.1145/568438.568455.

S.C. Hsieh, Product construction of finite-state machines, in: Proceedings of the World Congress on Engineering and Computer Science, Vol. I (WCECS 2010), October 20-22, 2010, San Francisco, USA, pp. 141 – 143, (2010), http://www.iaeng.org/publication/WCECS2010/WCECS2010_pp141-143.pdf.

S. Kandar, Introduction to Automata Theory, Formal Languages and Computation, Pearson Education India (2013).

K.L.P. Mishra and N. Chandrasekaran, Theory of Computer Science: Automata, Languages and Computation, PHI Learning Pvt. Ltd. (2006).

D.E. Muller, Theory of automata, in: F. Preparata (eds.), Theoretical Computer Science. C.I.M.E. Summer Schools, Vol. 68, Springer, Berlin — Heidelberg, (2011), DOI: 10.1007/978-3-642-11120-4_2.

D. Perrin, Formal models and semantics, in: Handbook of Theoretical Computer Science, J. van Leeuwen (ed.), 3 – 57 (1990), DOI: 10.1016/B978-0-444-88074-1.50006-8.

J.E. Pin, Formal Properties of Finite Automata and Applications, in: Proceedings of LITP Spring School on Theoretical Computer Science, Ramatuelle, France, May 23-27, 1988, Springer Science & Business Media (1989), https://link.springer.com/book/10.1007/BFb0013106.

A. Rajasekaran, J. Shallit and T. Smith, Additive number theory via automata theory, Theory of Computing Systems 64 (2020), 542 – 567, DOI: 10.1007/s00224-019-09929-9.

G. Rauzy, Numbers and automata, in: LITP 1988: Formal Properties of Finite Automata and Applications, J.E. Pin (ed.), Lecture Notes in Computer Science book series (LNCS, Vol. 386), Springer, Berlin — Heidelberg, 176 – 185 (1988), DOI: 10.1007/BFb0013120.

A. Restivo, Codes and automata, in: LITP 1988: Formal Properties of Finite Automata and Applications, J.E. Pin (ed.), Lecture Notes in Computer Science book series (LNCS, Vol. 386), Springer, Berlin — Heidelberg, 186 – 198 (1988), DOI: 10.1007/BFb0013121.

M. Rigo, Formal languages, automata and numeration systems, in: Applications to Recognizability and Decidability, Vol. 2, John Wiley & Sons (2014), https://orbi.uliege.be/handle/2268/176351.

A. Salomaa, Theory of Automata, 1st edition, Elsevier (1969), URL: https://www.elsevier.com/books/theory-of-automata/salomaa/978-0-08-013376-8.

W. Steiner, Numeration Systems: Automata, Combinatorics, Dynamical Systems, Number Theory, Doctoral dissertation, Institut de Recherche en Informatique Fondamenta, Université de Paris (2021), URL: https://www.irif.fr/~steiner/hdr.pdf.

S. Wolfram, Cellular Automata and Complexity, 1st edition, CRC Press, Boca Raton (2019), DOI: 10.1201/9780429494093.

Downloads

Published

23-05-2022
CITATION

How to Cite

Dutta, M., & Saikia, H. K. (2022). Automata in Chinese Remainder Theorem. Communications in Mathematics and Applications, 13(1), 183–197. https://doi.org/10.26713/cma.v13i1.1704

Issue

Section

Research Article