Displaying similar documents to “Finite presentability of strongly finite dilators”

Strong functors and interleaving fixpoints in game semantics

Pierre Clairambault (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We describe a sequent calculus with primitives for inductive and coinductive datatypes and equip it with reduction rules allowing a sound translation of Gödel’s system T. We introduce the notion of a , relying on a uniform interpretation of open formulas as strong functors. We show that any -closed category is a sound model for . We then turn to the construction of a concrete -closed category based on Hyland-Ong game semantics. The model relies on three main ingredients:...

-Bicomplete Categories and Parity Games

Luigi Santocanale (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

For an arbitrary category, we consider the least class of functors containing the projections and closed under finite products, finite coproducts, parameterized initial algebras and parameterized final coalgebras, the class of functors that are definable by -terms. We call the category -bicomplete if every -term defines a functor. We provide concrete examples of such categories and explicitly characterize this class of functors for the category of sets and functions. This goal is achieved...

Generalizing Substitution

Tarmo Uustalu (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

It is well known that, given an endofunctor on a category , the initial -algebras (if existing), , the algebras of (wellfounded) -terms over different variable supplies , give rise to a monad with substitution as the extension operation (the free monad induced by the functor ). Moss [17] and Aczel, Adámek, Milius and Velebil [12] have shown that a similar monad, which even enjoys the additional special property of having iterations for all guarded substitution rules (complete...

Equivalences and Congruences on Infinite Conway Games

Furio Honsell, Marina Lenisa, Rekha Redamalla (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Taking the view that infinite plays are , we study and . These admit a sharp presentation, where non-terminating games are seen as a and game contructors, such as , as . We have shown, in a previous paper, that Conway’s theory of terminating games can be rephrased naturally in terms of game . Namely, various conceptually independent notions of can be defined and shown to coincide on Conway’s terminating games. These are...

Equivalences and Congruences on Infinite Conway Games

Furio Honsell, Marina Lenisa, Rekha Redamalla (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

Taking the view that infinite plays are , we study and . These admit a sharp presentation, where non-terminating games are seen as a and game contructors, such as , as . We have shown, in a previous paper, that Conway’s theory of terminating games can be rephrased naturally in terms of game . Namely, various conceptually independent notions of can be defined and shown to coincide on Conway’s terminating games. These are...

Encoding FIX in Object Calculi

Roy L. Crole (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that the type theory introduced by Crole and Pitts [3] can be encoded in variants of Abadi and Cardelli's object calculi. More precisely, we show that the type theory presented with judgements of both equality and operational reduction can be translated into object calculi, and the translation proved sound. The translations we give can be seen as using object calculi as a metalanguge within which can be represented; an analogy can be drawn with Martin Löf's Theory of Arities...

Some algorithms to compute the conjugates of Episturmian morphisms

Gwenael Richomme (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Episturmian morphisms generalize Sturmian morphisms. They are defined as compositions of exchange morphisms and two particular morphisms , and . Epistandard morphisms are the morphisms obtained without considering . In [14], a general study of these morphims and of conjugacy of morphisms is given. Here, given a decomposition of an Episturmian morphism over exchange morphisms and , we consider two problems: how to compute a decomposition of one conjugate of ; how to compute...

Morphisms preserving the set of words coding three interval exchange

Tomáš Hejda (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Any amicable pair , of Sturmian morphisms enables a construction of a ternary morphism which preserves the set of infinite words coding 3-interval exchange. We determine the number of amicable pairs with the same incidence matrix in SL(2,ℕ) and we study incidence matrices associated with the corresponding ternary morphisms .

Easy lambda-terms are not always simple

Alberto Carraro, Antonino Salibra (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

A closed -term is if, for any other closed term , the lambda theory generated by  =  is consistent. Recently, it has been introduced a general technique to prove the easiness of -terms through the semantical notion of simple easiness. Simple easiness implies easiness and allows to prove consistency results construction of suitable filter models of -calculus living in the category of complete partial orderings: given a simple easy term and an arbitrary closed term , it is possible to...

Easy lambda-terms are not always simple

Alberto Carraro, Antonino Salibra (2012)

RAIRO - Theoretical Informatics and Applications

Similarity:

A closed -term is if, for any other closed term , the lambda theory generated by  =  is consistent. Recently, it has been introduced a general technique to prove the easiness of -terms through the semantical notion of simple easiness. Simple easiness implies easiness and allows to prove consistency results construction of suitable filter models of -calculus living in the category of complete partial orderings: given ...

On indecomposable sets with applications

Andrew Lorent (2014)

ESAIM: Control, Optimisation and Calculus of Variations

Similarity:

In this note we show the characteristic function of every indecomposable set in the plane is equivalent to the characteristic function a closed set See Formula in PDF See Formula in PDF . We show by example this is false in dimension three and above. As a corollary to this result we show that for every > 0 a set of finite perimeter can be approximated by a closed subset See Formula in PDF See Formula in PDF with finitely many indecomposable components and with the property that...