Search

International audience; We extend the existing encoding of abstract argumentation frameworks in DL-PA (Dynamic Logic of Propositional Assignments) in order to capture different formalisms for arguing with qualitative forms of uncertainty. More in particular, we encode the main reasoning tasks of (rich) incomplete argumentation frameworks and control argumentation frameworks. After that, and inspired by our encoding, we define and study a new class of structures that are shown to be maximally expressive: constrained incomplete argumentation frameworks.

The Classic McEliece cryptosystem is one of the most trusted quantum-resistant cryptographic schemes. Deploying it in practical applications, however, is challenging due to the size of its public key. In this work, we bridge this gap. We present an implementation of Classic McEliece on an ARM Cortex-M4 processor, optimized to overcome memory constraints. To this end, we present an algorithm to retrieve the public key ad-hoc. This reduces memory and storage requirements and enables the generation of larger key pairs on the device. To further improve the implementation, we perform the public key operation by streaming the key to avoid storing it as a whole. This additionally reduces the risk of denial of service attacks. Finally, we use these results to implement and run TLS on the embedded device.

We present a new approximation algorithm for the treewidth problem which constructs a corresponding tree decomposition as well. Our algorithm is a faster variation of Reed’s classical algorithm. For the benefit of the reader, and to be able to compare these two algorithms, we start with a detailed time analysis for Reed’s algorithm. We fill in many details that have been omitted in Reed’s paper. Computing tree decompositions parameterized by the treewidth k is fixed parameter tractable (FPT), meaning that there are algorithms running in time O(f(k)g(n)) where f is a computable function, g(n) is polynomial in n, and n is the number of vertices. An analysis of Reed’s algorithm shows \(f(k) = 2^{O(k \log k)}\) and \(g(n) = n \log n\) for a 5-approximation. Reed simply claims time \(O(n \log n)\) for bounded k for his constant factor approximation algorithm, but the bound of \(2^{\varOmega (k \log k)} n \log n\) is well known. From a practical point of view, we notice that the time of Reed’s algorithm also contains a term of \(O(k^2 2^{24k} n \log n)\), which for small k is much worse than the asymptotically leading term of \(2^{O(k \log k)} n \log n\). We analyze f(k) more precisely, because the purpose of this paper is to improve the running times for all reasonably small values of k.

We explore how to give Genetic Programming (GP) a head start to synthesize a programming problem. Our method uses a related problem and introduces a schedule that directs GP to solve the related problem first either fully or to some extent first, or at the same time. In addition, if the related problem’s solutions are written by students or evolved by GP, we explore the extent to which initializing the GP population with some of these solutions provides a head start. We find that having a population solve one programming problem before working to solve a related programming problem helps to a greater extent as the targeted problems and the intermediate problems themselves are selected to be more challenging.

We define nominal equational problems of the form $$\exists \overline{W} \forall \overline{Y} : P$$ ∃ W ¯ ∀ Y ¯ : P , where $$P$$ P consists of conjunctions and disjunctions of equations $$s\approx _\alpha t$$ s ≈ α t , freshness constraints $$a\#t$$ a # t and their negations: $$s \not \approx _\alpha t$$ s ≉ α t and "Equation missing", where $$a$$ a is an atom and $$s, t$$ s , t nominal terms. We give a general definition of solution and a set of simplification rules to compute solutions in the nominal ground term algebra. For the latter, we define notions of solved form from which solutions can be easily extracted and show that the simplification rules are sound, preserving, and complete. With a particular strategy for rule application, the simplification process terminates and thus specifies an algorithm to solve nominal equational problems. These results generalise previous results obtained by Comon and Lescanne for first-order languages to languages with binding operators. In particular, we show that the problem of deciding the validity of a first-order equational formula in a language with binding operators (i.e., validity modulo $$\alpha $$ α -equality) is decidable.

In this paper we study a variant of the classic d -Hitting Set problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, \(\mathscr {S} \), of sets over U, where each set in the family is of size at most d, a non-negative integer k; and additionally two functions \(\alpha :\mathscr {S} \rightarrow \{1,\ldots ,A\}\) and \(\beta :\mathscr {S} \rightarrow \{1,\ldots ,B\}\). The goal is to decide if there exists a hitting set of size at most k such that for every set S in the family \(\mathscr {S} \), the solution contains at least \(\alpha (S)\) elements and at most \(\beta (S)\) elements from S. We call this the \((A, B)\)-Multi d-Hitting Set problem. We study the problem in the realm of parameterized complexity. We show that \((A, B)\)-Multi d-Hitting Set can be solved in \(\mathcal {O}^{\star }(d^{k}) \) time. For the special case when \(d=3\) and \(d=4\), we have an improved bound of \(\mathcal {O}^\star (2.2738^k)\) and \(\mathcal {O}^\star (3.562^{k})\), respectively. The former matches the running time of the classical 3-Hitting Set problem. Furthermore, we show that if we do not have an upper bound constraint and the lower bound constraint is same for all the sets in the family, say \(A>1\), then the problem can be solved even faster than d-Hitting Set.

