In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.

Ex Input:
In this paper, we introduce a notion of backdoors to Reiter's propositional default logic and study structural properties of it. Also we consider the problems of backdoor detection (parameterised by the solution size) as well as backdoor evaluation (parameterised by the size of the given backdoor), for various kinds of target classes (cnf, horn, krom, monotone, positive-unit). We show that backdoor detection is fixed-parameter tractable for the considered target classes, and backdoor evaluation is either fixed-parameter tractable, in para-P2 , or in para-NP, depending on the target class.

Ex Output:
Strong Backdoors for Default Logic

Ex Input:
We define a logic of propositional formula schemata adding to the syntax of propositional logic indexed propositions (e.g., pi) and iterated connectives or ranging over intervals parameterized by arithmetic variables (e.g., n i=1 pi, where n is a parameter). The satisfiability problem is shown to be undecidable for this new logic, but we introduce a very general class of schemata, called bound-linear, for which this problem becomes decidable. This result is obtained by reduction to a particular class of schemata called regular, for which we provide a sound and complete terminating proof procedure. This schemata calculus (called stab) allows one to capture proof patterns corresponding to a large class of problems specified in propositional logic. We also show that the satisfiability problem becomes again undecidable for slight extensions of this class, thus demonstrating that bound-linear schemata represent a good compromise between expressivity and decidability.

Ex Output:
Decidability and Undecidability Results for Propositional Schemata

Ex Input:
We study the complexity of functions computable by deep feedforward neural networks with piecewise linear activations in terms of the number of regions of linearity that they have. Deep networks are able to sequentially map portions of each layer's input space to the same output. In this way, deep models compute functions with a compositional structure that is able to re-use pieces of computation exponentially often in terms of their depth. This note investigates the complexity of such compositional maps and contributes new theoretical results regarding the advantage of depth for neural networks with piece-wise linear activation functions.

Ex Output:
On the Number of Linear Regions of Deep Neural Networks