Search

• Eulerian trails are classical and important objects in theoretical computer science field. • Enumeration of Eulerian trails is known to be #P-complete. • Although the existence of an algorithm with linear time per output is known, the existence of a faster algorithm is open. • This paper shows optimal algorithms for Eulerian trails which run in constant time per solution on average. In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinct if the edge sequences are not identical, and they are said to be vertex-distinct if the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O (N + m) total time, where N is the number of solutions and m is the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015]. [ABSTRACT FROM AUTHOR]

Solid codes provide outstanding fault-tolerance when used for information transmission through a noisy channel involving not only symbol substitutions, but also synchronisation errors and black-outs. In this paper we provide an automaton theoretic characterisation of solid codes which takes this fault-tolerance into account. The fault-tolerance afforded by a solid code L can be summarised as follows: Consider messages, encoded using L , being sent through a noisy channel. Any code words in L , which are present in the received message, will be decoded correctly, unless they themselves happen to be the results of errors. Thus, errors in the received message will not lead to incorrect decodings of those parts which are error-free. In this paper we consider acceptors which are fault-tolerant in this sense when analysing such received messages. These acceptors characterise the class of solid codes. For finite solid codes an automaton characterisation was published in the sixties by Levenshtein and Romanov. The characterisation uses state-invariant finite-state transducers which act as decoders in such a way that an output is generated exactly when a code word has been read completely. State-invariance means that acceptance does not depend on the initial state — every state can be used as the initial state. The results of Levenshtein and Romanov depend strongly on the fact that the code is finite. In this paper we provide a general automaton theoretic characterisation of arbitrary solid codes without any such restriction. Moreover, the solid code is regular as a language if and only if the automaton used in the characterisation can be reduced to an equivalent finite automaton with equivalent properties. The main results of this paper are as follows: Every acceptor defines a solid code. For every solid code there is a fault-tolerant acceptor defining the code. Such acceptors expose the decomposition of potentially faulty received messages according to the code. For solid codes which are regular as languages these acceptors can be chosen to be finite while preserving all important combinatorial properties. Part of this work was presented at the 14th Journées Montoises of Theoretical Computer Science [32]. [ABSTRACT FROM AUTHOR]

The problem of reducing ϵ -NN to (c , r) -NN is very important in theoretical computer science area and has attracted many research efforts. In this paper a new algorithm for such problem is proposed, which achieves O (log ⁡ n) query time. Comparing with the former algorithms for the same problem, this query time is the lowest, which is the main contribution of this paper. The low query time complexity is achieved by raising the preprocessing time and space complexity. How to reduce the cost added into the two complexities is also discussed in this paper. [ABSTRACT FROM AUTHOR]

Boolean functions have important applications in information technology and computer science. Certificate complexity is an important combinatorial measure of Boolean function complexity. In this paper, we first introduce many concise and efficient notations then we study the elementary symmetric Boolean functions and obtain their certificate complexities when their degrees are odd or powers of 2. We show that both upper and lower bounds of certificate complexities can be attained. [ABSTRACT FROM AUTHOR]

String matching is one of the most extensively studied problems in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last few decades a myriad of alternative solutions have been proposed, based on very different techniques. However, automata have always played a very important role in the design of efficient string matching algorithms. In this paper we present the Range Automaton , a weak yet efficient variant of the non-deterministic suffix automaton of a string whose configuration can be encoded in a very simple form and which is particularly suitable to be used for solving a multitude of text-searching problems. We will firstly develop our approach in the case of exact string matching and present an efficient algorithm, named Backward Range Automaton Matcher, which turns out to be very fast in many practical cases. Later, we will show how the Range Automaton can be adapted in an effective way also to non-standard string matching problems such as swap matching and multiple string matching. Experimental results suggest that our approach is flexible and effective for all three search problems addressed, especially in the case of long patterns. • We present a simple and efficient technique for simulating the suffix automaton of a string. • The new technique leads to the definition of an automaton, called Range Automaton, for the weak recognition of the suffixes of a string. • We apply the Range Automaton to the exact string matching problem, obtaining an efficient and flexible solution in practice, especially in the case of long patterns. • We extend the application of the Range Automaton to the swap matching problem, a special case of approximate string matching. • We extend the application of the Range Automaton to the problem of multiple pattern matching. [ABSTRACT FROM AUTHOR]

