Maher (2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we s...
详细信息
Maher (2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we show that all the defeasible logics in the DL framework are equally expressive under this formulation of relative expressiveness. the second formulation of relative expressiveness is stronger than the first. However, we show that logics incorporating individual defeat are equally expressive as the corresponding logics with team defeat. thus the only differences in expressiveness of logics in DL arise from differences in how ambiguity is handled. this completes the study of relative expressiveness in DL begun in Maher (2012).
As a novel, grand AI challenge, General Game Playing is concerned withthe development of systems that understand the rules of unknown games and play these games well without human intervention. In this paper, we show...
详细信息
ISBN:
(纸本)9783642028458
As a novel, grand AI challenge, General Game Playing is concerned withthe development of systems that understand the rules of unknown games and play these games well without human intervention. In this paper, we show how Answer Set programming can assist a general game player withthe special class of single-player games. To this end, we present a translation from the general Game Description Language (GDL) into answer set programs (ASP). Correctness of this mapping is established by proving that the stable models of the resulting ASP coincide withthe possible developments of the original GDL game. We report on experiments with single-player games from past AAAI General Game Playing Competitions which substantiate the claim that Answer Set programming can provide valuable support to general game playing systems for this type of games.
We propose a novel framework to solve the combined retiming/gate sizing problem in the context of optimization of acyclic pipelines. the adjustment of sizes to gates in a combinational circuit is a continuous problem,...
详细信息
ISBN:
(纸本)9781479966585
We propose a novel framework to solve the combined retiming/gate sizing problem in the context of optimization of acyclic pipelines. the adjustment of sizes to gates in a combinational circuit is a continuous problem, solvable by a variety of convex optimization tools provided the delay model for each gate is placed in a convex framework. Retiming is a discrete problem since it involves physically moving registers from one location to another. In this paper, we enhance an existing convex optimization framework proposed by Boyd et al [1] to handle registers as 0-1 variables. We solve the relaxed formulation as a geometric program and glean valuable information about the circuit's performance. Another significant contribution of our paper is that we show that our problem is NP-hard.
Maher (2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we s...
详细信息
Maher (2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we show that all the defeasible logics in the DL framework are equally expressive under this formulation of relative expressiveness. the second formulation of relative expressiveness is stronger than the first. However, we show that logics incorporating individual defeat are equally expressive as the corresponding logics with team defeat. thus the only differences in expressiveness of logics in DL arise from differences in how ambiguity is handled. this completes the study of relative expressiveness in DL begun in Maher (2012).
Over the last two decades, propositional satisfiability (Sat) has become one of the most successful and widely applied techniques for the solution of NP-complete problems. the aim of this paper is to investigate theor...
详细信息
Over the last two decades, propositional satisfiability (Sat) has become one of the most successful and widely applied techniques for the solution of NP-complete problems. the aim of this paper is to investigate theoretically how Sat can be utilized for the efficient solution of problems that are harder than NP or co-NP. In particular, we consider the fundamental reasoning problems in propositional disjunctive answer set programming (Asp), Brave Reasoning and Skeptical Reasoning, which ask whether a given atom is contained in at least one or in all answer sets, respectively. Both problems are located at the second level of the Polynomial Hierarchy and thus assumed to be harder than NP or co-NP. One cannot transform these two reasoning problems into Sat in polynomial time, unless the Polynomial Hierarchy collapses. We show that certain structural aspects of disjunctive logic programs can be utilized to break through this complexity barrier, using new techniques from Parameterized Complexity. In particular, we exhibit transformations from Brave and Skeptical Reasoning to Sat that run in time O(2kn2) where k is a structural parameter of the instance and n the input size. In other words, the reduction is fixed-parameter tractable for parameter k. As the parameter k we take the size of a smallest backdoor with respect to the class of normal (i.e., disjunction-free) programs. Such a backdoor is a set of atoms that when deleted makes the program normal. In consequence, the combinatorial explosion, which is expected when transforming a problem from the second level of the Polynomial Hierarchy to the first level, can now be confined to the parameter k, while the running time of the reduction is polynomial in the input size n, where the order of the polynomial is independent of k. We show that such a transformation is not possible if we consider backdoors with respect to tightness instead of normality. We think that our approach is applicable to many other hard combinatorial
the proceedings contain 8 papers. the special focus in this conference is on Functional and Constraint logicprogramming. the topics include: On the Performance of Bytecode Interpreters in Prolog;memoized Pull-Tabbing...
ISBN:
(纸本)9783030753320
the proceedings contain 8 papers. the special focus in this conference is on Functional and Constraint logicprogramming. the topics include: On the Performance of Bytecode Interpreters in Prolog;memoized Pull-Tabbing for Functional logicprogramming;effectiveness of Annotation-Based Static Type Inference;a Framework for Generating Diverse Haskell-I/O Exercise Tasks;formally Verified Transformation of Non-binary Constraints into Binary Constraints;constraint-logic Object-Oriented programming with Free Arrays.
Fusemate is a logicprogramming system that implements the possible model semantics for disjunctive logic programs. Its input language is centered around a weak notion of stratification with comprehension and aggregat...
详细信息
ISBN:
(纸本)9783030798765;9783030798758
Fusemate is a logicprogramming system that implements the possible model semantics for disjunctive logic programs. Its input language is centered around a weak notion of stratification with comprehension and aggregation operators on top of it. Fusemate is implemented as a shallow embedding in the Scala programming language. this enables using Scala data types natively as terms, a tight interface with external systems, and it makes model computation available as an ordinary container data structure constructor. the paper describes the above features and implementation aspects. It also demonstrates them with a non-trivial use-case, the embedding of the description logic ALCIF into Fusemate's input language.
To align representations of law, of implementations of law and of concrete behaviours, we designed a common ground representational model for the three domains, based on the notion of position, building upon Petri net...
详细信息
ISBN:
(纸本)9781614996095;9781614996088
To align representations of law, of implementations of law and of concrete behaviours, we designed a common ground representational model for the three domains, based on the notion of position, building upon Petri nets. this paper reports on work to define subsumption between positional models.
Intuitionistic Propositional logic is complete w.r.t. Kripke semantics: if a formula is not intuitionistically valid, then there exists a finite Kripke model falsifying it. the problem of obtaining concise models has ...
ISBN:
(纸本)9780999241141
Intuitionistic Propositional logic is complete w.r.t. Kripke semantics: if a formula is not intuitionistically valid, then there exists a finite Kripke model falsifying it. the problem of obtaining concise models has been scarcely investigated in the literature. We present a procedure to generate minimal models in the number of worlds relying on Answer Set programming (ASP).
Many scientific applications rely on evaluation of elementary functions. Nowadays, high-level programming languages provide their own elementary function libraries in software by using lookup table and/or polynomial a...
详细信息
ISBN:
(纸本)9781509048250
Many scientific applications rely on evaluation of elementary functions. Nowadays, high-level programming languages provide their own elementary function libraries in software by using lookup table and/or polynomial approximation. However, one downside is slow since lookup tables could keep cache thrashing and polynomial approximations require a number of iterations to converge. thus, elementary functions evaluation becomes bottleneck for most scientific applications. Withthis motivation, we propose a generalized pipelined hardware architecture for elementary functions to accelerate scientific applications. this paper presents a pipelined, single precision logarithm hardware accelerator (SP-LHA). throughput of SP-LHA is at least 2.5GFLOPS in 65nm ASICs, while the circuit consists of approximate to 60,000 logic gates. Average accuracy of SP-LHA is 22.5 out of 23 bits, which is achieved by using 7.8KB lookup table and parabolic interpolation.
暂无评论