Search

The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the LCPs for lexicographically adjacent suffixes of a string. Together the two arrays are roughly equivalent to the suffix tree with the LCP array representing the tree shape. In order to better understand the combinatorics of LCP arrays, we consider the problem of inferring a string from an LCP array, i.e., determining whether a given array of integers is a valid LCP array, and if it is, reconstructing some string or all strings with that LCP array. There are recent studies of inferring a string from a suffix tree shape but using significantly more information (in the form of suffix links) than is available in the LCP array. We provide two main results. (1) We describe two algorithms for inferring strings from an LCP array when we allow a generalized form of LCP array defined for a multiset of cyclic strings: a linear time algorithm for binary alphabet and a general algorithm with polynomial time complexity for a constant alphabet size. (2) We prove that determining whether a given integer array is a valid LCP array is NP-complete when we require more restricted forms of LCP array defined for a single cyclic or non-cyclic string or a multiset of non-cyclic strings. The result holds whether or not the alphabet is restricted to be binary. In combination, the two results show that the generalized form of LCP array for a multiset of cyclic strings is fundamentally different from the other more restricted forms.

Metaheuristics are found to be efficient in different applications where the use of exact algorithms becomes short-handed. In the last decade, many of these algorithms have been introduced and used in a wide range of applications. Nevertheless, most of those approaches share similar components leading to a concern related to their novelty or contribution. Thus, in this paper, a pool template is proposed and used to categorize algorithm components permitting to analyze them in a structured way. We exemplify its use by means of continuous optimization metaheuristics, and provide some measures and methodology to identify their similarities and novelties. Finally, a discussion at a component level is provided in order to point out possible design differences and commonalities.

Consider a region that requires to be protected from unauthorized penetrations. The border of the region, modeled as a unit line segment, consists of high priority segments that require the highest level of protection separated by low priority segments that require to be visited infinitely often. We study the problem of patrolling the border with a set of k robots. The goal is to obtain a strategy that minimizes the maximum idle time (the time that a point is left unattended) of the high priority points while visiting the low priority points infinitely often. We use the concept of single lid cover (segments of fixed length) where each high priority point is covered with at least one lid, and then we extend it to strong double-lid cover where each high priority point is covered with at least two lids, and the unit line segment is fully covered. Let λk-1 be the minimum lid length that accepts a single λk-1-lid cover with k - 1 lids and Λ2k be the minimum lid length that accepts a strong double Λ2k-lid cover with 2k lids. We show that 2min(Λ2k, λk-1) is the lower bound of the idle time when the max speed of the robots is one. To compute Λ2k and λk-1, we present an algorithm with time complexity O(max(k, n) logn) where n is the number of high priority sections. Our algorithm improves by a factor of min(n, k) the previous O(knlogn) running time algorithm. For the upper bound, first we present a strategy with idle time λk-1 where one robot covers the unit line, and the remaining robots cover the lids of a single λk-1-lid cover with k - 1 lids. Then, we present a simple strategy with idle time 3Λ2k that splits the unit line into not-disjoint k segments of equal length that robots synchronously cover, i.e., reaching the leftmost and rightmost point simultaneously. Then, we present a complex strategy that split the unit line into k non-disjoint segments that robots asynchronously cover. We show that combining strategies one and two attain an approximation of 1.5 the optimal idle time and combining strategy one and third attain optimal idle time.

Recent theoretical research has shown that self-adjusting and self-adaptive mechanisms can provably outperform static settings in evolutionary algorithms for binary search spaces. However, the vast majority of these studies focuses on unimodal functions which do not require the algorithm to flip several bits simultaneously to make progress. In fact, existing self-adjusting algorithms are not designed to detect local optima and do not have any obvious benefit to cross large Hamming gaps. We suggest a mechanism called stagnation detection that can be added as a module to existing evolutionary algorithms (both with and without prior self-adjusting algorithms). Added to a simple (1+1) EA, we prove an expected runtime on the well-known Jump benchmark that corresponds to an asymptotically optimal parameter setting and outperforms other mechanisms for multimodal optimization like heavy-tailed mutation. We also investigate the module in the context of a self-adjusting (1+$\lambda$) EA and show that it combines the previous benefits of this algorithm on unimodal problems with more efficient multimodal optimization. To explore the limitations of the approach, we additionally present an example where both self-adjusting mechanisms, including stagnation detection, do not help to find a beneficial setting of the mutation rate. Finally, we investigate our module for stagnation detection experimentally., Comment: 26 pages. Full version of a paper appearing at GECCO 2020

Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: operators of a network and users of the network. Operators of the network post a price so as to attract users and maximize profit; users of the network select routes based on these prices and congestion from other users. Motivated by the fact that equilibrium in these games may not exist, may not be unique, and may induce an inefficient network performance, our main result is to observe that a simple regulation on the network owners’ market solves these three issues. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then the game among the link operators has a unique and strong Nash equilibrium and the users’ game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls and investigate the efficiency of great tolls with respect to the users’ surplus. We derive a bicriteria bound that compares the users’ surplus under great tolls with the users’ surplus under optimal tolls. Finally, we consider two different extensions of the model. First, we assume that operators face operating costs that depend on the amount of flow on the link, for which we prove existence of great tolls. Second, we allow operators to own more than one link. In this case, we prove that, when operators own complementary links (i.e., links for which an increase in toll value may only increase the flow on the other owned links), any toll vector that induces the optimal flow and that is upper bounded by the marginal tolls is a great set of tolls, and furthermore, we show that, when all links in the network are complementary, then the aforementioned toll vector is also a strong cap equilibrium.

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(n\alpha(n)\log^7 n)$ time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $O(n^2)$ time algorithms., Comment: 14 pages, 7 figures

