Knowledge representation (KR) is actually more than representation: It involves also inference, namely inference of “new” knowledge, i.e. new facts. Logic programming is a suitable KR medium, but more often than not discussions on this programming paradigm focus on aspects other than KR. In this paper, I elaborate on the general theory of logic programming and give the essentials of two of its main implementations, to wit, Prolog and Datalog, from the viewpoint of deductive computing over knowledge bases, which includes (...) deductive programming. (shrink)

We establish a general hierarchy theorem for quantifier classes in the infinitary logic L∞ωωon finite structures. In particular, it is shown that no infinitary formula with bounded number of universal quantifiers can express the negation of a transitive closure.This implies the solution of several open problems in finite model theory: On finite structures, positive transitive closure logic is not closed under negation. More generally the hierarchy defined by interleaving negation and transitive closure operators is strict. This proves a conjecture of (...) Immerman.We also separate the expressive power of several extensions of Datalog, giving new insight in the fine structure of stratified Datalog. (shrink)

The paper discusses properties of 4QL, a DATALOG⌉⌉-like query language, originally outlined by Maluszyński and Szalas (Maluszyński & Szalas, 2011). 4QL allows one to use rules with negation in heads and bodies of rules. It is based on a simple and intuitive semantics and provides uniform tools for “lightweight” versions of known forms of nonmonotonic reasoning. Negated literals in heads of rules may naturally lead to inconsistencies. On the other hand, rules do not have to attach meaning to some literals. (...) Therefore 4QL is founded on a four-valued semantics, employing the logic introduced in (Maluszyński et al., 2008; Vitória et al., 2009) with truth values: ‘true’, ‘false’, ‘inconsistent’ and ‘unknown’. In addition, 4QL is tractable w.r.t. data complexity and captures PTIME queries. Even though DATALOG⌉⌉ is known as a concept for the last 30 years, to our best knowledge no existing approach enjoys these properties.In the current paper we:investigate properties of well-supported models of 4QLprove the correctness of the algorithm for computing well-supported modelsshow that 4QL has PTIME data complexity and captures PTIME. (shrink)

Abstract State Machines (ASMs) provide a formal method for transparent design and specification of complex dynamic systems. They combine advantages of informal and formal methods. Applications of this method motivate a number of computability and decidability problems connected to ASMs. Such problems result for example from the area of verifying properties of ASMs. Their high expressive power leads rather directly to undecidability respectively uncomputability results for most interesting problems in the case of unrestricted ASMs. Consequently, it is rather natural to (...) ask whether there exist expressive classes of ASMs for which we can prove positive decidability and computability results. In this work, we introduce such a class of ASMs. The concept is similar to the one of the guarded fragment of first-order logic. We analyze the expressive power of this class and prove that it is stronger than Datalog LITE and the guarded fragment of first-order fixed point logic. Some decidability and computability results have been proven in earlier works. (shrink)

In the context of the emerging Semantic Web and the quest for a common logical framework underpinning its architecture, the relation of rule-based languages such as Answer Set Programming (ASP) and ontology languages such as the Web Ontology Language (OWL) has attracted a lot of attention in the literature over the past years. With its roots in Deductive Databases and Datalog though, ASP shares much more commonality with another Semantic Web standard, namely the Simple Protocol and RDF Query Language (SPARQL). (...) In this paper, we take the recent approval of the SPARQL1.1 standard by the World Wide Web consortium (W3C) as an opportunity to introduce this standard to the Logic Programming community by providing a translation of SPARQL1.1 into ASP. In this translation, we explain and highlight peculiarities of the new W3C standard. Along the way, we survey existing literature on foundations of SPARQL and SPARQL1.1, and also combinations of SPARQL with ontology and rules languages. Thereby, apart from providing the means to implement and support SPARQL natively within Logic Programming engines and particularly ASP engines, we hope to pave the way for further research on a common logical framework for Semantic Web languages, including query languages, from an ASP point of view. (shrink)

What could a social-justice oriented, feminist data studies look like? The current datalogical turn foregrounds the digital datafication of everyday life, increasing algorithmic processing and data as an emergent regime of power/knowledge. Scholars celebrate the politics of big data knowledge production for its omnipotent objectivity or dismiss it outright as data fundamentalism that may lead to methodological genocide. In this feminist and postcolonial intervention into gender-, race- and geography-blind ‘big data’ ideologies, I call for ethical, anti-oppressive digital data-driven research in (...) the social sciences and humanities. I argue that a reflexive data scholarship can emerge from the reintegration of feminist and postcolonial science studies and ethics of care ideals. Although it is not a panacea for all ails of data mining, I offer a road map for an alternative data-analysis practice that is more power-sensitive and accountable. By incorporating a people-centric and context-aware perspective that acknowledges relationships of dependency, reflects on temptations, and scrutinises benefits and harm, an ‘asymmetrically reciprocal’ (Young, 1997) research encounter may be achieved. I bring this perspective to bear on experiences of a two-year research project with eighty-four young Londoners on digital identities and living in a highly diverse city. I align awareness of uneven relations of power and knowledge with the messy relation of dependency between human and non-human actors in data analysis. This framework productively recognises that digital data cannot be expected to speak for itself, that data do not emerge from a vacuum, and that isolated data patterns cannot be the end-goal of a situated and reflexive research endeavor. Data-driven research, in turn, shows the urgency for renewed feminist ethical reflection on how digital mediation impacts upon responsibility, intersectional power relations, human subjectivity and the autonomy of research participants over their own data. (shrink)