Forgetting in Answer Set Programming (ASP) aims at reducing the language of a logic program without affecting the consequences over the remaining language. It has recently gained interest in the context of modular ASP where it allows simplifying a program of a module, making it more declarative, by omitting auxiliary atoms or hiding certain atoms/parts of the program not to be disclosed. Unlike for arbitrary programs, it has been shown that forgetting for modular ASP can always be applied, for input, output and hidden atoms, and preserve all dependencies over the remaining language (in line with uniform equivalence). However, the definition of the result is based solely on a semantic characterization in terms of HT-models. Thus, computing an actual result is a complicated process and the result commonly bears no resemblance to the original program, i.e., we are lacking a corresponding syntactic operator. In this paper, we show that there is no forgetting operator that preserves uniform equivalence (modulo the forgotten atoms) between the given program and its forgetting result by only manipulating the rules of the original program that contain the atoms to be forgotten. We then present a forgetting operator that preserves uniform equivalence and is syntactic whenever this is suitable. We also introduce a special class of programs, where syntactic forgetting is always possible, and as a complementary result, establish it as the largest known class where forgetting while preserving all dependencies is always possible. acceptedVersion

In Artificial Intelligence, Multi-Agent Systems are able to model many kinds of collective behavior and have a wide range of application. Logic is often used to model aspects of agents’ reasoning process. In this paper, we discuss social aspects of such systems. We propose a logical framework (Logic of “Inferable”) which reasons about whether a group of agents can perform an action, highlighting the concepts of action cost and budget that the group must have available in order to perform actions. The focus is on modeling the group dynamics of cooperative agents: if an agent of a group performs an action, that action to be considered as performed by the whole group, and the group can support a component agent in performing actions not affordable by that agent alone.

The digital age came with an extraordinary ability to generate data across organizations, people, and devices, data that needs to be analyzed, processed and stored. A well-known technique for analyzing this kind of data is Clustering. Many bio-inspired algorithms were proposed for this problem such as the Social Spider Optimization (SSO). In this work, we propose parallel island models of the SSO algorithm for the Clustering problem, using 24 processors for each parallel algorithm. Such models were implemented using static and dynamic topologies, and datasets from the UCI Machine Learning Repository used for the stage of experiments. The achieved average speedups range from 15 to 28 times faster than the SSO algorithm for large and small datasets, respectively, and a parallel model with static ring topology performs a little bit faster than the other parallel models. The parallel algorithms provide results with similar precision to the ones computed with the SSO algorithm.

Part 5: Autonomous Agents; International audience; Real-word intelligent agents must be able to detect sudden and unexpected changes to their task environment and effectively respond to those changes in order to function properly in the long term. We thus isolate a set of perturbations that agents ought to address and demonstrate how task-agnostic perturbation detection and mitigation mechanisms can be integrated into a cognitive robotic architecture. We present results from experimental evaluations of perturbation mitigation strategies in a multi-robot system that show how intelligent systems can achieve higher levels of autonomy by explicitly handling perturbations.

Confusion and diffusion are important design principles in block ciphers. The famous structures in block ciphers such as SPN, Feistel and Misty are proposed based on them and towards provable security against differential and linear cryptanalyses. There is few structure based on the two principles in stream ciphers except for Trivium. In this paper, we generalize the design ideas of Trivium to propose a new construction of Galois structure nonlinear feedback shift registers based on confusion and diffusion principles. As an application of this construction, a stream cipher named Bagua is proposed, which is a hardware-oriented primitive of 128-bit initialization vector and 128-bit or 256-bit key. It can be implemented in parallel up to 32 iterations at once, and the maximum throughout can be up to 8 Gbps. One can choose the parallel degree in implementation according to the requirement of throughput and hardware overhead in different application environments. Its resistances against differential and linear cryptanalyses are estimated theoretically and experimentally.