We propose a novel constraint-handling technique for the covariance matrix adaptation evolution strategy (CMA-ES). The proposed technique is aimed at solving explicitly constrained black-box continuous optimization problems, in which the explicit constraint is a constraint whereby the computational time for the constraint violation and its (numerical) gradient are negligible compared to that for the objective function. This method is designed to realize two invariance properties: invariance to the affine transformation of the search space, and invariance to the increasing transformation of the objective and constraint functions. The CMA-ES is designed to possess these properties for handling difficulties that appear in black-box optimization problems, such as non-separability, ill-conditioning, ruggedness, and the different orders of magnitude in the objective. The proposed constraint-handling technique (CHT), known as ARCH, modifies the underlying CMA-ES only in terms of the ranking of the candidate solutions. It employs a repair operator and an adaptive ranking aggregation strategy to compute the ranking. We developed test problems to evaluate the effects of the invariance properties, and performed experiments to empirically verify the invariance of the algorithm. We compared the proposed method with other CHTs on the CEC 2006 constrained optimization benchmark suite to demonstrate its efficacy. Empirical studies reveal that ARCH is able to exploit the explicitness of the constraint functions effectively, sometimes even more efficiently than an existing box-constraint handling technique on box-constrained problems, while exhibiting the invariance properties. Moreover, ARCH overwhelmingly outperforms CHTs by not exploiting the explicit constraints in terms of the number of objective function calls., Accepted to Evolutionary Computation (MIT Press)

An $H$-free editing problem asks whether we can edit at most $k$ edges to make a graph contain no induced copy of the fixed graph $H$. We obtain a polynomial kernel for this problem when $H$ is a diamond. The incompressibility dichotomy for $H$ being a 3-connected graph and the classical complexity dichotomy suggest that except for $H$ being a complete/empty graph, $H$-free editing problems admit polynomial kernels only for a few small graphs $H$. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of $H$-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.

Constraint answer set programming or CASP, for short, is a hybrid approach in automated reasoning putting together the advances of distinct research areas such as answer set programming, constraint processing, and satisfiability modulo theories. Constraint answer set programming demonstrates promising results, including the development of a multitude of solvers: acsolver, clingcon, ezcsp, idp, inca, dingo, mingo, aspmt, clingo[l,dl], and ezsmt. It opens new horizons for declarative programming applications such as solving complex train scheduling problems. Systems designed to find solutions to constraint answer set programs can be grouped according to their construction into, what we call, integrational or translational approaches. The focus of this paper is an overview of the key ingredients of the design of constraint answer set solvers drawing distinctions and parallels between integrational and translational approaches. The paper also provides a glimpse at the kind of programs its users develop by utilizing a CASP encoding of Travelling Salesman problem for illustration. In addition, we place the CASP technology on the map among its automated reasoning peers as well as discuss future possibilities for the development of CASP., Under consideration in Theory and Practice of Logic Programming (TPLP)

Spiking neural P systems with rules on synapses (RSSNP systems) are a class of computation models which are inspired by the information processing and communication manner of neurons. In this work, we consider labeled RSSNP systems (lRSSNP systems), where each rule is assigned either with a label chosen from an alphabet Σ or with the empty label λ. A string over an alphabet is accepted by an lRSSNP system if the string is processed from left to right by the system in the sense that in a step only rules labeled with the processed symbol or with λ are used (not both), and the system reaches a final configuration in the moment when the whole string is processed. The set of all accepted strings is categorized as the restricted (computations are done with the application of the rules labeled with symbols from the given alphabet) control language and the unrestricted (rules labeled with λ are allowed in the computations) control language of the system. We study the language accepting power of lRSSNP systems using only standard spiking rules by comparing the family of control languages of lRSSNP systems with the families of languages in the Chomsky hierarchy. It is proved that restricted lRSSNP systems can accept no more than context-sensitive languages, and unrestricted lRSSNP systems can accept recursively enumerable languages.

The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop ( 1 , 2 )-Minimum Spanning Tree problem (abbr. 2H-( 1 , 2 )-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-( 1 , 2 )-MSTP (including the ( 1 + 1 ) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i.e., the expected number of fitness evaluations) to obtain a 3 2 -approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the ( 1 + 1 ) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a 3 2 -approximate solution, which is better than the above mentioned ones.

Meta-learning aims to leverage experience from previous tasks to achieve an effective and fast adaptation ability when encountering new tasks. However, it is unclear how the generalization property applies to new tasks. Probably approximately correct (PAC) Bayes bound theory provides a theoretical framework to analyze the generalization performance for meta-learning with an explicit numerical generalization error upper bound. A tighter upper bound may achieve better generalization performance. However, for the PAC-Bayes meta-learning bound, the prior distribution is selected randomly which results in poor generalization performance. In this paper, we derive three novel generalization error upper bounds for meta-learning based on the PAC-Bayes relative entropy bound. Furthermore, in order to avoid randomly prior distribution, based on the empirical risk minimization (ERM) method, a data-dependent prior for the PAC-Bayes meta-learning bound algorithm is developed and the sample complexity and computational complexity are analyzed. The experiments illustrate that the proposed three PAC-Bayes bounds for meta-learning achieve a competitive generalization guarantee, and the extended PAC-Bayes bound with a data-dependent prior can achieve rapid convergence ability.

Toward combating the malicious rumor spreading on online social networks, we discuss a hybrid control strategy that combines a continuous truth spreading method and an impulsive rumor blocking method in this article. In this strategy, the truth is introduced as an anti-rumor to compete with the rumor while the rumor-infected users would be quarantined with a limited isolation period. The stability of the rumor-free equilibrium of the rumor-truth propagation system is analyzed and conditions to reach uniform asymptotic stability as well as global exponential stability are obtained. For the endemic case, the conditions under which rumor would persist uniformly are obtained. An optimal hybrid control problem is formulated to address the tradeoff between restraining rumor and minimizing the cost of control. The necessary conditions for optimal system and the structure of optimal hybrid control are obtained. Numerical simulations are carried out to illustrate the theoretical results and evaluate the potential roles of the hybrid control strategy.

Because edge modification problems are computationally difficult for most target graph classes, considerable attention has been devoted to inclusion-minimal edge modifications, which are usually polynomial-time computable and which can serve as an approximation of minimum cardinality edge modifications, albeit with no guarantee on the cardinality of the resulting modification set. Over the past fifteen years, the primary design approach used for inclusion-minimal edge modification algorithms is based on a specific incremental scheme. Unfortunately, nothing guarantees that the set E of edge modifications of a graph G that can be obtained in this specific way spans all the inclusion-minimal edge modifications of G. Here, we focus on edge modification problems into the class of chordal graphs and we show that for this the set E may not even contain any solution of minimum size and may not even contain a solution close to the minimum; in fact, we show that it may not contain a solution better than within an Ω ( n ) factor of the minimum. These results show strong limitations on the the use of the current favored algorithmic approach to inclusion-minimal edge modification in heuristics for computing a minimum cardinality edge modification. They suggest that further developments might be better using other approaches.

We present a randomized $O(m \log^2 n)$ work, $O(\text{polylog } n)$ depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP'20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA'18], which performs $O(m \log^4 n)$ work in $O(\text{polylog } n)$ depth. Our algorithm makes use of three components that might be of independent interest. Firstly, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves the work bounds of a previous data structure of Geissmann and Gianinazzi and is work efficient with respect to the best sequential algorithm. Secondly, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger's sequential algorithm for minimum cuts. Lastly, we design an efficient parallel algorithm for solving the minimum $2$-respecting cut problem., This is the full version of the paper appearing in the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021

