The Influence of Temporal Logic on Finite Automata

Kareem, Bilal Abdullateef; Senjari, Ahmad

doi:10.33899/rengj.2023.136476.1208

Document Type : Research Paper

Authors

¹ Electrical Engineering Department, College of Engineering, Salahaddin Universtiy,Erbil, Iraq

² Electrical Engineering Department, College of Engineering, Salahaddin Universtiy, Erbil, Iraq

10.33899/rengj.2023.136476.1208

Abstract

The theory of automata combines ideas from engineering, linguistics, mathematics, philosophy, etc. The Entscheidungsproblem asks if it is possible to design a series of steps that replaces a mathematician. An automaton is an abstract machine that processes data. C. Shannon's theory is today's most popular despite having no relationship with the other. The Kt system is called "minimal" because it makes no assumptions about the structure of time. In LKt, we have four monary temporal operators, F, P, G and H, which are mutually interdefinable. Interdefinability means that we will pass logic in the future is the same as saying I will never fail logic, interpreting not passing logic as failing logic. The minimal system syntax of temporal logic introduces operators that have the property of being defined in terms of others. Modal logic studies the reasoning that involves the use of expressions "necessarily" and "possibly". In this article, we will represent through a finite automaton the temporal logic formula Fp. It allows us to see an acceptance pattern for Fp by considering two variables: p and q. Kt's axiomatic system of time expresses the idea that both the present and the past are fixed, if it has always been in the past that it will be some time in the future that p is now. No philosophical argument supports deterministic time flow; the logic of time must be open.Temporal logic has revived many old problems, from the Megaric-Stoics to the minimal system of temporal logic. Our work suggests that the future operators of system Kt follow an evaluation pattern, but we must be cautious because this pattern can only apply to models whose time flow is based on instants and precedence relations.

Keywords

Main Subjects

Computer Engineering

References

[1] R. S. Stanković, J. T. Astola, A. A. Shalyto, and A. V. Strukov, “Reprints from the Early Days of Information Sciences”, 2016.

[2] M. A. Orgun and W. Ma, “An overview of temporal and modal logic programming,” in Temporal Logic: First International Conference, ICTL’94 Bonn, Germany, July 11–14, 1994 Proceedings, 2005, pp. 445–479.

[3] A. Meduna, Automata and languages: theory and applications. Springer Science & Business Media, 2012.

[4] C. Reid and H. Weyl, “David Hilbert and His Mathematical Work,” Hilbert, pp. 245–283, 1970.

[5] W. Thomas, Languages, automata, and logic. Springer, 1997.

[6] A. Church, “A note on the Entscheidungsproblem,” The journal of symbolic logic, vol. 1, no. 1, pp. 40–41, 1936.

[7] K. Gödel, "Collected Works: Volume I: Publications 1929-1936," Oxford University Press, vol. 1, USA, 1986.

[8] Bowen, J.P.J.T.S.A.E.o.D.T. and Hudson, Alan Turing., p. 270-275, 2012.

[9] J. van Benthem, “Tense logic and time.,” Notre Dame Journal of Formal Logic, vol. 25, no. 1, pp. 1–16, 1984.

[10] J. R. Shoenfield, Mathematical logic. CRC Press, 2018.

[11] N. Rescher and A. Urquhart, Temporal logic, vol. 3. Springer Science & Business Media, 2012.

[12] T. D. Schneider, “Claude Shannon: Biologist [information theory used in biology],” IEEE Engineering in Medicine and Biology Magazine, vol. 25, no. 1, pp. 30–33, 2006.

[13] M. K. Kerimov, “Brief history of the Dorodnicyn Computing Center, Russian Academy of Sciences (dedicated to the 50th anniversary of its foundation),” Computational Mathematics and Mathematical Physics, vol. 46, pp. 1086–1120, 2006.

[14] S. Chakraverty, D. M. Sahoo, N. R. Mahato, S. Chakraverty, D. M. Sahoo, and N. R. Mahato, “McCulloch–Pitts neural network model,” Concepts of soft computing: fuzzy and ANN with programming, pp. 167–173, 2019.

[15] J. Von Neumann, Mathematical foundations of quantum mechanics: New edition, vol. 53. Princeton university press, 2018.

[16] S. C. Kleene, “On the interpretation of intuitionistic number theory,” The journal of symbolic logic, vol. 10, no. 4, pp. 109–124, 1945.

[17] D. Giri, K.-K. R. Choo, S. Ponnusamy, W. Meng, S. Akleylek, and S. P. Maity, Proceedings of the Seventh International Conference on Mathematics and Computing: ICMC 2021, vol. 1412. Springer Nature, 2022.

[18] A. Salomaa, Theory of automata. Elsevier, 2014.

[19] JG. Jäger and J. Rogers, “Formal language theory: refining the Chomsky hierarchy,” Philosophical Transactions of the Royal Society B: Biological Sciences, vol. 367, no. 1598, pp. 1956–1970, 2012.

[20] G. Priest, An introduction to non-classical logic: From if to is. Cambridge University Press, 2008.

[21] S. I. Hayakawa, “Semantics, General Semantics,” ETC: A Review of General Semantics, pp. 161–170, 1947.

[22] A. N. Prior, “The syntax of time-distinctions,” Franciscan studies, vol. 18, no. 2, pp. 105–120, 1958.

[23] D. M. Gabbay, I. Hodkinson, and M. A. Reynolds, “Temporal logic: mathematical foundations and computational aspects,” 1994.

[24] M. R. Genesereth and N. J. Nilsson, Logical foundations of artificial intelligence. Morgan Kaufmann, 2012.

[25] L. M. Tabajara and M. Y. Vardi, “Linear Temporal Logic–From Infinite to Finite Horizon,” in Automated Technology for Verification and Analysis: 19th International Symposium, ATVA 2021, Gold Coast, QLD, Australia, October 18–22, 2021, Proceedings, 2021, pp. 3–12.

[26] L. Floridi, The Blackwell guide to the philosophy of computing and information. John Wiley & Sons, 2008.

[27] J. Van Benthem, J. F. van Benthem, J. F. van Benthem, I. Mathématicien, and J. F. van Benthem, Modal logic for open minds. Center for the Study of Language, 2010.

[28] D. C. Kozen, Automata and computability. Springer Science & Business Media, 2007.

[29] C. Areces and P. Blackburn, Bringing them all together, vol. 11. Oxford University Press, 2001, pp. 657–669.

[30] T. Müller, Tense or temporal logic. 2011.