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:
Fixed Points of Functors - A Short Abstract Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Product Rules and Distributive Laws

verfasst von : Joost Winter

Erschienen in: Coalgebraic Methods in Computer Science

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

We give a categorical perspective on various product rules, including Brzozowski’s product rule (\((st)_a = s_a t + o(s) t_a\)) and the familiar rule of calculus (\((st)_a = s_a t + s t_a\)). It is already known that these product rules can be represented using distributive laws, e.g. via a suitable quotient of a GSOS law. In this paper, we cast these product rules into a general setting where we have two monads S and T, a (possibly copointed) behavioural functor F, a distributive law of T over S, a distributive law of S over F, and a suitably defined distributive law \(TF \Rightarrow FST\). We introduce a coherence axiom giving a sufficient and necessary condition for such triples of distributive laws to yield a new distributive law of the composite monad ST over F, allowing us to determinize FST-coalgebras into lifted F coalgebras via a two step process whenever this axiom holds.

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 Category Theoretic Semantics for Theorem Proving in Logic Programming: Embracing the Laxness
Nächstes Kapitel On the Logic of Generalised Metric Spaces
Fußnoten
1
For a semiring K that is not commutative, one can define two distinct monad structures on \(\mathrm {Lin}_{K}({-})\), with a different multiplication, one corresponding to left-K-semimodules, and one corresponding to right K-semimodules. When K is commutative, these two monads are identical.
 
2
In the literature often called a unital associative algebra.
 
3
See e.g. [Bec69] for \(\mathbb {Z}\) and [Jac06a] for \(\mathbb {N}\) and \(\mathbb {B}\).
 
4
If K is not commutative, we can consider left K-semimodules, but for this paper, this is not relevant.
 
5
called linear weighted automata in e.g. [BBB+12].
 
6
In some of the literature, monads are called triples, but in this paper it simply means a list of three elements.
 
Literatur
[Awo10]
Awodey, S.: Category Theory. Oxford University Press, Oxford (2010)MATH
[Bar04]
Bartels, F.: On generalized coinduction and probabilistic specification formats. Ph.D. thesis, Vrije Universiteit Amsterdam (2004)
[BBB+12]
Bonchi, F., Bonsangue, M.M., Boreale, M., Rutten, J., Silva, A.: A coalgebraic perspective on linear weighted automata. Inf. Comput. 211, 77–105 (2012)MathSciNetCrossRefMATH
[Bec69]
Beck, J.: Distributive laws. In: Eckmann, B. (ed.) Seminar on Triples and Categorical Homology Theory, pp. 119–140. Springer, Heidelberg (1969)CrossRef
[BHKR13]
Bonsangue, M.M., Hansen, H.H., Kurz, A., Rot, J.: Presenting distributive laws. In: Heckel, R., Milius, S. (eds.) CALCO 2013. LNCS, vol. 8089, pp. 95–109. Springer, Heidelberg (2013)CrossRef
[BMSZ15]
[BRW12]
Bonsangue, M.M., Rutten, J., Winter, J.: Defining context-free power series coalgebraically. In: Pattinson and Schröder [PS12], pp. 20–39
[Brz64]
[BW85]
Barr, M., Wells, C.: Toposes, Triples, and Theories. Grundlehren der mathematischen Wissenschaften. Springer, New York (1985)CrossRefMATH
[Che07]
[Eil76]
Eilenberg, S.: Automata, Languages, and Machines. Academic Press Inc., Orlando (1976)MATH
[Jac06a]
Jacobs, B.: A bialgebraic review of deterministic automata, regular expressions and languages. In: Futatsugi, K., Jouannaud, J.-P., Meseguer, J. (eds.) Algebra, Meaning, and Computation. LNCS, vol. 4060, pp. 375–404. Springer, Heidelberg (2006)CrossRef
[Jac06b]
[JSS12]
Jacobs, B., Silva, A., Sokolova, A.: Trace semantics via determinization. In: Pattinson and Schröder [PS12], pp. 109–129
[Kli11]
Klin, B.: Bialgebras for structural operational semantics: an introduction. Theoret. Comput. Sci. 412(38), 5043–5069 (2011)MathSciNetCrossRefMATH
[LPW00]
Lenisa, M., Power, J., Watanabe, H.: Distributivity for endofunctors, pointed and co-pointed endofunctors, monads and comonads. Electr. Notes Theor. Comput. Sci. 33, 230–260 (2000)MathSciNetCrossRefMATH
[Mac71]
MacLane, S.: Categories for the Working Mathematician. Springer, New York (1971)MATH
[MMS13]
Milius, S., Moss, L.S., Schwencke, D.: Abstract GSOS rules and a modular treatment of recursive definitions. Logical Methods Comput. Sci. 9(3) (2013)
[MPW16]
Milius, S., Pattinson, D., Wißmann, T.: A new foundation for finitary corecursion. CoRR, abs/1601.01532 (2016)
[PS12]
Pattinson, D., Schröder, L. (eds.): CMCS 2012. LNCS, vol. 7399. Springer, Heidelberg (2012)MATH
[RR08]
Rosenkranz, M., Regensburger, G.: Integro-differential polynomials and operators. In: Proceedings of the Twenty-First International Symposium on Symbolic and Algebraic Computation, ISSAC 2008, pp. 261–268. ACM, New York (2008)
[Rut98]
Rutten, J.J.M.M.: Automata and coinduction (an exercise in coalgebra). In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 194–218. Springer, Heidelberg (1998)CrossRef
[Rut00]
[Rut03]
Rutten, J.: Behavioural differential equations: a coinductive calculus of streams, automata, and power series. Theoret. Comput. Sci. 308(1–3), 1–53 (2003)MathSciNetCrossRefMATH
[Rut05]
[SBBR10]
Silva, A., Bonchi, F., Bonsangue, M.M., Rutten, J.: Generalizing the powerset construction, coalgebraically. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS. LIPIcs, vol. 8, pp. 272–283. Schloss Dagstuhl–Leibniz-Zentrum für Informatik (2010)
[SBBR13]
Silva, A., Bonchi, F., Bonsangue, M., Rutten, J.: Generalizing determinization from automata to coalgebras. Logical Methods Comput. Sci. 9(1) (2013)
[Sch14]
Schwencke, D.: Compositional and effectful recursive specification formats. Ph.D. thesis, Technische Universität Braunschweig (2014)
[WBR11]
Winter, J., Bonsangue, M.M., Rutten, J.: Context-free languages, coalgebraically. In: Corradini, A., Klin, B., Cîrstea, C. (eds.) CALCO 2011. LNCS, vol. 6859, pp. 359–376. Springer, Heidelberg (2011)CrossRef
[WBR13]
Winter, J., Bonsangue, M.M., Rutten, Jan J. M. M : Coalgebraic characterizations of context-free languages. Logical Methods Comput. Sci. 9(3:14) (2013)
[Win14]
Winter, J.: Coalgebraic characterizations of automata-theoretic classes. Ph.D. thesis, Radboud Universiteit Nijmegen (2014)
[Wor09]
Worthington, J.: Automata, representations, and proofs. Ph.D. thesis, Cornell University (2009)
Metadaten
Titel
Product Rules and Distributive Laws
verfasst von
Joost Winter
Copyright-Jahr
2016
Buch
Coalgebraic Methods in Computer Science

Print ISBN: 978-3-319-40369-4

Electronic ISBN: 978-3-319-40370-0

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-40370-0_8