In this paper, we develop a novel logic-based approach to detecting high-level temporally extended events from time-stamped data and background knowledge. Our framework employs logical rules to capture existence and termination conditions for simple temporal events and to combine these into meta-events. In the medical domain, for example, disease episodes and therapies are inferred from timestamped clinical observations, such as diagnoses and drug administrations stored in patient records, and can be further combined into higher-level disease events. As some incorrect events might be inferred, we use constraints to identify incompatible combinations of events and propose a repair mechanism to select preferred consistent sets of events. While reasoning in the full framework is intractable, we identify relevant restrictions that ensure polynomial-time data complexity. Our prototype system implements core components of the approach using answer set programming. An evaluation on a lung cancer use case supports the interest of the approach, both in terms of computational feasibility and positive alignment of our results with medical expert opinions. While strongly motivated by the needs of the healthcare domain, our framework is purposely generic, enabling its reuse in other areas.

We study the problem of explaining observations about the probabilities of events such as ‘it rains 20% of the time’, ‘rain and snow are equally likely’, etc. We explain these statements with a probability distribution or a statement about probabilities of (other) events that are consistent with our knowledge and entail the observation. We formalise this problem in a fuzzy probabilistic logic FP. We define and motivate the notions of abduction problems and their solutions. We analyse the complexity of solution recognition and existence for a given abduction problem in FP for the case of full language and its disjunctive-clause fragments. We also obtain a translation of classical probabilistic abduction (finding the most likely explanation of a given event) to FP.

Neurosymbolic systems can satisfy logical constraints during learning without achieving the intended concept-label correspondence; this is a problem known as reasoning shortcuts. We formalize reasoning shortcuts as a constraint satisfaction problem and investigate under which conditions concept mappings are uniquely determined by the constraints. We prove that a discrimination property (requiring that no valid concept mapping can be transformed into another valid mapping by swapping two concept values) is necessary for shortcut-freeness under bijective mappings, but demonstrate via a counterexample that it is insufficient even when the constraint graph is connected. We develop an ASP-based algorithm that verifies whether a given constraint set uniquely determines the intended concept mapping, with proven soundness and completeness. When shortcuts are detected, a greedy repair algorithm eliminates them by augmenting the constraint set, converging in at most k iterations, where k is the number of alternative valid mappings. We further provide a complexity classification: deciding shortcut-freeness is coNP-complete, counting shortcuts is #P-complete, and finding minimal repairs is NP-hard. We also establish sample complexity bounds showing that logarithmically many label queries suffice for disambiguation in favorable cases, while querying all ambiguous positions suffices in the worst case. Experiments across eight benchmark domains validate our approach.

In this paper, we explore the problem of explaining observations starting from a classically inconsistent theory by adopting a paraconsistent framework. More precisely, we consider theories formulated in the well-known Belnap–Dunn paraconsistent four-valued logic BD and its implicative expansion BD⊃. Abductive solutions are then given in one of the two further expansions of BD: BD∘, which introduces formulas of the form ∘φ (‘the information on φ is reliable’), and BD△, which augments the language with formulas of the form △φ (‘there is information that φ is true’). We show that explanations in BD∘ and BD△ are not reducible to one another. We analyse the complexity of standard abductive reasoning tasks (solution recognition, solution existence, and relevance/necessity of hypotheses) depending on the language of the solution (BD∘ or BD△) and on the language of the theory (BD or BD⊃). In addition, we consider the complexity of abductive reasoning in the Horn fragment of BD⊃. By showing how to reduce abduction in BD and its expansions to abduction in classical propositional logic, we enable the reuse of existing abductive reasoning procedures.

Abstract In this paper, we address the problem of giving names to predicates in logic rules using Large Language Models (LLMs). In the context of Inductive Logic Programming, various rule generation methods produce rules containing unnamed predicates, with Predicate Invention being a key example. This hinders the readability, interpretability, and reusability of the logic theory. Leveraging recent advancements in LLMs development, we explore their ability to process natural language and code to provide semantically meaningful suggestions for giving a name to unnamed predicates. The evaluation of our approach on some hand-crafted logic rules indicates that LLMs hold potential for this task.

Rule learning-based models are widely used in highly interpretable scenarios due to their transparent structures. Inductive logic programming (ILP), a form of machine learning, induces rules from facts while maintaining interpretability. Differentiable ILP models enhance this process by leveraging neural networks to improve robustness and scalability. However, most differentiable ILP methods rely on symbolic datasets, facing challenges when learning directly from raw data. Specifically, they struggle with explicit label leakage: The inability to map continuous inputs to symbolic variables without explicit supervision of input feature labels. In this work, we address this issue by integrating a self-supervised differentiable clustering model with a novel differentiable ILP model, enabling rule learning from raw data without explicit label leakage. The learned rules effectively describe raw data through its features. We demonstrate that our method intuitively and precisely learns generalized rules from time series and image data.

In this work, we show how the class of improvement operators --- a general class of iterated belief change operators --- can be used to define a learning model. Focusing on binary classification, we present learning and inference algorithms suited to this learning model and we evaluate them empirically. Our findings highlight two key insights: first, that iterated belief change can be viewed as an effective form of online learning, and second, that the well-established axiomatic foundations of belief change operators offer a promising avenue for the axiomatic study of classification tasks.

Repair-based semantics have been extensively studied as a means of obtaining meaningful answers to queries posed over inconsistent knowledge bases (KBs). While several works have considered how to exploit a priority relation between facts to select optimal repairs, the question of how to specify such preferences remains largely unaddressed. This motivates us to introduce a declarative rule-based framework for specifying and computing a priority relation between conflicting facts. As the expressed preferences may contain undesirable cycles, we consider the problem of determining when a set of preference rules always yields an acyclic relation, and we also explore a pragmatic approach that extracts an acyclic relation by applying various cycle removal techniques. Towards an end-to-end system for querying inconsistent KBs, we present a preliminary implementation and experimental evaluation of the framework, which employs answer set programming to evaluate the preference rules, apply the desired cycle resolution techniques to obtain a priority relation, and answer queries under prioritized-repair semantics.

