Search

Your search keyword '"Initial algebra"' showing total 282 results
Start Over Descriptor "Initial algebra"
282 results on '"Initial algebra"'

1. Presenting the Sierpinski Gasket in Various Categories of Metric Spaces.

Author

Ratnayake, Jayampathy, Manokaran, Annanthakrishna, Jayewardene, Romaine, Noquez, Victoria, and Moss, Lawrence S.

Abstract

This paper studies presentations of the Sierpinski gasket as a final coalgebra for a functor on three categories of metric spaces with additional designated points. The three categories which we study differ on their morphisms: one uses short (non-expanding) maps, the second uses continuous maps, and the third uses Lipschitz maps. The functor in all cases is very similar to what we find in the standard presentation of the gasket as an attractor. It was previously known that the Sierpinski gasket is bilipschitz equivalent (though not isomorhpic) to the final coalgebra of this functor in the category with short maps, and that final coalgebra is obtained by taking the completion of the initial algebra. In this paper, we prove that the Sierpiniski gasket itself is the final coalgebra in the category with continuous maps, though it does not occur as the completion of the initial algebra. In the Lipschitz setting, we show that the final coalgebra for this functor does not exist. [ABSTRACT FROM AUTHOR]

Published
2024
Full Text
View/download PDF

2. On Well-Founded and Recursive Coalgebras

Author

Adámek, Jiří, Milius, Stefan, Moss, Lawrence S., Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Goubault-Larrecq, Jean, editor, and König, Barbara, editor

Published
2020
Full Text
View/download PDF

3. Gaussian graphical models with toric vanishing ideals.

Author

Misra, Pratik and Sullivant, Seth

Subjects
*COMPLETE graphs, *COMPUTATIONAL biology, *CONES, *LOGICAL prediction, *COVARIANCE matrices
Abstract

Gaussian graphical models are semi-algebraic subsets of the cone of positive definite covariance matrices. They are widely used throughout natural sciences, computational biology and many other fields. Computing the vanishing ideal of the model gives us an implicit description of the model. In this paper, we resolve two conjectures given by Sturmfels and Uhler. In particular, we characterize those graphs for which the vanishing ideal of the Gaussian graphical model is generated in degree 1 and 2. These turn out to be the Gaussian graphical models whose ideals are toric ideals, and the resulting graphs are the 1-clique sums of complete graphs. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

4. ALGEBRAIC COCOMPLETENESS AND FINITARY FUNCTORS.

Author

ADÁMEK, JIŘÍ

Subjects
ALGEBRA, CARDINAL numbers
Abstract

A number of categories is presented that are algebraically complete and cocomplete, i.e., every endofunctor has an initial algebra and a terminal coalgebra. Example: assuming GCH, the category Setμ of sets of power at most λ has that property, whenever λ is an uncountable regular cardinal. For all finitary (and, more generally, all precontinuous) set functors the initial algebra and terminal coalgebra are proved to carry a canonical partial order with the same ideal completion. And they also both carry a canonical ultrametric with the same Cauchy completion. Finally, all endofunctors of the category Setλ are finitary if λ has countable cofinality and there are no measurable cardinals μ ≤ λ. [ABSTRACT FROM AUTHOR]

Published
2021
Full Text
View/download PDF

5. Locally Nameless Sets

Author

Pitts, AM, Pitts, AM [0000-0001-7775-3471], and Apollo - University of Cambridge Repository

Subjects
category theory, initial algebra, metatheory of syntax, locally nameless, Safety, Risk, Reliability and Quality, Agda, Software, name binding, cofinite quantification
Abstract

This paper provides a new mathematical foundation for the locally nameless representation of syntax with binders, one informed by nominal techniques. It gives an equational axiomatization of two key locally nameless operations, "variable opening" and "variable closing" and shows that a lot of the locally nameless infrastructure can be defined from that in a syntax-independent way, including crucially a "shift" functor for name binding. That functor operates on a category whose objects we call locally nameless sets . Functors combining shift with sums and products have initial algebras that recover the usual locally nameless representation of syntax with binders in the finitary case. We demonstrate this by uniformly constructing such an initial locally nameless set for each instance of Plotkin's notion of binding signature. We also show by example that the shift functor is useful for locally nameless sets of a semantic rather than a syntactic character. The category of locally nameless sets is proved to be isomorphic to a known topos of finitely supported M-sets, where M is the full transformation monoid on a countably infinite set. A corollary of the proof is that several categories that have been used in the literature to model variable renaming operations on syntax with binders are all equivalent to each other and to the category of locally nameless sets.

