DROPS

Document

DOI: 10.4230/LIPIcs.CALCO.2015.304

Revisiting the Institutional Approach to Herbrand’s Theorem

Authors: Ionut Tutu and José Luiz Fiadeiro

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

Abstract

More than a decade has passed since Herbrand’s theorem was first generalized to arbitrary institutions, enabling in this way the development of the logic-programming paradigm over formalisms beyond the conventional framework of relational first-order logic. Despite the mild assumptions of the original theory, recent developments have shown that the institution-based approach cannot capture constructions that arise when service-oriented computing is presented as a form of logic programming, thus prompting the need for a new perspective on Herbrand’s theorem founded instead upon a concept of generalized substitution system. In this paper, we formalize the connection between the institution- and the substitution-system-based approach to logic programming by investigating a number of features of institutions, like the existence of a quantification space or of representable substitutions, under which they give rise to suitable generalized substitution systems. Building on these results, we further show how the original institution independent versions of Herbrand’s theorem can be obtained as concrete instances of a more general result.

Cite as

Ionut Tutu and José Luiz Fiadeiro. Revisiting the Institutional Approach to Herbrand’s Theorem. In 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 35, pp. 304-319, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{tutu_et_al:LIPIcs.CALCO.2015.304,
  author =	{Tutu, Ionut and Fiadeiro, Jos\'{e} Luiz},
  title =	{{Revisiting the Institutional Approach to Herbrand’s Theorem}},
  booktitle =	{6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015)},
  pages =	{304--319},
  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.304},
  URN =		{urn:nbn:de:0030-drops-55419},
  doi =		{10.4230/LIPIcs.CALCO.2015.304},
  annote =	{Keywords: Institution theory, Substitution systems, Herbrand’s theorem}
}

Document

DOI: 10.4230/DagSemProc.05081.1

05081 Abstracts Collection – Foundations of Global Computing

Authors: José Luiz Fiadeiro, Ugo Montanari, and Martin Wirsing

Published in: Dagstuhl Seminar Proceedings, Volume 5081, Foundations of Global Computing (2006)

Abstract

From 20.02.05 to 25.02.05, the Dagstuhl Seminar 05081 on ``Foundations of Global Computing'' 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

José Luiz Fiadeiro, Ugo Montanari, and Martin Wirsing. 05081 Abstracts Collection – Foundations of Global Computing. In Foundations of Global Computing. Dagstuhl Seminar Proceedings, Volume 5081, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fiadeiro_et_al:DagSemProc.05081.1,
  author =	{Fiadeiro, Jos\'{e} Luiz and Montanari, Ugo and Wirsing, Martin},
  title =	{{05081 Abstracts Collection – Foundations of Global Computing}},
  booktitle =	{Foundations of Global Computing},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5081},
  editor =	{Jos\'{e} Luiz Fiadeiro and Ugo Montanari and Martin Wirsing},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05081.1},
  URN =		{urn:nbn:de:0030-drops-4590},
  doi =		{10.4230/DagSemProc.05081.1},
  annote =	{Keywords: Global Computing}
}

Search Results

Documents authored by Fiadeiro, José Luiz

Revisiting the Institutional Approach to Herbrand’s Theorem

Abstract

Cite as

05081 Abstracts Collection – Foundations of Global Computing

Abstract

Cite as

Thanks for your feedback!

Could not send message