Automata in Chinese Remainder Theorem
DOI:
https://doi.org/10.26713/cma.v13i1.1704Keywords:
Automata, Cartesian product of DFA, Chinese Remainder TheoremAbstract
. 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
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
How to Cite
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a CCAL that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