Published
2023
Full Text
View/download PDF

6. A Coalgebraic View of Bar Recursion and Bar Induction

Author

Capretta, Venanzio, Uustalu, Tarmo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jacobs, Bart, editor, and Löding, Christof, editor

Published
2016
Full Text
View/download PDF

7. Fixed Points of Functors - A Short Abstract

Author

Adámek, Jiří, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Josef, Kittler, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Hasuo, Ichiro, editor

Published
2016
Full Text
View/download PDF

8. The Rational Numbers as an Abstract Data Type.

Author

Bergstra, J. A. and Tucker, J. V.

Subjects
RATIONAL numbers, ALGEBRA, SEMANTICS, MATHEMATICAL models, EQUATIONS, AXIOMATIC set theory, DIVISIBILITY groups
Abstract

We give an equational specification of the field operations on the rational numbers under initial algebra semantics using just total field operations and 12 equations. A consequence of this specification is that 0-1 = 0, an interesting equation consistent with the ring axioms and many properties of division. The existence of an equational specification of the rationals without hidden functions was an open question. We also give an axiomatic examination of the divisibility operator, from which some interesting new axioms emerge along with equational specifications of algebras of rationals, including one with the modulus function. Finally, we state some open problems, including: Does there exist an equational specification of the field operations on the rationals without hidden functions that is a complete term rewriting system? [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

9. The p-adic Integers as Final Coalgebra

Author

Bhattacharya, Prasit, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, de Paiva, Valeria, editor, de Queiroz, Ruy, editor, Moss, Lawrence S., editor, Leivant, Daniel, editor, and de Oliveira, Anjolina G., editor

Published
2015
Full Text
View/download PDF

10. Witnessing (Co)datatypes

Author

Blanchette, Jasmin Christian, Popescu, Andrei, Traytel, Dmitriy, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Vitek, Jan, editor

Published
2015
Full Text
View/download PDF

11. How to Kill Epsilons with a Dagger : A Coalgebraic Take on Systems with Algebraic Label Structure

Author

Bonchi, Filippo, Milius, Stefan, Silva, Alexandra, Zanasi, Fabio, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Kobsa, Alfred, Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Bonsangue, Marcello M., editor

Published
2014
Full Text
View/download PDF

12. Initial Algebras of Terms with Binding and Algebraic Structure

Author

Jacobs, Bart, Silva, Alexandra, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Casadio, Claudia, editor, Coecke, Bob, editor, Moortgat, Michael, editor, and Scott, Philip, editor

Published
2014
Full Text
View/download PDF

13. Cardinals in Isabelle/HOL

Author

Blanchette, Jasmin Christian, Popescu, Andrei, Traytel, Dmitriy, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Klein, Gerwin, editor, and Gamboa, Ruben, editor

Published
2014
Full Text
View/download PDF

14. An Incremental Learning Algorithm for Extended Mealy Automata

Author

Meinke, Karl, Niu, Fei, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Margaria, Tiziana, editor

Published
2012
Full Text
View/download PDF

15. Order-Sorted Equality Enrichments Modulo Axioms

Author

Gutiérrez, Raúl, Meseguer, José, Rocha, Camilo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Durán, Franciso, editor

Published
2012
Full Text
View/download PDF

16. My ADT Shrine

Author

Ehrich, Hans-Dieter, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Mossakowski, Till, editor, and Kreowski, Hans-Jörg, editor

Published
2012
Full Text
View/download PDF

18. Minlog - A Tool for Program Extraction Supporting Algebras and Coalgebras

Author

Berger, Ulrich, Miyamoto, Kenji, Schwichtenberg, Helmut, Seisenberger, Monika, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Corradini, Andrea, editor, Klin, Bartek, editor, and Cîrstea, Corina, editor

Published
2011
Full Text
View/download PDF

19. Type Fusion

Author

Hinze, Ralf, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Johnson, Michael, editor, and Pavlovic, Dusko, editor

Published
2011
Full Text
View/download PDF

20. Monadic Maps and Folds for Multirelations in an Allegory

Author

Martin, C. E., Curtis, S. A., Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Butterfield, Andrew, editor

Published
2010
Full Text
View/download PDF

21. Adjoint Folds and Unfolds : Or: Scything through the Thicket of Morphisms

Author

Hinze, Ralf, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bolduc, Claude, editor, Desharnais, Jules, editor, and Ktari, Béchir, editor

Published
2010
Full Text
View/download PDF

22. Monads Need Not Be Endofunctors

Author

Altenkirch, Thorsten, Chapman, James, Uustalu, Tarmo, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, and Ong, Luke, editor

Published
2010
Full Text
View/download PDF

23. The Foldl Operator as a Coequalizer Using Coq

Author

Blanco, Antonio, Freire, Enrique, Freire, Jose Luis, Paris, Javier, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Moreno-Díaz, Roberto, editor, Pichler, Franz, editor, and Quesada-Arencibia, Alexis, editor

Published
2009
Full Text
View/download PDF

24. Order-Sorted Parameterization and Induction

Author

Meseguer, José, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Palsberg, Jens, editor

Published
2009
Full Text
View/download PDF

25. Traces, Executions and Schedulers, Coalgebraically

Author

Jacobs, Bart, Sokolova, Ana, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kurz, Alexander, editor, Lenisa, Marina, editor, and Tarlecki, Andrzej, editor

Published
2009
Full Text
View/download PDF

26. Complete Iterativity for Algebras with Effects

Author

Milius, Stefan, Palm, Thorsten, Schwencke, Daniel, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kurz, Alexander, editor, Lenisa, Marina, editor, and Tarlecki, Andrzej, editor

Published
2009
Full Text
View/download PDF

27. Extensional Universal Types for Call-by-Value

Author

Asada, Kazuyuki, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Ramalingam, G., editor

Published
2008
Full Text
View/download PDF

28. Bootstrapping Types and Cotypes in HasCASL

Author

Schröder, Lutz, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Mossakowski, Till, editor, Montanari, Ugo, editor, and Haveraaen, Magne, editor

Published
2007
Full Text
View/download PDF

29. Interpreting Polymorphic FPC into Domain Theoretic Models of Parametric Polymorphism

Author

Møgelberg, Rasmus Ejlers, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bugliesi, Michele, editor, Preneel, Bart, editor, Sassone, Vladimiro, editor, and Wegener, Ingo, editor

Published
2006
Full Text
View/download PDF

30. From OBJ to ML to Coq

Author

Chrząszcz, Jacek, Jouannaud, Jean-Pierre, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Futatsugi, Kokichi, editor, Jouannaud, Jean-Pierre, editor, and Meseguer, José, editor

Published
2006
Full Text
View/download PDF

31. Context-Free Languages via Coalgebraic Trace Semantics

Author

Hasuo, Ichiro, Jacobs, Bart, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fiadeiro, José Luiz, editor, Harman, Neil, editor, Roggenbach, Markus, editor, and Rutten, Jan, editor

Published
2005
Full Text
View/download PDF

32. Build, Augment and Destroy, Universally

Author

Ghani, Neil, Uustalu, Tarmo, Vene, Varmo, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Dough, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, and Chin, Wei-Ngan, editor

Published
2004
Full Text
View/download PDF

34. Derivatives of Containers

Author

Abbott, Michael, Altenkirch, Thorsten, Ghani, Neil, McBride, Conor, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, and Hofmann, Martin, editor

Published
2003
Full Text
View/download PDF

35. Formal Methods in CafeOBJ

Author

Futatsugi, Kokichi, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Hu, Zhenjiang, editor, and Rodríguez-Artalejo, Mario, editor

Published
2002
Full Text
View/download PDF

36. A Total Approach to Partial Algebraic Specification

Author

Meseguer, José, Roşu, Grigore, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Widmayer, Peter, editor, Eidenbenz, Stephan, editor, Triguero, Francisco, editor, Morales, Rafael, editor, Conejo, Ricardo, editor, and Hennessy, Matthew, editor

Published
2002
Full Text
View/download PDF

44. Initial Algebras Without Iteration ((Co)algebraic pearls)

Author

Jiří Adámek and Stefan Milius and Lawrence S. Moss, Adámek, Jiří, Milius, Stefan, Moss, Lawrence S., Jiří Adámek and Stefan Milius and Lawrence S. Moss, Adámek, Jiří, Milius, Stefan, and Moss, Lawrence S.

Abstract

The Initial Algebra Theorem by Trnková et al. states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point A of the functor, it uses Pataraia’s theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of A. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.

Published
2021
Full Text
View/download PDF

45. Fibrational Initial Algebra-Final Coalgebra Coincidence over Initial Algebras: Turning Verification Witnesses Upside Down

Author

Mayuko Kori and Ichiro Hasuo and Shin-ya Katsumata, Kori, Mayuko, Hasuo, Ichiro, Katsumata, Shin-ya, Mayuko Kori and Ichiro Hasuo and Shin-ya Katsumata, Kori, Mayuko, Hasuo, Ichiro, and Katsumata, Shin-ya

Abstract

The coincidence between initial algebras (IAs) and final coalgebras (FCs) is a phenomenon that underpins various important results in theoretical computer science. In this paper, we identify a general fibrational condition for the IA-FC coincidence, namely in the fiber over an initial algebra in the base category. Identifying (co)algebras in a fiber as (co)inductive predicates, our fibrational IA-FC coincidence allows one to use coinductive witnesses (such as invariants) for verifying inductive properties (such as liveness). Our general fibrational theory features the technical condition of stability of chain colimits; we extend the framework to the presence of a monadic effect, too, restricting to fibrations of complete lattice-valued predicates. Practical benefits of our categorical theory are exemplified by new "upside-down" witness notions for three verification problems: probabilistic liveness, and acceptance and model-checking with respect to bottom-up tree automata.

Published
2021
Full Text
View/download PDF

46. Basic foundations

Author

Goos, Gerhard, editor, Hartmanis, Juris, editor, Bidoit, Michel, editor, Kreowski, Hans-Jörg, editor, Lescanne, Pierre, editor, Orejas, Fernando, editor, and Sannella, Donald, editor

Published
1991
Full Text
View/download PDF

50. Crisp-determinization of weighted tree automata over strong bimonoids

Author

Zoltán Fülöp, Heiko Vogler, and Dávid Kószó

Subjects
FOS: Computer and information sciences, Initial algebra, Class (set theory), Quantitative Biology::Neurons and Cognition, General Computer Science, Formal Languages and Automata Theory (cs.FL), Computer Science::Neural and Evolutionary Computation, Order (ring theory), Computer Science - Formal Languages and Automata Theory, Theoretical Computer Science, Undecidable problem, Automaton, Combinatorics, Tree (descriptive set theory), Discrete Mathematics and Combinatorics, Algebra over a field, Unit (ring theory), Mathematics
Abstract

We consider weighted tree automata (wta) over strong bimonoids and their initial algebra semantics and their run semantics. There are wta for which these semantics are different; however, for bottom-up deterministic wta and for wta over semirings, the difference vanishes. A wta is crisp-deterministic if it is bottom-up deterministic and each transition is weighted by one of the unit elements of the strong bimonoid. We prove that the class of weighted tree languages recognized by crisp-deterministic wta is the same as the class of recognizable step mappings. Moreover, we investigate the following two crisp-determinization problems: for a given wta ${\cal A}$, (a) does there exist a crisp-deterministic wta which computes the initial algebra semantics of ${\cal A}$ and (b) does there exist a crisp-deterministic wta which computes the run semantics of ${\cal A}$? We show that the finiteness of the Nerode algebra ${\cal N}({\cal A})$ of ${\cal A}$ implies a positive answer for (a), and that the finite order property of ${\cal A}$ implies a positive answer for (b). We show a sufficient condition which guarantees the finiteness of ${\cal N}({\cal A})$ and a sufficient condition which guarantees the finite order property of ${\cal A}$. Also, we provide an algorithm for the construction of the crisp-deterministic wta according to (a) if ${\cal N}({\cal A})$ is finite, and similarly for (b) if ${\cal A}$ has finite order property. We prove that it is undecidable whether an arbitrary wta ${\cal A}$ is crisp-determinizable. We also prove that both, the finiteness of ${\cal N}({\cal A})$ and the finite order property of ${\cal A}$ are undecidable.

Published
2021
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results