The problem of two-sided matching markets is well-studied in computer science and economics, owing to its diverse applications across numerous domains. Since market participants are usually uncertain about their preferences in various online matching platforms, an emerging line of research is dedicated to the online setting where one-side participants (players) learn their unknown preferences through multiple rounds of interactions with the other side (arms). Sankararaman et al. [23] provide an Ω (N log ⁡ (T) Δ 2 + K log ⁡ (T) Δ) regret lower bound for this problem under serial dictatorship assumption, where N is the number of players, K (≥ N) is the number of arms, Δ is the minimum reward gap across players and arms, and T is the time horizon. Serial dictatorship assumes arms have the same preferences, which is common in reality when one side participants have a unified evaluation standard. Recently, the work of Kong and Li [10] proposes the ET-GS algorithm and achieves an O (K log ⁡ (T) Δ 2 ) regret upper bound, which is the best upper bound attained so far. Nonetheless, a gap between the lower and upper bounds, ranging from N to K , persists. It remains unclear whether the lower bound or the upper bound needs to be improved. In this paper, we propose a multi-level successive selection algorithm that obtains an O (N log ⁡ (T) Δ 2 + K log ⁡ (T) Δ) regret bound when the market satisfies serial dictatorship. To the best of our knowledge, we are the first to propose an algorithm that matches the lower bound in the problem of matching markets with bandits. [ABSTRACT FROM AUTHOR]

Graph energies and spectral radii have application in molecular computing and computer sciences. In this paper, we concentrate on new findings about the Symmetric Division Deg, (SDD) energies, and (SDD) spectral radii of p splitting and p shadow graphs built on the foundation of any regular graph. In fact it becomes natural to ask how the SDD energies and spectral radii of newly formed graphs depend on the SDD energies and spectral radii of the given regular graph. [ABSTRACT FROM AUTHOR]

• We consider a variant of the online buffer management problem. • This variant is called the 2-bounded delay buffer management problem with lookahead. • We design an optimal online algorithm for this variant. The bounded delay buffer management problem, which was proposed by Kesselman et al. (STOC 2001 and SIAM Journal on Computing 33(3), 2004), is an online problem focusing on buffer management of a switch supporting Quality of Service (QoS). The problem definition is as follows: Packets arrive to a buffer over time and each packet is specified by the release time , deadline and value. An algorithm can transmit at most one packet from the buffer at each integer time and can gain its value as the profit if transmitting the packet by its deadline after its release time. The objective of this problem is to maximize the gained profit. We say that an instance of the problem is s -bounded if for any packet, an algorithm has at most s chances to transmit it. For any s ≥ 2 , Hajek (CISS 2001) showed that the competitive ratio of any deterministic algorithm is at least (1 + 5) / 2 ≥ 1.618. Recently, Veselý et al. (SODA 2019) designed an online algorithm matching the lower bound. Böhm et al. (ISAAC 2016 and Theoretical Computer Science, 2019) introduced the lookahead ability to an online algorithm. At a time t , the algorithm obtains information about packets arriving at time t + 1 , and showed that for s = 2 , there is an algorithm which achieves the competitive ratio of (− 1 + 13) / 2 ≤ 1.303. Also, they showed that the competitive ratio of any deterministic algorithm is at least (1 + 17) / 4 ≥ 1.280. In this paper, for the 2-bounded model with lookahead, we design an algorithm with a matching competitive ratio of (1 + 17) / 4. [ABSTRACT FROM AUTHOR]

The lambda calculus can be seen as a language that connects mathematics with computer science. However, the models used in both disciplines have different basic properties. In computer science these models are mainly based on domain theory with its partial functions and its fixed point property. In mathematics the models use total functions and relations and allow the integration of logic. Typically, mathematical models are based on set theory with its actual infinite sets, which are incongruous with computer science. We will present a dynamic model that is based consequently on the potential infinite. It uses total functions, whereby functions and the function spaces are seen as interdependent, increasing finite entities. It moreover allows the integration of higher-order logic (to be demonstrated in a separate paper), provided the universal quantifier is interpreted in a specific, dynamic way. Such a model can serve as a common denotational semantics of the lambda calculus for both, mathematics and computer science. • The paper presents a mathematical formulation of a potential infinite set, called factor system. • Factor systems are closed under the function space construction, so they are potential infinite models of simple type theory. • Each factor system has a limit whose elements can be characterized as maximal, consistent sets of states. • Models based on factor systems allow the integration of higher-order logic. The presentation of this is a future task. [ABSTRACT FROM AUTHOR]

• Generalising confluence to confluence up to garbage. • Critical pair analysis for confluence up to garbage. • Back-tracking free recognition of graph languages. 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. [ABSTRACT FROM AUTHOR]

• Study the minsum k -sink problems on dynamic flow path networks for the confluent/non-confluent flow model. • Develop algorithms which run in almost linear time regardless of the number of sinks k. • Improve upon the previous results for the same problem with the confluent flow model. • Provide the first polynomial time algorithm for the problem with the non-confluent flow model. • The main theoretical contribution is to construct novel data structures for solving subproblems in polylogarithmic time. We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks , all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm. [ABSTRACT FROM AUTHOR]

Suppose that two independent sets I b and I r of a graph such that | I b | = | I r | are given, and a token is placed on each vertex in I b. The sliding token problem is to determine whether there exists a sequence of independent sets which transforms I b into I r so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. The sliding token problem is one of the reconfiguration problems that attract the attention from the viewpoint of theoretical computer science. Recently, the problems that aim at finding a shortest reconfiguration sequence are investigated. In general, even if it is polynomial time solvable to decide whether two instances are reconfigurable into each other, it can be NP-hard to find a shortest sequence between them. In this paper, we show that the problem for finding a shortest sequence between two independent sets is polynomial time solvable for some graph classes which are subclasses of the class of interval graphs. As far as the authors know, this is the first polynomial time algorithm for the shortest sliding token problem for a graph class that requires detours. [ABSTRACT FROM AUTHOR]

