World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

The semaphore codes attached to a Turing machine via resets and their various limits

    https://doi.org/10.1142/S0218196716500296Cited by:2 (Source: Crossref)

    We introduce semaphore codes associated to a Turing machine via resets. Semaphore codes provide an approximation theory for resets. In this paper, we generalize the set-up of our previous paper “Random walks on semaphore codes and delay de Bruijn semigroups” to the infinite case by taking the profinite limit of k-resets to obtain (ω)-resets. We mention how this opens new avenues to attack the vs. NP problem.

    Communicated by S. Margolis

    AMSC: 20M07, 20M30, 54H15, 68Q05, 68Q15, 68Q7

    References

    • 1. J. Berstel, Transductions and Context-Free Languages (Teubner, Stuttgart, 1979). CrossrefGoogle Scholar
    • 2. J. Berstel, D. Perrin and C. Reutenauer, Codes and automata, Encyclopedia of Mathematics and its Applications, Vol. 129 (Cambridge University Press, Cambridge, 2010). Google Scholar
    • 3. G. Hognas and A. Mukherjea, Probability Measures on Semigroups, Springer Series in Probability and its Applications (Springer, 2011). CrossrefGoogle Scholar
    • 4. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation (Addison-Wesley, 1979). Google Scholar
    • 5. K. Krohn and J. Rhodes, Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines, Trans. Amer. Math. Soc. 116 (1965) 450–464. Crossref, Web of ScienceGoogle Scholar
    • 6. J. Rhodes, Applications of Automata Theory and Algebra: Via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy, and Games, (World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2010), xviii+274 pp. 1, With an editorial preface by Chrystopher L. Nehaniv and a foreword by Morris W. Hirsch. Google Scholar
    • 7. J. Rhodes, A. Schilling and P. V. Silva, Random walks on semaphore codes and delay de Bruijn semigroups, Int. J. Algebra Comput. 26(4) (2016) doi: 10.1142/ S0218196716500284. Link, Web of ScienceGoogle Scholar
    • 8. J. Rhodes and P. V. Silva, Turing machines and bimachines, Theor. Comput. Sci. 400(1–3) (2008) 182–224. Crossref, Web of ScienceGoogle Scholar
    • 9. J. Rhodes and B. Steinberg, The q-theory of Finite Semigroups, Springer Monographs in Mathematics (Springer, 2009). CrossrefGoogle Scholar
    • 10. J. Rhodes and P. Weil, Algebraic and topological theory of languages, RAIRO Theoret. Inform. Appl. 29 (1995) 1–44. Crossref, Web of ScienceGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out Algebra & Computation books in the Mathematics 2021 catalogue.