The Hamming Quasi-Cyclic (HQC) proposal is a promising candidate in the second round of the NIST Post-Quantum Cryptography Standardization project. It features small public key sizes, precise estimation of its decryption failure rates and contrary to most of the code-based systems, its security does not rely on hiding the structure of an error-correcting code. In this paper, we propose the first power side-channel attack on the Key Encapsulation Mechanism (KEM) version of HQC. Our attack utilizes a power side-channel to build an oracle that outputs whether the BCH decoder in HQC’s decryption algorithm corrects an error for a chosen ciphertext. Based on the decoding algorithm applied in HQC, it is shown how to design queries such that the output of the oracle allows to retrieve a large part of the secret key. The remaining part of the key can then be determined by an algorithm based on linear algebra. It is shown in experiments that less than 10000 measurements are sufficient to successfully mount the attack on the HQC reference implementation running on an ARM Cortex-M4 microcontroller.

The growing role of models across the life-cycle of enterprises, and their information and software systems, fuels the need for a more fundamental reflection on the foundations of modeling. Two of the core theories of the discipline of enterprise engineering (Factual Information (FI) theory and the Model Universe (MU) theory) aim at contributing to these foundations.

For timed automata, there is the notion of quasi-equal clocks. Two clocks are quasi-equal if, in each reachable configuration, they are equal or at least one has value 0. There are approaches to exploit quasi-equality of clocks to speed up reachability checking for timed automata. There is a procedure to detect quasi-equal clocks and a syntactical transformation of networks of timed automata where quasi-equal clocks are encoded by one representative clock and one boolean token per clock.

In rendez-vous protocols an arbitrarily large number of indistinguishable finite-state agents interact in pairs. The cut-off problem asks if there exists a number B such that all initial configurations of the protocol with at least B agents in a given initial state can reach a final configuration with all agents in a given final state. In a recent paper [17], Horn and Sangnier prove that the cut-off problem is equivalent to the Petri net reachability problem for protocols with a leader, and in "Image missing" for leaderless protocols. Further, for the special class of symmetric protocols they reduce these bounds to "Image missing" and "Image missing" , respectively. The problem of lowering these upper bounds or finding matching lower bounds is left open. We show that the cut-off problem is "Image missing" -complete for leaderless protocols, "Image missing" -complete for symmetric protocols with a leader, and in "Image missing" for leaderless symmetric protocols, thereby solving all the problems left open in [17].

Many complex activities in production cycles, such as quality control or fault analysis, require highly experienced specialists to perform various operations on (semi)finished products using different tools. In practical scenarios, the next operation selection is complicated since each expert has only a local view on the entire set of operations to be performed. As a result, decisions made by the specialists are suboptimal and might cause high costs. In this paper, we consider a Multi-resource Partial-ordering Flexible Job-shop Scheduling (MPF-JSS) problem where partially-ordered sequences of operations must be scheduled on multiple required resources, such as tools and specialists. The resources are flexible and can perform one or more operations depending on their properties. We model the problem using Answer Set Programming (ASP), which can efficiently handle time assignments using Difference Logic. Moreover, we suggest two multi-shot solving strategies aiming to identify the time bounds allowing for a solution to the schedule optimization problem. Experiments conducted on a set of instances extracted from a medium-sized semiconductor fault analysis lab indicate that our approach can find schedules for 87 out of 91 considered real-world instances.

We address the problem of verifying whether unwanted states, characterized as a given state formula, are reachable in a given parameterized multi-agent system (PMAS), i.e., whether the PMAS is unsafe. As the multi-agent system is parameterized, it only describes the finite set of possible agent templates, while the actual number of concrete agent instances for each template is unbounded and cannot be foreseen. However, as safety depends in general on the number of agent instances, the verification result must be correct irrespective of such a number. After having defined two distinct execution semantics of PMASs, in this paper we focus on an implemented approach for checking safety, which is composed of two steps. First, we have implemented a modeling tool, called SAFE, that allows to specify the agent templates in the PMAS and their possible interactions, and to automatically translate this model into a textual encoding of an array-based system (ABS). Second, we check safety via infinite-state model checking based on satisfiability modulo theories (SMT), by using the general purpose SMT-based model checker MCMT, which accepts ABS specifications as input. We show the correctness guarantees of this approach by relying on the theory of ABSs. Finally we discuss how this approach lends itself to richer parameterized and data-aware MAS settings beyond the state-of-the-art solutions in the literature, using SMT-based results now available thanks to this work.

A secret-sharing scheme allows to distribute a secret s among n parties such that only some predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about s. The collection of authorized/unauthorized sets can be captured by a monotone function \(f:\{0,1\}^n\rightarrow \{0,1\}\). In this paper, we focus on monotone functions that all their min-terms are sets of size a, and on their duals – monotone functions whose max-terms are of size b. We refer to these classes as (a, n)-upslices and (b, n)-downslices, and note that these natural families correspond to monotone a-regular DNFs and monotone \((n-b)\)-regular CNFs. We derive the following results.

Recently, a general framework for enumerating every non-isomorphic element in a graph class was given. Applying this framework, some graph classes have been enumerated using supercomputers, and their catalogs are provided on the web. Such graph classes include the classes of interval graphs, permutation graphs, and proper interval graphs. Last year, the enumeration algorithm for the class of Ptolemaic graphs that consists of graphs that satisfy Ptolemy inequality for the distance was investigated. They provided a polynomial time delay algorithm, but it is far from implementation. From the viewpoint of graph classes, the class is an intersection of the class of chordal graphs and the class of distance-hereditary graphs. In this paper, using the recent framework for enumerating every non-isomorphic element in a graph class, we give enumeration algorithms for the classes of distance-hereditary graphs and Ptolemaic graphs. For distance-hereditary graphs, its delay per graph is a bit slower than a previously known theoretical enumeration algorithm, however, ours is easy for implementation. In fact, although the previously known theoretical enumeration algorithm has never been implemented, we implemented our algorithm and obtained a catalog of distance-hereditary graphs of vertex numbers up to 14. We then modified the algorithm for distance-hereditary graphs to one for Ptolemaic graphs. Its delay can be the same as one for distance-hereditary graphs, which is much efficient than one proposed last year. We succeeded to enumerate Ptolemaic graphs of vertex numbers up to 15.

Search-optimization problems are plentiful in scientific and engineering domains. MaxSAT and answer set programming with weak constraints (ASP-WC) are popular frameworks for modeling and solving search problems with optimization criteria. There is a solid understanding on how SAT relates to ASP. Yet, the question on how MaxSAT relates to ASP-WC is not trivial. The answer to this question provides us with the means for cross fertilization between distinct subareas of automated reasoning. In this paper, we propose a weighted abstract modular framework that allows us to (i) capture MaxSAT and ASP-WC and (ii) state the exact link between these distinct paradigms. These findings translate, for instance, into the immediate possibility of utilizing MaxSAT solvers for finding solutions to ASP-WC programs.

Recently, Rowe and Aishwaryaprajna [FOGA 2019] introduced a simple majority vote technique that efficiently solves Jump with large gaps, OneMax with large noise, and any monotone function with a polynomial-size image. In this paper, we identify a pathological condition for this algorithm: the presence of spin-flip symmetry. Spin-flip symmetry is the invariance of a pseudo-Boolean function to complementation. Many important combinatorial optimization problems admit objective functions that exhibit this pathology, such as graph problems, Ising models, and variants of propositional satisfiability. We prove that no population size exists that allows the majority vote technique to solve spin-flip symmetric functions with reasonable probability. To remedy this, we introduce a symmetry-breaking technique that allows the majority vote algorithm to overcome this issue for many landscapes. We prove a sufficient condition for a spin-flip symmetric function to possess in order for the symmetry-breaking voting algorithm to succeed, and prove its efficiency on generalized TwoMax and families of constructed 3-NAE-SAT and 2-XOR-SAT formulas. We also prove that it fails on the one-dimensional Ising model, and suggest different techniques for overcoming this. Finally, we present empirical results that explore the tightness of the runtime bounds and the performance of the technique on randomized satisfiability variants.

In this paper, we investigate the refutability of Difference Constraint Systems (DCSs) in the Unit Read-once Refutation (UROR) system. Recall that a difference constraint is a linear relationship of the form: \(x_{i}-x_{j} \le b_{ij}\) and a DCS is a conjunction of such constraints. DCSs arise in a number of application domains such as program verification and scheduling. It follows that efficient refutation methodologies for these systems are of paramount interest. The UROR system is incomplete, in that unsatisfiable difference constraint systems may not have a refutation in this system. However, this refutation system provides a useful tool for proving if a DCS is infeasible because of a restriction on the values the variables can take. Note that without any absolute constraints, the values of the variable in a solution to a DCS can be uniformly increased or decreased without changing the validity of the solution. Thus, the UROR refutations of a DCS depend upon the restrictions placed on the values variables can take. This is in contrast to unrestricted refutations, which need not depend on these restrictions. Investigating weak (incomplete) refutation systems leads to a better understanding of the inference rules required for establishing the infeasibility of the given constraint system.