We explore the problem of explaining observations in contexts involving statements with truth degrees, such as ‘the lift is loaded’, ‘the symptoms are severe’, etc. To formalise these contexts, we consider infinitely-valued Łukasiewicz fuzzy logic. We define and motivate the notions of abduction problems and explanations in the language of Łukasiewicz logic expanded with ‘interval literals’ of the form p≥c, p≤c, and their negations that express the set of values a variable can have. We analyse the complexity of standard abductive reasoning tasks (solution recognition, solution existence, and relevance / necessity of hypotheses) in Łukasiewicz logic for the case of the full language and for the case of theories containing only disjunctive clauses and show that in contrast to classical propositional logic, the abduction in the clausal fragment has lower complexity than in the general case.

Neural Disjunctive Normal Form (DNF) based models are powerful and interpretable approaches to neuro-symbolic learning and have shown promising results in classification and reinforcement learning settings without prior knowledge of the tasks. However, their performance is degraded by the thresholding of the post-training symbolic translation process. We show here that part of the performance degradation during translation is due to its failure to disentangle the learned knowledge represented in the form of the networks’ weights. We address this issue by proposing a new disentanglement method; by splitting nodes that encode nested rules into smaller independent nodes, we are able to better preserve the models’ performance. Through experiments on binary, multiclass, and multilabel classification tasks (including those requiring predicate invention), we demonstrate that our disentanglement method provides compact and interpretable logical representations for the neural DNF-based models, with performance closer to that of their pre-translation counterparts. Our code is available at https://github.com/kittykg/disentangling-ndnf-classification.

Integrating logical constraints into object detection models for autonomous driving (AD) is a promising way to enhance their compliance with rules and thereby increase the safety of the system. T-norms have been utilized to calculate the constrained loss, i.e., the violations of logical constraints as losses. While prior works have statically selected a few t-norms, we conduct an extensive experimental study to identify the most effective choices, as suboptimal t-norms can lead to undesired model behavior. To this end, we present MOD-ECL, a neurosymbolic framework that implements a wide range of t-norms and applies them in an adaptive manner. It includes an algorithm that selects well-performing t-norms during training and a scheduler that regulates the impact of the constrained loss. We evaluate its effectiveness on the ROAD-R and ROAD-Waymo-R datasets for object detection in AD, using attached common-sense constraints. Our results show that careful selection of parameters is crucial for effective constrained loss behavior. Moreover, our framework not only reduces constraint violations but also, in some cases, improves detection performance. Additionally, our methods offer fine-grained control over the trade-off between accuracy and constraint violation.

The use of deep learning to solve fundamental AI problems such as Boolean Satisfiability (SAT) has been explored recently to develop robust and scalable reasoning systems. This work advances such neural-based reasoning approaches by developing a new Graph Neural Network (GNN) to differentiably solve (weighted) Maximum Satisfiability (MaxSAT). To this end, we propose SAT-based Graph Attention Networks (SGATs) as novel GNNs that are built on t-norm based attention and message passing mechanisms, and structurally designed to approximate greedy distributed local search. To demonstrate the effectiveness of our model, we develop a local search solver that uses SGATs to continuously solve any given MaxSAT problem. Experiments on (weighted) MaxSAT benchmark datasets demonstrate that SGATs significantly outperform existing neural-based architectures, and achieve state-of-the-art performance among continuous approaches, highlighting the strength of the proposed model.

In this paper, we propose an enhancement to the SAT-based counterexample-guided abstraction refinement (CEGAR) approach for solving the Hamiltonian Cycle Problem (HCP). Many SAT-based methods for HCP have been proposed, including a CEGAR-based method that repeatedly solves a relaxed version of HCP strengthened by counterexamples. However, when the counterexample space - represented by the full set of subcycle partitions - is large, it becomes difficult to find a solution. To address this, we introduce cut-set constraints in the refinement step, replacing traditional subcycle blocking constraints. Our evaluation shows that these cut-set constraints achieve equal or better reduction in the counterexample space, making it easier to find valid solutions. We further assessed performance using all 1001 instances from the FHCP challenge set and confirmed that the proposed method solved 937 instances within 1800 seconds, outperforming both the existing eager and CEGAR encodings (which solved at most 666 instances). This demonstrates the effectiveness of incorporating cut-set constraints into SAT-based CEGAR approaches.

This paper presents BeliefFlow, a novel framework for representing how logical beliefs spread among interacting agents within a network. In a Belief Flow Network (BFN), agents communicate asynchronously. The agents' beliefs are represented using epistemic states, which encompass their current beliefs and conditional beliefs guiding future changes. When communication occurs between two connected agents, the receiving agent changes its epistemic state using an improvement operator, a well-known type of rational iterated belief change operator that generalizes belief revision operators. We show that BFNs satisfy appealing properties, leading to two significant outcomes. First, in any BFN with strong network connectivity, the beliefs of all agents converge towards a global consensus. Second, within any BFN, we show that it is possible to compute an optimal strategy for influencing the global beliefs. This strategy, which involves controlling the beliefs of a least number of agents through bribery, can be identified from the topology of the network and can be computed in polynomial time.

We introduce a new method for integrating neural networks with logic programming in Neural-Symbolic AI (NeSy), aimed at learning with distant supervision, in which direct labels are unavailable. Unlike prior methods, our approach does not depend on symbolic solvers for reasoning about missing labels. Instead, it evaluates logical implications and constraints in a differentiable manner by embedding both neural network outputs and logic programs into matrices. This method facilitates more efficient learning under distant supervision. We evaluated our approach against existing methods while maintaining a constant volume of training data. The findings indicate that our method not only matches or exceeds the accuracy of other methods across various tasks but also speeds up the learning process. These results highlight the potential of our approach to enhance both accuracy and learning efficiency in NeSy applications.