Fair division of indivisible resources is a fundamental problem in many disciplines, including computer science, economy, operations research, etc. The existence of PMMS allocations of goods is a major open problem in fair division, even for additive valuations. At the state of the art, there is no identified setting where PMMS allocations are deemed impossible, and the known existing results regarding their existence are limited to highly constrained settings. In this paper, we provide an algorithm for computing a PMMS allocation for identical variant. We also use the algorithm to find the PMMS allocations for 3 agents in line graphs. Moreover, we show that a 4 5 -PMMS allocation can be computed in polynomial time when agents agree on the ordinal ranking of the goods. A quantitative gauge for assessing the impact on social welfare is known as the price of fairness , which quantifies the maximum possible reduction in social welfare due to the imposition of fairness constraints. Originally explored in the context of divisible goods, the concept of the price of fairness continues to be a pivotal metric for evaluating the effect of fairness considerations on overall social welfare. Consequently, we study the efficiency decrease under PMMS allocations and prove a tight upper bound on the price of PMMS allocations. • We present an algorithm to compute a PMMS allocation if agents' valuation functions are identical. • We analyze an existing algorithm terminates with a 4 5 -PMMS allocation in polynomial time when agents have identical ordinal ranking values of the goods. • We also examine the efficiency loss associated with PMMS allocations and establish their precise price bound. [ABSTRACT FROM AUTHOR]

In a recent paper (M. Barash, A. Okhotin, “An extension of context-free grammars with one-sided context specifications”, Inform. and Comput. , 2014), the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions, presents several examples of grammars and establishes a basic normal form theorem. This normal form, in particular, leads to a simple parsing algorithm working in time O ( n 4 ) , where n is the length of the input string. [ABSTRACT FROM AUTHOR]

Many problems in Computer Science can be abstracted to the following question: given a set of objects and rules respectively, which new objects can be produced? In the paper, we consider a succinct version of the question: given a set of binary strings and several operations like conjunction and disjunction , which new binary strings can be generated? Although it is a fundamental problem, to the best of our knowledge, the problem hasn't been studied yet. In this paper, an O ( m 2 n ) algorithm is presented to determine whether a string s is representable by a set W , where n is the number of strings in W and each string has the same length m . However, looking for the minimum subset to represent a given string is shown to be NP -hard. Also, finding the smallest subset to represent each string in the original set is NP -hard. We establish tight inapproximability results and approximation algorithms for these NP -hard problems. In addition, we prove that counting the number of representable strings is # P -complete. We then explore how the problems change when the operator negation is available. For example, if the operator negation can be used, the counting problem is as simple as some power of 2. This difference may help us to better understand the problem. [ABSTRACT FROM AUTHOR]

Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the sliding windows model of streaming (where elements eventually expire) the problem of finding L 2 -heavy elements has remained completely open despite multiple papers and considerable success in finding L 1 -heavy elements. Since the L 2 -heavy element problem doesn't satisfy certain conditions, existing methods for sliding windows algorithms, such as smooth histograms or exponential histograms are not directly applicable to it. In this paper, we develop the first polylogarithmic-memory algorithm for finding L 2 -heavy elements in the sliding window model. Our technique allows us not only to find L 2 -heavy elements, but also heavy elements with respect to any L p with 0 < p ≤ 2 on sliding windows. By this we completely “close the gap” and resolve the question of finding L p -heavy elements in the sliding window model with polylogarithmic memory, since it is well known that for p > 2 this task is impossible. We demonstrate a broader applicability of our method on two additional examples: we show how to obtain a sliding window approximation of the similarity of two streams, and of the fraction of elements that appear exactly a specified number of times within the window (the α -rarity problem). In these two illustrative examples of our method, we replace the current expected memory bounds with worst case bounds. [ABSTRACT FROM AUTHOR]

The problem of automated theorem finding is one of the 33 basic research problems in automated reasoning which was originally proposed by Wos in 1988, and it is still an open problem. To solve the problem, an approach of forward deduction based on the strong relevant logics was proposed. Following the approach, this paper presents a systematic methodology for automated theorem finding. To show the effectiveness of our methodology, the paper presents two case studies, one is automated theorem finding in NBG set theory and the other is automated theorem finding in Peano's arithmetic. Some known theorems have been found in our case studies. [ABSTRACT FROM AUTHOR]

This paper is about two generalizations of the mistake bound model to online multiclass classification. In the standard model , the learner receives the correct classification at the end of each round, and in the bandit model , the learner only finds out whether its prediction was correct or not. For a set F of multiclass classifiers, let opt std (F) and opt bandit (F) be the optimal bounds for learning F according to these two models. We show that an opt bandit (F) ≤ (1 + o (1)) (| Y | ln ⁡ | Y |) opt std (F) bound is the best possible up to the leading constant, closing a Θ (log ⁡ | Y |) factor gap. [ABSTRACT FROM AUTHOR]