We look at nondeterministic finite automata augmented with multiple reversal-bounded counters where, during an accepting computation, the behavior of the counters is specified by some fixed pattern. These patterns can serve as a useful "bridge" to other important automata and grammar models in the theoretical computer science literature, thereby helping in their study. Various pattern behaviors are considered, together with characterizations and comparisons. For example, one such pattern defines exactly the smallest full trio containing all the bounded semilinear languages. Another pattern defines the smallest full trio containing all the bounded context-free languages. The "bridging" to other families is then applied, e.g. to certain Turing machine restrictions, as well as other families. Certain general decidability properties are also studied using this framework., 28 pages, 1 figure

Meta-heuristics are powerful tools for solving optimization problems whose structural properties are unknown or cannot be exploited algorithmically. We propose such a meta-heuristic for a large class of optimization problems over discrete domains based on the particle swarm optimization (PSO) paradigm. We provide a comprehensive formal analysis of the performance of this algorithm on certain “easy” reference problems in a black-box setting, namely the sorting problem and the problem OneMax. In our analysis we use a Markov model of the proposed algorithm to obtain upper and lower bounds on its expected optimization time. Our bounds are essentially tight with respect to the Markov model. We show that for a suitable choice of algorithm parameters the expected optimization time is comparable to that of known algorithms and, furthermore, for other parameter regimes, the algorithm behaves less greedy and more explorative, which can be desirable in practice in order to escape local optima. Our analysis provides a precise insight on the tradeoff between optimization time and exploration. To obtain our results we introduce the notion of indistinguishability of states of a Markov chain and provide bounds on the solution of a recurrence equation with non-constant coefficients by integration.

This archive contains the raw evaluation results and scripts associated with the experiments described in the article "Making Higher-Order Superposition Work" by Vukmirović, Bentkamp, Blanchette, Cruanes, Nummelin and Tourret available at: https://matryoshka-project.github.io/pubs/mhosw_article.pdf The problems we used for the evaluation are in problems/ subdirectory, divided in categories sh and tptp as in the article. In the results/ directory there are two subdirectories, sh and tptp, one for each benchmark category. Both subdirectories contain files named fD.csv where D is a number from 1 to 10. The files contain experiment results for the figure labelled with the number D, and the benchmark category corresponding to the parent directory. In the result files, the columns give the results of the experiment run for a given prover configuration (e.g., CPU time, reported status, memory usage, etc.). Each row corresponds to one problem file, whose name is given in the "prob_name" column. The "i_solver" column corresponds to a prover, whereas the "i_configuration" column corresponds to a configuration, where i is a natural number identifying a combination of prover and configuration. Files ending with "summary.csv" contain concise summaries of evaluation runs for a corresponding results file. Columns of these files are of the form "{solver}_{configuration}", and rows contain different statistics described in the "summary" column. The names of the solvers and configurations used in result files are self-explanatory (for DCS, DCI and IC configurations presence of av in the name of the configuration denotes that Avatar is enabled). In some cases, for uniformity, configurations are used in multiple figures. We used the following versions of higher-order provers: CVC4 1.9 ([git cascJ10 db26022c]), Leo-III 1.5.6, Satallax 3.5, Vampire 4.5.1 (commit 68d3e7314), E 2.7 (603992156b943171002cacca72aa3f2d0a211ee3). The "zipperposition/" directory contains the scripts that can be used to run the provided Zipperposition binary (compiled for Linux) on a given problem using a given configuration. To run Zipperposition on a single problem using some configuration, use the scripts with the name "run_*", where * stands for the configuration used in the evaluation. The configuration names match those used in the result files. Except for "run_coop" and "run_uncoop", scripts accept three arguments: 1) path to the problem 2) CPU timeout 3) path to the temporary directory for files used to communicate with Ehoh. "run_coop" and "run_uncoop" expect only the first two arguments For example, to run problem with the path ~/problem.p using configuration which enables PEHO priority function for up to 15 seconds execute ./run_prio_peho ~/problem.p 15 /tmp Working installation of Python 3 and bash is required. Source code for Zipperposition can be obtained from the wip-merge-hlbe branch of Zipperposition git repository: git@github.com:sneeuwballen/zipperposition.git. The binary stored under scripts/ directory corresponds to compiled sources tagged with commit hash 8d205ecf8869c76dcfdf0c1faa98b002226780a1. Compilation instructions are as in README.md file contained in the git repository. As noted in footnote 2, three tables have been evaluated using a faulty version of Ehoh prover. Reevaluation is being performed, and it is expected that the evaluation results will stay mostly the same, up to the noise in the evaluation environment. "eprover-ho" binary provided in this archive is the corrected version of the one used to evaluate tables 7, 8 and 9.

