9 Search Results for "Hughes, John"


Document
First-Order Guarded Coinduction in Coq

Authors: Łukasz Czajka

Published in: LIPIcs, Volume 141, 10th International Conference on Interactive Theorem Proving (ITP 2019)


Abstract
We introduce two coinduction principles and two proof translations which, under certain conditions, map coinductive proofs that use our principles to guarded Coq proofs. The first principle provides an "operational" description of a proof by coinduction, which is easy to reason with informally. The second principle extends the first one to allow for direct proofs by coinduction of statements with existential quantifiers and multiple coinductive predicates in the conclusion. The principles automatically enforce the correct use of the coinductive hypothesis. We implemented the principles and the proof translations in a Coq plugin.

Cite as

Łukasz Czajka. First-Order Guarded Coinduction in Coq. In 10th International Conference on Interactive Theorem Proving (ITP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 141, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{czajka:LIPIcs.ITP.2019.14,
  author =	{Czajka, {\L}ukasz},
  title =	{{First-Order Guarded Coinduction in Coq}},
  booktitle =	{10th International Conference on Interactive Theorem Proving (ITP 2019)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-122-1},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{141},
  editor =	{Harrison, John and O'Leary, John and Tolmach, Andrew},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.14},
  URN =		{urn:nbn:de:0030-drops-110690},
  doi =		{10.4230/LIPIcs.ITP.2019.14},
  annote =	{Keywords: coinduction, Coq, guardedness, corecursion}
}
Document
Vision Paper
Why Classificatory Information of Geographic Regions Is Quantum Information (Vision Paper)

Authors: Thomas Bittner

Published in: LIPIcs, Volume 142, 14th International Conference on Spatial Information Theory (COSIT 2019)


Abstract
This paper gives an information - theoretic argument in support of the claim that there is geographic quantum information. Quantum information is information in the sense of Shannon’s information theory, that, in addition, satisfies two characteristic postulates. The paper aims to show that if the density of information (bits per unit of space) that is possible for classificatory geographic qualities is limited, then it follows that the two characteristic postulates of quantum information are satisfied for information about those geographic qualities.

Cite as

Thomas Bittner. Why Classificatory Information of Geographic Regions Is Quantum Information (Vision Paper). In 14th International Conference on Spatial Information Theory (COSIT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 142, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{bittner:LIPIcs.COSIT.2019.16,
  author =	{Bittner, Thomas},
  title =	{{Why Classificatory Information of Geographic Regions Is Quantum Information}},
  booktitle =	{14th International Conference on Spatial Information Theory (COSIT 2019)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-115-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{142},
  editor =	{Timpf, Sabine and Schlieder, Christoph and Kattenbeck, Markus and Ludwig, Bernd and Stewart, Kathleen},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.COSIT.2019.16},
  URN =		{urn:nbn:de:0030-drops-111088},
  doi =		{10.4230/LIPIcs.COSIT.2019.16},
  annote =	{Keywords: Information theory, quantum information, classification and delineation}
}
Document
A Typing Discipline for Hardware Interfaces

Authors: Jan de Muijnck-Hughes and Wim Vanderbauwhede

Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)


Abstract
Modern Systems-on-a-Chip (SoC) are constructed by composition of IP (Intellectual Property) Cores with the communication between these IP Cores being governed by well described interaction protocols. However, there is a disconnect between the machine readable specification of these protocols and the verification of their implementation in known hardware description languages. Although tools can be written to address such separation of concerns, the tooling is often hand written and used to check hardware designs a posteriori. We have developed a dependent type-system and proof-of-concept modelling language to reason about the physical structure of hardware interfaces using user provided descriptions. Our type-system provides correct-by-construction guarantees that the interfaces on an IP Core will be well-typed if they adhere to a specified standard.

Cite as

Jan de Muijnck-Hughes and Wim Vanderbauwhede. A Typing Discipline for Hardware Interfaces. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 6:1-6:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{demuijnckhughes_et_al:LIPIcs.ECOOP.2019.6,
  author =	{de Muijnck-Hughes, Jan and Vanderbauwhede, Wim},
  title =	{{A Typing Discipline for Hardware Interfaces}},
  booktitle =	{33rd European Conference on Object-Oriented Programming (ECOOP 2019)},
  pages =	{6:1--6:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-111-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{134},
  editor =	{Donaldson, Alastair F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.6},
  URN =		{urn:nbn:de:0030-drops-107983},
  doi =		{10.4230/LIPIcs.ECOOP.2019.6},
  annote =	{Keywords: System-on-a-Chip, AXI, Dependent Types, Substructural Typing}
}
Document
Final Coalgebras from Corecursive Algebras

Authors: Paul Blain Levy

Published in: LIPIcs, Volume 35, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)


Abstract
We give a technique to construct a final coalgebra in which each element is a set of formulas of modal logic. The technique works for both the finite and the countable powerset functors. Starting with an injectively structured, corecursive algebra, we coinductively obtain a suitable subalgebra called the "co-founded part". We see—first with an example, and then in the general setting of modal logic on a dual adjunction—that modal theories form an injectively structured, corecursive algebra, so that this construction may be applied. We also obtain an initial algebra in a similar way. We generalize the framework beyond Set to categories equipped with a suitable factorization system, and look at the examples of Poset and Set-op .

Cite as

Paul Blain Levy. Final Coalgebras from Corecursive Algebras. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 221-237, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{levy:LIPIcs.CALCO.2015.221,
  author =	{Levy, Paul Blain},
  title =	{{Final Coalgebras from Corecursive Algebras}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{221--237},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-84-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{35},
  editor =	{Moss, Lawrence S. and Sobocinski, Pawel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2015.221},
  URN =		{urn:nbn:de:0030-drops-55365},
  doi =		{10.4230/LIPIcs.CALCO.2015.221},
  annote =	{Keywords: coalgebra, modal logic, bisimulation, category theory, factorization system}
}
Document
DynSem: A DSL for Dynamic Semantics Specification

Authors: Vlad Vergu, Pierre Neron, and Eelco Visser

Published in: LIPIcs, Volume 36, 26th International Conference on Rewriting Techniques and Applications (RTA 2015)


Abstract
The formal semantics of a programming language and its implementation are typically separately defined, with the risk of divergence such that properties of the formal semantics are not properties of the implementation. In this paper, we present DynSem, a domain-specific language for the specification of the dynamic semantics of programming languages that aims at supporting both formal reasoning and efficient interpretation. DynSem supports the specification of the operational semantics of a language by means of statically typed conditional term reduction rules. DynSem supports concise specification of reduction rules by providing implicit build and match coercions based on reduction arrows and implicit term constructors. DynSem supports modular specification by adopting implicit propagation of semantic components from I-MSOS, which allows omitting propagation of components such as environments and stores from rules that do not affect those. DynSem supports the declaration of native operators for delegation of aspects of the semantics to an external definition or implementation. DynSem supports the definition of auxiliary meta-functions, which can be expressed using regular reduction rules and are subject to semantic component propagation. DynSem specifications are executable through automatic generation of a Java-based AST interpreter.

Cite as

Vlad Vergu, Pierre Neron, and Eelco Visser. DynSem: A DSL for Dynamic Semantics Specification. In 26th International Conference on Rewriting Techniques and Applications (RTA 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 36, pp. 365-378, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{vergu_et_al:LIPIcs.RTA.2015.365,
  author =	{Vergu, Vlad and Neron, Pierre and Visser, Eelco},
  title =	{{DynSem: A DSL for Dynamic Semantics Specification}},
  booktitle =	{26th International Conference on Rewriting Techniques and Applications (RTA 2015)},
  pages =	{365--378},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-85-9},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{36},
  editor =	{Fern\'{a}ndez, Maribel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2015.365},
  URN =		{urn:nbn:de:0030-drops-52080},
  doi =		{10.4230/LIPIcs.RTA.2015.365},
  annote =	{Keywords: programming languages, dynamic semantics, reduction semantics, semantics engineering, IDE, interpreters, modularity}
}
Document
04381 Abstracts Collection – Dependently Typed Programming

Authors: Thorsten Altenkirch, Martin Hofmann, and John Hughes

Published in: Dagstuhl Seminar Proceedings, Volume 4381, Dependently Typed Programming (2005)


Abstract
From 12.09.04 to 17.09.04, the Dagstuhl Seminar 04381 ``Dependently Typed Programming'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Thorsten Altenkirch, Martin Hofmann, and John Hughes. 04381 Abstracts Collection – Dependently Typed Programming. In Dependently Typed Programming. Dagstuhl Seminar Proceedings, Volume 4381, pp. 1-8, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{altenkirch_et_al:DagSemProc.04381.1,
  author =	{Altenkirch, Thorsten and Hofmann, Martin and Hughes, John},
  title =	{{04381 Abstracts Collection – Dependently Typed Programming}},
  booktitle =	{Dependently Typed Programming},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4381},
  editor =	{Thorsten Altenkirch and Martin Hofmann and John Hughes},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04381.1},
  URN =		{urn:nbn:de:0030-drops-1864},
  doi =		{10.4230/DagSemProc.04381.1},
  annote =	{Keywords: dependently typed programming}
}
Document
Interactive Programs and Weakly Final Coalgebras in Dependent Type Theory (Extended Version)

Authors: Anton Setzer and Peter Hancock

Published in: Dagstuhl Seminar Proceedings, Volume 4381, Dependently Typed Programming (2005)


Abstract
We reconsider the representation of interactive programs in dependent type theory that the authors proposed in earlier papers. Whereas in previous versions the type of interactive programs was introduced in an ad hoc way, it is here defined as a weakly final coalgebra for a general form of polynomial functor. The are two versions: in the first the interface with the real world is fixed, while in the second the potential interactions can depend on the history of previous interactions. The second version may be appropriate for working with specifications of interactive programs. We focus on command-response interfaces, and consider both client and server programs, that run on opposite sides such an interface. We give formation/introduction/elimination/equality rules for these coalgebras. These are explored in two dimensions: coiterative versus corecursive, and monadic versus non-monadic. We also comment upon the relationship of the corresponding rules with guarded induction. It turns out that the introduction rules are nothing but a slightly restricted form of guarded induction. However, the form in which we write guarded induction is not recursive equations (which would break normalisation – we show that type checking becomes undecidable), but instead involves an elimination operator in a crucial way.

Cite as

Anton Setzer and Peter Hancock. Interactive Programs and Weakly Final Coalgebras in Dependent Type Theory (Extended Version). In Dependently Typed Programming. Dagstuhl Seminar Proceedings, Volume 4381, pp. 1-30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2005)


