Search

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]

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]

Abstract: Upward-closed sets of integer vectors enjoy the merit of having a finite number of minimal elements, which is behind the decidability of a number of Petri net related problems. In general, however, such a finite set of minimal elements may not be effectively computable. In this paper, we develop a unified strategy for computing the sizes of the minimal elements of certain upward-closed sets associated with Petri nets. Our approach can be regarded as a refinement of a previous work by Valk and Jantzen (in which a necessary and sufficient condition for effective computability of the set was given), in the sense that complexity bounds now become available provided that a bound can be placed on the size of a witness for a key query. The sizes of several upward-closed sets that arise in the theory of Petri nets as well as in backward-reachability analysis in automated verification are derived in this paper, improving upon previous decidability results shown in the literature. [Copyright &y& Elsevier]

Abstract: The 2-interval pattern problem, introduced in [Stéphane Vialette, On the computational complexity of 2-interval pattern matching problems Theoret. Comput. Sci. 312 (2–3) (2004) 223–249], models general problems with biological structures such as protein contact maps and macroscopic describers of secondary structures of ribonucleic acids. Given a set of 2-intervals and a model , the problem is to find a maximum cardinality subset of such that any two 2-intervals in satisfy , where is a subset of relations on disjoint 2-intervals: precedence , nest , and cross . The problem left unanswered at present is that of whether there is a polynomial time solution for the 2-interval pattern problem, when and all the support intervals of are disjoint. In this paper, we present a reduction from the clique problem to show that, in this case, the problem is NP-hard. The disjoint 2-interval pattern matching problem is to decide whether a disjoint 2-interval pattern (called the pattern) is a substructure of another disjoint 2-interval pattern (called the target). In general, the problem is NP-hard, but when there are restrictions on the form of the pattern, the problem can, in some cases, be solved in polynomial time. In particular, a polynomial time algorithm has been proposed (Gramm, WABI 2004 and IEEE/ACM TCBB 2004) for the case where the patterns are so-called crossing contact maps. In this paper we show that the problem is actually NP-hard and point out an error in the analysis of the above algorithm. 1 [1] The second part of this paper appeared in WABI’2006. [Copyright &y& Elsevier]

Abstract: This paper is intended more to ask questions than give answers. Specifically, we consider models for labeling schemes, and discuss issues regarding the number of labels consulted vs. the sizes of the labels. Recently, quite a few papers studied methods for representing network properties by assigning informative labels to the vertices of a network. Consider a graph function on pairs of vertices (for example, can be the distance function). In an -labeling scheme, the labels are constructed in such a way so that given the labels of any two vertices and , one can compute the function (e.g. the graph distance between and ) just by looking at these two labels. Some very involved lower bounds for the sizes of the labels were proven. Also, some highly sophisticated labeling schemes were developed to ensure short labels. In this paper, we demonstrate that such lower bounds are very sensitive to the number of vertices consulted. That is, we show several constructions of such labeling schemes that beat the lower bounds by large margins. Moreover, as opposed to the strong technical skills that were needed to develop the traditional labeling schemes, most of our schemes are almost trivial. The catch is that in our model, one needs to consult the labels of three vertices instead of two. That is, a query about vertices and can access also the label of some third vertex ( is determined by the labels of and ). More generally, we address the model in which a query about vertices and can access also the labels of other vertices. We term our generalized model labeling schemes with queries. The main importance of this model is theoretical. Specifically, this paper may serve as a first step towards investigating different tradeoffs between the amount of labels consulted and the amount of information stored at each vertex. As we show, if all vertices can be consulted then the problem almost reduces to the corresponding sequential problem. On the other hand, consulting just the labels of and (or even just the label of ) reduces the problem to a purely distributed one. Therefore, in a sense, our model spans a range of intermediate notions between the sequential and the distributed settings. In addition to the theoretical interest, we also show cases that schemes constructed for our model can be translated to the traditional model or to the sequential model, thus, simplifying the construction for those models as well. For implementing query labeling schemes in a distributed environment directly, we point at a potential usage for some new paradigms that became common recently, such as P2P and overlay networks. [Copyright &y& Elsevier]

