<div class="csl-bib-body">
<div class="csl-entry">Afshari, B., Hetzl, S., & Leigh, G. (2015). Herbrand Disjunctions, Cut Elimination and Context-Free Tree Grammars. In T. Altenkirch (Ed.), <i>13th International Conference on Typed Lambda Calculi and Applications - TLCA 2015</i> (pp. 1–16). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.TLCA.2015.1</div>
</div>
-
dc.identifier.isbn
978-3-939897-87-3
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/41409
-
dc.description.abstract
Recently a new connection between proof theory and formal language theory was introduced. It was shown that the operation of cut elimination for proofs in first-order predicate logic involving Pi_1-cuts corresponds to computing the language of a particular class of regular tree grammars. The present paper expands this connection to the level of Pi_2-cuts. Given a proof pi of a Sigma_1 formula with cuts only on Pi_2 formulæ, we show there is associated to pi a natural context-free tree grammar whose language is finite and yields a Herbrand disjunction for pi.
en
dc.language.iso
en
-
dc.publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.subject
Classical logic
-
dc.subject
Context-free grammars
-
dc.subject
Cut elimination
-
dc.subject
First-order logic
-
dc.subject
Herbrand´s theorem
-
dc.subject
Proof theory
-
dc.title
Herbrand Disjunctions, Cut Elimination and Context-Free Tree Grammars
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.publication
13th International Conference on Typed Lambda Calculi and Applications - TLCA 2015
-
dc.relation.isbn
978-3-939897-87-3
-
dc.relation.issn
1868-8969
-
dc.description.startpage
1
-
dc.description.endpage
16
-
dc.type.category
Full-Paper Contribution
-
dc.publisher.place
Dagstuhl, Deutschland
-
tuw.booktitle
13th International Conference on Typed Lambda Calculi and Applications - TLCA 2015
-
tuw.container.volume
38
-
tuw.relation.publisher
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
-
tuw.relation.publisherplace
Dagstuhl
-
tuw.researchTopic.id
X1
-
tuw.researchTopic.name
außerhalb der gesamtuniversitären Forschungsschwerpunkte
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E104-02 - Forschungsbereich Computational Logic
-
tuw.publisher.doi
10.4230/LIPIcs.TLCA.2015.1
-
dc.description.numberOfPages
16
-
tuw.event.name
TLCA'15
-
tuw.event.startdate
01-07-2015
-
tuw.event.enddate
03-07-2015
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Warschau
-
tuw.event.country
PL
-
tuw.event.presenter
Afshari, Bahareh
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1010
-
wb.facultyfocus
Diskrete Mathematik und Geometrie
de
wb.facultyfocus
Discrete Mathematics and Geometry
en
wb.facultyfocus.faculty
E100
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie
-
crisitem.author.dept
E104-02 - Forschungsbereich Computational Logic
-
crisitem.author.dept
E104 - Institut für Diskrete Mathematik und Geometrie
-
crisitem.author.orcid
0000-0002-6461-5982
-
crisitem.author.parentorg
E100 - Fakultät für Mathematik und Geoinformation
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