Copy BibTex To Clipboard

@InProceedings{setzer_et_al:DagSemProc.04381.2,
  author =	{Setzer, Anton and Hancock, Peter},
  title =	{{Interactive Programs and Weakly Final Coalgebras in Dependent Type Theory (Extended Version)}},
  booktitle =	{Dependently Typed Programming},
  pages =	{1--30},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4381},
  editor =	{Thorsten Altenkirch and Martin Hofmann and John Hughes},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04381.2},
  URN =		{urn:nbn:de:0030-drops-1768},
  doi =		{10.4230/DagSemProc.04381.2},
  annote =	{Keywords: Dependently types programming , interactive programs , coalgebras , weakly final coalgebras , coiteration , corecursion , monad}
}
Document
Functional Programming in the Real World (Dagstuhl Seminar 9420)

Authors: Robert Giegerich and John Hughes

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Robert Giegerich and John Hughes. Functional Programming in the Real World (Dagstuhl Seminar 9420). Dagstuhl Seminar Report 89, pp. 1-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (1994)


Copy BibTex To Clipboard

@TechReport{giegerich_et_al:DagSemRep.89,
  author =	{Giegerich, Robert and Hughes, John},
  title =	{{Functional Programming in the Real World (Dagstuhl Seminar 9420)}},
  pages =	{1--22},
  ISSN =	{1619-0203},
  year =	{1994},
  type = 	{Dagstuhl Seminar Report},
  number =	{89},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.89},
  URN =		{urn:nbn:de:0030-drops-149776},
  doi =		{10.4230/DagSemRep.89},
}
Document
Functional Languages: Compiler Technology and Parallelism (Dagstuhl Seminar 9213)