Abstract: In this paper, we show that it can be tested in polynomial time as to whether a scenario is an execution of a Petri net. This holds for a wide variety of Petri net classes, ranging from elementary nets to general inhibitor nets. Scenarios are given by causal structures expressing causal dependencies and concurrency among events. In the case of elementary nets and of place/transition nets, such causal structures are partial orders among transition occurrences. For several extended Petri net classes, the extension of partial orders to stratified order structures is considered. The algorithms are based on the representation of the non-sequential behavior of Petri nets by so-called token flow functions and a characterization of Petri net executions called token flow property. This property allows nontrivial transformations into flow optimization problems, which can be solved in polynomial time. The paper is a revised, consolidated and extended version of the conference papers [G. Juhás, R. Lorenz, J. Desel, Can I execute my scenario in your net?, in: G. Ciardo, P. Darondeau (Eds.), ICATPN, in: Lecture Notes in Computer Science, Springer, 2005, pp. 289–308; R. Lorenz, S. Mauser, R. Bergenthum, Testing the Executability of Scenarios in General Inhibitor Nets, in: ACSD, IEEE Computer Society, 2007, pp. 167–176] and includes parts of the habilitation thesis [R. Lorenz, Szenario-basierte Verifikation und Synthese von Perinetzen: Theorie und Anwendungen, Habilitation, 2006]. [Copyright &y& Elsevier]

Abstract: The -median problem on a tree is to find a set of vertices on that minimizes the sum of distances from ’s vertices to . In this paper, we study two generalizations of the 2-median problem, which are obtained by imposing constraints on the two vertices selected as a 2-median: one is to limit their distance while the other is to limit their eccentricity. Previously, both the best upper bounds of these two generalizations were [A. Tamir, D. Perez-Brito, J.A. Moreno-Perez, A polynomial algorithm for the -centdian problem on a tree, Networks 32 (1998) 255–262; B.-F. Wang, S.-C. Ku, K.-H. Shi, Cost-optimal parallel algorithms for the tree bisector problem and applications, IEEE Transactions on Parallel and Distributed Systems 12 (9) (2001) 888–898]. In this paper, we solve both in time. We also study cases when linear time algorithms exist for the two generalizations. For example, we solve both in linear time when edge lengths and vertex weights are all polynomially bounded integers. Furthermore, we consider the relaxation of the two generalized problems by allowing 2-medians on any position of edges, instead of just on vertices, and we give -time algorithms for them. A problem, named the tree marker problem, arises several times in our approaches to the two generalized 2-median problems, and we give an -time algorithm for this problem. We also use this algorithm to speedup an algorithm of Gupta and Punnen [S.K. Gupta, A.P. Punnen, Group center and group median of a tree, European Journal of Operational Research 65 (1993) 400–406] for the group median problem, improving the running time from to , where is the number of groups in the input. [Copyright &y& Elsevier]

Abstract: The purpose of this paper is to show how the rewriting-logic-based Real-Time Maude language and tool can be used to formally model, simulate, and model check advanced wireless sensor network (WSN) algorithms. This is done by first proposing some general techniques for modeling and analyzing WSN algorithms, and then by showing how these techniques have been applied to the modeling, performance estimation, and model checking of the state-of-the-art optimal geographical density control (OGDC) density control algorithm. Wireless sensor networks in general, and the OGDC algorithm in particular, pose many challenges to their formal specification and analysis, including novel communication forms, spatial entities, time-dependent and probabilistic features, and the need to analyze both correctness and performance. We focus on Monte Carlo simulations to evaluate the performance of OGDC. Extensive simulations with up to 800 sensor nodes, and comparison with the ns-2 simulations of OGDC, indicate that Real-Time Maude simulations provide fairly accurate performance estimates of WSN algorithms. As a consequence, simulating the high-level Real-Time Maude model of a WSN algorithm eliminates the need for implementing it on a simulation tool to get a faithful estimate of its performance, while providing much greater flexibility in defining the appropriate simulation scenario; in addition, Real-Time Maude model checking can search for “corner case” bugs and evaluate best-case and worst-case performance. Some of the techniques presented in this paper are also used in an ongoing analysis effort of another state-of-the-art WSN algorithm. [Copyright &y& Elsevier]