In logic programming, partial evaluation (PE) performs unfolding rules in advance to reduce the cost of inferencing. Recently, PE of logic programs has been implemented in vector spaces by computing the powers of matrix representations. It has been reported that linear algebraic PE substantially enhances the practical performance of linear algebraic methods for logic programming. However, most recent research has focused exclusively on And-rules, assuming that their dependency graph is acyclic. In this paper, we introduce cycle-resolving techniques to ensure that linear algebraic PE works effectively even with cycles in the program. Additionally, we demonstrate that linear algebraic PE can also be extended to accommodate Or-rules. Moreover, we propose using eigendecomposition and Jordan normal form to conduct PE in vector spaces. We compare the proposed techniques on a set of acyclic and cyclic logic programs to evaluate their effectiveness. It is shown that the iteration method for PE, especially with sparse format, is the most efficient one in general cases. However, the decomposition method has the potential for future research to leverage eigenvalues and eigenvectors of program matrices for reasoning.

We explore the problem of explaining observations starting from a classically inconsistent theory by adopting a paraconsistent framework. We consider two expansions of the well-known Belnap-Dunn paraconsistent four-valued logic BD: BD-circ introduces formulas of the form circ phi (‘the information about phi is reliable’), while BD-triangle augments the language with formulas triangle phi (‘there is information that phi is true’). We define and motivate the notions of abduction problems and explanations in BD-circ and BD-triangle and show that they are not reducible to one another. We analyse the complexity of standard abductive reasoning tasks (solution recognition, solution existence, and relevance / necessity of hypotheses) in both logics. Finally, we show how to reduce abduction in BD-circ and BD-triangle to abduction in classical propositional logic, thereby enabling the reuse of existing abductive reasoning procedures.

We propose Large Neighborhood Prioritized Search (LNPS) for solving combinatorial optimization problems in Answer Set Programming (ASP). LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution. Due to the variability of neighborhoods, LNPS allows for flexible search without strongly depending on the destroy operators. We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization. Furthermore, we establish the competitiveness of our LNPS approach by empirically contrasting it to (adaptive) large neighborhood search.

Abstract We propose a method for generating rule sets as global and local explanations for tree-ensemble learning methods using answer set programming (ASP). To this end, we adopt a decompositional approach where the split structures of the base decision trees are exploited in the construction of rules, which in turn are assessed using pattern mining methods encoded in ASP to extract explanatory rules. For global explanations, candidate rules are chosen from the entire trained tree-ensemble models, whereas for local explanations, candidate rules are selected by only considering rules that are relevant to the particular predicted instance. We show how user-defined constraints and preferences can be represented declaratively in ASP to allow for transparent and flexible rule set generation, and how rules can be used as explanations to help the user better understand the models. Experimental evaluation with real-world datasets and popular tree-ensemble algorithms demonstrates that our approach is applicable to a wide range of classification tasks.

This paper is about editing Boolean classifiers, i.e., determining how a Boolean classifier should be modified when new pieces of evidence must be incorporated. Our main goal is to delineate what are the rational ways of making such edits. This goes through a number of rationality postulates inspired from those considered so far for belief revision. We give a representation theorem and present some families of edit operators satisfying the postulates.

Abstract Boolean networks (BNs) are well-studied models of genomic regulation in biology where nodes are genes and their state transition is controlled by Boolean functions. We propose to learn Boolean functions as Boolean formulas in disjunctive normal form (DNFs) by an explainable neural network Mat_DNF and apply it to learning BNs. Directly expressing DNFs as a pair of binary matrices, we learn them using a single layer NN by minimizing a logically inspired non-negative cost function to zero. As a result, every parameter in the network has a clear meaning of representing a conjunction or literal in the learned DNF. Also we can prove that learning DNFs by the proposed approach is equivalent to inferring interpolants in logic between the positive and negative data. We applied our approach to learning three literature-curated BNs and confirmed its effectiveness. We also examine how generalization occurs when learning data is scarce. In doing so, we introduce two new operations that can improve accuracy, or equivalently generalizability for scarce data. The first one is to append a noise vector to the input learning vector. The second one is to continue learning even after learning error becomes zero. The first one is explainable by the second one. These two operations help us choose a learnable DNF, i.e., a root of the cost function, to achieve high generalizability.

Learning first-order logic programs (LPs) from relational facts which yields intuitive insights into the data is a challenging topic in neuro-symbolic research. We introduce a novel differentiable inductive logic programming (ILP) model, called differentiable first-order rule learner (DFOL), which finds the correct LPs from relational facts by searching for the interpretable matrix representations of LPs. These interpretable matrices are deemed as trainable tensors in neural networks (NNs). The NNs are devised according to the differentiable semantics of LPs. Specifically, we first adopt a novel propositionalization method that transfers facts to NN-readable vector pairs representing interpretation pairs. We replace the immediate consequence operator with NN constraint functions consisting of algebraic operations and a sigmoid-like activation function. We map the symbolic forward-chained format of LPs into NN constraint functions consisting of operations between subsymbolic vector representations of atoms. By applying gradient descent, the trained well parameters of NNs can be decoded into precise symbolic LPs in forward-chained logic format. We demonstrate that DFOL can perform on several standard ILP datasets, knowledge bases, and probabilistic relation facts and outperform several well-known differentiable ILP models. Experimental results indicate that DFOL is a precise, robust, scalable, and computationally cheap differentiable ILP model.

One task of game designers is to give NPCs fun behaviors, where “fun” can have many different manifestations. Several classic methods exist in Game AI to model NPCs' behaviors; one of them is utility-based AI. Utility functions constitute a powerful tool to define behaviors but can be tedious and time-consuming to make and tune correctly until the desired behavior is achieved. Here, we propose a method to learn utility functions from data collected after some human-played games, to recreate a target behavior. Utility functions are modeled using Interpretable Compositional Networks, allowing us to get interpretable results, unlike regular neural networks. We show our method can handle noisy data and learn utility functions able to credibly reproduce different target behaviors, with a median accuracy from 64.5% to 83.7%, using the FightingICE platform, an environment for AI agent competitions. We believe our method can be useful to game designers to quickly prototype NPCs' behaviors, and even to define their final utility functions.

