Skip to main content

Research Repository

Advanced Search

Professor THORSTEN ALTENKIRCH's Outputs (12)

Combinatory logic and lambda calculus are equal, algebraically (2023)
Presentation / Conference Contribution
Altenkirch, T., Kaposi, A., Šinkarovs, A., & Végh, T. Combinatory logic and lambda calculus are equal, algebraically. Presented at FSCD, Rome, Italy

It is well-known that extensional lambda calculus is equivalent to extensional combinatory logic. In this paper we describe a formalisation of this fact in Cubical Agda. The distinguishing features of our formalisation are the following: (i) Both lan... Read More about Combinatory logic and lambda calculus are equal, algebraically.

The Integers as a Higher Inductive Type (2020)
Presentation / Conference Contribution
Altenkirch, T., & Scoccola, L. (2020, July). The Integers as a Higher Inductive Type. Presented at LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken Germany

We consider the problem of defining the integers in Homotopy Type Theory (HoTT). We can define the type of integers as signed natural numbers (i.e., using a coproduct), but its induction principle is very inconvenient to work with, since it leads to... Read More about The Integers as a Higher Inductive Type.

Free Higher Groups in Homotopy Type Theory (2018)
Presentation / Conference Contribution
Kraus, N., & Altenkirch, T. (2018, July). Free Higher Groups in Homotopy Type Theory. Presented at LICS '18: 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, Oxford United Kingdom

© 2018 ACM. Given a type A in homotopy type theory (HoTT), we can define the free∞-group onA as the loop space of the suspension ofA+1. Equivalently, this free higher group can be defined as a higher inductive type F(A) with constructors unit : F(A),... Read More about Free Higher Groups in Homotopy Type Theory.

Quotient inductive-inductive types (2018)
Presentation / Conference Contribution
Altenkirch, T., Capriotti, P., Dijkstra, G., Kraus, N., & Nordvall Forsberg, F. (2018, April). Quotient inductive-inductive types. Presented at 21st International Conference, FOSSACS 2018, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2018, Thessaloniki, Greece

Higher inductive types (HITs) in Homotopy Type Theory (HoTT) allow the definition of datatypes which have constructors for equalities over the defined type. HITs generalise quotient types and allow to define types which are not sets in the sense of H... Read More about Quotient inductive-inductive types.

Partiality, Revisited: The Partiality Monad as a Quotient Inductive-Inductive Type (2017)
Presentation / Conference Contribution
Altenkirch, T., Danielson, N. A., & Kraus, N. (2017, April). Partiality, Revisited: The Partiality Monad as a Quotient Inductive-Inductive Type. Presented at 20th International Conference, FOSSACS 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, Uppsala, Sweden

Capretta’s delay monad can be used to model partial computations, but it has the “wrong” notion of built-in equality, strong bisimilarity. An alternative is to quotient the delay monad by the “right” notion of equality, weak bisimilarity. However, re... Read More about Partiality, Revisited: The Partiality Monad as a Quotient Inductive-Inductive Type.

Extending Homotopy Type Theory with Strict Equality (2016)
Presentation / Conference Contribution
Altenkirch, T., Capriotti, P., & Kraus, N. (2016, August). Extending Homotopy Type Theory with Strict Equality. Presented at 25th EACSL Annual Conference on Computer Science Logic, CSL 2016., Marseille, France

In homotopy type theory (HoTT), all constructions are necessarily stable under homotopy equivalence. This has shortcomings: for example, it is believed that it is impossible to define a type of semi-simplicial types. More generally, it is difficult a... Read More about Extending Homotopy Type Theory with Strict Equality.

Normalisation by evaluation for dependent types (2016)
Presentation / Conference Contribution
Altenkirch, T., & Kaposi, A. Normalisation by evaluation for dependent types. Presented at FSCD 2016: 1st International Conference on Formal Structures for Computation and Deduction

We develop normalisation by evaluation (NBE) for dependent types based on presheaf categories. Our construction is formulated using internal type theory using quotient inductive types. We use a typed presentation hence there are no preterms or realiz... Read More about Normalisation by evaluation for dependent types.

Type theory in type theory using quotient inductive types (2016)
Presentation / Conference Contribution
Altenkirch, T., & Kaposi, A. (2016, January). Type theory in type theory using quotient inductive types. Presented at POPL '16 The 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St Petersburg, Florida, USA

We present an internal formalisation of a type heory with dependent types in Type Theory using a special case of higher inductive types from Homotopy Type Theory which we call quotient inductive types (QITs). Our formalisation of type theory avoids r... Read More about Type theory in type theory using quotient inductive types.

Some constructions on ω-groupoids (2014)
Presentation / Conference Contribution
Altenkirch, T., Li, N., & Ondřej, R. (2014, July). Some constructions on ω-groupoids. Presented at LFMTP '14: Theory and Practice, Vienna, Austria

Weak ω-groupoids are the higher dimensional generalisation of setoids and are an essential ingredient of the constructive semantics of Homotopy Type Theory [13]. Following up on our previous formalisation [3] and Brunerie's notes [6], we present a ne... Read More about Some constructions on ω-groupoids.

Generalizations of Hedberg’s Theorem (2013)
Presentation / Conference Contribution
Kraus, N., Escardó, M., Coquand, T., & Altenkirch, T. (2013, June). Generalizations of Hedberg’s Theorem. Presented at TLCA: International Conference on Typed Lambda Calculi and Applications, Eindhoven, The Netherlands

As the groupoid interpretation by Hofmann and Streicher shows, uniqueness of identity proofs (UIP) is not provable. Generalizing a theorem by Hedberg, we give new characterizations of types that satisfy UIP. It turns out to be natural in this context... Read More about Generalizations of Hedberg’s Theorem.

When is a function a fold or an unfold? (2001)
Presentation / Conference Contribution
Gibbons, J., Hutton, G., & Altenkirch, T. When is a function a fold or an unfold?. Presented at Workshop on Coalgebraic Methods in Computer Science (4th)

We give a necessary and sufficient condition for when a set-theoretic function can be written using the recursion operator fold, and a dual condition for the recursion operator unfold. The conditions are simple, practically useful, and generic in the... Read More about When is a function a fold or an unfold?.