BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Uwe Egly

Uwe Egly contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Logic in Computer ScienceArtificial IntelligenceComputational Complexity

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
8works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

8 published item(s)

preprint2016arXiv

Conformant Planning as a Case Study of Incremental QBF Solving

We consider planning with uncertainty in the initial state as a case study of incremental quantified Boolean formula (QBF) solving. We report on experiments with a workflow to incrementally encode a planning instance into a sequence of QBFs. To solve this sequence of incrementally constructed QBFs, we use our general-purpose incremental QBF solver DepQBF. Since the generated QBFs have many clauses and variables in common, our approach avoids redundancy both in the encoding phase and in the solving phase. Experimental results show that incremental QBF solving outperforms non-incremental QBF solving. Our results are the first empirical study of incremental QBF solving in the context of planning and motivate its use in other application domains.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Stronger Calculi for QBFs

Quantified Boolean formulas (QBFs) generalize propositional formulas by admitting quantifications over propositional variables. QBFs can be viewed as (restricted) formulas of first-order predicate logic and easy translations of QBFs into first-order formulas exist. We analyze different translations and show that first-order resolution combined with such translations can polynomially simulate well-known deduction concepts for QBFs. Furthermore, we extend QBF calculi by the possibility to instantiate a universal variable by an existential variable of smaller level. Combining such an enhanced calculus with the propositional extension rule results in a calculus with a universal quantifier rule which essentially introduces propositional formulas for universal variables. In this way, one can mimic a very general quantifier rule known from sequent systems.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Q-Resolution with Generalized Axioms

Q-resolution is a proof system for quantified Boolean formulas (QBFs) in prenex conjunctive normal form (PCNF) which underlies search-based QBF solvers with clause and cube learning (QCDCL). With the aim to derive and learn stronger clauses and cubes earlier in the search, we generalize the axioms of the Q-resolution calculus resulting in an exponentially more powerful proof system. The generalized axioms introduce an interface of Q-resolution to any other QBF proof system allowing for the direct combination of orthogonal solving techniques. We implemented a variant of the Q-resolution calculus with generalized axioms in the QBF solver DepQBF. As two case studies, we apply integrated SAT solving and resource-bounded QBF preprocessing during the search to heuristically detect potential axiom applications. Experiments with application benchmarks indicate a substantial performance improvement.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Satisfiability-Based Methods for Reactive Synthesis from Safety Specifications

Existing approaches to synthesize reactive systems from declarative specifications mostly rely on Binary Decision Diagrams (BDDs), inheriting their scalability issues. We present novel algorithms for safety specifications that use decision procedures for propositional formulas (SAT solvers), Quantified Boolean Formulas (QBF solvers), or Effectively Propositional Logic (EPR). Our algorithms are based on query learning, templates, reduction to EPR, QBF certification, and interpolation. A parallelization combines multiple algorithms. Our optimizations expand quantifiers and utilize unreachable states and variable independencies. Our approach outperforms a simple BDD-based tool and is competitive with a highly optimized one. It won two medals in the SyntComp competition.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Automated Benchmarking of Incremental SAT and QBF Solvers

Incremental SAT and QBF solving potentially yields improvements when sequences of related formulas are solved. An incremental application is usually tailored towards some specific solver and decomposes a problem into incremental solver calls. This hinders the independent comparison of different solvers, particularly when the application program is not available. As a remedy, we present an approach to automated benchmarking of incremental SAT and QBF solvers. Given a collection of formulas in (Q)DIMACS format generated incrementally by an application program, our approach automatically translates the formulas into instructions to import and solve a formula by an incremental SAT/QBF solver. The result of the translation is a program which replays the incremental solver calls and thus allows to evaluate incremental solvers independently from the application program. We illustrate our approach by different hardware verification problems for SAT and QBF solvers.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Incrementally Computing Minimal Unsatisfiable Cores of QBFs via a Clause Group Solver API

We consider the incremental computation of minimal unsatisfiable cores (MUCs) of QBFs. To this end, we equipped our incremental QBF solver DepQBF with a novel API to allow for incremental solving based on clause groups. A clause group is a set of clauses which is incrementally added to or removed from a previously solved QBF. Our implementation of the novel API is related to incremental SAT solving based on selector variables and assumptions. However, the API entirely hides selector variables and assumptions from the user, which facilitates the integration of DepQBF in other tools. We present implementation details and, for the first time, report on experiments related to the computation of MUCs of QBFs using DepQBF's novel clause group API.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Complexity Classifications for logic-based Argumentation

We consider logic-based argumentation in which an argument is a pair (Fi,al), where the support Fi is a minimal consistent set of formulae taken from a given knowledge base (usually denoted by De) that entails the claim al (a formula). We study the complexity of three central problems in argumentation: the existence of a support Fi ss De, the validity of a support and the relevance problem (given psi is there a support Fi such that psi ss Fi?). When arguments are given in the full language of propositional logic these problems are computationally costly tasks, the validity problem is DP-complete, the others are SigP2-complete. We study these problems in Schaefer's famous framework where the considered propositional formulae are in generalized conjunctive normal form. This means that formulae are conjunctions of constraints build upon a fixed finite set of Boolean relations Ga (the constraint language). We show that according to the properties of this language Ga, deciding whether there exists a support for a claim in a given knowledge base is either polynomial, NP-complete, coNP-complete or SigP2-complete. We present a dichotomous classification, P or DP-complete, for the verification problem and a trichotomous classification for the relevance problem into either polynomial, NP-complete, or SigP2-complete. These last two classifications are obtained by means of algebraic tools.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Incremental QBF Solving

We consider the problem of incrementally solving a sequence of quantified Boolean formulae (QBF). Incremental solving aims at using information learned from one formula in the process of solving the next formulae in the sequence. Based on a general overview of the problem and related challenges, we present an approach to incremental QBF solving which is application-independent and hence applicable to QBF encodings of arbitrary problems. We implemented this approach in our incremental search-based QBF solver DepQBF and report on implementation details. Experimental results illustrate the potential benefits of incremental solving in QBF-based workflows.

0 citations0 reviewsNo code linkedOpen access