An Interaction Between User and an Augmented Reality System using A Generalized Finite State Automata and A Universal Turing Machine
Aslan Alwi1, Azhari2, Suprapto3

1Aslan Alwi*, Doctoral Student at Computer Science and Electronics Department, Universitas Gadjah Mada, Yogyakarta, Indonesia.
2Azhari,Lecturer at Computer Science and Electronics Department, Universitas Gadjah Mada, Yogyakarta, Indonesia.
3Suprapto,Lecturer at Engineering Departement, Universitas Muhammadiyah Ponorogo, Indonesia.

Manuscript received on September 16, 2019. | Revised Manuscript received on 24 September, 2019. | Manuscript published on October 10, 2019. | PP: 1084-1090 | Volume-8 Issue-12, October 2019. | Retrieval Number: L38781081219/2019©BEIESP | DOI: 10.35940/ijitee.L3878.1081219
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (

Abstract: Most interactions between users and augmented reality system (ARS) are that user assigns a marker to ARS, and the ARS responds the marker. In this context, a marker is mapped to an ARS’s response, or in general, an array of markers is mapped to an array of ARS’s responses. This interaction is a constant or linear complexity interaction since there is only a bijective mapping between a set of markers and a set of ARS’s responses. In this research, we propose the expansion of user – ARS complexity into the polynomial. It is an interaction in which not only one marker for a single response (or an array of markers for an array of ARS’s responses), but the interaction by which user provides a string of markers as a word of markers (i.e., a combination of multiple markers as a word) for a single ARS’s response. The set of strings of markers to the ARS provided by users built a regular language. So that, the complexity of the user-ARS interaction became polynomial. This interaction was implemented by stating the user’s language by means of a generalization of finite state automata (gFSA) and placing a universal Turing machine (UTM) between user and ARS, where the UTM as an interpreter translating or mapping the user language to ARS. To summarize our research, overall we apply the idea of a formal language into the interaction between the user and ARS, thereby changing the complexity of the interaction to polynomial even expandable to nondeterministic polynomials.
Keywords: Interpreter, Polynomial Interaction, Turing Machine, Word Marker.
Scope of the Article: Human Computer Interaction (HCI)