Pattern languages have been an object of study in various subfields of computer science for decades. This paper introduces and studies a decision problem on patterns called the finite distinguishability problem: given a pattern π , are there finite sets T + and T − of strings such that the only pattern language containing all strings in T + and none of the strings in T − is the language generated by π ? This problem is related to the complexity of teacher-directed learning, as studied in computational learning theory, as well as to the long-standing open question whether the equivalence of two patterns is decidable. We show that finite distinguishability is decidable if the underlying alphabet is of size other than 2 or 3, and provide a number of related results, such as (i) partial solutions for alphabet sizes 2 and 3, and (ii) decidability proofs for variants of the problem for special subclasses of patterns, namely, regular, 1-variable, and non-cross patterns. For the same subclasses, we further determine the values of two complexity parameters in teacher-directed learning, namely the teaching dimension and the recursive teaching dimension. [ABSTRACT FROM AUTHOR]

Combinatorial problems are a fundamental research subject of theoretical computer science, and for a general graph many combinatorial problems are NP-hard and even #P-complete. Thus, it is interesting to seek or design special graphs for which these difficult combinatorial problems can be exactly solved. In this paper, we study some combinatorial problems for the Farey graphs, which are translated from Farey sequences and have received considerable attention from the scientific community. We determine exactly the domination number, the independence number, and the matching number. Moreover, we derive exact or recursive solutions to the number of minimum dominating sets, the number of dominating sets, the number of maximum independent sets, the number of independent sets, the number of maximum matchings, as well as the number of matchings. Finally, we obtain explicit expressions for the number of acyclic orientations and the number of root-connected acyclic orientations. Since the considered combinatorial problems have found wide applications in diverse fields, such as network science and graph data miming, this work is helpful for deepening our understanding of the applications for these combinatorial problems. [ABSTRACT FROM AUTHOR]

• The minimum cycle cover problem. • A simplified approach of analysis. • An O (n 2) time 24/5-approximation algorithm. • A new O (n 3) time 14/3-approximation algorithm. • An improved O (n 5) time 32/7-approximation algorithm. Given an undirected weighted graph G = (V , E) with nonnegative weight function obeying the triangle inequality, a set { C 1 , C 2 , ... , C k } of cycles is called a cycle cover if V ⊆ ⋃ i = 1 k V (C i) and its cost is given by the maximum weight of the cycles. The Minimum Cycle Cover Problem aims to find a cycle cover of cost at most λ with the minimum number of cycles. An O (n 2) 24/5-approximation algorithm and an O (n 5) 14/3-approximation algorithm are given by Yu and Liu (Improved approximation algorithms for some min-max cycle cover problems. Theoretical Computer Science 654 (2016) 45–58). However, the original proofs for approximation ratios are incomplete. In this paper we first present a corrected simplified analysis on the 24/5-approximation algorithm. Based on the simplified approach of analysis and some new observations, we present a new 14/3-approximation algorithm that runs in O (n 3) and give an improved 32/7-approximation algorithm that runs in O (n 5). [ABSTRACT FROM AUTHOR]

Boolean nested canalizing functions (NCF) have important applications in molecular regulatory networks, engineering and computer science. In the literature, there are two sensitivities to measure the complexity of a Boolean function. One is average sensitivity, the other one is maximal sensitivity. We follow the tradition and omit the word "maximal". In other words, in this paper, sensitivity is always maximal sensitivity. Using the past work of the authors and their coauthors on a characterization of NCF, we obtain the formula of the sensitivity of any NCF. We find that the sensitivity of any NCF is between ⌈ n + 2 2 ⌉ and n. Both lower and upper bounds are tight. We prove that the block sensitivity, hence the l -block sensitivity, is the same as the sensitivity for NCF. It is well known that monotone Boolean functions (MBF) also have this property. We characterize all functions which are both monotone and nested canalizing (MNCF). The closed formula of the cardinality of the set of MNCFs is also provided. • The closed formula of the maximal sensitivity of Boolean nested canalizing functions is obtained. • Both the lower and upper tight bounds of the maximal sensitivity of Boolean nested canalizing functions are computed. • The maximal sensitivity and the block sensitivity of nested canalizing functions are equal. • The algebraic normal forms of monotone nested canalizing functions are provided. • The closed formula of the number of monotone nested canalizing functions is obtained. [ABSTRACT FROM AUTHOR]

Abstract: A breakthrough in the field of text algorithms was the discovery of the fact that the maximal number of runs in a word of length n is and that they can all be computed in time. We study some applications of this result. New simpler time algorithms are presented for classical textual problems: computing all distinct k-th word powers for a given k, in particular squares for , and finding all local periods in a given word of length n. Additionally, we present an efficient algorithm for testing primitivity of factors of a word and computing their primitive roots. Applications of runs, despite their importance, are underrepresented in existing literature (approximately one page in the paper of Kolpakov and Kucherov, 1999 [25,26]). In this paper we attempt to fill in this gap. We use Lyndon words and introduce the Lyndon structure of runs as a useful tool when computing powers. In problems related to periods we use some versions of the Manhattan skyline problem. [Copyright &y& Elsevier]