Broadcast is one of the fundamental network communication primitives. One node of a network, called the $\mathit{source}$, has a message that has to be learned by all other nodes. We consider the feasibility of deterministic broadcast in radio networks. If nodes of the network do not have any labels, deterministic broadcast is impossible even in the four-cycle. On the other hand, if all nodes have distinct labels, then broadcast can be carried out, e.g., in a round-robin fashion, and hence $O(\log n)$-bit labels are sufficient for this task in $n$-node networks. In fact, $O(\log \Delta)$-bit labels, where $\Delta$ is the maximum degree, are enough to broadcast successfully. Hence, it is natural to ask if very short labels are sufficient for broadcast. Our main result is a positive answer to this question. We show that every radio network can be labeled using 2 bits in such a way that broadcast can be accomplished by some universal deterministic algorithm that does not know the network topology nor any bound on its size. Moreover, at the expense of an extra bit in the labels, we get the additional strong property that there exists a common round in which all nodes know that broadcast has been completed. Finally, we show that 3-bit labels are also sufficient to solve both versions of broadcast in the case where the labeling scheme does not know which node is the source., Comment: updated version of the paper that appeared in SPAA 2019: now contains a solution for the case where the source node is not designated when the labeling scheme is applied

An information system (IS) is an important mathematical tool for artificial intelligence. A fuzzy probabilistic information system (FPIS), the combination of some fuzzy relations in the same universe which satisfies the probability distribution, can be seen as an IS with fuzzy relations. A FPIS overcomes the shortcoming that rough set theory assumes elements in the universe with equal probability and leads to lose some useful information. This paper integrates the probability distribution into the fuzzy relations in a FPIS and studies its reduction. Firstly, the concept of a FPIS is introduced and its reduction is proposed. Then, the fuzzy relations in a FPIS are divided into three categories (P-necessary, P-relatively necessary and P-unnecessary fuzzy relations) according to their importance. Next, entropy measurement for a FPIS is investigated. Moreover, some reduction algorithms are constructed. Finally, an example is given to verify the effectiveness of these proposed algorithms.

The transformation of graphs and graph-like structures is ubiquitous in computer science. When a system is described by graph-transformation rules, it is often desirable that the rules are both terminating and confluent so that rule applications in an arbitrary order produce unique resulting graphs. However, there are application scenarios where the rules are not globally confluent but confluent on a subclass of graphs that are of interest. In other words, non-resolvable conflicts can only occur on graphs that are considered as "garbage". In this paper, we introduce the notion of confluence up to garbage and generalise Plump's critical pair lemma for double-pushout graph transformation, providing a sufficient condition for confluence up to garbage by non-garbage critical pair analysis. We apply our results in two case studies about efficient language recognition: we present backtracking-free graph reduction systems which recognise a class of flow diagrams and a class of labelled series-parallel graphs, respectively. Both systems are non-confluent but confluent up to garbage. We also give a critical pair condition for subcommutativity up to garbage which, together with closedness, implies confluence up to garbage even in non-terminating systems., 33 pages, 2021