Trying to infer the strategy of the opponent is very important in games. Especially in Real-Time Strategy Games (RTS), where you have uncertainty and thus cannot see most of the opponent’s actions, but you do not want to be unprepared for its strategy. Good human players can do it almost naturally, but it is a different story for AI players. Plan recognition is a challenging problem, especially with uncertainty and the number of possible actions and states of the world in RTS games. We address the problem of plan recognition in RTS games. We show that an approach based on plan recognition as planning and heuristic search can yield good results and be robust to noise. Furthermore, we found that such an approach has its accuracy decreasing slightly with noisy data, does not need any training beforehand, and could be easily adapted to different RTS games.Our approach allows us to infer in real-time the plan that a player might be pursuing in an RTS game, here we focus on the RTS game called StarCraft, but it could be adapted to many other RTS games.

Linear algebraic characterization of logic programs has been investigated to perform logical inference in large-scale knowledge bases and has gained encouraging results. In this paper, we further extend the linear algebraic characterization in abductive reasoning by exploiting the transpose of the program matrix. Then we propose an efficient exhaustive search strategy, which combines the flexibility and robustness of numerical computation with the compactness and efficiency of set operations, in order to compute solutions of abductive Horn propositional tasks. Experimental results demonstrate that our method is competitive with conflict-driven techniques and has the potential to speed up on parallel computing platforms.

Abstract In this paper, we introduce methods of encoding propositional logic programs in vector spaces. Interpretations are represented by vectors and programs are represented by matrices. The least model of a definite program is computed by multiplying an interpretation vector and a program matrix. To optimize computation in vector spaces, we provide a method of partial evaluation of programs using linear algebra. Partial evaluation is done by unfolding rules in a program, and it is realized in a vector space by multiplying program matrices. We perform experiments using artificial data and real data, and show that partial evaluation has the potential for realizing efficient computation of huge scale of programs in vector spaces.

Digital games have proven to be valuable simulation environments for plan and goal recognition. Though, goal recognition is a hard problem, especially in the field of digital games where players unintentionally achieve goals through exploratory actions, abandon goals with little warning, or adopt new goals based upon recent or prior events. In this paper, a method using simulation and bayesian programming to infer the player's strategy in a Real-Time-Strategy game (RTS) is described, as well as how we could use it to make more adaptive AI for this kind of game and thus make more challenging and entertaining games for the players.

Team formation (TF) faces the problem of defining teams of agents able to accomplish a set of tasks. Resilience on TF problems aims to provide robustness and adaptability to unforeseen events involving agent deletion. However, agents are unaware of the inherent social welfare in these teams. This article tackles the problem of how teams can minimise their effort in terms of organisation and communication considering these dynamics. Our main contribution is twofold: first, we introduce the Stabilisable Team Formation (STF) as a generalisation of current resilient TF model, where a team is stabilisable if it possesses and preserves its inter-agent organisation from a graph-based perspective. Second, our experiments show that stabilisability is able to reduce the exponential execution time in several units of magnitude with the most restrictive configurations, proving that communication effort in subsequent task allocation problems are relaxed compared with current resilient teams. To do so, we developed SBB-ST, a branch-and-bound algorithm based on Distributed Constrained Optimisation Problems (DCOP) to compute teams. Results evidence that STF improves their predecessors, extends the resilience to subsequent task allocation problems represented as DCOP, and evidence how Stabilisability contributes to resilient TF problems by anticipating decisions for saving resources and minimising the effort on team organisation in dynamic scenarios.

Meta-Interpretive Learning (MIL) is a recent approach for Inductive Logic Programming (ILP) implemented in Prolog. Alternatively, MIL-problems can be solved by using Answer Set Programming (ASP), which may result in performance gains due to efficient conflict propagation. However, a straightforward MIL-encoding results in a huge size of the ground program and search space. To address these challenges, we encode MIL in the HEX-extension of ASP, which mitigates grounding issues, and we develop novel pruning techniques.

We consider the problem of identifying the change formula in a belief revision scenario: given that an unknown announcement (a formula mu) led a set of agents to revise their beliefs and given the prior beliefs and the revised beliefs of the agents, what can be said about mu? We show that under weak conditions about the rationality of the revision operators used by the agents, the set of candidate formulae has the form of a logical interval. We explain how the bounds of this interval can be tightened when the revision operators used by the agents are known and/or when mu is known to be independent from a given set of variables. We also investigate the completeness issue, i.e., whether mu can be exactly identified. We present some sufficient conditions for it, identify its computational complexity, and report the results of some experiments about it.

In this demonstration, a real-time auto-exposure Histogram Equalization (HE) video-system is presented. The video histogram is extracted in each frame by the Frequent Items Counter (FIC) core. Based on the HE Transformation Function (HE-TF), the camera exposure value is adjusted to fit the current luminance condition. The proposed system was developed on the VEEK-MT-SoCKit with an FPGA chip of Altera Cyclone V SoC and a 5-Megapixel (5-MP) Charge Coupled Device (CCD). The video resolution is 1280×800. The monitor display rate is at 60Hz while the CCD capture rate is at 24.28Hz to 38.98Hz depend on the exposure value. The histogram, the transformation function, and the camera exposure value are changed in each frame to satisfy the real-time requirement.

Although bitmap index (BI) can surmount complex and multi-dimensional queries, the creation of BI itself is a time-consuming task. Many studies exploit the highly parallel processing capabilities of multi-core CPUs, graphics processing units (GPUs), or field-programmable gate arrays (FPGAs) to overcome this obstacle. This study, on the other hand, proposes a 65-nm silicon-on-thin-buried-oxide (SOTB) hardware accelerator dedicated to BI creation. The fabricated chip could operate at different supply voltages, from 0.45-V to 1.2-V. Concretely, in the active mode with the supply voltage of 1.2-V, this chip was fully operational at 90-MHz and consumed approximately 88.1-pJ/cycle. In the standby mode with the supply voltage of 0.45-V and clock gated, the power consumption was only 476.1-nW. Moreover, when the reverse back-gate bias voltage of -2.5-V is supplied, the standby power sharply dropped to 0.27-nW or approximately 1,763 times. This achievement is vitally essential for the energy-efficient applications, where the performance should be maximized during peak workload hours and the power should be minimized during off-peak time.