Abstract: This paper studies the deviations of the regret in a stochastic multi-armed bandit problem. When the total number of plays n is known beforehand by the agent, Audibert et al. [2] exhibit a policy such that with probability at least , the regret of the policy is of order log n. They have also shown that such a property is not shared by the popular ucb1 policy of Auer et al. [3]. This work first answers an open question: it extends this negative result to any anytime policy (i.e. any policy that does not take the number of plays n into account). Another contribution of this paper is to design robust anytime policies for specific multi-armed bandit problems in which some restrictions are put on the set of possible distributions of the different arms. We also show that, for any policy (i.e. even when the number of plays n is known), the regret is of order log n with probability at least , so that the policy of Audibert et al. has the best possible deviation properties. [Copyright &y& Elsevier]

Abstract: There are many folded states consistent with a given mountain–valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in time where is the number of creases and is the total crease width. [Copyright &y& Elsevier]

Abstract: We consider perfect-information reachability stochastic games for 2 players on countable graphs. Such a game is strongly determined if, whenever we fix an inequality and a threshold , either Player Max has a strategy which forces the value of the game to satisfy against any strategy of Player Min, or Min has a strategy which forces the opposite against any strategy of Max. One of our results shows that whenever one of the players has an optimal strategy in every state of a game, then this game is strongly determined. This significantly generalises, e.g., recent results on finitely-branching reachability games. For strong determinacy, our methods are substantially different, based on which player has the optimal strategy, because the roles of the players are not symmetric. We also do not restrict the branching of the games, and where we provide an extension of results for finitely-branching games, we had to overcome significant complications and employ new methods as well. The other result is finding a subclass of stochastic games where Player Max has an optimal strategy in each state. The subclass is defined by the property that if is an accumulation point of the set of all values of a game then . These results complement recent results classifying the existence of an optimal strategy for Player Min, and our general strong-determinacy theorem applies here as well. We also apply our results for Max in the context of recently studied One-Counter stochastic games. This work extends a workshop version of this paper which appeared in GandALF 2011, in particular, we prove a conjecture raised in that paper for the class of all reachability games. [Copyright &y& Elsevier]

Abstract: This paper describes the biological and theoretical foundations of a new Artificial Immune System the Receptor Density Algorithm. The algorithm is developed with inspiration from T cell signalling processes and has application in anomaly detection. Connections between the Receptor Density Algorithm and kernel density estimation with exponential smoothing are demonstrated. Finally, the paper evaluates the algorithm’s performance on two types of anomaly detection problem. [Copyright &y& Elsevier]

Abstract: Reaction systems are a formal model based on the regulation mechanisms of facilitation and inhibition between biochemical reactions, which underlie the functioning of living cells. The aim of this paper is to explore the expressive power of reaction systems as a modeling framework, showing how their basic assumptions and properties can be exploited to formalize computer science and biology oriented problems. In this view, we first provide a reaction-based description of an iterative algorithm to solve the Tower of Hanoi puzzle. Then, we show how the regulation of gene expression in the lac operon, involved in the metabolism of lactose in Escherichia coli cells, can be formalized in terms of reaction systems. Finally, we present a method to derive, given a reaction system with reactions, a functionally equivalent system with reactions using simplification methods of boolean expressions. Some final remarks and directions for future research conclude the paper. [Copyright &y& Elsevier]

Abstract: In this paper, we prove the coincidence between strong/weak context bisimulation and strong/weak normal bisimulation for higher order -calculus, which generalizes Sangiorgi’s work. To achieve this aim, we introduce indexed higher order -calculus, which is similar to higher order -calculus except that every prefix of any process is assigned indices. Furthermore we present corresponding indexed bisimulations for this calculus, and prove the equivalence between these indexed bisimulations. Based on this result, we prove the main result of this paper, i.e., the equivalence between strong/weak context bisimulation and strong/weak normal bisimulation. [Copyright &y& Elsevier]

Abstract: The utilization of populations is one of the most important features of evolutionary algorithms (EAs). There have been many studies analyzing the impact of different population sizes on the performance of EAs. However, most of such studies are based on computational experiments, except for a few cases. The common wisdom so far appears to be that a large population would increase the population diversity and thus help an EA. Indeed, increasing the population size has been a commonly used strategy in tuning an EA when it did not perform as well as expected for a given problem. He and Yao (2002)  showed theoretically that for some problem instance classes, a population can help to reduce the runtime of an EA from exponential to polynomial time. This paper analyzes the role of population further in EAs and shows rigorously that large populations may not always be useful. Conditions, under which large populations can be harmful, are discussed in this paper. Although the theoretical analysis was carried out on one multimodal problem using a specific type of EAs, it has much wider implications. The analysis has revealed certain problem characteristics, which can be either the problem considered here or other problems, that lead to the disadvantages of large population sizes. The analytical approach developed in this paper can also be applied to analyzing EAs on other problems. [Copyright &y& Elsevier]