International audience; Causal broadcast is a communication abstraction built on top of point-to-point send/receive networks, which ensures that any two messages whose broadcasts are causally related (as captured by Lamport's "happened before" relation) are delivered in their sending order. Several causal broadcast algorithms have been designed for failure-free and crash-prone asynchronous message-passing systems. This article first gives a formal definition of a causal broadcast abstraction in the presence of Byzantine processes, in the form of two equivalent characterizations, and then presents a simple causal broadcast algorithm that implements it. The main difficulty in the design and the proof of this algorithm comes from the very nature of Byzantine faults: Byzantine processes may have arbitrary behavior, and the algorithm must ensure that correct processes (i) maintain a coherent view of causality and (ii) are never prevented from communicating between themselves. To this end, the algorithm is built modularly, namely it works on top of any Byzantine-tolerant reliable broadcast algorithm. Due to this modularity, the proposed algorithm is easy to understand and inherits the computability assumptions (notably the maximal number of processes that may be Byzantine) and the message/time complexities of the underlying reliable broadcast on top of which it is built.

Indexing of static and dynamic sets is fundamental to a large set of applications such as information retrieval and caching. Denoting the characteristic vector of the set by B, we consider the problem of encoding sets and multisets to support approximate versions of the operations rank(i) (i.e., computing sum_{j = i}) queries. We study multiple types of approximations (allowing an error in the query or the result) and present lower bounds and succinct data structures for several variants of the problem. We also extend our model to sliding windows, in which we process a stream of elements and compute suffix sums. This is a generalization of the window summation problem that allows the user to specify the window size at query time. Here, we provide an algorithm that supports updates and queries in constant time while requiring just (1+o(1)) factor more space than the fixed-window summation algorithms., To appear in ISAAC 2018

Two nature-inspired computing techniques, i.e. the Firefly and the controlled Genetic Algorithm in a restricted divergence environment has been combined to propose an improved Clinical Decision Support System (CDSS) query optimizer. The proposed model is intended to get better query execution plan which will detract the input-output, processing and communication lust for the execution of the CDSS queries. The amalgamated use of the proposed CDSS query optimizer framework will yield substantial variation in two consecutive generations which will efficaciously resolve the slow convergence problem of the controlled Genetic Algorithm. Furthermore, the results of the proposed CDSS query optimizer are tested against the effects of other genetic algorithm based CDSS query optimizers. It is experimentally found that the results produced using RDFG_CDQO are 13%, 10%, 7% and 3.5% better than the outcomes of the other CDSS query optimizers designed using simple, novel, restricted and entropy-based restricted genetic algorithm respectively. To get the best possible solution using RDFG_CDQO, the value of divergence rate should be set up to 50%. Furthermore, to statistically approve the proposed framework, the results obtained using RDFG_CDQO are validated using different measures of regression analysis viz. assumption of linearity, independence, and constant variance.

Extending the popular Answer Set Programming (ASP) paradigm by introspective reasoning capacities has received increasing interest within the last years. Particular attention is given to the formalism of epistemic logic programs (ELPs) where standard rules are equipped with modal operators which allow to express conditions on literals for being known or possible, i.e., contained in all or some answer sets, respectively. ELPs thus deliver multiple collections of answer sets, known as world views. Employing ELPs for reasoning problems so far has mainly been restricted to standard decision problems (complexity analysis) and enumeration (development of systems) of world views. In this paper, we take a next step and contribute to epistemic logic programming in two ways: First, we establish quantitative reasoning for ELPs, where the acceptance of a certain set of literals depends on the number (proportion) of world views that are compatible with the set. Second, we present a novel system that is capable of efficiently solving the underlying counting problems required to answer such quantitative reasoning problems. Our system exploits the graph-based measure treewidth and works by iteratively finding and refining (graph) abstractions of an ELP program. On top of these abstractions, we apply dynamic programming that is combined with utilizing existing search-based solvers like (e)clingo for hard combinatorial subproblems that appear during solving. It turns out that our approach is competitive with existing systems that were introduced recently. This work is under consideration for acceptance in TPLP., Comment: Paper presented at the 37th International Conference on Logic Programming (ICLP 2021), 16 pages

Inspired by fuzzy hyperalgebras and fuzzy polynomial function (term function), some homomorphism properties of fundamental relation on fuzzy hyperalgebras are conveyed. The obtained relations of fuzzy hyperalgebra are utilized for certain applications, i.e., biological phenomena and genetics along with some elucidatory examples presenting various aspects of fuzzy hyperalgebras. Then, by considering the definition of identities (weak and strong) as a class of fuzzy polynomial function, the smallest equivalence relation (fundamental relation) is obtained which is an important tool for fuzzy hyperalgebraic systems. Through the characterization of these equivalence relations of a fuzzy hyperalgebra, we assign the smallest equivalence relation α i 1 i 2 ∗ on a fuzzy hyperalgebra via identities where the factor hyperalgebra is a universal algebra. We extend and improve the identities on fuzzy hyperalgebras and characterize the smallest equivalence relation α J ∗ on the set of strong identities.

Catalytic P systems are among the first variants of membrane systems ever considered in this area. This variant of systems also features some prominent computational complexity questions, and in particular the problem of using only one catalyst in the whole system: is one catalyst enough to allow for generating all recursively enumerable sets of multisets? Several additional ingredients have been shown to be sufficient for obtaining computational completeness even with only one catalyst. In this paper, we show that one catalyst is sufficient for obtaining computational completeness if either catalytic rules have weak priority over non-catalytic rules or else instead of the standard maximally parallel derivation mode, we use the derivation mode maxobjects, i.e., we only take those multisets of rules which affect the maximal number of objects in the underlying configuration.

Magnetic Resonance Imaging (MRI) is a widely used medical diagnosis technique. However, the quality of MR image is affected by the noise which is caused by mechanical and environmental reasons during the MR image acquisition process. For decades, various kinds of methods including filtering approaches, transform domain approaches and statistical approaches have been applied to the MR image denoising problem, while there are also some drawbacks exiting in these methods such as arising undesirable change of texture and long computation time needed. In this paper, we proposed a novel MR image denoising method called DESN which is a neural network method and has a novel network architecture with well-designed loss function. In DESN, the convolutional neural networks itself is considered as a regularizer or image prior information for the inverse problems such as denoising. The network architecture of DESN is designed from the auto-encoder architecture, it has three main parts: encoder network for extracting low-resolution image features, decoder network for restoring high-resolution features and skip connections for transmitting abstract information from encoder network to decoder network. Besides, we also design a novel loss function which contains two main parts: data fidelity loss ( L f i d e l i t y ), image quality penalty ( L q ) and three loss terms: mean squared error term ( L M S E ), image structure similarity term ( L S ), image information entropy term ( L I E ). We compare the performance of DESN with DIP and some state of the art denoising methods, and the performance of our network with different loss terms are also compared in three MR modalities. The comparative results show that DESN have the superior performance in generating high-quality MR image with enough edge and texture information.

We study a security game over a network played between adefenderandkattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of$$\lambda $$λnodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizingdefense-optimalnetworks which allow for the bestequilibrium defense ratio; this is the ratio ofkover the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for$$\lambda $$λconstantly close to 1 orn. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is$${\mathtt {NP}}$$NP-hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for thePrice of Defensefor any$$\lambda $$λ; this is the worst equilibrium defense ratio over all graphs.

Gene regulatory networks represent the interactions among genes regulating the activation of specific cell functionalities. They have been successfully modelled using Boolean networks, where a set of Boolean variables model the activation state of each gene, and Boolean functions model positive and negative influences among genes. Moreover, when the effect of such influences is additive, threshold Boolean networks, in which Boolean functions are replaced by simpler threshold functions, turned out to be particularly effective. In this paper we propose a systematic translation of threshold Boolean networks into Ehrenfeucht and Rozenberg's reaction systems. Our translation produces a non redundant set of reactions, each using a minimal set of objects. This translation allows us to simulate the behaviour of a general threshold Boolean network by simply executing the (closed) reaction system we obtain, and to investigate causality relations among genes by applying tools available for reaction systems. We implemented our translation in an open-source tool and applied it in two case studies: the gene regulation network of segment polarity in Drosophila melanogaster and the one controlling the differentiation of Th cells in the immune system. In both case studies, we investigate causalities among genes in the reaction system obtained from the translation by applying a tool for the computation of formula based predictors. In the context of the second case study, we show that also Boolean networks with non-additive influences and modelling genes with multiple expression levels can be dealt with by our approach.

Given a text T and a set of r patterns P 1 , P 2 , … , P r , the exact multiple pattern matching problem reports the ending positions of all occurrences of P i in T for 1 ≤ i ≤ r . By transforming all substrings with a fixed length of T into a reference tree such that each internal node stores a reference string, the exact multiple pattern matching problem can be efficiently solved by searching patterns in the tree via the guidance of the reference strings. We design elegant algorithms to construct the reference tree (the preprocessing phase) and to search patterns in the tree (the searching phase) using bitwise operations. The experiments involving problem instances from the DNA sequence and the English language are conducted to compare the performance of our approach against those of the suffix tree and suffix array algorithms. The computational results demonstrate the advantage of our approach over these algorithms. In spite of the simplicity, our approach is quite efficient, flexible and robust.

In two-player games on graphs, the players move a token through a graph to produce a finite or infinite path, which determines the qualitative winner or quantitative payoff of the game. We study bidding games in which the players bid for the right to move the token. Several bidding rules were studied previously. In Richman bidding, in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Poorman bidding is similar except that the winner of the bidding pays the "bank" rather than the other player. Taxman bidding spans the spectrum between Richman and poorman bidding. They are parameterized by a constant tau in [0,1]: portion tau of the winning bid is paid to the other player, and portion 1-tau to the bank. While finite-duration (reachability) taxman games have been studied before, we present, for the first time, results on infinite-duration taxman games. It was previously shown that both Richman and poorman infinite-duration games with qualitative objectives reduce to reachability games, and we show a similar result here. Our most interesting results concern quantitative taxman games, namely mean-payoff games, where poorman and Richman bidding differ significantly. A central quantity in these games is the ratio between the two players' initial budgets. While in poorman mean-payoff games, the optimal payoff of a player depends on the initial ratio, in Richman bidding, the payoff depends only on the structure of the game. In both games the optimal payoffs can be found using (different) probabilistic connections with random-turn games in which in each turn, instead of bidding, a coin is tossed to determine which player moves. While the value with Richman bidding equals the value of a random-turn game with an un-biased coin, with poorman bidding, the bias in the coin is the initial ratio of the budgets. We give a complete classification of mean-payoff taxman games that is based on a probabilistic connection: the value of a taxman bidding game with parameter tau and initial ratio r, equals the value of a random-turn game that uses a coin with bias F(tau, r) = (r+tau * (1-r))/(1+tau). Thus, we show that Richman bidding is the exception; namely, for every tau

In this paper, we consider the logic ${\textsf{ITL}}^{e}$, a variant of intuitionistic linear temporal logic that is interpreted over the class of dynamic Kripke frames. These are bi-relational structures of the form $ \langle{W, \preccurlyeq , f}\rangle $ where $\preccurlyeq $ is a partial order on $W$ and $f: W \to W$ is a $\preccurlyeq $-monotone function. Our main result answers a question recently raised by Boudou et al. (2017, A decidable intuitionistic temporal logic. In Computer Science Logic 2017, pp. 14:1–14:17. Vol. 82 of LIPIcs) about axiomatizing this logic. We provide an axiomatization of ${\textsf{ITL}}^{e}$ and prove its strong completeness with respect to the class of all dynamic Kripke frames. The proposed axiomatization is infinitary; it has two derivation rules with countably many premises and one conclusion. It should be mentioned that ${\textsf{ITL}}^{e}$ is semantically non-compact, so no finitary proof system for this logic could be strongly complete.

In this paper, we introduce the online service with delay problem. In this problem, there are $n$ points in a metric space that issue service requests over time, and a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, that has many applications in operations management, operating systems, logistics, supply chain management, and scheduling. Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm. The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We hope this technique will be useful for related problems such as reordering buffer management, online TSP, vehicle routing, etc. We also generalize our results to $k > 1$ servers., 30 pages, 11 figures, Appeared in 49th ACM Symposium on Theory of Computing (STOC), 2017

Introduction. The organization of branches and repetitions in the context of logical programming is considered by an example of the Prolog language. The fundamental feature of the program in a logical programming language is the fact that a computer must solve a problem by reasoning like a human. Such a program contains a description of objects and relations between them in the language of mathematical logic. At the same time, the software implementation of branching and repetition remains a challenge in the absence of special operators for the indicated constructions in the logical language. The objectives of the study are to identify the most effective ways to solve problems using branching and repetition by means of the logic programming language Prolog, as well as to demonstrate the results obtained by examples of computational problems. Materials and Methods. An analysis of the literature on the subject of the study was carried out. Methods of generalization and systematization of knowledge, of the program testing, and analysis of the program execution were used. Results. Constructions of branching and repetition organization in a Prolog program are proposed. To organize repetitions, various options for completing a recursive cycle when solving problems are given. Discussion and Conclusions. The methods of organizing branches and repetitions in the logic programming language Prolog are considered. All these methods are illustrated by examples of solving computational problems. The results obtained can be used in the further development of the recursive predicates in logical programming languages, as well as in the educational process when studying logical programming in the Prolog language. The examples of programs given in the paper provide using them as a technological basis for programming branches and repetitions in the logic programming language Prolog.

We consider a two-stage production scheduling problem where each operation can be outsourced or processed in-house. For each operation in the same machine, the ratio of its outsourcing cost to its processing time is constant. The objective is to minimize the sum of the makespan and the total outsourcing cost. It is known that this problem is either polynomial time solvable or NP-hard according to the conditions of the ratios. Even though approximation algorithms for NP-hard cases had been developed, their tight worst-case performance ratios are still open. In this paper, we carefully analyze the approximation algorithms to identify their tight worst-case performance ratios for cases. In one case, we propose a new approximation algorithm with a better and tight worst-case performance ratio. In the process of analyzing the algorithm, we propose a technique utilizing nonlinear optimization.

Snoopy is a powerful modelling and simulation tool for various types of Petri nets, which have been applied to a wide range of biochemical reaction networks. We present an enhanced version of Snoopy, now supporting coloured and uncoloured stochastic, continuous and hybrid Petri Nets with fuzzy kinetic parameters. Colour helps to cope with modelling challenges imposed by larger and more complex networks. Fuzzy parameters are specifically useful when kinetic parameter values can not be precisely measured or estimated. By running fuzzy simulation we obtain output bands of the variables of interest induced by the effect of the fuzzy kinetic parameters. Simulation is always done on the uncoloured level. For this purpose, coloured fuzzy Petri nets are automatically unfolded to their corresponding uncoloured counterparts. Combining the power of fuzzy kinetic parameters with the modelling convenience of coloured Petri nets provides a new quality in user support with sophisticated modelling and analysis features.

The exploration of one-factorizations of complete graphs is the foundation of some classical sports scheduling problems. One has to traverse the landscape of such one-factorizations by moving from one of those to a so-called neighbor one-factorization. This approach amounts to modifying locally the coloring associated with a one-factorization. We consider some particular types of modifications and describe various constructions which give one-factorizations which may be modified or not by these techniques. Among those are recoloring of bichromatic cycles, altering of optimally colored subcliques of even size, or recoloring of chordless lanterns.

In the buffer minimization in multiprocessor systems with conflicts or simply buffer minimization problem, a multi-processor system is modelled as an undirected graph. A conflict occurs if two processors are connected by an edge. Conflicting processors can not run at the same time. At any time, load may arrive on one or more processors. Incoming workload is stored in an input buffer and a machine that is running reduces its workload at a constant rate. The goal is to find a schedule that minimizes the maximum workload over all machines and over time. We consider the special case where the graph is a path. We give upper and lower bounds on the competitive ratio for paths of various lengths. We also consider online algorithms that have resource augmentation on their speed (processing rate), and give a ( 1 + 2 e ) -speed ( 1 / e + 2 ) -competitive algorithm.

Hedonic games are coalition formation games where players only specify preferences over coalitions they are part of. We introduce and systematically study three local fairness notions in hedonic games called max-min fairness, grand-coalition fairness, and min-max fairness. To this end, we define suitable threshold coalitions for these three concepts. A coalition structure (i.e., a partition of the players into coalitions) is considered locally fair if all players' coalitions in this structure are each at least as good as their threshold coalitions. Based on this approach, we then introduce three specific notions of local fairness by suitably adapting fairness notions from fair division. We show that they form a proper hierarchy and how they are related to previously studied solution concepts in hedonic games. We also study the computational aspects of finding threshold coalitions and of deciding whether fair coalition structures exist in additively separable hedonic games, and we investigate the related price of local fairness.

The parking problem has become one of the major issues in urban transportation planning and traffic management research. The present paper deals with the dynamic assignment problem of the parking slots (places). The objectives are to provide a global satisfaction of all customers and maximize parking occupancy. A dynamic assignment problem consists in solving a sequence of assignment problems over time. To cope with all these aspects, we offer in this paper, a new approach based on a learning strategy: an Estimation of Distribution Algorithm (EDA) where a reinforcement learning method is used to support the assignment algorithm. We tested our approach with simulations for over 120 days, using a set of up to 10 parking lots (i.e. with up to 7,000 parking slots) and 13,000 requests distributed with different patterns over a day. The comparative study between an assignment algorithm with and without reinforcement learning algorithm has proven the relevance of our approach: the saving is up to 80%. The results also showed the effects and the benefits of the learning strategy.

The notion of comparison between system runs is fundamental in formal verification. This concept is implicitly present in the verification of qualitative systems, and is more pronounced in the verification of quantitative systems. In this work, we identify a novel mode of comparison in quantitative systems: the online comparison of the aggregate values of two sequences of quantitative weights. This notion is embodied by comparator automata (comparators, in short), a new class of automata that read two infinite sequences of weights synchronously and relate their aggregate values. We show that aggregate functions that can be represented with B\"uchi automaton result in comparators that are finite-state and accept by the B\"uchi condition as well. Such $\omega$-regular comparators further lead to generic algorithms for a number of well-studied problems, including the quantitative inclusion and winning strategies in quantitative graph games with incomplete information, as well as related non-decision problems, such as obtaining a finite representation of all counterexamples in the quantitative inclusion problem. We study comparators for two aggregate functions: discounted-sum and limit-average. We prove that the discounted-sum comparator is $\omega$-regular iff the discount-factor is an integer. Not every aggregate function, however, has an $\omega$-regular comparator. Specifically, we show that the language of sequence-pairs for which limit-average aggregates exist is neither $\omega$-regular nor $\omega$-context-free. Given this result, we introduce the notion of prefix-average as a relaxation of limit-average aggregation, and show that it admits $\omega$-context-free comparators i.e. comparator automata expressed by B\"uchi pushdown automata.

We consider the Connectivity Augmentation Problem (CAP), a classical problem in the area of Survivable Network Design. It is about increasing the edge-connectivity of a graph by one unit in the cheapest possible way. More precisely, given a $k$-edge-connected graph $G=(V,E)$ and a set of extra edges, the task is to find a minimum cardinality subset of extra edges whose addition to $G$ makes the graph $(k+1)$-edge-connected. If $k$ is odd, the problem is known to reduce to the Tree Augmentation Problem (TAP) -- i.e., $G$ is a spanning tree -- for which significant progress has been achieved recently, leading to approximation factors below $1.5$ (the currently best factor is $1.458$). However, advances on TAP did not carry over to CAP so far. Indeed, only very recently, Byrka, Grandoni, and Ameli (STOC 2020) managed to obtain the first approximation factor below $2$ for CAP by presenting a $1.91$-approximation algorithm based on a method that is disjoint from recent advances for TAP. We first bridge the gap between TAP and CAP, by presenting techniques that allow for leveraging insights and methods from TAP to approach CAP. We then introduce a new way to get approximation factors below $1.5$, based on a new analysis technique. Through these ingredients, we obtain a $1.393$-approximation algorithm for CAP, and therefore also TAP. This leads to the currently best approximation result for both problems in a unified way, by significantly improving on the above-mentioned $1.91$-approximation for CAP and also the previously best approximation factor of $1.458$ for TAP by Grandoni, Kalaitzis, and Zenklusen (STOC 2018). Additionally, a feature we inherit from recent TAP advances is that our approach can deal with the weighted setting when the ratio between the largest to smallest cost on extra links is bounded, in which case we obtain approximation factors below $1.5$.

Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The extra connectivity is an important parameter for the reliability evaluation of interconnection networks and is a generalization of the traditional connectivity. Let $g\geq 0$ be an integer and $G$ be a connected graph; the $g$-extra connectivity of $G$ is the minimum cardinality of a set of vertices in $G$, if it exists, whose removal disconnects $G$ and leaves every component with more than $g$ vertices. Determining the $g$-extra connectivity is still an unsolved problem in many interconnection networks. Let $n$, $k$ be positive integers. Let $Q_{n,k}\, (1 \leq k \leq n-1)$ denote the $(n, k)$-enhanced hypercube. In this paper, we determine the $g$-extra connectivity of $Q_{n,k}$ is $(n+1)(g+1)-\frac{g(g+3)}{2}$ for $0\leq g\leq n-k-1$, $4\leq k\leq n-5\,(n\geq 9)$. Some previous results in [Zhang, M. and Zhou, J. (2015) On g-extra connectivity of folded hypercubes. Theor. Comput. Sci., 593, 146–153.] and [Sabir, E., Mamut, A. and Vumar, E. (2019) The extra connectivity of the enhanced hypercubes. Theor. Comput. Sci., 799, 22–31.] are extended.

Surrogate-assisted evolutionary algorithms have the potential to be of high value for real-world optimization problems when fitness evaluations are expensive, limiting the number of evaluations that can be performed. In this article, we consider the domain of pseudo-Boolean functions in a black-box setting. Moreover, instead of using a surrogate model as an approximation of a fitness function, we propose to precisely learn the coefficients of the Walsh decomposition of a fitness function and use the Walsh decomposition as a surrogate. If the coefficients are learned correctly, then the Walsh decomposition values perfectly match with the fitness function, and, thus, the optimal solution to the problem can be found by optimizing the surrogate without any additional evaluations of the original fitness function. It is known that the Walsh coefficients can be efficiently learned for pseudo-Boolean functions with k -bounded epistasis and known problem structure. We propose to learn dependencies between variables first and, therefore, substantially reduce the number of Walsh coefficients to be calculated. After the accurate Walsh decomposition is obtained, the surrogate model is optimized using GOMEA, which is considered to be a state-of-the-art binary optimization algorithm. We compare the proposed approach with standard GOMEA and two other Walsh decomposition-based algorithms. The benchmark functions in the experiments are well-known trap functions, NK-landscapes, MaxCut, and MAX3SAT problems. The experimental results demonstrate that the proposed approach is scalable at the supposed complexity of O (ℓ log ℓ) function evaluations when the number of subfunctions is O (ℓ) and all subfunctions are k -bounded, outperforming all considered algorithms.

The computationally hard problem of finite language decomposition is investigated. A finite language L is decomposable if there are two languages L1 and L2 such that L = L1L2. Otherwise, L is prime. The main contribution of the paper is an adaptive parallel algorithm for finding all decompositions L1L2 of L. The algorithm is based on an exhaustive search and incorporates several original methods for pruning the search space. Moreover, the algorithm is adaptive since it changes its behavior based on the runtime acquired data related to its performance. Comprehensive computational experiments on more than 4000 benchmark languages generated over alphabets of various sizes have been carried out. The experiments showed that by using the power of parallel computing the decompositions of languages containing more than 200000 words can be found. Decompositions of languages of that size have not been reported in the literature so far.

Bipartite matching markets pair agents on one side of a market with agents, items, or contracts on the opposing side. Prior work addresses online bipartite matching markets, where agents arrive over time and are dynamically matched to a known set of disposable resources. In this paper, we propose a new model, Online Matching with (offline) Reusable Resources under Known Adversarial Distributions (OM-RR-KAD), in which resources on the offline side are reusable instead of disposable; that is, once matched, resources become available again at some point in the future. We show that our model is tractable by presenting an LP-based adaptive algorithm that achieves an online competitive ratio of 1/2 - eps for any given eps greater than 0. We also show that no non-adaptive algorithm can achieve a ratio of 1/2 + o(1) based on the same benchmark LP. Through a data-driven analysis on a massive openly-available dataset, we show our model is robust enough to capture the application of taxi dispatching services and ride-sharing systems. We also present heuristics that perform well in practice., Comment: To appear in AAAI 2018

With the slowing down of Moore's law, the use of hardware other than CPUs, such as graphics processing units (GPUs) or field-Programmable gate arrays (FPGAs), is increasing. However, when using het...