Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Higher-Order Languages: Bisimulation and Coinductive Equivalences (Extended Abstract) Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

How to Kill Epsilons with a Dagger

A Coalgebraic Take on Systems with Algebraic Label Structure

verfasst von : Filippo Bonchi, Stefan Milius, Alexandra Silva, Fabio Zanasi

Erschienen in: Coalgebraic Methods in Computer Science

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

We propose an abstract framework for modeling state-based systems with internal behavior as e.g. given by silent or \(\epsilon \)-transitions. Our approach employs monads with a parametrized fixpoint operator \(\dagger \) to give a semantics to those systems and implement a sound procedure of abstraction of the internal transitions, whose labels are seen as the unit of a free monoid. More broadly, our approach extends the standard coalgebraic framework for state-based systems by taking into account the algebraic structure of the labels of their transitions. This allows to consider a wide range of other examples, including Mazurkiewicz traces for concurrent systems.

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 "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

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
Vorheriges Kapitel Coalgebraic Multigames
Nächstes Kapitel On Coalgebras with Internal Moves
Fußnoten
1
More generally, one could consider labels from an arbitrary monoid.
 
2
The equality of least and canonical fixpoint solutions can be used to state a stronger result, namely that canonical fixpoint solutions satisfy the axioms of iteration theories (cf. Example 2.10). However, the double dagger law is the only property that we need here, explaining the statement of Corollary 4.3.
 
3
Mazurkiewicz traces were defined over labelled transition systems which are similar to NDA but where every state is final. For simplicity, we consider LTS here immediately as NDA.
 
Literatur
1.
2.
Adámek, J., Milius, S., Velebil, J.: Elgot theories: a new perspective of the equational properties of iteration. Math. Structures Comput. Sci. 21(2), 417–480 (2011)MATHMathSciNet
3.
Asada, K., Hidaka, S., Kato, H., Hu, Z., Nakano, K.: A parameterized graph transformation calculus for finite graphs with monadic branches. In: Peña, R., Schrijvers, T. (eds.) PPDP, pp. 73–84. ACM (2013)
4.
Balan, A., Kurz, A.: On coalgebras over algebras. Theoret. Comput. Sci. 412(38), 4989–5005 (2011)MATHMathSciNet
5.
6.
Bloom, S.L., Ésik, Z.: Iteration Theories: The Equational Logic of Iterative. EATCS Monographs on Theoretical Computer Science. Springer, Heidelberg (1993)MATH
7.
Bonsangue, M.M., Hansen, H.H., Kurz, A., Rot, J.: Presenting distributive laws. In: Heckel and Milius [15], pp. 95–109
8.
Main, M.G., Melton, A.C., Mislove, M.W., Schmidt, D., Brookes, S.D. (eds.): MFPS 1993. LNCS, vol. 802. Springer, Heidelberg (1994)MATH
9.
Freyd, P.J.: Remarks on Algebraically Compact Categories. London Mathematical Society Lecture Notes Series, vol. 177. Cambridge University Press, London (1992)
10.
Gadducci, F., Montanari, U.: The tile model. In: Plotkin, G.D., Stirling, C., Tofte, M. (eds.) Proof, Language, and Interaction, pp. 133–166. MIT Press, Boston (2000)
11.
Hasuo, I., Jacobs, B., Sokolova, A.: Generic forward and backward simulations. In: (Partly in Japanese) Proceedings of JSSST Annual Meeting (2006)
12.
Hasuo, I., Jacobs, B., Sokolova, A.: Generic trace semantics via coinduction. Log. Methods Comput. Sci. 3(4:11), 1–36 (2007)MathSciNet
13.
Heckel, R., Milius, S. (eds.): Algebra and Coalgebra in Computer Science. Lecture Notes in Computer Science, vol. 8089. Springer, Heidelberg (2013)MATH
14.
Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Wesley, Lebanon (2006)
15.
Johnstone, P.: Adjoint lifting theorems for categories of algebras. Bull. London Math. Soc. 7, 294–297 (1975)MATHMathSciNet
16.
Kelly, G.M.: A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on. Bull. Austral. Math. Soc. 22, 1–83 (1980)MATHMathSciNet
17.
Mazurkiewicz, A.: Concurrent program schemes and their interpretation. DAIMI PB-78, Computer Science Department, Aarhus University (1977)
18.
Mac Lane, S.: Categories for the Working Mathematician. Springer, Berlin (1971)MATH
19.
Milius, S., Palm, T., Schwencke, D.: Complete iterativity for algebras with effects. In: Kurz, A., Lenisa, M., Tarlecki, A. (eds.) CALCO 2009. LNCS, vol. 5728, pp. 34–48. Springer, Heidelberg (2009)
20.
Mulry, P.S.: Lifting theorems for Kleisli categories. In: Brookes et al. [10], pp. 304–319
21.
Rabinovich, A.M.: A complete axiomatisation for trace congruence of finite state behaviors. In: Brookes et al. [10], pp. 530–543
22.
Silva, A., Westerbaan, B.: A coalgebraic view of \(\varepsilon \)-transitions. In: Heckel and Milius [15], pp. 267–281
23.
Sobociński, P.: Relational presheaves as labelled transition systems. In: Pattinson, D., Schröder, L. (eds.) CMCS 2012. LNCS, vol. 7399, pp. 40–50. Springer, Heidelberg (2012)
24.
Turi, D., Plotkin, G.: Towards a mathematical operational semantics. In: Proceedings of Logic in Computer Science (LICS’97). IEEE Computer Society (1997)
Metadaten
Titel
How to Kill Epsilons with a Dagger
verfasst von
Filippo Bonchi
Stefan Milius
Alexandra Silva
Fabio Zanasi
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
Buch
Coalgebraic Methods in Computer Science

Print ISBN: 978-3-662-44123-7

Electronic ISBN: 978-3-662-44124-4

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-3-662-44124-4_4