2016/06/19 by Bahareh Afshari, Stefan Hetzl, Graham E. Leigh
Computer Science · Mathematics · #Algebra over a field #Combinatorics #Computer science #Content (measure theory) #Discrete mathematics #Formal Methods in Verification #Geometry #Grammar #Linguistics #Logic, programming, and type systems #Mathematical proof #Mathematics #Natural language processing #Order (exchange) #Philosophy #Programming language #Pure mathematics #Reduction (mathematics) #Representation (politics) #Rule-based machine translation #Tree (set theory) #cs.FL #cs.LO #math.LO #semigroups and automata theory
paper · pdf · doi:10.4204/eptcs.213.1
published as EPTCS 213, 2016, pp. 1-10 · In Proceedings CL&C 2016, arXiv:1606.05820
openalex publication_date 2016/06/19 · arxiv created 2016/06/21 · arxiv updated 2016/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We present a structural representation of the Herbrand content of LK-proofs with cuts of complexity prenex Sigma-2/Pi-2. The representation takes the form of a typed non-deterministic tree grammar of order 2 which generates a finite language of first-order terms that appear in the Herbrand expansions obtained through cut-elimination. In particular, for every Gentzen-style reduction between LK-proofs we study the induced grammars and classify the cases in which language equality and inclusion hold.