Authors: Došen, Kosta 
Petrić, Zoran 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Graphs of plural cuts
Journal: Theoretical Computer Science
Volume: 484
First page: 41
Last page: 55
Issue Date: 6-May-2013
Rank: M23
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2013.02.001
Plural (or multiple-conclusion) cuts are inferences made by applying a structural rule introduced by Gentzen for his sequent formulation of classical logic. As singular (single-conclusion) cuts yield trees, which underlie ordinary natural deduction derivations, so plural cuts yield graphs of a more complicated kind, related to trees, which this paper defines. Besides the inductive definition of these oriented graphs, which is based on sequent systems, a non-inductive, graph-theoretical, combinatorial, definition is given, and to reach that other definition is the main goal of the paper. As trees underlie multicategories, so the graphs of plural cuts underlie polycategories. The graphs of plural cuts are interesting in particular when the plural cuts are appropriate for sequent systems without the structural rule of permutation, and the main body of the paper deals with that matter. It gives a combinatorial characterization of the planarity of the graphs involved.
Keywords: Multiple-conclusion sequent | Oriented graph | Planarity | Plural cut | Plural sequent | Polycategory
Publisher: Elsevier
Project: Representations of logical structures and formal languages and their application in computing 

Show full item record


checked on Jul 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.