Abstract: In this paper, we prove decidability properties and new results on the position of the family of languages generated by (circular) splicing systems within the Chomsky hierarchy. The two main results of the paper are the following. First, we show that it is decidable, given a circular splicing language and a regular language, whether they are equal. Second, we prove the language generated by an alphabetic splicing system is context-free. Alphabetic splicing systems are a generalization of simple and semi-simple splicing systems already considered in the literature. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to obtain a theoretical foundation of inconsistency-tolerant (or paraconsistent) reasoning by presenting a comprehensive study of the structural proof-theory of David Nelson’s paraconsistent logic. Inconsistency handling has a growing importance in Computer Science since inconsistencies may frequently occur in knowledge-based and intelligent information systems. Paraconsistent, inconsistency-tolerant logics have been studied to cope with such inconsistencies. In this paper, proof systems for Nelson’s paraconsistent logic N4 are comprehensively studied. The logic N4 is a fundamental system and known to be a common basis for various extended and useful paraconsistent logics. Some basic theorems including cut-elimination, normalization and completeness are uniformly proved using various embedding theorems. A variety of sequent calculi and natural deduction systems for N4 and some closely related systems are presented and compared. [Copyright &y& Elsevier]

Abstract In this paper we study the approximation ratio of the solutions achieved after an ϵ -approximate one-round walk in non-atomic congestion games. Prior to this work, the solution concept of one-round walks had been studied for atomic congestion games with linear latency functions only (Christodoulou et al. [1] , Bilò et al. [2]). We give an explicit formula to determine the approximation ratio for non-atomic congestion games having general latency functions. In particular, we focus on polynomial latency functions, and, we prove that the approximation ratio is exactly ((1 + ϵ) (p + 1)) p + 1 for every polynomial of degree p. Then, we show that, by resorting to static (resp. dynamic) resource taxation, the approximation ratio can be lowered to (1 + ϵ) p + 1 (p + 1) p (resp. (1 + ϵ) p + 1 (p + 1) !). [ABSTRACT FROM AUTHOR]

Abstract This paper studies the well-known problem of gathering multiple mobile agents moving in a graph, but unlike previous results, we consider the problem in the presence of an adversarial mobile entity which we call the malicious agent. The malicious entity can occupy any empty node and prevent honest mobile agents from entering this node. This new adversarial model is interesting as it models transient mobile faults that can appear anywhere in a network. Moreover, our model lies between the less powerful delay-fault model , where the adversary can block an agent for only a finite time, and the more powerful but static fault model of black holes that can even destroy the agents. We study the problem for ring networks and we provide a complete characterization of the solvability of gathering, depending on the size n of the ring and the number of agents k. We consider both oriented or unoriented rings with either synchronous or asynchronous agents. We prove that in an unoriented ring network with asynchronous agents the problem is not solvable when k is even, while for synchronous agents the problem is unsolvable when both n is odd and k is even. We then present algorithms that solve gathering for all the remaining cases, thus completely solving the problem. Finally, we provide a proof-of-concept implementation of the synchronous algorithms using programmable Lego Mindstorms EV3 robots. [ABSTRACT FROM AUTHOR]

Abstract A locally connected spanning tree (LCST) T of a graph G is a spanning tree of G such that, for each node, its neighborhood in T induces a connected subgraph in G. The problem of determining whether a graph contains an LCST or not has been proved to be NP-complete, even if the graph is planar or chordal. The main result of this paper is a simple linear time algorithm that, given a maximal planar chordal graph, determines in linear time whether it contains an LCST or not, and produces one if it exists. We give an analogous result for the case when the input graph is a maximal outerplanar graph. [ABSTRACT FROM AUTHOR]

Abstract Since the 80s, model checking (MC) has been applied to the automatic verification of hardware/software systems. Point-based temporal logics, such as LTL , CTL , CTL ⁎ , and the like, are commonly used in MC as the specification language; however, there are some inherently interval-based properties of computations, e.g., temporal aggregations and durations, that cannot be properly dealt with by these logics, as they model a state-by-state evolution of systems. Recently, an MC framework for the verification of interval-based properties of computations, based on Halpern and Shoham's interval temporal logic (HS , for short) and its fragments, has been proposed and systematically investigated. In this paper, we focus on the boundaries that separate tractable and intractable HS fragments in MC. We first prove that MC for the logic BE of Allen's relations started-by and finished-by is provably intractable, being Expspace -hard. Such a lower bound immediately propagates to full HS. Then, in contrast, we show that other noteworthy HS fragments, i.e., the logic A A ‾ B B ‾ (resp., A A ‾ E E ‾) of Allen's relations meets , met-by , starts (resp., finishes), and started-by (resp., finished-by), are well-behaved, and turn out to have the same complexity as LTL (Pspace -complete). Halfway are the fragments A A ‾ B B ‾ E ‾ and A A ‾ E B ‾ E ‾ , whose Expspace membership and Pspace hardness are already known. Here, we give an original proof of Expspace membership, that substantially simplifies the complexity of the constructions previously used for such a result. Contraction techniques—suitably tailored to each HS fragment—are at the heart of our results, enabling us to prove a pair of remarkable small-model properties. [ABSTRACT FROM AUTHOR]

