4 found
Order:
  1.  12
    On the Correspondence Between Arithmetic Theories and Propositional Proof Systems - a Survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
    The purpose of this paper is to survey the correspondence between bounded arithmetic and propositional proof systems. In addition, it also contains some new results which have appeared as an extended abstract in the proceedings of the conference TAMC 2008 [11].Bounded arithmetic is closely related to propositional proof systems; this relation has found many fruitful applications. The aim of this paper is to explain and develop the general correspondence between propositional proof systems and arithmetic theories, as introduced by Krajíček and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  38
    Proof Complexity of Propositional Default Logic.Olaf Beyersdorff, Arne Meier, Sebastian Müller, Michael Thomas & Heribert Vollmer - 2011 - Archive for Mathematical Logic 50 (7-8):727-742.
    Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen’s system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  3.  18
    Do There Exist Complete Sets for Promise Classes?Olaf Beyersdorff & Zenon Sadowski - 2011 - Mathematical Logic Quarterly 57 (6):535-550.
    In this paper we investigate the following two questions: Q1: Do there exist optimal proof systems for a given language L? Q2: Do there exist complete problems for a given promise class equation image?For concrete languages L and concrete promise classes equation image , these questions have been intensively studied during the last years, and a number of characterizations have been obtained. Here we provide new characterizations for Q1 and Q2 that apply to almost all promise classes equation image and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  4.  13
    Comparing Axiomatizations of Free Pseudospaces.Olaf Beyersdorff - 2009 - Archive for Mathematical Logic 48 (7):625-641.
    Independently and pursuing different aims, Hrushovski and Srour (On stable non-equational theories. Unpublished manuscript, 1989) and Baudisch and Pillay (J Symb Log 65(1):443–460, 2000) have introduced two free pseudospaces that generalize the well know concept of Lachlan’s free pseudoplane. In this paper we investigate the relationship between these free pseudospaces, proving in particular, that the pseudospace of Baudisch and Pillay is a reduct of the pseudospace of Hrushovski and Srour.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark