27 citations · 49 across the 15 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.CC2019
Proof complexity of systems of (non-deterministic) decision trees and branching programs
Sam Buss, Anupam Das, Alexander Knop
This paper studies propositional proof systems in which lines are sequents of decision trees or branching programs - deterministic and nondeterministic. The systems LDT and LNDT ar…
cs.LO2019
From QBFs to MALL and back via focussing: fragments of multiplicative additive linear logic for each level of the polynomial hierarchy
Anupam Das
In this work we investigate how to extract alternating time bounds from 'focussed' proof systems. Our main result is the obtention of fragments of MALLw (MALL with weakening) compl…
cs.LO2019
A Functional (Monadic) Second-Order Theory of Infinite Trees
Anupam Das, Colin Riba
This paper presents a complete axiomatization of Monadic Second-Order Logic (MSO) over infinite trees. MSO on infinite trees is a rich system, and its decidability ("Rabin's Tree T…