nach oben

Theory of Computing Systems

Erschienen in:

01.11.2013

A Process Calculus with Finitary Comprehended Terms

verfasst von: J. A. Bergstra, C. A. Middelburg

Erschienen in: Theory of Computing Systems | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We introduce the notion of an ACP process algebra and the notion of a meadow enriched ACP process algebra. The former notion originates from the models of the axiom system ACP. The latter notion is a simple generalization of the former notion to processes in which data are involved, the mathematical structure of data being a meadow. Moreover, for all associative operators from the signature of meadow enriched ACP process algebras that are not of an auxiliary nature, we introduce variable-binding operators as generalizations. These variable-binding operators, which give rise to comprehended terms, have the property that they can always be eliminated. Thus, we obtain a process calculus whose terms can be interpreted in all meadow enriched ACP process algebras. Use of the variable-binding operators can have a major impact on the size of terms.

Vorheriger Artikel Sofic Tree-Shifts

Nächster Artikel Log-Space Algorithms for Paths and Matchings in k-Trees

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

We write \(\mathbb{N}^{+}\) for the set \(\mathbb{N}\setminus \{ 0 \}\).

The name comprehended term originates from the name comprehended expression introduced in [27].

We write ≡ for syntactic identity.

We use the convention that, whenever we write log₂(n) in a context requiring a natural number, ⌈log₂(n)⌉ is implicitly meant.

Baeten, J.C.M., van Glabbeek, R.J.: Merge and termination in process algebra. In: Nori, K.V. (ed.) Proceedings 7th Conference on Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science, vol. 287, pp. 153–172. Springer, Berlin (1987) CrossRef

Baeten, J.C.M., Middelburg, C.A.: Process Algebra with Timing. Monographs in Theoretical Computer Science, An EATCS Series. Springer, Berlin (2002) MATHCrossRef

Baeten, J.C.M., Weijland, W.P.: Process Algebra. Cambridge Tracts in Theoretical Computer Science, vol. 18. Cambridge University Press, Cambridge (1990) CrossRef

Bergstra, J.A., Bethke, I., Ponse, A.: Process algebra with combinators. In: Börger, E., Gurevich, Y., Meinke, K. (eds.) CSL’93. Lecture Notes in Computer Science, vol. 832, pp. 36–65. Springer, Berlin (1994)

Bergstra, J.A., Bethke, I., Ponse, A.: Cancellation meadows: a generic basis theorem and some applications. Comput. J. 56(1), 3–14 (2013) CrossRef

Bergstra, J.A., Hirshfeld, Y., Tucker, J.V.: Meadows and the equational specification of division. Theor. Comput. Sci. 410(12–13), 1261–1271 (2009) MathSciNetMATHCrossRef

Bergstra, J.A., Klop, J.W.: Process algebra for synchronous communication. Inf. Control 60(1–3), 109–137 (1984) MathSciNetMATHCrossRef

Bergstra, J.A., Middelburg, C.A.: Splitting bisimulations and retrospective conditions. Inf. Comput. 204(7), 1083–1138 (2006) MathSciNetMATHCrossRef

Bergstra, J.A., Middelburg, C.A.: Meadow enriched ACP process algebras. arXiv:0901.3012v2 [math.RA] (2009)

10.

Bergstra, J.A., Middelburg, C.A.: A process calculus with finitary comprehended terms. arXiv:0903.2914v1 [cs.LO] (2009)

11.

Bergstra, J.A., Middelburg, C.A.: Inversive meadows and divisive meadows. J. Appl. Log. 9(3), 203–220 (2011) MathSciNetMATHCrossRef

12.

Bergstra, J.A., Tucker, J.V.: Elementary algebraic specifications of the rational complex numbers. In: Futatsugi, K., et al. (eds.) Goguen Festschrift. Lecture Notes in Computer Science, vol. 4060, pp. 459–475. Springer, Berlin (2006)

13.

Bergstra, J.A., Tucker, J.V.: The rational numbers as an abstract data type. J. ACM 54(2), 7 (2007) MathSciNetCrossRef

14.

Burris, S., Sankappanavar, H.P.: A Course in Universal Algebra. Graduate Texts in Mathematics, vol. 78. Springer, Berlin (1981) MATHCrossRef

15.

Fokkink, W.J.: Introduction to Process Algebra. Texts in Theoretical Computer Science, An EATCS Series. Springer, Berlin (2000) MATHCrossRef

16.

Groote, J.F., Ponse, A.: Proof theory for μCRL: A language for processes with data. In: Andrews, D.J., Groote, J.F., Middelburg, C.A. (eds.) Semantics of Specification Languages. Workshops in Computing Series, pp. 232–251. Springer, Berlin (1994) CrossRef

17.

Groote, J.F., Ponse, A.: The syntax and semantics of μCRL. In: Ponse, A., Verhoef, C., van Vlijmen, S.F.M. (eds.) Algebra of Communicating Processes 1994. Workshops in Computing Series, pp. 26–62. Springer, Berlin (1995) CrossRef

18.

Hindley, J.R., Seldin, J.P.: Introduction to Combinators and λ-Calculus. Cambridge University Press, Cambridge (1986)

19.

Hodges, W.A.: Model Theory. Encyclopedia of Mathematics and Its Applications, vol. 42. Cambridge University Press, Cambridge (1993) MATHCrossRef

20.

Kosiuczenko, P., Meinke, K.: On the power of higher-order algebraic specification methods. Inf. Comput. 124(1), 85–101 (1996) MathSciNetMATHCrossRef

21.

Koymans, C.P.J., Vrancken, J.L.M.: Extending process algebra with the empty process ϵ. Logic Group Preprint Series 1. Department of Philosophy, Utrecht University, Utrecht (1985)

22.

Luttik, S.P.: Choice quantification in process algebra. PhD thesis, Programming Research Group, University of Amsterdam, Amsterdam (2002)

23.

Mauw, S., Veltink, G.J.: A process specification formalism. Fundam. Inform. 13(2), 85–139 (1990) MATH

24.

Meinke, K.: Universal algebra in higher types. Theor. Comput. Sci. 100(2), 385–417 (1992) MathSciNetMATHCrossRef

25.

Meinke, K.: Proof theory of higher-order equations: conservativity, normal forms and term rewriting. J. Comput. Syst. Sci. 67(1), 127–173 (2003) MathSciNetMATHCrossRef

26.

Meinke, K., Tucker, J.V.: Universal algebra. In: Abramsky, S., Gabbay, D.M., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, vol. I, pp. 189–411. Oxford University Press, Oxford (1992)

27.

RAISE Language Group: The RAISE Specification Language. Prentice-Hall, Englewood Cliffs (1992)

28.

Sannella, D., Tarlecki, A.: Algebraic preliminaries. In: Astesiano, E., Kreowski, H.J., Krieg-Brückner, B. (eds.) Algebraic Foundations of Systems Specification, pp. 13–30. Springer, Berlin (1999) CrossRef

29.

Yong, S.: An algebraic generalization of Frege structures—binding algebras. Theor. Comput. Sci. 211(1–2), 189–232 (1999) MATH

30.

Vrancken, J.L.M.: The algebra of communicating processes with empty process. Theor. Comput. Sci. 177(2), 287–328 (1997) MathSciNetMATHCrossRef

31.

Wirsing, M.: Algebraic specification. In: van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. B, pp. 675–788. Elsevier, Amsterdam (1990)

Titel: A Process Calculus with Finitary Comprehended Terms
verfasst von: J. A. Bergstra
C. A. Middelburg
Publikationsdatum: 01.11.2013
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 4/2013
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-013-9468-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2013

A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments

Normalized Range Voting Broadly Resists Control

Motion Planning with Pulley, Rope, and Baskets

Sofic Tree-Shifts

On Enumerating Monomials and Other Combinatorial Structures by Polynomial Interpolation

Corrigendum. The Linear Arrangement Problem Parameterized Above Guaranteed Value

Premium Partner