Abstract: Faugère’s algorithm is one of the fastest algorithms to compute Gröbner bases. It uses two criteria namely the criterion and the IsRewritten criterion to detect the useless critical pairs (see Faugère (2002) ). The IsRewritten criterion has been used in the algorithm, but it has not been explicitly declared in the related paper. In this paper, we give first a complete proof for the IsRewritten criterion and then using a signature structure on Buchberger’s algorithm, we apply this criterion on Buchberger’s algorithm. We have implemented a new algorithm (based on the above results) in Maple to compute a Gröbner basis of a general ideal and we evaluate its performance via some examples. [Copyright &y& Elsevier]

Abstract: Self-stabilizing distributed control is often modeled by token abstractions. A system with a single token may implement mutual exclusion; a system with multiple tokens may ensure that immediate neighbors do not simultaneously enjoy a privilege. In models of process control, tokens may represent physical objects whose movement is controlled. The problem studied in this paper is to ensure that a synchronous system with circulating tokens has at least distance between tokens. This problem is first considered in a ring where is given whilst and the ring size are unknown. The protocol solving this problem can be uniform, with all processes running the same program, or it can be non-uniform, with some processes acting only as token relays. The protocol for this first problem is simple, and can be expressed with a Petri net formalism. A second problem is to maximize when is given, and is unknown. For the second problem, this paper presents a non-uniform protocol with a single corrective process. [Copyright &y& Elsevier]

Abstract: In this paper we study the protein structure comparison problem where each protein is modeled as a sequence of 3D points, and a contact edge is placed between every two of these points that are sufficiently close. Given two proteins represented this way, our problem is to find a subset of points from each protein, and a bijective matching of points between these two subsets, with the objective of maximizing either (A) the size of the subsets (the LCP problem), or (B) the number of edges that exist simultaneously in both subsets (the CMO problem), under the requirement that only points within a specified proximity can be matched. It is known that the general CMO problem (without the proximity requirement) is hard to approximate. However, with the proximity requirement, it is known that if a minimum inter-residue distance is imposed on the input, approximate solutions can be efficiently obtained. In this paper we mainly show that the CMO problem under these conditions: (1) is NP-hard, but (2) allows a PTAS. The rest of this paper shows algorithms for the LCP problem which improve on known results. [Copyright &y& Elsevier]

Abstract: This paper is the first part of a series of two papers dealing with bulking: a quasi-order on cellular automata comparing space–time diagrams up to some rescaling. Bulking is a generalization of grouping taking into account universality phenomena, giving rise to a maximal equivalence class. In the present paper, we discuss the proper components of grouping and study the most general extensions. We identify the most general space–time transforms and give an axiomatization of bulking quasi-order. Finally, we study some properties of intrinsically universal cellular automata obtained by comparing grouping to bulking. [Copyright &y& Elsevier]

Abstract: This paper is the second part of a series of two papers dealing with bulking: a way to define quasi-order on cellular automata by comparing space-time diagrams up to rescaling. In the present paper, we introduce three notions of simulation between cellular automata and study the quasi-order structures induced by these simulation relations on the whole set of cellular automata. Various aspects of these quasi-orders are considered (induced equivalence relations, maximum elements, induced orders, etc.) providing several formal tools allowing to classify cellular automata. [Copyright &y& Elsevier]

Abstract: This paper studies directional dynamics on one-dimensional cellular automata, a formalism previously introduced by the third author. The central idea is to study the dynamical behavior of a cellular automaton through the conjoint action of its global rule (temporal action) and the shift map (spacial action): qualitative behaviors inherited from topological dynamics (equicontinuity, sensitivity, expansivity) are thus considered along arbitrary curves in space–time. The main contributions of the paper concern equicontinuous dynamics which can be connected to the notion of consequences of a word. We show that there is a cellular automaton with an equicontinuous dynamics along a parabola, but which is sensitive along any linear direction. We also show that real numbers that occur as the slope of a limit linear direction with equicontinuous dynamics in some cellular automaton are exactly the computably enumerable numbers. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . A subset is a mixed dominating set if every element is either adjacent or incident to an element of . The mixed domination problem is to find a minimum mixed dominating set of . In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs. [Copyright &y& Elsevier]