We propose a new approach to abduction, i.e., non-deductive inference to find a hypothesis H for an observation O such that H,KB |- O where KB is background knowledge. We reformulate it linear algebraically in vector spaces to abduce ``relations'', not logical formulas, to realize approximate but scalable abduction that can deal with web-scale knowledge bases. More specifically we consider the problem of abducing relations for Datalog programs with binary predicates. We treat two cases, the non-recursive case and the recursive case. In the non-recursive case, given r1(X,Y) and r3(X,Z), we abduce r2(Y,Z) so that r3(X,Z) <= r1(X,Y)&r2(Y,Z) approximately holds, by computing a matrix R2 that approximately satisfies a matrix equation R3 = min1(R1R2) containing a nonlinear function min1(x). Here R1, R2 andR3 encode as adjacency matrix r1(X,Y), r2(Y,Z) and r3(Y,Z) respectively. We apply this matrix-based abduction to rule discovery and relation discovery in a knowledge graph. The recursive case is mathematically more involved and computationally more difficult but solvable by deriving a recursive matrix equation and solving it. We illustrate concrete recursive cases including a transitive closure relation.

Priority encoder (PE) is recognized as an indispensable component in the content-addressable memory. In this paper, two efficient architecture of 64-bit PE and 256-bit PE using 1D-array to 2D-array conversion (1D-to-2D) method are presented and implemented in a 65-nm Silicon-on-thin-buried-oxide (SOTB) CMOS process. The 1D-to-2D method is exploited because of its advantages in large-sized PE construction. The SOTB CMOS process is utilized because of its prominent advantages of low-power and high-performance configuration using back bias voltages. The measurement results at 1.2 V showed that a fabricated PE256 chip was fully operational at 45 MHz and consumed approximately 219 μW. Additionally, in sleep mode, the leakage power dropped as low as 0.34 μW at 0.6 V.

Abstract Meta-Interpretive Learning (MIL) learns logic programs from examples by instantiating meta-rules, which is implemented by the Metagol system based on Prolog. Viewing MIL-problems as combinatorial search problems, they can alternatively be solved by employing Answer Set Programming (ASP), which may result in performance gains as a result of efficient conflict propagation. However, a straightforward ASP-encoding of MIL results in a huge search space due to a lack of procedural bias and the need for grounding. To address these challenging issues, we encode MIL in the HEX-formalism, which is an extension of ASP that allows us to outsource the background knowledge, and we restrict the search space to compensate for a procedural bias in ASP. This way, the import of constants from the background knowledge can for a given type of meta-rules be limited to relevant ones. Moreover, by abstracting from term manipulations in the encoding and by exploiting the HEX interface mechanism, the import of such constants can be entirely avoided in order to mitigate the grounding bottleneck. An experimental evaluation shows promising results.

Learning from interpretation transition (LFIT) automatically constructs a model of the dynamics of a system from the observation of its state transitions. So far, the systems that LFIT handles are restricted to discrete variables or suppose a discretization of continuous data. However, when working with real data, the discretization choices are critical for the quality of the model learned by LFIT . In this paper, we focus on a method that learns the dynamics of the system directly from continuous time-series data. For this purpose, we propose a modeling of continuous dynamics by logic programs composed of rules whose conditions and conclusions represent continuums of values.

Text analytics has become increasingly important in the past few years because of the substantial growth in the amount of research, business, and government needs. An efficient text analytics system is likely to require high-powered regular expression matching (REGEX), as REGEX operations dominate the whole execution time. Some approaches have exploited the parallelism of graphic processing units (GPUs) and field-programmable logic arrays (FPGAs) to boost REGEX's performance. Nevertheless, those approaches still used finite-state automaton to detect the given patterns while automation structure is naturally inadequate for parallel processing. In this paper, we propose a completely different hardware architecture of REGEX that employs a bitmap index instead of the finite-state automaton. Internal logic gates/registers and embedded memory of FPGA are used to construct the query processing units and a bitmap index, respectively. The experimental results on an Intel Arria V FPGA prove that our REGEX is fully operational at 100 MHz and can process a 64-character query inside a 64-KB text data within 43.76 μs. The throughput achieved, therefore, reaches 11.98 Gbps.

Probabilistic planners have improved recently to the point that they can solve difficult tasks with complex and expressive models. In contrast, learners cannot tackle yet the expressive models that planners do, which forces complex models to be mostly handcrafted. We propose a new learning approach that can learn relational probabilistic models with both action effects and exogenous effects. The proposed learning approach combines a multi-valued variant of inductive logic programming for the generation of candidate models, with an optimization method to select the best set of planning operators to model a problem. We also show how to combine this learner with reinforcement learning algorithms to solve complete problems. Finally, experimental validation is provided that shows improvements over previous work in both simulation and a robotic task. The robotic task involves a dynamic scenario with several agents where a manipulator robot has to clear the tableware on a table. We show that the exogenous effects learned by our approach allowed the robot to clear the table in a more efficient way.

An overview of notable ILP areas, focusing on three invited talks at ILP 2015, two best student papers and the panel discussion on "ILP 25 Years".

Recent years have witnessed a massive growth of global data due to the ubiquitous internet-of-thing products, social networking services, and mobile devices. Fast database analytics, therefore, has been increasingly attractive to numerous research. In this paper, a low-latency FPGA-based Database Processor (DBP) using bitmap index is proposed. By exploiting available embedded memory blocks and logic elements, a 50-MHz DBP is capable of performing 1,024 queries for entire 32,768 4-KB records within around 3.31 ms. In other words, the DBP can analyze a capacity data of nearly 37.76 GB per second.