Abstract: In this paper a proof outline logic is introduced for the partial correctness of multi-threaded object-oriented programs like in Java. The main contribution is a generalization of the Owicki& Gries proof method for shared-variable concurrency to dynamic thread creation. This paper also provides a formal justification of this generalization in terms of soundness and completeness proofs. [Copyright &y& Elsevier]

Abstract: The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. Möbius cubes form a class of hypercube variants that give better performance with the same number of edges and vertices. In this paper, we consider embedding of meshes in Möbius cubes. The main results obtained in this paper are: (1) For , there exists a mesh that can be embedded in the -dimensional Möbius cube with dilation 1 and expansion 1. (2) For , there exists a mesh that can be embedded in the -dimensional Möbius cube with dilation 2 and expansion 1. (3) For , there are two disjoint meshes that can be embedded in the 0-type -dimensional Möbius cube with dilation 1. (4) For , there are two disjoint meshes that can be embedded in the 1-type -dimensional Möbius cube with dilation 2. Results of (1) and (3) are optimal in the sense that the dilations of the embeddings are 1. [Copyright &y& Elsevier]

Abstract: We study a generalized version of reversal bounded Turing machines where, apart from several tapes on which the number of head reversals is bounded by , there are several further tapes on which head reversals remain unrestricted, but size is bounded by (where denotes the input length). Recently [M. Grohe, C. Koch, N. Schweikardt, Tight lower bounds for query processing on streaming and external memory data, Theoretical Computer Science 380 (1–2) (2007) 199–217; M. Grohe, N. Schweikardt, Lower bounds for sorting with few random accesses to external memory, in: Proc. PODS’05, ACM Press, 2005, pp. 238–249], such machines were introduced as a formalization of a computation model that restricts random access to external memory and internal memory space. Here, each of the tapes with a restriction on the head reversals corresponds to an external memory device, and the tapes of restricted size model internal memory. We use to denote the class of all problems that can be solved by deterministic Turing machines that comply to the above resource bounds. Similarly, and , respectively, are used for the corresponding nondeterministic and randomized classes. While previous papers focused on lower bounds for particular problems, including sorting, the set equality problem, and several query evaluation problems, the present paper addresses the relations between the -classes and classical complexity classes and investigates the structural complexity of the -classes. Our main results are (1) a trade-off between internal memory space and external memory head reversals, (2) correspondences between the classes and “classical” time-bounded, space-bounded, reversal-bounded, and circuit complexity classes, and (3) hierarchies of -classes in terms of increasing numbers of head reversals on external memory tapes. [Copyright &y& Elsevier]

Abstract: Rabi and Sherman [M. Rabi, A. Sherman, An observation on associative one-way functions in complexity theory, Information Processing Letters 64 (5) (1997) 239–244; M. Rabi, A. Sherman, Associative one-way functions: A new paradigm for secret-key agreement and digital signatures, Tech. Rep. CS-TR-3183/UMIACS-TR-93-124, Department of Computer Science, University of Maryland, College Park, MD, 1993] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i.e., p-time computable, honest, p-time noninvertible functions; this paper is in the worst-case model, not the average-case model) that are total, commutative, and associative but not strongly noninvertible. In this paper we improve the sufficient condition to . More generally, in this paper we completely characterize which types of one-way functions stand or fall together with (plain) one-way functions—equivalently, stand or fall together with . We look at the four attributes used in Rabi and Sherman’s seminal work on algebraic properties of one-way functions (see [M. Rabi, A. Sherman, An observation on associative one-way functions in complexity theory, Information Processing Letters 64 (5) (1997) 239–244; M. Rabi, A. Sherman, Associative one-way functions: A new paradigm for secret-key agreement and digital signatures, Tech. Rep. CS-TR-3183/UMIACS-TR-93-124, Department of Computer Science, University of Maryland, College Park, MD, 1993]) and subsequent papers–strongness (of noninvertibility), totality, commutativity, and associativity–and for each attribute, we allow it to be required to hold, required to fail, or “don’t care”. In this categorization there are potential types of one-way functions. We prove that each of these 81 feature-laden types stands or falls together with the existence of (plain) one-way functions. [Copyright &y& Elsevier]

Abstract: This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, proves its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes a possible algorithm for the two-dimensional case and presents partial simulation results of its effectiveness. [Copyright &y& Elsevier]