License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2015.128
URN: urn:nbn:de:0030-drops-54113
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5411/
Go to the corresponding LIPIcs Volume Portal

Schubert, Aleksy ; Dekkers, Wil ; Barendregt, Henk P.

Automata Theoretic Account of Proof Search

pdf-format:
8.pdf (0.6 MB)

Abstract

Automata theoretical techniques are developed that handle inhabitant search in the simply typed lambda calculus. The automata-theoretic model for inhabitant search, which can be viewed as proof search by the Curry-Howard isomorphism, is proven to be adequate by reduction of the inhabitant existence problem to the emptiness problem for the automata. To strengthen the claim, it is demonstrated that the latter has the same complexity as the former. We also discuss the basic closure properties of the automata.

BibTeX - Entry

@InProceedings{schubert_et_al:LIPIcs:2015:5411,
  author =	{Aleksy Schubert and Wil Dekkers and Henk P. Barendregt},
  title =	{{Automata Theoretic Account of Proof Search}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{128--143},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Stephan Kreutzer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5411},
  URN =		{urn:nbn:de:0030-drops-54113},
  doi =		{10.4230/LIPIcs.CSL.2015.128},
  annote =	{Keywords: simple types, automata, trees, languages of proofs}
}

Keywords: simple types, automata, trees, languages of proofs
Collection: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Issue Date: 2015
Date of publication: 07.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI