The Experts below are selected from a list of 408 Experts worldwide ranked by ideXlab platform

Philip D. Welch - One of the best experts on this subject based on the ideXlab platform.

  • Countable unions of simple sets in the core model
    Journal of Symbolic Logic, 1996
    Co-Authors: Philip D. Welch
    Abstract:

    We follow [8] in asking when a set of ordinals X ⊆ α is a countable union of sets in K , the core model. We show that, analogously to L , an X closed under the canonical Σ 1 Skolem Function for K α can be so decomposed provided K is such that no ω -closed filters are put on its measure sequence, but not otherwise. This proviso holds if there is no inner model of a weak Erdős-type property.

  • Countable Unions of Simple Sets in the Core Model
    1996
    Co-Authors: Philip D. Welch
    Abstract:

    We follow [8] in asking when a set of ordinals X ` ff is a countable union of sets in K, the core model. We show that, analogously to L, an X closed under the canonical \Sigma 1 Skolem Function for K ff can be so decomposed, provided K is such that no !-closed filters are put on its measure sequence, but not otherwise. This proviso holds if there is no inner model of a weak Erdos type property. Introduction In [8], Magidor proved that if there are no ! 1 -Erdos cardinals in the core model K, then for every fi there is a K-definable algebra of Functions on fi, so that every set X ` fi, closed under these Functions, is a countable union of sets in K. His algebras are uniformly K-definable in fi-in a \Sigma ZF 2 way. Magidor's theorem came about as a generalisation of another theorem in that paper, where he proves that if :O ] , then every primitively set closed subset of fi is a countable union of sets in L. The statement above is his generalization to K. As he notes there, a the..

Herwig Nübling - One of the best experts on this subject based on the ideXlab platform.

  • Adding Skolem Functions to simple theories
    2008
    Co-Authors: Herwig Nübling
    Abstract:

    We examine the conditions under which we can keep simplicity or categoricity after adding a Skolem Function to the theory. AMS classification: 03C45, 03C5

  • Reducts and Expansions of Stable and Simple Theories
    2004
    Co-Authors: Herwig Nübling
    Abstract:

    c ○ This copy of the thesis has been supplied on condition that anyone who consults it is understood to recognise that its copyright rests with the author and that no quotation from the thesis, nor any information derived therefrom, may be published without the author’s prior consent. In this thesis we will study certain properties like simplicity, categoricity or CM-triviality of reducts and Skolem expansions of simple and stable theories. The first part is about Skolem expansions of simple theories. We will show that if we add the Skolem Function for an algebraic formula to an algebraically bounded, model-complete, simple theory T, then its model-completion T ∗, which we know exists from Winkler’s Theorem, is again simple. If T is ω-categorical then so is T ∗. This will give us a method to turn algebraic closure into definable closure without losing simplicity or ω-categoricity. We illustrate with an example that if T is uncountably categorical then T ∗ need not to be. After that we examine the case of adding the Skolem Function for a non algebrai

Chakraborty Supratik - One of the best experts on this subject based on the ideXlab platform.

  • A Normal Form Characterization for Efficient Boolean Skolem Function Synthesis
    2021
    Co-Authors: Shah Preey, Bansal Aman, Akshay S., Chakraborty Supratik
    Abstract:

    Boolean Skolem Function synthesis concerns synthesizing outputs as Boolean Functions of inputs such that a relational specification between inputs and outputs is satisfied. This problem, also known as Boolean Functional synthesis, has several applications, including design of safe controllers for autonomous systems, certified QBF solving, cryptanalysis etc. Recently, complexity theoretic hardness results have been shown for the problem, although several algorithms proposed in the literature are known to work well in practice. This dichotomy between theoretical hardness and practical efficacy has motivated the research into normal forms or representations of input specifications that permit efficient synthesis, thus explaining perhaps the efficacy of these algorithms. In this paper we go one step beyond this and ask if there exists a normal form representation that can in fact precisely characterize "efficient" synthesis. We present a normal form called SAUNF that precisely characterizes tractable synthesis in the following sense: a specification is polynomial time synthesizable iff it can be compiled to SAUNF in polynomial time. Additionally, a specification admits a polynomial-sized Functional solution iff there exists a semantically equivalent polynomial-sized SAUNF representation. SAUNF is exponentially more succinct than well-established normal forms like BDDs and DNNFs, used in the context of AI problems, and strictly subsumes other more recently proposed forms like SynNNF. It enjoys compositional properties that are similar to those of DNNF. Thus, SAUNF provides the right trade-off in knowledge representation for Boolean Functional synthesis.Comment: Full version of conference paper accepted at LICS'202

  • Knowledge Compilation for Boolean Functional Synthesis
    2019
    Co-Authors: Akshay S., Chakraborty Supratik, Arora Jatin, Krishna S., Raghunathan Divya, Shah Shetal
    Abstract:

    Given a Boolean formula F(X,Y), where X is a vector of outputs and Y is a vector of inputs, the Boolean Functional synthesis problem requires us to compute a Skolem Function vector G(Y)for X such that F(G(Y),Y) holds whenever \exists X F(X,Y) holds. In this paper, we investigate the relation between the representation of the specification F(X,Y) and the complexity of synthesis. We introduce a new normal form for Boolean formulas, called SynNNF, that guarantees polynomial-time synthesis and also polynomial-time existential quantification for some order of quantification of variables. We show that several normal forms studied in the knowledge compilation literature are subsumed by SynNNF, although SynNNFcan be super-polynomially more succinct than them. Motivated by these results, we propose an algorithm to convert a specification in CNF to SynNNF, with the intent of solving the Boolean Functional synthesis problem. Experiments with a prototype implementation show that this approach solves several benchmarks beyond the reach of state-of-the-art tools.Comment: Full version of conference paper accepted at FMCAD 201

  • Skolem Functions for Factored Formulas
    2015
    Co-Authors: John, Ajith K., Chakraborty Supratik, Shah Shetal, Trivedi Ashutosh, Akshay S.
    Abstract:

    Given a propositional formula F(x,y), a Skolem Function for x is a Function \Psi(y), such that substituting \Psi(y) for x in F gives a formula semantically equivalent to \exists F. Automatically generating Skolem Functions is of significant interest in several applications including certified QBF solving, finding strategies of players in games, synthesising circuits and bit-vector programs from specifications, disjunctive decomposition of sequential circuits etc. In many such applications, F is given as a conjunction of factors, each of which depends on a small subset of variables. Existing algorithms for Skolem Function generation ignore any such factored form and treat F as a monolithic Function. This presents scalability hurdles in medium to large problem instances. In this paper, we argue that exploiting the factored form of F can give significant performance improvements in practice when computing Skolem Functions. We present a new CEGAR style algorithm for generating Skolem Functions from factored propositional formulas. In contrast to earlier work, our algorithm neither requires a proof of QBF satisfiability nor uses composition of monolithic conjunctions of factors. We show experimentally that our algorithm generates smaller Skolem Functions and outperforms state-of-the-art approaches on several large benchmarks.Comment: Full version of FMCAD 2015 conference publicatio

Akshay S. - One of the best experts on this subject based on the ideXlab platform.

  • A Normal Form Characterization for Efficient Boolean Skolem Function Synthesis
    2021
    Co-Authors: Shah Preey, Bansal Aman, Akshay S., Chakraborty Supratik
    Abstract:

    Boolean Skolem Function synthesis concerns synthesizing outputs as Boolean Functions of inputs such that a relational specification between inputs and outputs is satisfied. This problem, also known as Boolean Functional synthesis, has several applications, including design of safe controllers for autonomous systems, certified QBF solving, cryptanalysis etc. Recently, complexity theoretic hardness results have been shown for the problem, although several algorithms proposed in the literature are known to work well in practice. This dichotomy between theoretical hardness and practical efficacy has motivated the research into normal forms or representations of input specifications that permit efficient synthesis, thus explaining perhaps the efficacy of these algorithms. In this paper we go one step beyond this and ask if there exists a normal form representation that can in fact precisely characterize "efficient" synthesis. We present a normal form called SAUNF that precisely characterizes tractable synthesis in the following sense: a specification is polynomial time synthesizable iff it can be compiled to SAUNF in polynomial time. Additionally, a specification admits a polynomial-sized Functional solution iff there exists a semantically equivalent polynomial-sized SAUNF representation. SAUNF is exponentially more succinct than well-established normal forms like BDDs and DNNFs, used in the context of AI problems, and strictly subsumes other more recently proposed forms like SynNNF. It enjoys compositional properties that are similar to those of DNNF. Thus, SAUNF provides the right trade-off in knowledge representation for Boolean Functional synthesis.Comment: Full version of conference paper accepted at LICS'202

  • Knowledge Compilation for Boolean Functional Synthesis
    2019
    Co-Authors: Akshay S., Chakraborty Supratik, Arora Jatin, Krishna S., Raghunathan Divya, Shah Shetal
    Abstract:

    Given a Boolean formula F(X,Y), where X is a vector of outputs and Y is a vector of inputs, the Boolean Functional synthesis problem requires us to compute a Skolem Function vector G(Y)for X such that F(G(Y),Y) holds whenever \exists X F(X,Y) holds. In this paper, we investigate the relation between the representation of the specification F(X,Y) and the complexity of synthesis. We introduce a new normal form for Boolean formulas, called SynNNF, that guarantees polynomial-time synthesis and also polynomial-time existential quantification for some order of quantification of variables. We show that several normal forms studied in the knowledge compilation literature are subsumed by SynNNF, although SynNNFcan be super-polynomially more succinct than them. Motivated by these results, we propose an algorithm to convert a specification in CNF to SynNNF, with the intent of solving the Boolean Functional synthesis problem. Experiments with a prototype implementation show that this approach solves several benchmarks beyond the reach of state-of-the-art tools.Comment: Full version of conference paper accepted at FMCAD 201

  • Skolem Functions for Factored Formulas
    2015
    Co-Authors: John, Ajith K., Chakraborty Supratik, Shah Shetal, Trivedi Ashutosh, Akshay S.
    Abstract:

    Given a propositional formula F(x,y), a Skolem Function for x is a Function \Psi(y), such that substituting \Psi(y) for x in F gives a formula semantically equivalent to \exists F. Automatically generating Skolem Functions is of significant interest in several applications including certified QBF solving, finding strategies of players in games, synthesising circuits and bit-vector programs from specifications, disjunctive decomposition of sequential circuits etc. In many such applications, F is given as a conjunction of factors, each of which depends on a small subset of variables. Existing algorithms for Skolem Function generation ignore any such factored form and treat F as a monolithic Function. This presents scalability hurdles in medium to large problem instances. In this paper, we argue that exploiting the factored form of F can give significant performance improvements in practice when computing Skolem Functions. We present a new CEGAR style algorithm for generating Skolem Functions from factored propositional formulas. In contrast to earlier work, our algorithm neither requires a proof of QBF satisfiability nor uses composition of monolithic conjunctions of factors. We show experimentally that our algorithm generates smaller Skolem Functions and outperforms state-of-the-art approaches on several large benchmarks.Comment: Full version of FMCAD 2015 conference publicatio

Jeremy Avigad - One of the best experts on this subject based on the ideXlab platform.