Abstract We address the problem of belief revision of logic programs (LPs), i.e., how to incorporate to a LP P a new LP Q. Based on the structure of SE interpretations, Delgrande et al. (2008. Proc. of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR'08), 411–421; 2013b. Proc. of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'13), 264–276) adapted the well-known AGM framework (Alchourrón et al. 1985. Journal of Symbolic Logic 50, 2, 510–530) to LP revision. They identified the rational behavior of LP revision and introduced some specific operators. In this paper, a constructive characterization of all rational LP revision operators is given in terms of orderings over propositional interpretations with some further conditions specific to SE interpretations. It provides an intuitive, complete procedure for the construction of all rational LP revision operators and makes easier the comprehension of their semantic and computational properties. We give a particular consideration to LPs of very general form, i.e., the generalized logic programs (GLPs). We show that every rational GLP revision operator is derived from a propositional revision operator satisfying the original AGM postulates. Interestingly, the further conditions specific to GLP revision are independent from the propositional revision operator on which a GLP revision operator is based. Taking advantage of our characterization result, we embed the GLP revision operators into structures of Boolean lattices, that allow us to bring to light some potential weaknesses in the adapted AGM postulates. To illustrate our claim, we introduce and characterize axiomatically two specific classes of (rational) GLP revision operators which arguably have a drastic behavior. We additionally consider two more restricted forms of LPs, i.e., the disjunctive logic programs (DLPs) and the normal logic programs (NLPs) and adapt our characterization result to disjunctive logic program and normal logic program revision operators.

Belief revision games (BRGs) are concerned with the dynamics of the beliefs of a group of communicating agents. BRGs are "zero-player" games where at each step every agent revises her own beliefs by taking account for the beliefs of her acquaintances. Each agent is associated with a belief state defined on some finite propositional language. We provide a general definition for such games where each agent has her own revision policy, and show that the belief sequences of agents can always be finitely characterized. We then define a set of revision policies based on belief merging operators. We point out a set of appealing properties for BRGs and investigate the extent to which these properties are satisfied by the merging-based policies under consideration.

Delayed effects are important in modeling biological systems, and timed Boolean networks have been proposed for such a framework. Yet it is not an easy task to design such Boolean models with delays precisely. Recently, an attempt to learn timed Boolean networks has been made in Ribeiro et al 2015 in the framework of learning state transition rules from time-series data. However, this approach still has two limitations: (1) The maximum delay has to be given as input to the algorithm, (2) The possible value of each state is assumed to be Boolean, i.e., twovalued. In this paper, we extend the previous learning mechanism to overcome these limitations. We propose an algorithm to learn multi-valued biological models with delayed influence by automatically tuning the delay. The delay is determined so as to minimally explain the necessary influences. The merits of our approach is then verified on benchmarks coming from the DREAM4 challenge.

A Constraint Satisfaction Problem (CSP) is a fundamental problem that can formalize various applications related to Artificial Intelligence problems. A Weighted Constraint Satisfaction Problem (WCSP) is a CSP where constraints can be violated, and the aim of this problem is to find an assignment that minimizes the sum of weights of the violated constraints. Most researches have focused on developing algorithms for solv- ing static mono-objective problems. However, many real world satisfaction/optimization problems involve multiple criteria that should be considered separately and satisfied/optimized simultaneously. Additionally, they are often dynamic, i.e., the problem changes at runtime. In this paper, we introduce a Multi-Objective WCSP (MO-WCSP) and develop a novel MO-WCSP algorithm called Multi-Objective Branch and Bound (MO-BnB), which is based on a new solution criterion called (l, s)-Pareto solution. Furthermore, we first for- malize a Dynamic MO-WCSP (DMO-WCSP). As an initial step forward developing an algorithm for solving a DMO-WCSP, we focus on the change of weights of constraints and develop the first algorithm called Dynamic Multi-Objective Branch and Bound (DMO-BnB) for solving a DMO-WCSPs, which is based on MO-BnB. Finally, we provide the complexity of our algorithm and evaluate DMO-BnB with different problem settings.

We address the problem of multi-objective constraint optimization problems (MO-COPs). Solving a MO-COP traditionally consists in computing the set of all Pareto optimal solutions, which is an exponentially large set in the general case. So this causes two main problems: first is the time complexity concern, second is a lack of decisiveness. In this paper, we formalize the notion of a MO-COP operator which associates every MO-COP with a subset of Pareto optimal solutions satisfying some desirable additional properties. Then, we present two specific classes of MO-COP operators that give preference to some subsets of Pareto optimal solutions. These operators correspond to two classical doctrines in Decision Theory: utilitarianism and egalitarianism. They compute solutions much more efficiently than standard operators computing all Pareto optimal solutions. In practice, they return a very few number of solutions even for problems involving a high number of objectives.

Environment domain models are a key part of the information used by adaptive systems to determine their behaviour. These models can be incomplete or inaccurate. In addition, since adaptive systems generally operate in environments which are subject to change, these models are often also out of date. To update and correct these models, the system should observe how the environment responds to its actions, and compare these responses to those predicted by the model. In this paper, we use a probabilistic rule learning approach, NoMPRoL, to update models using feedback from the running system in the form of execution traces. NoMPRoL is a technique for nonmonotonic probabilistic rule learning based on a transformation of an inductive logic programming task into an equivalent abductive one. In essence, it exploits consistent observations by finding general rules which explain observations in terms of the conditions under which they occur. The updated models are then used to generate new behaviour with a greater chance of success in the actual environment encountered.

This paper describes techniques for simplifying a propositional clausal formula during the search process of the satisfiability checking of the formula. Generally, simplification technique has a trade-off between the checking cost and the effect of it. If the simplification technique is executed during search, then the cost can be problematic. We propose some on-the-fly simplification techniques whose computational cost is negligibly small. Hence, these techniques are executed frequently throughout the process of a CDCL solver, that is, unit propagation, conflict analysis, removal of satisfied clauses, etc. The proposed simplification techniques are based on binary resolvents, which are derived from unit propagation process, and consist of various probing techniques, self-subsuming resolution and on-demand addition of binary resolvents. The experimental results show that these simplification techniques can improve the performance of CDCL solvers.

