CCS(25,12) is Turing-complete

• Autorzy: Gorrieri R.

Identyfikatory

DOI

10.3233/FI-2017-1557

• Języki publikacji: EN

Abstrakty

EN

CCS(h,k) is the CCS subcalculus which can use at most h constants and k actions. We show that CCS(25,12) is Turing-complete by simulating Neary and Woods’ universal Turing machine with 15 states and 2 symbols.

Słowa kluczowe

EN

process algebra; CCS; universal turing machine

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 145--166
• Opis fizyczny: Bibliogr. 21 poz., tab.

Twórcy

autor

Gorrieri R.

• Dipartimento di Informatica — Scienza e Ingegneria, Università di Bologna, Mura A. Zamboni, 7, 40127 Bologna, Italy

Bibliografia

• [1] Milner R. Communication and Concurrency, Prentice-Hall, 1989. ISBN: 0-13-114984-9
• [2] Gorrieri R, Versari C. Introduction to Concurrency Theory: Transition Systems and CCS, EATCS Texts in Theoretical Computer Science, Springer-Verlag, 2015. ISBN: 978-3-319-21491-7
• [3] Minsky ML. Computation: Finite and Infinite Machines, Prentice-Hall, Upper Saddle River, NJ, USA, 1967. ISBN: 0-13-165563-9
• [4] Turing AM. “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society, Series 2, 1936;42:230-265. doi:10.1112/plms/s2-42.1.230
• [5] Davis MD, Weyuker EJ. Computability, Complexity and Languages, Academic Press, New York, 1983. ISBN: 0-12-206380-5
• [6] Hopcroft JE, Motwani R, Ullman JD. Introduction to Automata Theory, Languages and Computation, 2nd ed., Addison-Wesley, 2001. ISBN: 0-201-44124-1
• [7] Rogozhin Y. “Small Universal Turing Machines”, Theoretical Computer Science 1996;168:215–240. doi:10.1016/S0304-3975(96)00077-1
• [8] T. Neary, D. Woods, “Four Small Universal Turing Machines”, Fundam. Inform. 2009;91(1):123–144. doi:10.3233/FI-2009-0036
• [9] Versari C, Busi N, Gorrieri R. “An Expressiveness Study of Priority in Process Calculi”, Mathematical Structures in Computer Science 2009;19(6):1161–1189. doi:10.1017/S0960129509990168
• [10] Gorrieri R. Process Algebras for Petri Nets: The Alphabetization of Distributed Systems, EATCS Monographs in Theoretical Computer Science, Springer-Verlag, 2017. ISBN: 978-3-319-55559-1
• [11] Peterson JL. Petri Net Theory and the Modeling of Systems, Prentice-Hall, 1981. ISBN: 0-13-661983-5
• [12] Reisig W. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies, Springer-Verlag, 2013. ISBN: 978-3-642-33277-7
• [13] Plotkin GD. “A Structural Approach to Operational Semantics”, J. Logic and Algebraic Programming 2004;60-61:17–139. Revised version of the original Technical Report DAIMI FN-19, Aarhus University, 1981. doi:10.1016/j.jlap.2004.05.001
• [14] Taubner D. Finite Representations of CCS and TCSP Programs by Automata and Petri Nets, Lecture Notes in Computer Science 369, Springer-Verlag, 1989. ISBN: 978-3-540-51525-8
• [15] Shannon CE. “A Universal Turing Machine with Two Internal States”, in Automata Studies, Ann. Math. Stud. 1956;34:157–165, Princeton Univ.Press. doi:10.2307/2269988
• [16] Busi N, Gabbrielli M, Zavattaro G. “On the Expressive Power of Recursion, Replication and Iteration in Process Calculi”, Mathematical Structures in Computer Science 2009;19(6):1191–1222. doi:10.1017/S096012950999017X
• [17] Busi N, Gorrieri R, and Zavattaro G. “A Process Algebraic View of Linda Coordination Primitives”, Theoretical Computer Science 1998;192(2):167–199. doi:10.1016/S0304-3975(97)00149-7
• [18] Parrow J. “An Introduction to the p-calculus”, Chapter 8 of [21], 2001; pp. 479–543. doi:10.1016/B978-044482830-9/50026-6
• [19] Sangiorgi D, Walker D. The p-calculus: A Theory of Mobile Processes, Cambridge University Press, 2001. ISBN: 978-0521781770
• [20] Bekič H. “The Semantics of Parallel Processing”, in (Cliff B. Jones, ed.) Programming Languages and Their Definition - Hans Bekič (1936-1982), LNCS 177, Springer-Verlag, 1984 pp. 215–229. doi:10.1007/bfb0048946
• [21] Bergstra JA, Ponse A, Smolka SA (eds.). Handbook of Process Algebra, Elsevier, 2001. ISBN: 978-0-444-82830-9