Formal Language Foundations for Polynomial and Nondeterministic Polynomial Interaction in Augmented Reality Systems

(MODELING INTERACTIONS BETWEEN USER AND AUGMENTED REALITY SYSTEM INTO FORMAL LANGUAGES USING TIMED AUTOMATA)

Author: Aslan Alwi, Azhari Azhari, Suprapto Suprapto

Problem and Challenge

Conventional user–Augmented Reality System (ARS) interactions rely on simple marker–response mappings, where each marker corresponds to a single ARS response. Such mappings are either constant or linear in complexity, providing limited expressiveness and scalability. This constrained model fails to accommodate richer interaction paradigms, such as combining multiple markers dynamically, scaling to real-time contexts, or supporting nondeterministic behaviors.

Research Objective

This dissertation set out to transform the complexity of user–ARS interaction by embedding principles of formal languages, automata, and computability theory. The aim was to expand interaction from simple bijective mappings into the domain of polynomial and nondeterministic polynomial (NP) complexities, enabling structured yet expressive languages of interaction.

Methodology

The research was conducted in several stages:

1. Literature Review and Problem Analysis
   • Comparative study of prior ARS interaction models (Shetty, Neha–Talwar, Rizov–Rizova, Etienne–Etienne).
   • Identification of weaknesses: user-friendliness, memory consumption, rendering speed, bandwidth limitations, and scalability.
2. Construction of Conjectures and Models
   • Formulation of conjectures linking ARS interaction to P vs. NP domains.
   • Introduction of Generalized Finite State Automata (gFSA) and Timed Automata for real-time interaction modeling.

Embedding Universal Turing Machine (UTM) constructs as interpreters and compilers of interaction languages.

1. Proof and Verification
   • Mathematical proofs based on the Chomsky hierarchy showing that ARS interaction languages can span from regular and context-free to context-sensitive and recursively enumerable languages.
   • White-box verification of models via Turing Machine instruction tracing, ensuring transparency and formal correctness.
2. Implementation Prototypes
   • Design of gFSA–UTM interpreters and compilers.
   • Extension into timed grammars and timed generalized Turing Machines (gTM) for real-time and nondeterministic real-time interaction.

Key Results and Findings

• Polynomial and NP Complexity Achieved: Interactions no longer constrained to O(1) or O(n), but expanded into polynomial and NP domains, supporting rich combinations of markers (strings/words of markers).
• Chomsky Hierarchy Application: Users can construct interaction languages at multiple levels—from regular to recursively enumerable—depending on complexity requirements.
• Real-time and Nondeterministic Extensions: The models generalize into timed and nondeterministic timed domains, enabling practical real-time interactive systems.
• Robust Computational Models: Verified interpreters and compilers (deterministic, nondeterministic, timed) were developed, guaranteed by rigorous mathematical theorems and white-box verification.
• Generality: The framework applies not only to user–ARS interaction but to user–machine and machine–machine interaction, laying the groundwork for broader applications.

Value Proposition

This dissertation delivers a formal theoretical foundation for scalable and expressive interaction in ARS, with three major contributions:

1. A shift in complexity from linear to polynomial/NP, aligning ARS interaction with the richness of formal language theory.
2. Interpreter and compiler models for ARS interaction languages, verified both mathematically and computationally.
3. Extensible frameworks that anticipate future paradigms—fuzzy, probabilistic, and even quantum interaction languages—potentially applicable to communication protocols, encryption, and blockchain systems.

Conclusions

The research demonstrates that ARS interactions can be modeled as formal languages spanning the Chomsky hierarchy, thereby enabling user-defined interaction languages of increasing complexity. The resulting interpreters and compilers ensure correct execution in both deterministic and nondeterministic real-time contexts. Unlike black-box evaluations, the models were validated using white-box verification, ensuring consistency at the level of Turing Machine execution steps.

Thus, this work contributes not only to ARS but also to general machine interaction paradigms, offering a universal foundation for scalable, verifiable interaction.

Recommendations for Future Research

The dissertation lays a foundation for several promising directions:

• Fuzzy and Probabilistic Languages: Extending ARS interactions into probabilistic computation for adaptive and context-sensitive systems.
• Quantum Interaction Languages: Exploring quantum interpreters and compilers for real-time machine–machine and user–machine interactions.
• Secure Communication Protocols: Leveraging the framework to design encrypted interaction protocols, analogous to blockchain infrastructures.
• Societal Contribution: Future work should emphasize applications that benefit national and global communities, ensuring that theoretical advances translate into meaningful contributions to civilization.