A CAM-based (Content Addressable Memory) image matching system is implemented on hardware system using FPGA. The system has simple structure, does not employ any Central Processor Units (CPUs) as well as complicated computations. The authors take advantages of CAM which has an ability of parallel multi-match mode for designing the system. Thus increases the matching performance of the system. The system is applied for exact image matching or approximate image matching with various required search patterns without using search principles. In this paper, the authors present the system for fast image matching applications on 2-D data.

Meta-level abduction is a method to abduce missing rules in explaining observations. By representing rule structures of a problem in a form of causal networks, meta-level abduction infers missing links and unknown nodes from incomplete networks to complete paths for observations. We examine applicability of meta-level abduction on networks containing both positive and negative causal effects. Such networks appear in many domains including biology, in which inhibitory effects are important in several biological pathways. Reasoning in networks with inhibition involves nonmonotonic inference, which can be realized by making default assumptions in abduction. We show that meta-level abduction can consistently produce both positive and negative causal relations as well as invented nodes. Case studies of meta-level abduction are presented in p53 signaling networks, in which causal relations are abduced to suppress a tumor with a new protein and to stop DNA synthesis when damage has occurred. Effects of our method are also analyzed through experiments of completing networks randomly generated with both positive and negative links.

Abstract The course timetabling problem can be generally defined as the task of assigning a number of lectures to a limited set of timeslots and rooms, subject to a given set of hard and soft constraints. The modeling language for course timetabling is required to be expressive enough to specify a wide variety of soft constraints and objective functions. Furthermore, the resulting encoding is required to be extensible for capturing new constraints and for switching them between hard and soft, and to be flexible enough to deal with different formulations. In this paper, we propose to make effective use of ASP as a modeling language for course timetabling. We show that our ASP-based approach can naturally satisfy the above requirements, through an ASP encoding of the curriculum-based course timetabling problem proposed in the third track of the second international timetabling competition (ITC-2007). Our encoding is compact and human-readable, since each constraint is individually expressed by either one or two rules. Each hard constraint is expressed by using integrity constraints and aggregates of ASP. Each soft constraint S is expressed by rules in which the head is the form of penalty(S,V,C), and a violation V and its penalty cost C are detected and calculated respectively in the body. We carried out experiments on four different benchmark sets with five different formulations. We succeeded either in improving the bounds or producing the same bounds for many combinations of problem instances and formulations, compared with the previous best known bounds.

Inductive Logic Programming (ILP) is an area of Machine Learning which has now reached its twentieth year. Using the analogy of a human biography this paper recalls the development of the subject from its infancy through childhood and teenage years. We show how in each phase ILP has been characterised by an attempt to extend theory and implementations in tandem with the development of novel and challenging real-world applications. Lastly, by projection we suggest directions for research which will help the subject coming of age.

There is a growing interest in building large knowledge bases. Dealing with a huge amount of knowledge, two problems can be encountered in real domains. The first case is that knowledge is originally centralized so that one can access the whole knowledge but the size of the knowledge base is too huge to be handled. The second case is that knowledge is distributed in several sources so that it is hard or impossible to immediately access the whole or part of knowledge. We focus here on the case in which a single reasoner might not be able to cope with the entire database, and tries to partitioned the data to improve its scalability, which is likely to happen if the knowledge is partitioned into overlapping but cohesive components. We thus consider distributed reasoning with such structures, each partition collaborating with the other to produce a coherent output. We thus propose a generalization of partition-based theorem proving to partition-based consequence finding (sharing a specification of ``interesting'' consequences), with a sequential and a parallel version. As termination cannot always be ensured in first order, we also investigate bounded searches. Finally we provide an experimental analysis comparing our two variants with the centralized case using some automated process to decompose the theory, and show that for most problems, partitioning the data can indeed increase the efficiency, though proper choice of the decomposition (and especially of the starting point of the algorithm) can be difficult.

The Boolean network is a mathematical model of biological systems, and has attracted much attention as a qualitative tool for analyzing the regulatory system. The stable states and dynamics of Boolean networks are characterized by their attractors, whose properties have been analyzed computationally, yet not much work has been done from the viewpoint of logical inference systems. In this paper, we show direct translations of Boolean networks into logic programs, and propose new methods to compute their trajectories and attractors based on inference on such logic programs. In particular, point attractors of both synchronous and asynchronous Boolean networks are characterized as supported models of logic programs so that SAT techniques can be applied to compute them. Investigation of these relationships suggests us to view Boolean networks as logic programs and vice versa.

What happens when distributed sources of information (agents) hold and acquire information locally, and have to communicate with neighbouring agents in order to refine their hypothesis regarding the actual global state of this environment? This question occurs when it is not be possible (e. g. for practical or privacy concerns) to collect observations and knowledge, and centrally compute the resulting theory. In this paper, we assume that agents are equipped with full clausal theories and individually face abductive tasks, in a globally consistent environment. We adopt a learner/critic approach. Previous work in this line mostly relied on some assumptions of compositionality (which allow to treat each piece of exchanged information separately). Because no shared background knowledge is assumed to start with, this does not hold here. We design a protocol guaranteeing convergence to a situation “sufficiently” satisfying as far as consistency of the system is concerned, and discuss its other properties.

We propose a satisfiability testing (SAT) based exact approach for solving the two-dimensional strip packing problem (2SPP). In this problem, we are given a set of rectangles and one large rectangle called a strip. The goal of the problem is to pack all rectangles without overlapping, into the strip by minimizing the overall height of the packing. Although the 2SPP has been studied in Operations Research, some instances are still hard to solve. Our method solves the 2SPP by translating it into a SAT problem through a SAT encoding called order encoding. The translated SAT problems tend to be large; thus, we apply several techniques to reduce the search space by symmetry breaking and positional relations of rectangles. To solve a 2SPP, that is, to compute the minimum height of a 2SPP, we need to repeatedly solve similar SAT problems. We thus reuse learned clauses and assumptions from the previously solved SAT problems. To evaluate our approach, we obtained results for 38 instances from the literature and made comparisons with a constraint satisfaction solver and an ad-hoc 2SPP solver.