International audience; Evidential preference based on belief function theory has been proposed recently, simultaneously characterizing preference information with uncertainty and imprecision. However, traditional distances on belief functions do not adapt to some intrinsic properties of preference relations, especially when indifference relation is taken into comparison, therefore may cause inconsistent results in preference-based applications. In order to solve this issue, Unequal Singleton Pair (USP) distance has been proposed previously, with applications limited in preference aggregation. This paper explores forward the effectiveness of USP distance in preference clustering, especially confronting multiple conflicting sources. Moreover, a combination strategy for multiple conflicting sources of preference is proposed. The experiments on synthetic data show that USP distance can effectively improve the clustering results in Adjusted Rand Index (ARI).

Unit testing frameworks are nowadays considered a best practice, foregone in almost all modern software development processes, to achieve rapid development of correct specifications. The first unit testing specification language for Answer Set Programming (ASP) was proposed in 2011 as a feature of the ASPIDE development environment. Later, a more portable unit testing language was included in the LANA annotation language. In this paper we propose a revisited unit testing specification language that allows one to inline tests within ASP program and an ASP-based test execution mechanism. Moreover, we present a programming environment supporting test driven development (TDD) of ASP programs with our language.

The use of meta-rules, i.e., rules whose content includes other rules, has been advocated to model policies and the notion of power in legal reasoning, where an agent has the power to create new norms affecting other agents. The use of Defeasible Logic (DL) to model meta-rules in the application area we just alluded to has been investigated, but not from a computational viewpoint. Our aim is to fill this gap by introducing a variant of DL, Defeasible Meta-Logic, to represent defeasible meta-theories, by proposing efficient algorithms to compute the (meta-)extensions of such theories, and by proving their computational complexity.

Research on the input language of the ASP grounder gringo uses a translation that converts rules in that language into first-order formulas. That translation often transforms short rules into formulas that are syntactically complex. In this note we identify a class of rules that can be transformed into formulas in a simpler, more natural way. The new translation contributes to our understanding of the relationship between the language of gringo and first-order languages.

PRINCE is a widely analyzed block cipher proposed in 2012. Subspace trail cryptanalysis is a new cryptanalytic technique to generalize the invariant subspace attack. So far, two subspace trails that exist with probability 1 are known for 2.5 rounds of PRINCE. In this paper, we first describe a new non-random property for 4.5 rounds of PRINCE based on subspace trail with certain probability, which is independent of the secret key, the details of the Linear layer and of the S-Box layer. Then, we obtain that by appropriate choices of difference for a number of input pairs, it is possible to make sure that the number of times that the difference of the resulting output pairs lie in a particular subspace is always a multiple of 8. Later, a detailed proof is given as why it has to exist. Relying on this property, a new distinguisher can be set up to distinguish the 4.5-round PRINCE from a random permutation.

Argumentation frameworks with collective attacks (SETAFs) have gained increasing attention in recent years as they provide a natural extension of the well-known abstract argumentation frameworks (AFs) due to Dung. Concerning complexity, it is known that for the standard reasoning tasks in abstract argumentation, SETAFs show the same behavior as AFs, i.e. they are mainly located on the first or second level of the polynomial hierarchy. However, while for AFs there is a rich literature on easier fragments, complexity analyses in this direction are still missing for SETAFs. In particular, the well-known graph-classes of acyclic AFs, even-cycle-free AFs, symmetric AFs, and bipartite AFs have been shown tractable. In this paper, we aim to extend these results to the more general notion of SETAFs. In particular, we provide various syntactic notions on SETAFs that naturally generalize the graph properties for directed hypergraphs, and perform a complexity analysis of the prominent credulous and skeptical acceptance problems for several different widely used semantics.

We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative$$\omega $$ω-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability 1 when starting at a given energy levelk, is decidable and in$$\mathsf {NP}\cap \mathsf {coNP}$$NP∩coNP. The same holds for checking if such akexists and if a givenkis minimal.

Grammatical Evolution (GE) is one of the most popular Genetic Programming (GP) variants, and it has been used with success in several problem domains. Since the original proposal, many enhancements have been proposed to GE in order to address some of its main issues and improve its performance.

Standard grammatical evolution (GE) uses a one-point crossover (“ripple crossover”) that exchanges codons between two genotypes. The two resulting genotypes are then mapped to their respective phenotypes using a Backus-Naur form grammar. This article studies how different types of grammars affect the resulting individuals of a ripple crossover. We distinguish different grammars based on the expected number of non-terminals chosen when mapping genotype codons to phenotypes, \(B_{avg}\). The grammars only differ in \(B_{avg}\) but can express the same phenotypes. We perform crossover operations on the genotypes and find that grammars with \(B_{avg} > 1\) lead to high numbers of either very small trees or invalid individuals. Due to the re-sampling of the invalid individuals, the algorithmic runtime is higher compared to grammars with a small \(B_{avg}\), despite being able to express the same phenotypes. In grammars with \(B_{avg} \le 1\), the bias towards small trees is reduced and instead, the frequency of valid large trees is increased. Our results give insights on favorable grammar designs and underline the central role of grammar design in GE.