This paper draws together empirical findings from our study of hackathons in the UK with literature on big data through three interconnected frameworks: data as discourse, data as datalogical and data as materiality. We suggest not only that hackathons resonate the wider socio-technical and political constructions of data that are currently enacted in policy, education and the corporate sector, but also that an investigation of hackathons reveals the extent to which ‘data’ operates as a powerful discursive tool; how the discourses (...) of data mask and reveal a series of tropes pertaining to data; that the politics of data are routinely and simultaneously obscured and claimed with serious implications for expertise and knowledge; and that ultimately, and for the vast majority of hackathons we have attended, the discursive and material constructions of data serve to underpin rather than challenge existing power relations and politics. (shrink)

Many logics considered in finite model theory have a natural notion of an arity. The purpose of this article is to study the hierarchies which are formed by the fragments of such logics whose formulae are of bounded arity.Based on a construction of finite graphs with a certain property of homogeneity, we develop a method that allows us to prove that the arity hierarchies are strict for several logics, including fixed-point logics, transitive closure logic and its deterministic version, variants of (...) the database language Datalog, and extensions of first-order logic by implicit definitions.Furthermore, we show that all our results already hold on the class of finite graphs. (shrink)

This thesis aims to develop a domain-independent system for repairing faulty Datalog-like theories by combining three existing techniques: abduction, belief revision, and conceptual change. Accordingly, the proposed system is named the ABC repair system. Given an observed assertion and a current theory, abduction adds axioms, which explain that observation by making the corresponding assertion derivable from the expanded theory. Belief revision incorporates a new piece of information which conflicts with the input theory by deleting old axioms. Conceptual change uses the (...) reformation algorithm for blocking unwanted proofs or unblocking wanted proofs. The former two techniques change an axiom as a whole, while reformation changes the language in which the theory is written. These three techniques are complementary. But they have not previously been combined into one system. We are working on aligning these three techniques in ABC, which is capable of repairing logical theories with better result than each individual technique alone. In addition, ABC extends abduction and belief revision to operate on preconditions: the former deletes preconditions from rules, and the latter adds preconditions to rules. Datalog is used as the underlying logic of theories in this thesis, but the proposed system has the potential to be adapted to theories in other logics.Abstract prepared by Xue Li by taking directly from the thesis.E-mail: xuerr.lee@gmail.com. (shrink)

A general game player automatically learns to play arbitrary new games solely by being told their rules. For this purpose games are specified in the general Game Description Language (GDL), a variant of Datalog with function symbols that uses a few game-specific keywords. A recent extension of basic GDL allows the description of nondeterministic games with any number of players who may have incomplete, asymmetric information. In this paper, we analyse the epistemic structure and expressiveness of this language in terms (...) of modal epistemic logic and prove two main results: (1) The operational semantics of GDL entails that the situation at any stage of a game can be characterised by a multi-agent epistemic (i.e., S5-) model; (2) GDL is sufficiently expressive to model any situation that can be described by a (finite) multi-agent epistemic model. (shrink)

Despite its successes, to date Artificial Intelligence (AI) is still characterized by a number of shortcomings with regards to different application domains and goals. These limitations are arguably both conceptual (e.g., related to the underlying theoretical models, such as symbolic vs.connectionist), and operational (e.g., related to robustness and ability to generalize). Biologically inspired AI, and more specifically brain-inspired AI, promises to provide further biological aspects beyond those that are already traditionally included in AI, making it possible to assess and possibly (...) overcome some of its present shortcomings. This article examines some conceptual, technical, and ethical issues raised by the development and use of brain-inspired AI. Against this background, the paper asks whether there is anything ethically unique about brain-inspired AI. The aim of the paper is to introduce a method that has a heuristic nature and that can be applied to identify and address the ethical issues arising from brain-inspired AI (and from AI more generally). The conclusion resulting from the application of this method is that, compared to traditional AI, brain-inspired AI raises new foundational ethical issues and some new practical ethical issues, and exacerbates some of the issues raised by traditional AI. (shrink)

We present game-theoretic characterizations of the complexity/expressibility measures “dimension” and “the number of variables” as Least Fixed Point queries. As an example, we use these characterizations to compute the dimension and number of variables of Connectivity and Connectivity.

Contemporary ethical analysis of Artificial Intelligence is growing rapidly. One of its most recognizable outcomes is the publication of a number of ethics guidelines that, intended to guide governmental policy, address issues raised by AI design, development, and implementation and generally present a set of recommendations. Here we propose two things: first, regarding content, since some of the applied issues raised by AI are related to fundamental questions about topics like intelligence, consciousness, and the ontological and ethical status of humans, (...) among others, the treatment of these issues would benefit from interfacing with neuroethics that has been addressing those same issues in the context of brain research. Second, the identification and management of some of the practical ethical challenges raised by AI would be enriched by embracing the methodological resources used in neuroethics. In particular, we focus on the methodological distinction between conceptual and action-oriented neuroethical approaches. We argue that the normative discussion about AI will benefit from further integration of conceptual analysis, including analysis of some operative assumptions, their meaning in different contexts, and their mutual relevance in order to avoid misplaced or disproportionate concerns and achieve a more realistic and useful approach to identifying and managing the emerging ethical issues. (shrink)