Abstract: The independent spanning trees (ISTs) problem attempts to construct a set of pairwise independent spanning trees and it has numerous applications in networks such as data broadcasting, scattering and reliable communication protocols. The well-known ISTs conjecture, Vertex/Edge Conjecture, states that any -connected/-edge-connected graph has vertex-ISTs/edge-ISTs rooted at an arbitrary vertex . It has been shown that the Vertex Conjecture implies the Edge Conjecture. In this paper, we consider the independent spanning trees problem on the -dimensional locally twisted cube . The very recent algorithm proposed by Hsieh and Tu (2009) is designed to construct edge-ISTs rooted at vertex 0 for . However, we find out that is not vertex-transitive when ; therefore Hsieh and Tu’s result does not solve the Edge Conjecture for . In this paper, we propose an algorithm for constructing vertex-ISTs for ; consequently, we confirm the Vertex Conjecture (and hence also the Edge Conjecture) for . [Copyright &y& Elsevier]

Abstract: In the past, research on multiple criteria scheduling assumes that the number of available machines is fixed during the whole scheduling horizon and research on scheduling with limited machine availability assumes that there is only a single criterion that needs to be optimized. Both assumptions may not hold in real life. In this paper we simultaneously consider both bicriteria scheduling and scheduling with limited machine availability. We focus on two parallel machines’ environment and the goal is to find preemptive schedules to optimize both makespan and total completion time subject to machine availability. Our main contribution in this paper is that we showed three bicriteria scheduling problems are in P by providing polynomial time optimal algorithms. [Copyright &y& Elsevier]

Abstract: The paper 1 [1] Supported by Engineering and Physical Sciences Research Council (EPSRC), U.K., grant EP/F014406/1. develops a technique for computation inference rules admissible in temporal logic . The problem whether there exists an algorithm recognizing inference rules admissible in is a long-standing open problem. The logic has neither the extension property nor the co-cover property which previously were central instruments for construction decision algorithms for admissibility in modal logics (e.g. reflexive and transitive modal logic ). Our paper uses a linear-compression property, a zigzag-ray property and a zigzag stretching property which hold for . The main result of the paper is a sufficient condition for admissibility inference rules in . It is shown that all rules which are valid in special finite models (with an effective upper bound on size) must be admissible in . [Copyright &y& Elsevier]

Abstract: This paper investigates the criteria for deciding whether two words are matrix equivalent. Certain upper diagonal matrices, generally referred to as the Parikh matrices, have been widely investigated because of their usefulness in computing the numbers of subword occurrences and thereby characterizing words by numbers. However, apart from the binary alphabet, not much is known about the properties of the matrix equivalent words, that is, words possessing the same matrix. The paper investigates both the general criteria, as well as the criteria valid in natural special cases. An exhaustive solution is obtained for ternary alphabets. [Copyright &y& Elsevier]

Abstract: This paper considers gossiping among mobile agents in graphs: agents move on the graph and have to disseminate their initial information to every other agent. We focus on self-stabilizing solutions for the gossip problem, where agents may start from arbitrary locations in arbitrary states. Self-stabilization requires (some of the) participating agents to keep moving forever, hinting at maximizing the number of agents that could be allowed to stop moving eventually. This paper formalizes the self-stabilizing agent gossip problem, introduces the quiescence number (i.e., the maximum number of eventually stopping agents) of self-stabilizing solutions and investigates the quiescence number with respect to several assumptions related to agent anonymity, synchrony, link duplex capacity, and whiteboard capacity. [Copyright &y& Elsevier]

Abstract: Automata theory provides two ways of defining an automaton: either by its transition system, defining its states and events, or by its language, the set of sequences (traces) of events in which it can engage. For many classes of automaton, these forms of definition have been proved equivalent. For example, there is a well-known isomorphism between regular languages and finite deterministic automata. This paper suggests that for (demonically) the non-deterministic automata (as treated in process algebra), the appropriate link between transition systems and languages may be a retraction rather than an isomorphism. A pair of automata, defined in the tradition of CCS by their transition systems, may be compared by a pre-ordering based on some kind of simulation or bisimulation, for example, weak, strong, or barbed. Automata defined in the tradition of CSP are naturally ordered by set inclusion of their languages (often called refinement); variations in ordering arise from different choices of basic event, including for example, refusals and divergences. In both cases, we characterise a theory by its underlying transition system and its choice of ordering. Our treatment is therefore wholly semantic, independent of the syntax and definition of operators of the calculus. We put forward a series of retractions relating the above-mentioned versions of CSP to their corresponding CCS transition models. A retraction is an injection that is (with respect to the chosen ordering) monotonic, increasing and idempotent (up to equivalence). It maps the nodes of a transition system of its source theory to those of a system that has been saturated by additional transitions. Each retraction will be defined by a transition rule, in the style of operational semantics; the proofs use the familiar technique of co-induction, often abbreviated by encoding in the relational calculus. The aim of this paper is to contribute to unification of theories of reactive system programming. More practical benefits may follow. For example, we justify a method to improve the efficiency of model checking based on simulation. Furthermore, we show how model checking of a transition network fits consistently with theorem-proving tools, which reason directly about specifications and designs that are expressed in terms of sets of sequences of observable events. [Copyright &y& Elsevier]