Decision Problems for Nonemptiness of Hyperlanguages: Undecidability and Complexity Results

References

[1] E. John, R. M. Hopcroft, and J. D. Ullman, “Introduction to automata theory languages, and computation [m],” 2004.

[2] C. Li, “From sum of two squares to arithmetic siegel–weil formulas,” Bulletin of the American Mathematical Society, vol. 60, no. 3, pp. 327– 370, 2023.

[3] N. Zhao, H. Zhang, X. Yang, J. Yan, and F. You, “Emerging information and communication technologies for smart energy systems and renewable transition,” Advances in Applied Energy, vol. 9, p. 100125, 2023.

[4] F. Kruger, Z. Queen, O. Radelva, and N. Lawrence, “Comparative analysis of scientific approaches in computer science: A quantitative study,” International Transactions on Education Technology (ITEE), vol. 2, no. 2, pp. 120–128, 2024.

[5] J. A. Goguen and J. Meseguer, “Security policies and security models,” in IEEE Symp. on Security and Privacy, 1982, pp. 11–20.

[6] S. Zdancewic and A. C. Myers, “Observational determinism for concurrent program security,” in Proceedings of the 16th IEEE Computer Security Foundations Workshop (CSFW), 2003, p. 29.

[7] G. Boudol and I. Castellani, “Noninterference for concurrent programs and thread systems,” Theoretical Computer Science (TCS), vol. 281, no. 1-2, pp. 109–130, 2002.

[8] D. McCullough, “Noninterference and the composability of security properties,” in Proceedings of the 1988 IEEE Symposium on Security and Privacy, 1988, pp. 177–186.

[9] A. Sabelfeld and D. Sands, “Probabilistic noninterference for multithreaded programs,” in Proceedings of the 13th IEEE Computer Security Foundations Workshop (CSFW), 2000, pp. 200–214.

[10] Angluin, “Learning regular sets from queries and counterexamples,” Infornation and Computation, vol. 75, no. 2, pp. 87–106, 1987.

@article{1707244,
      author = {Hyacinthe Hamon},
      title = {Decision Problems for Nonemptiness of Hyperlanguages: Undecidability and Complexity Results},
      journal = {Iconic Research And Engineering Journals},
      year = {2025},
      volume = {8},
      number = {8},
      pages = {675-683},
      issn = {2456-8880},
      url = {https://www.irejournals.com/formatedpaper/1707244.pdf},
      abstract = {This paper examines different choice issues connected with the nonemptiness of Non-Deterministic Limited Hyperautomata (NFH). I show that while the nonemptiness issue for NFH is for the most part undecidable, it becomes decidable for explicit pieces. I give a decrease from the Post Correspondence Issue (PCP) to demonstrate the undecidability of the nonemptiness issue for NFH, delineating how encoded arrangements of PCP can address legitimate hyperwords. Furthermore, I lay out that the nonemptiness issue for both NFH with existential and widespread evaluation (NFH? and NFH?) is NL-finished. At last, I present a choice methodology for the nonemptiness issue of NFH with blended evaluation (NFH??), demonstrating that it very well may be settled in polynomial space compared with the machine size. Our outcomes add to a more profound comprehension of hyperlanguage choice issues and their computational intricacy},
      month = {February},
  }