A rectangular dual of a graph g is a contact representation of g by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The partial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. Combinatorially, a rectangular dual can be described by a regular edge labeling (rel), which determines the orientations of the rectangle contacts. We characterize the rels that admit an extension, which leads to a linear-time testing algorithm. In the affirmative, we can construct an extension in linear time.keywordsrectangular dualpartial representation extension.

A 1-bend boundary labelling problem consists of an axis-aligned rectangle B, n points (called sites) in the interior, and n points (called ports) on the labels along the boundary of B. The goal is to find a set of n axis-aligned curves (called leaders), each having at most one bend and connecting one site to one port, such that the leaders are pairwise disjoint. A 1-bend boundary labelling problem is k-sided (\(1\le k\le 4\)) if the ports appear on k different sides of B. Kindermann et al. [Algorithmica, 76(1): 225–258, 2016] showed that the 1-bend 4-sided and 3-sided boundary labelling problems can be solved in \(O(n^9)\) and \(O(n^4)\) time, respectively. Bose et al. [SWAT, 12:1–12:14, 2018] improved the former running time to \(O(n^6)\) by reducing the problem to computing maximum independent set in an outerstring graph. In this paper, we improve both previous results by giving new algorithms with running times \(O(n^5)\) and \(O(n^3\log n)\) to solve the 1-bend 4-sided and 3-sided boundary labelling problems, respectively.

This paper presents a framework for reasoning about trustworthiness in cyber-physical systems (CPS) that combines ontology-based reasoning and answer set programming (ASP). It introduces a formal definition of CPS and several problems related to trustworthiness of a CPS such as the problem of identification of the most vulnerable components of the system and of computing a strategy for mitigating an issue. It then shows how a combination of ontology based reasoning and ASP can be used to address the aforementioned problems. The paper concludes with a discussion of the potentials of the proposed methodologies.

The process of developing civil aircraft and their related systems includes multiple phases of Preliminary Safety Assessment (PSA). An objective of PSA is to link the classification of failure conditions and effects (produced in the functional hazard analysis phases) to appropriate safety requirements for elements in the aircraft architecture. A complete and correct preliminary safety assessment phase avoids potentially costly revisions to the design late in the design process. Hence, automated ways to support PSA are an important challenge in modern aircraft design. A modern approach to conducting PSAs is via the use of abstract propagation models, that are basically hyper-graphs where arcs model the dependency among components, e.g. how the degradation of one component may lead to the degraded or failed operation of another. Such models are used for computingfailure propagations: the fault of a component may have multiple ramifications within the system, causing the malfunction of several interconnected components. A central aspect of this problem is that of identifying the minimal fault combinations, also referred to asminimal cut sets, that cause overall failures.In this paper we propose an expressive framework to model failure propagation, catering for multiple levels of degradation as well as cyclic and nondeterministic dependencies. We define a formal sequential semantics, and present an efficient SMT-based method for the analysis of failure propagation, able to enumerate cut sets that are minimal with respect to the order between levels of degradation. In contrast with the state of the art, the proposed approach is provably more expressive, and dramatically outperforms other systems when a comparison is possible.

An independent set S in a graph G is k-swap optimal if there is no independent set \(S'\) such that \(|S'|>|S|\) and \(|(S'\setminus S)\cup (S\setminus S')|\le k\). Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex v is contained in some k-swap optimal independent set or in all k-swap optimal independent sets. We show that these problems are NP-hard for constant values of k even on graphs with constant maximum degree. Moreover, we show that the problems are \(\mathrm {\Sigma ^{\text {P}}_{2}} \)-hard when k is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path problem. We show that for a given edge we can decide in \(f(\varDelta +k)\cdot n^{\mathcal {O}(1)}\) time whether it is in some k-optimal path.

Benefits of static type systems are well-known: they offer guarantees that no type error will occur during runtime and, inherently, inferred types serve as documentation on how functions are called. On the other hand, many type systems have to limit expressiveness of the language because, in general, it is undecidable whether a given program is correct regarding types. Another concern that was not addressed so far is that, for logic programming languages such as Prolog, it is impossible to distinguish between intended and unintended failure and, worse, intended and unintended success without additional annotations.