Authors: Werner Damm, Chris Hankin, and John Hughes

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)


Abstract

Cite as

Werner Damm, Chris Hankin, and John Hughes. Functional Languages: Compiler Technology and Parallelism (Dagstuhl Seminar 9213). Dagstuhl Seminar Report 36, pp. 1-32, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (1992)


Copy BibTex To Clipboard

@TechReport{damm_et_al:DagSemRep.36,
  author =	{Damm, Werner and Hankin, Chris and Hughes, John},
  title =	{{Functional Languages: Compiler Technology and Parallelism (Dagstuhl Seminar 9213)}},
  pages =	{1--32},
  ISSN =	{1619-0203},
  year =	{1992},
  type = 	{Dagstuhl Seminar Report},
  number =	{36},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.36},
  URN =		{urn:nbn:de:0030-drops-149240},
  doi =		{10.4230/DagSemRep.36},
}
  • Refine by Author
  • 3 Hughes, John
  • 1 Altenkirch, Thorsten
  • 1 Bittner, Thomas
  • 1 Czajka, Łukasz
  • 1 Damm, Werner
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Type theory
  • 1 Hardware → System on a chip
  • 1 Software and its engineering → System description languages
  • 1 Theory of computation → Logic and verification
  • 1 Theory of computation → Quantum information theory

  • Refine by Keyword
  • 2 corecursion
  • 1 AXI
  • 1 Coq
  • 1 Dependent Types
  • 1 Dependently types programming
  • Show More...

  • Refine by Type
  • 9 document

  • Refine by Publication Year
  • 3 2019
  • 2 2005
  • 2 2015
  • 1 1992
  • 1 1994

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail