Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Higher-Order Languages: Bisimulation and Coinductive Equivalences (Extended Abstract) Read chapter Read first chapter

2014 | OriginalPaper | Chapter

A Coalgebraic View of Characteristic Formulas in Equational Modal Fixed Point Logics

Authors : Sebastian Enqvist, Joshua Sack

Published in: Coalgebraic Methods in Computer Science

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The literature on process theory and structural operational semantics abounds with various notions of behavioural equivalence and, more generally, simulation preorders. An important problem in this area from the point of view of logic is to find formulas that characterize states in finite transition systems with respect to these various relations. Recent work by Aceto et al. shows how such characterizing formulas in equational modal fixed point logics can be obtained for a wide variety of behavioural preorders using a single method. In this paper, we apply this basic insight from the work by Aceto et al. to Baltag’s “logics for coalgebraic simulation” to obtain a general result that yields characteristic formulas for a wide range of relations, including strong bisimilarity, simulation, as well as bisimulation and simulation on Markov chains and more. Hence this paper both generalizes the work of Aceto et al. and makes explicit the coalgebraic aspects of their work.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter On Coalgebras with Internal Moves
next chapter Coalgebraic Simulations and Congruences
Footnotes
1
Here, for lax extensions \(L_1\) and \(L_2\) we define \(L_1 \cap L_2\) by \(R \mapsto L_1 R \cap L_2 R\).
 
2
Given a mapping \(h : X \rightarrow Y\), \(Qh : QY \rightarrow QX\) is defined by \(Qh(Z) = h^{-1}[Z]\).
 
3
To be concrete, we can take \(\varSigma _n = T(n)\), and we can define the action of \(p_X\) on \((\sigma ,u_1,\ldots ,u_n) \in \varSigma _n \times X^n\) by
$$p_X(\sigma ,u_1,\ldots ,u_n) = Th(\sigma ),$$
where \(h : n \rightarrow X\) is the mapping defined by \(i \mapsto u_i\). These details will not be relevant to us, however. All we need to know is that \(p\) is a natural transformation, and each of its components is surjective.
 
Literature
1.
Adámek, J., Gumm, H.P., Trnková, V.: Presentation of set functors: a coalgebraic perspective. J. Logic Comput. 20(5), 991–1015 (2010)CrossRefMATHMathSciNet
2.
Aceto, L., Ingolfsdottir, A., Levy, P., Sack, J.: Characteristic formulae for fixed-point semantics: a general framework. Math. Struct. Comput. Sci. 22(02), 125–173 (2012)CrossRefMATHMathSciNet
3.
4.
Barr, M.: Relational algebras. In: MacLane, S., et al. (eds.) Reports of the Midwest Category Seminar IV. Lecture Notes in Mathematics, vol. 137, pp. 39–55. Springer, Heidelberg (1970)CrossRef
5.
6.
van Breugel, F., Mislove, M., Ouaknine, J., Worrell, J.: Domain theory, testing and simulation for labelled Markov processes. Theor. Comput. Sci. 333, 171–197 (2005)CrossRefMATH
7.
8.
Kurz, A., Leal, R.: Equational coalgebraic logic. In: Abramsky, S., Mislove, M., Palamidessi, C. (eds.): Proceedings of the 25th Conference on Mathematical Foundations of Programming Semantics (MFPS 2009) Electronic Notes in Theoretical Computer Science, vol. 249, pp. 333–356 (2009)
9.
Levy, P.B.: Similarity quotients as final coalgebras. In: Hofmann, M. (ed.) FOSSACS 2011. LNCS, vol. 6604, pp. 27–41. Springer, Heidelberg (2011) CrossRef
10.
Marti, J.: Relation liftings in coalgebraic modal logic. M.Sc. thesis, Institute for Logic, Language and Computation, University of Amsterdam (2011)
11.
Marti, J., Venema, Y.: Lax extensions of coalgebra functors. In: Pattinson, D., Schröder, L. (eds.) CMCS 2012. LNCS, vol. 7399, pp. 150–169. Springer, Heidelberg (2012) CrossRef
12.
Marti, J., Venema, Y.: Lax extensions of coalgebra functors and their logics. J. Comput. Syst. Sci. (2014), to appear
13.
14.
Müller-Olm, M.: Derivation of characteristic formulae. Electron. Notes Theor. Comput. Sci. 18, 159–170 (1998)CrossRef
15.
Sack, J., Zhang, L.: A general framework for probabilistic characterizing formulae. In: Kuncak, V., Rybalchenko, A. (eds.) VMCAI 2012. LNCS, vol. 7148, pp. 396–411. Springer, Heidelberg (2012) CrossRef
16.
Segala, R., Lynch, N.: Probabilistic simulations for probabilistic processes. Nord. J. Comput. 2(2), 250–273 (1995)MATHMathSciNet
17.
Thijs, A.: Simulation and fixpoint semantics. Ph.D. thesis, University of Groningen (1996)
18.
Metadata
Title
A Coalgebraic View of Characteristic Formulas in Equational Modal Fixed Point Logics
Authors
Sebastian Enqvist
Joshua Sack
Copyright Year
2014
Publisher
Springer Berlin Heidelberg
Book
Coalgebraic Methods in Computer Science

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

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

Copyright Year: 2014

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

Premium Partner

    Image Credits