Kernel machines are a powerful class of methods for classification and regression. Making kernel machines fast and scalable to large data, however, is still a challenging problem due to the need of storing and operating on the Gram matrix. In this paper we propose a novel approach to sample condensation for kernel machines, preferably without impairing the classification performance. To our best knowledge, there is no previous work with the same goal reported in the literature. For this purpose we make use of the neural network interpretation of kernel machines. Explainable AI techniques, in particular the Layer-wise Relevance Propagation method, are used to measure the relevance (importance) of training samples. Given this relevance measure, a decremental strategy is proposed for sample condensation. Experimental results on three data sets show that our approach is able to achieve the goal of substantial reduction of the number of training samples.

Over the last years,algorithmic game theoryhas received growing interest in AI, as it allows to tackle complex real-world scenarios involving multiple artificial agents engaged in a competitive interaction. These settings call for rational agents endowed with the capability of reasoning strategically, which is achieved by exploitingequilibriumconcepts from game theory.

Agent-based modelling languages naturally implement concurrency for handling complex interactions between communicating agents. On the other hand, the field of Argumentation Theory lacks of instruments to explicitly model concurrent behaviours. In this paper we introduce a tool for dealing with concurrent argumentation processes and that can be used, for instance, to model agents debating, negotiating and persuading. The tool implements operations as expansion, contraction and revision. We also provide a web interface exposing the functionalities of the tool and allowing for a more careful study of concurrent processes.

Graph routing problem (GRP) and its generalizations have been extensively studied because of their broad applications in the real world. In this paper, we study a variant of GRP called the general cluster routing problem (GCRP). Let \(G=\left( V,\,E\right) \) be a complete undirected graph with edge weight \(c\left( e\right) \) satisfying the triangle inequality. The vertex set is partitioned into a family of clusters \(C_{1},...,C_{m}\). We are given a required vertex subset \(\overline{V} \subseteq V\) and a required edge subset \(\overline{E} \subseteq E\). The aim is to compute a minimum cost tour that visits each vertex in \(\overline{V}\) exactly once and traverses each edge in \(\overline{E}\) at least once, while the vertices and edges of each cluster are visited consecutively. When the starting and ending vertices of each cluster are specified, we devise an approximation algorithm via incorporating Christofides’ algorithm with minimum weight bipartite matching, achieving an approximation ratio that equals the best approximation ratio of path TSP. Then for the case there are no specified starting and ending vertices for each cluster, we propose a more complicated algorithm with a compromised ratio of 2.67 by employing directed spanning tree against the designated auxiliary graph. Both approximation ratios improve the state-of-art approximation ratio that are respectively 2.4 and 3.25.

This work proposes a method to estimate the Pareto front even in areas without objective vectors in the objective space. For the Pareto front approximation, we use a set of non-dominated points, objective vectors, in the objective space. To finely approximate the Pareto front, we need to increase the number of objective vectors. It is worth to estimate the Pareto front with a limited number of objective vectors. The proposed method uses the Kriging approximation and estimates the Pareto front using the unit hyperplane in the objective space. In the experiment using representative simple and complicated Pareto fronts derived from the DTLZ family, we visually show the estimation quality of the proposed method. Also, we show that the shape of the Pareto front and the distribution of sample objective vectors affect the estimation quality.

Answer set programming (ASP) is a declarative programming paradigm that is geared towards difficult combinatorial search problems. Sometimes, run times of ASP systems suffer due to so called grounding bottleneck. Lazy grounding solvers aim to mitigate this issue. In this paper we describe a new lazy grounding solver called DualGrounder. The DualGrounder system leverages multi-shot capabilities of the advanced ASP platform clingo. This paper also includes experimental data to explore the performance of DualGrounder compared to similar ASP grounding and solving systems.

Given a graph, an L(p, 1)-labeling of the graph is an assignment f from the vertex set to the set of nonnegative integers such that for any pair of vertices \((u,v),|f (u) - f (v)| \ge p\) if u and v are adjacent, and \(f(u) \ne f(v)\) if u and v are at distance 2. The L(p, 1)-labeling problem is to minimize the span of f (i.e.,\(\max _{u\in V}(f(u)) - \min _{u\in V}(f(u))+1\)). It is known to be NP-hard even for graphs of maximum degree 3 or graphs with tree-width 2, whereas it is fixed-parameter tractable with respect to vertex cover number. Since the vertex cover number is a kind of the strongest parameter, there is a large gap between tractability and intractability from the viewpoint of parameterization. To fill up the gap, in this paper, we propose new fixed-parameter algorithms for L(p, 1)-Labeling by the twin cover number plus the maximum clique size and by the tree-width plus the maximum degree. These algorithms reduce the gap in terms of several combinations of parameters.

For intractable problems on graphs of bounded treewidth, two graph parameters treedepth and vertex cover number have been used to obtain fine-grained complexity results. Although the studies in this direction are successful, we still need a systematic way for further investigations because the graphs of bounded vertex cover number form a rather small subclass of the graphs of bounded treedepth. To fill this gap, we use vertex integrity, which is placed between the two parameters mentioned above. For several graph problems, we generalize fixed-parameter tractability results parameterized by vertex cover number to the ones parameterized by vertex integrity. We also show some finer complexity contrasts by showing hardness with respect to vertex integrity or treedepth.

Let \(\varSigma \) and \(\varPi \) be disjoint alphabets, respectively called the static alphabet and the parameterized alphabet. Two strings x and y over \(\varSigma \cup \varPi \) of equal length are said to parameterized match (p-match) if there exists a renaming bijection f on \(\varSigma \) and \(\varPi \) which is identity on \(\varSigma \) and maps the characters of x to those of y so that the two strings become identical. The indexing version of the problem of finding p-matching occurrences of a given pattern in the text is a well-studied topic in string matching. In this paper, we present a state-of-the-art indexing structure for p-matching called the parameterized suffix tray of an input text T, denoted by \(\mathsf {PSTray}(T)\). We show that \(\mathsf {PSTray}(T)\) occupies O(n) space and supports pattern matching queries in \(O(m + \log (\sigma +\pi ) + occ )\) time, where n is the length of t, m is the length of a query pattern P, \(\pi \) is the number of distinct symbols of \(|\varPi |\) in T, \(\sigma \) is the number of distinct symbols of \(|\varSigma |\) in T and \( occ \) is the number of p-matching occurrences of P in T. We also present how to build \(\mathsf {PSTray}(T)\) in O(n) time from the parameterized suffix tree of T.

In the past several years, it has become apparent that the effectiveness of Pareto dominance-based multiobjective evolutionary algorithms degrades dramatically when solving many-objective optimization problems (MaOPs). Instead, research efforts have been driven toward developing evolutionary algorithms (EAs) that do not rely on Pareto dominance (e.g., decomposition-based techniques) to solve MaOPs. However, it is still a non-trivial issue for many existing non-Pareto-dominance-based EAs to deal with unknown irregular Pareto front shapes. In this paper, we develop the novel “(M-1)+1" framework of relaxed Pareto dominance to address MaOPs, which can simultaneously promote both convergence and diversity. To be specific, we apply M symmetrical cases of relaxed Pareto dominance during the environmental selection step, where each enhances the selection pressure of M-1 objectives by expanding the dominance area of solutions, while remaining unchanged for the one objective left out of that process. Experiments demonstrate that the proposed method is very competitive with or outperforms state-of-the-art methods on a variety of scalable test problems.

An oriented r-coloring of an oriented graph G corresponds to an oriented graph H on r vertices, such that there exists a homomorphism from G to H. The problem of deciding whether an acyclic digraph allows an oriented 4-coloring is already NP-hard. The oriented chromatic number of an oriented graph G is the smallest integer r such that G allows an oriented r-coloring.

25th International Workshop, WADT 2020, Virtual Event, April 29, 2020, Revised Selected Papers; International audience; Cellular automata as well as simultaneous assignments in Python can be understood as the parallel application of local rules to a grid or an environment that can be easily represented as an attributed graph. Since the result of such transformations cannot generally be obtained by a sequential application of the involved rules, this situation infringes the standard notion of parallel independence. An algebraic approach with production rules of the form L←K←I→R is adopted and a condition of parallel coherence more general than parallel independence is formulated, that enable the definition of the Parallel Coherent Transformation (PCT). This transformation supports a generalisation of the Parallelism Theorem in the theory of adhesive HLR categories, showing that the PCT yields the expected result of sequential rewriting steps when parallel independence holds. Categories of finitely attributed structures are proposed, in which PCTs are guaranteed to exist. These notions are introduced and illustrated on several detailed examples.

After decades of effort, evolutionary algorithms have been able to solve a variety of multiobjective optimisation problems with diverse characteristics. However, the presence of irregularity in the Pareto-optimal front is increasingly recognised as a big challenge to some well-established algorithms. In order to further our understanding of this irregularity and its effect on algorithms, we develop a generic framework of constructing irregular Pareto-optimal front shapes, and use it as a tool to examine the performance of some well-known algorithms. Experimental results reveal that conventional algorithms are not always inferior to the state of the arts, and all the algorithms considered in this paper face some unexpected challenges when dealing with irregularity of Pareto-optimal front. The findings suggest that a systematic evaluation and analysis is needed for any newly-developed algorithms to avoid biases.