This paper proposes a novel grammar-based framework of concept representation for randomized search in Relational Learning (RL), namely for Inductive Logic Programming. The utilization of grammars guarantees that the search operations produce syntactically correct concepts and that the background knowledge encoded in the grammar can be used both for directing the search and for restricting the space of possible concepts to relevant candidate concepts (semantically valid concepts). Not only that it enables handling and incorporating the domain knowledge in a declarative fashion, but grammars also make the new approach transparent, flexible, less problem-specific and allow it to be easily used by almost any randomized algorithm within RL. Initial test results suggest that the grammar-based algorithm has strong potential for RL tasks.

This paper introduces two methods for comparing explanation power of different abductive theories. One is comparing for observations, and the other is comparing explanation content for observations. Those two measures are represented by generality relations over abductive theories. The generality relations are naturally related to the notion of abductive equivalence introduced by Inoue and Sakama. We also analyze the computational complexity of these relations.

Egawa and Saito proved that every k-connected graph with girth at least 4 has an induced cycle C such that $G-V(C)$ is $(k-3)$-connected, and every edge of C is contractible. This means that we can find not only a nonseparating cycle C but also one that consists of contractible edges. Motivated by this result, we prove that if G is a k-connected graph which does not contain $K_4^{-}$, then G has an induced cycle C such that $G - V(C)$ is $(k-2)$-connected and either every edge of C is k-contractible or C is a triangle. As a corollary of this result, we get the following result: Every k-connected graph with girth at least 4 has an induced cycle C such that $G-V(C)$ is $(k-2)$-connected, and every edge of C is contractible. This theorem is a generalization of some known theorems. In particular, this generalizes the above-mentioned result proved by Egawa and Saito and the result of Egawa which says that a k-connected graph with girth at least 4 has an induced cycle C such that $G-V(C)$ is $(k-2)$-connected.

This article studies a semantics of multiple logic programs, and synthesizes a program having such a collective semantics. More precisely, the following two problems are considered: given two logic programs P 1 and P 2 , which have the collections of answer sets AS ( P 1 ) and AS ( P 2 ), respectively; (i) find a program Q which has the set of answer sets such that AS ( Q ) = AS ( P 1 ) ∪ AS ( P 2 ); (ii) find a program R which has the set of answer sets such that AS ( R ) = AS ( P 1 ) ∩ AS ( P 2 ). A program Q satisfying the condition (i) is called generous coordination of P 1 and P 2 ; and R satisfying (ii) is called rigorous coordination of P 1 and P 2 . Generous coordination retains all of the answer sets of each program, but permits the introduction of additional answer sets of the other program. By contrast, rigorous coordination forces each program to give up some answer sets, but the result remains within the original answer sets for each program. Coordination provides a program that reflects the meaning of two or more programs. We provide methods for constructing these two types of coordination and address its application to logic-based multi-agent systems.

In this paper, we present a current cooperative work involving different Institutes around the world. Our aim is to provide an online inductive logic programming tool. This is the first step in a more complete structure for enabling e-technology for machine learning and bio-informatics. We describe the main architecture of the project and how the data will be formatted for being sent to the ILP machinery. We focus on a biological application (yeast fermentation process) due to its importance for high added value end products.

This paper introduces an abductive framework for updating knowledge bases represented by extended disjunctive programs. We first provide a simple transformation from abductive programs to update programs which are logic programs specifying changes on abductive hypotheses. Then, extended abduction, which was introduced by the same authors as a generalization of traditional abduction, is computed by the answer sets of update programs. Next, different types of updates, view updates and theory updates are characterized by abductive programs and computed by update programs. The task of consistency restoration is also realized as special cases of these updates. Each update problem is comparatively assessed from the computational complexity viewpoint. The result of this paper provides a uniform framework for different types of knowledge base updates, and each update is computed using existing procedures of logic programming.

In recent years, research on planning algorithms has made big progress. Recent approaches encode the plan search space into a data structure called the planning graph. To extract plans, a planning graph is transformed into the satisfiability problem (SAT), which is solved by a high-speed SAT solver. This kind of planning is called SAT planning. On the other hand, recent research on reasoning about action has also progressed. Since Gelfond and Lifschitz (1993) proposed the action language /spl Ascr/, a lot of work has been done to improve action languages. We combine these two approaches. Namely, we extend techniques for SAT planning to cover other aspects of reasoning about action, so that various types of queries can be answered for action languages. For this purpose, we implemented an action language processing system AMP in Java. Using this system, it becomes possible to answer queries for not only planning but model generation for a domain description written in the action language /spl Ascr/.

A hybrid genetic algorithm (GA) which combines the global search power of GA with the local search power of a local optimization algorithm is described for the graph coloring problem (GCP). Each solution of the GCP, which is called phenotype, is represented by a set of isomorphic genotypes conceptually. Then, a metric function between two phenotypes is defined by the least Hamming distance between the corresponding sets of isomorphic genotypes. The phenotypic distance is useful to analyze and control the behavior of genotypes in the search space from the view point of the problem space. A new crossover technique named harmonic crossover is proposed for the GCP. The phenotypic distance between two parents is considered in the harmonic crossover for preserving their common characteristics. Furthermore, the phenotypic distance between two parents is also used to predict promising regions in the problem space. In the proposed hybrid GA for the GCP, the local optimization algorithm is applied only in the most promising regions restrictedly and intensively. Consequently, the run of the local optimization algorithm does not hinder the performance of GA in its progress of global search.

This paper presents declarative semantics of possibly inconsistent disjunctive logic programs. We introduce the paraconsistent minimal and stable model semantics for extended disjunctive programs, which can distinguish inconsistent information from other information in a program. These semantics are based on lattice-structured multi-valued logics, and are characterized by a new fixpoint semantics of extended disjunctive programs. Applications of the paraconsistent semantics for reasoning in inconsistent programs are also presented.