Search

Abstract: In this short note we point to an error in the proof of a theorem stated in [L. Balková, E. Pelantová, Š. Starosta, On Brlek-Reutenauer conjecture, Theoret. Comput. Sci. 412 (2011) 5649–5655]. By constructing a counterexample, we show that the assertion of the theorem is actually incorrect. Although this theorem is of a technical character, it was used in an argument leading to a corollary of a general interest to the Brlek-Reutenauer conjecture, and thus as a consequence of this note we have that the proof of the mentioned corollary is also flawed. [Copyright &y& Elsevier]

Abstract: We recall some bibliography on fast polynomial multiplication related to the recent progress in the paper by Cenk and Ozbudak of 2011. [Copyright &y& Elsevier]

One of the fundamental open questions in computational complexity is whether the class of problems solvable by use of stochasticity under the Random Polynomial time (RP) model is larger than the class of those solvable in deterministic polynomial time (P). However, this question is only open for Turing machines, not for Random Access Machines (RAMs). Simon (1981) [31] was able to show that for a sufficiently equipped Random Access Machine, the ability to switch states nondeterministically entails no computational advantage. On the other hand, in the same paper, Simon describes a different (and arguably more natural) model for RAM stochasticity. According to Simon's proposal, instead of receiving a new random bit at each execution step, the RAM program is able to execute the pseudofunction RAND ( y ) , which returns a uniformly distributed random integer in the range [ 0 , y ) . Whether the ability to allot a random integer in this fashion is more powerful than the ability to allot a random bit remained an open question for the last 30 years. In this paper, we close Simon's open problem by fully characterising the class of languages recognisable in polynomial time by each of the RAMs regarding which the question was posed. We show that for some of these stochasticity does not entail any advantage, but, more interestingly, we show that for others it does. These results carry over also to BPP-like and coRP-like acceptance criteria. [ABSTRACT FROM AUTHOR]

While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat, that is, the unnecessary growth of solution lengths, which may slow down the optimization process. So far, the mathematical runtime analysis could not deal well with bloat and required explicit assumptions limiting bloat. In this paper, we provide the first mathematical runtime analysis of a GP algorithm that does not require any assumptions on the bloat. Previous performance guarantees were only proven conditionally for runs in which no strong bloat occurs. Together with improved analyses for the case with bloat restrictions our results show that such assumptions on the bloat are not necessary and that the algorithm is efficient without explicit bloat control mechanism. More specifically, we analyzed the performance of the (1 + 1) GP on the two benchmark functions Order and Majority. When using lexicographic parsimony pressure as bloat control, we show a tight runtime estimate of O (T init + n log ⁡ n) iterations both for Order and Majority. For the case without bloat control, the bounds O (T init log ⁡ T init + n (log ⁡ n) 3) and Ω (T init + n log ⁡ n) (and Ω (T init log ⁡ T init) for n = 1) hold for Majority. 1 [ABSTRACT FROM AUTHOR]

This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg ⁡ n − 1.4427 n + O (log ⁡ n). For many efficient algorithms, the first n lg ⁡ n term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is −1.3999 for the MergeInsertion sort. Our new value is −1.4106, narrowing the gap by some 25%. An important building block of our algorithm is "two-element insertion," which inserts two elements A and B , A < B , into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach together with the binary insertion. [ABSTRACT FROM AUTHOR]

There is a very short and beautiful proof that the number of distinct non-empty palindromes in a word of length n is at most n . In this paper we show, with a very complicated proof, that the number of distinct non-empty palindromes with length at most n in a circular word of length n is less than 5 n / 3 . For n divisible by 3 we present circular words of length n containing 5 n / 3 − 2 distinct palindromes, so the bound is almost sharp. The paper finishes with some open problems. [ABSTRACT FROM AUTHOR]

Abstract: A vertex-colored graph is rainbow vertex-connected if any pair of vertices in are connected by a path whose internal vertices have distinct colors, which was introduced by Krivelevich and Yuster. The rainbow vertex-connection number of a connected graph , denoted by , is the smallest number of colors that are needed in order to make rainbow vertex-connected. In a previous paper we showed that it is NP-Complete to decide whether a given graph has . In this paper we show that for every integer , deciding whether is NP-Hard. We also show that for any fixed integer , this problem belongs to NP-class, and so it becomes NP-Complete. [Copyright &y& Elsevier]

Abstract: In their paper on the “chasm at depth four”, Agrawal and Vinay have shown that polynomials in variables of degree which admit arithmetic circuits of size also admit arithmetic circuits of depth four and size . This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case. In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of matrices has circuits of size polynomial in , then it also has depth 4 circuits of size . If the original circuit uses only integer constants of polynomial size, then the same is true for the resulting depth four circuit. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also use our techniques to reprove two results on: [–] the existence of nontrivial boolean circuits of constant depth for languages in ; [–] reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree. [Copyright &y& Elsevier]

Abstract: The aim of a Software Transactional Memory (STM) is to discharge the programmers from the management of synchronization in multiprocess programs that access concurrent objects. To that end, an STM system provides the programmer with the concept of a transaction. The job of the programmer is to design each process the application is made up of as a sequence of transactions. A transaction is a piece of code that accesses concurrent objects, but contains no explicit synchronization statement. It is the job of the underlying STM system to provide the illusion that each transaction appears as being executed atomically. Of course, for efficiency, an STM system has to allow transactions to execute concurrently. Consequently, due to the underlying STM concurrency management, a transaction commits or aborts. This paper first presents a new STM consistency condition, called virtual world consistency. This condition states that no transaction reads object values from an inconsistent global state. It is similar to opacity for the committed transactions but weaker for the aborted transactions. More precisely, it states that (1) the committed transactions can be totally ordered, and (2) the values read by each aborted transaction are consistent with respect to its causal past. Hence, virtual world consistency is weaker than opacity while keeping its spirit. Then, assuming the objects shared by the processes are atomic read/write objects, the paper presents an STM protocol that ensures virtual world consistency (while guaranteeing the invisibility of the read operations). From an operational point of view, this protocol is based on a vector-clock mechanism. Finally, the paper considers the case where the shared objects are regular read/write objects. It also shows how the protocol can easily be weakened while still providing an STM system that satisfies causal consistency, a condition strictly weaker than virtual world consistency. [Copyright &y& Elsevier]

Abstract The interconnection networks are generally modeled by a connected graph G , and the connectivity of G is an important parameter for reliability and fault tolerance of the network. A connected graph G = (V , E) is maximally edge-connected (or maximally- λ for short) if its edge-connectivity attains its minimum degree. We define a maximally- λ graph G to be m -maximally- λ if G − S is still maximally- λ for any edge subset S ⊆ E (G) with | S | ≤ m. The maximum integer of such m , denoted by m λ (G) , is said to be the edge fault tolerance of G with respect to the maximally- λ property. In this paper, we discuss the edge fault tolerance for maximally- λ property of two families of interconnection networks, from which we determine the exact values of m λ (G) for some well-known networks. [ABSTRACT FROM AUTHOR]

Abstract: The maximum weight matching problem is a fundamental problem in graph theory with a variety of important applications. Recently Manne and Mjelde presented the first self-stabilizing algorithm computing a -approximation of the optimal solution. They established that their algorithm stabilizes after (resp. ) moves under a central (resp. distributed) scheduler. This paper contributes a new analysis, improving these bounds considerably. In particular it is shown that the algorithm stabilizes after moves under the central scheduler and that a modified version of the algorithm also stabilizes after moves under the distributed scheduler. The paper presents a new proof technique based on graph reduction for analyzing the complexity of self-stabilizing algorithms. [Copyright &y& Elsevier]

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 A 2-partition of a digraph D is a partition (V 1 , V 2) of V (D) into two disjoint non-empty sets V 1 and V 2 such that V 1 ∪ V 2 = V (D). A semicomplete digraph is a digraph with no pair of non-adjacent vertices. We consider the complexity of deciding whether a given semicomplete digraph has a 2-partition such that each part of the partition induces a (semicomplete) digraph with some specified property. In [4] and [5] Bang-Jensen, Cohen and Havet determined the complexity of 120 such 2-partition problems for general digraphs. Several of these problems are NP-complete for general digraphs and thus it is natural to ask whether this is still the case for well-structured classes of digraphs, such as semicomplete digraphs. This is the main topic of the paper. More specifically, we consider 2-partition problems where the set of properties are minimum out-, minimum in- or minimum semi-degree. Among other results we prove the following: • For all integers k 1 , k 2 ≥ 1 and k 1 + k 2 ≥ 3 it is NP-complete to decide whether a given digraph D has a 2-partition (V 1 , V 2) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2. • For every fixed choice of integers α , k 1 , k 2 ≥ 1 there exists a polynomial algorithm for deciding whether a given digraph of independence number at most α has a 2-partition (V 1 , V 2) such that D 〈 V i 〉 has out-degree at least k i for i = 1 , 2. • For every fixed integer k ≥ 1 there exists a polynomial algorithm for deciding whether a given semicomplete digraph has a 2-partition (V 1 , V 2) such that D 〈 V 1 〉 has out-degree at least one and D 〈 V 2 〉 has in-degree at least k. • It is NP-complete to decide whether a given semicomplete digraph D has a 2-partition (V 1 , V 2) such that D 〈 V i 〉 is a strong tournament. [ABSTRACT FROM AUTHOR]

Abstract This paper introduces a new variant of the game Nim–Bounded Greedy Nim. This game is a combination of Bounded Nim and Greedy Nim. We present a complete solution to this game, which generalizes the solution of Greedy Nim. [ABSTRACT FROM AUTHOR]

Abstract: Cellular automata are often used to model systems in physics, social sciences, biology that are inherently asynchronous. Over the past 20 years, studies have demonstrated that the behavior of cellular automata drastically changes under asynchronous updates. Still, the few mathematical analyses of asynchronism focus on 1D probabilistic cellular automata, either on single examples or on specific classes. As for other classic dynamical systems in physics, extending known methods from 1D to 2D systems is a long lasting challenging problem. In this paper, we address the problem of analyzing an apparently simple 2D asynchronous cellular automaton: 2D Minority where each cell, when fired, updates to the minority state of its neighborhood. Our simulations reveal that in spite of its simplicity, the minority rule exhibits a quite complex response to asynchronism. By focusing on the fully asynchronous regime, we are however able to describe completely the asymptotic behavior of this dynamics as long as the initial configuration satisfies some natural constraints. Besides these technical results, we have strong reasons to believe that our techniques relying on defining an energy function from the transition table of the automaton may be extended to the wider class of threshold automata. 2 [2] An abstract version of this paper has been published in [D. Regnault, N. Schabanel, É. Thierry, Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority, in: LNCS Proc. of 32nd Symp. of Mathematical Foundations of Computer Science, MFCS, vol. 4708, Springer, 2007, pp. 320–332]. [Copyright &y& Elsevier]

Abstract: Set multi-covering is a generalization of the set covering problem where each element may need to be covered more than once and thus some subset in the given family of subsets may be picked several times for minimizing the number of sets to satisfy the coverage requirement. In this paper, we propose a family of exact algorithms for the set multi-covering problem based on the inclusion–exclusion principle. The presented ESMC (Exact Set Multi-Covering) algorithm takes time and space where is the maximum value in the coverage requirement set (The notation omits a factor). We also propose the other three exact algorithms through different tradeoffs of the time and space complexities. To the best of our knowledge, this present paper is the first one to give exact algorithms for the set multi-covering problem with nontrivial time and space complexities. This paper can also be regarded as a generalization of the exact algorithm for the set covering problem given in [A. Björklund, T. Husfeldt, M. Koivisto, Set partitioning via inclusion–exclusion, SIAM Journal on Computing, in: FOCS 2006 (in press, special issue)]. [Copyright &y& Elsevier]

Abstract: This work studies comparator networks in which several of the outputs are accelerated. That is, they are generated much faster than the other outputs, and this without hindering the other outputs. We study this acceleration in the context of merging networks and sorting networks. The paper presents a new merging technique, the Tri-section technique, that separates, using a depth 1 network, two sorted sequences into three sets, such that every key in one set is smaller than or equal to any key in the following set. After this separation, each of these sets can be sorted separately, causing the above acceleration of certain outputs. An additional contribution of this paper concerns the well-known – Principle [D.E. Knuth, The Art of Computer Programming vol. 3: Sorting and Searching, second edition, Addison-Wesley, 1998]. This principle is a powerful tool that simplifies the construction and analysis of comparator networks. The paper demonstrates that, in some cases, there is a better tool for achieving the same goal. In the case at hand, this new tool simplifies one of our proofs by having fewer special cases than the classical – Principle. A second additional contribution concerns Batcher’s merging techniques. It was shown in [T. Levy, A. Litman, On Merging Networks, Technical Report CS-2007-16, Technion, Department of Computer Science, 2007] that all published merging networks, whose width is a power of 2, are a natural generalization of Batcher’s odd–even merging network. All these published merging networks are of minimal depth and have no degenerate comparators. This raises the following question. Is there a merging network, having the above properties, that is not a natural generalization of Batcher’s odd–even merging network? The Tri-section technique provides a positive answer to this question. [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: 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 paper describes and analyzes a method for computing border bases of a zero-dimensional ideal . The criterion used in the computation involves specific commutation polynomials, and leads to an algorithm and an implementation extending the ones in [B. Mourrain, Ph. Trébuchet, Generalised normal forms and polynomial system solving, in: M. Kauers (Ed.), Proc. Intern. Symp. on Symbolic and Algebraic Computation, ACM Press, New-York, 2005, pp. 253–260]. This general border basis algorithm weakens the monomial ordering requirement for Gröbner bases computations. It is currently the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and a new representation that does not fit into the previous categories. With this formalism, we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This feature has a huge impact on practical efficiency, as illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper. [Copyright &y& Elsevier]

Abstract: Intersection types are well known to type theorists mainly for two reasons. Firstly, they type all and only the strongly normalizable lambda terms. Secondly, the intersection type operator is a meta-level operator, that is, there is no direct logical counterpart in the Curry–Howard isomorphism sense. In particular, its meta-level nature implies that it does not correspond to the intuitionistic conjunction. The intersection type system is naturally a type inference system (system à la Curry), but the meta-level nature of the intersection operator does not allow to easily design an equivalent typed system (system à la Church). There are many proposals in the literature to design such systems, but none of them gives an entirely satisfactory answer to the problem. In this paper, we will review the main results in the literature both on the logical interpretation of intersection types and on proposed typed lambda calculi. The core of this paper is a new proposal for a true intersection typed lambda calculus, without any meta-level notion. Namely, any typable term (in the intersection type inference) has a corresponding typed term (which is the same as the untyped term by erasing the type decorations and the typed term constructors) with the same type, and vice versa. The main idea is to introduce a relevant parallel term constructor which corresponds to the intersection type constructor, in such a way that terms in parallel share the same resources, that is, the same context of free typed variables. Three rules allow us to generate all typed terms. The first two rules, Application and Lambda-abstraction, are performed on all the components of a parallel term in a synchronized way. Finally, via the third rule of Local Renaming, once a free typed variable is bounded by lambda-abstraction, each of the terms in parallel can do its local renaming, with type refinement, of that particular resource. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to make a contribution to (compositional) development methods for concurrent programs. In particular, it takes a fresh look at a number of familiar ideas including the problem of interference. Some subtle issues of observability–including granularity–are explored. Based on these points, the paper sets out some requirements for an approach to developing systems by “splitting atoms safely”. [Copyright &y& Elsevier]

Abstract: In this paper we provide a simple characterization of (weak) fairness of components as defined by Costa and Stirling in [Weak and strong fairness in CCS, Inform. and Comput. 73 (1987) 207–244]. The study is carried out at system specification level by resorting to a common process description language. This paper follows and exploits similar techniques as those developed in [F. Corradini, M.R. Di Berardini, W. Vogler, Relating fairness and timing in process algebras, Proc. of Concur’03, Lecture Notes in Computer Science, Vol. 2761, Springer, Berlin, 2003, pp. 446–460]—where fairness of actions was taken into account and was contrasted to the PAFAS timed operational semantics—but the characterization of fair executions is based on a new semantics for PAFAS; it makes use of only two copies of each basic action instead of infinitely many as in [G. Costa, C. Stirling, Weak and strong fairness in CCS, Inform. and Comput. 73 (1987) 207–244] and allows for a simple and finite representation of fair executions by using regular expressions. The new semantics can also be understood as describing timed behaviour of systems with upper time bounds. The paper discusses in detail how this new semantics differs from the old one, and why theses changes are necessary to properly capture fairness of components. [Copyright &y& Elsevier]

Abstract: This paper presents a method for the decomposition of HML formulas. It can be used to decide whether a process algebra term satisfies a HML formula, by checking whether subterms satisfy certain formulas, obtained by decomposing the original formula. The method uses the structural operational semantics of the process algebra. The main contribution of this paper is the extension of an earlier decomposition method for the De Simone format from the Ph.D. thesis of Larsen in 1986, to more general formats. [Copyright &y& Elsevier]

Abstract: In this paper, we prove two general theorems on monotone Boolean functions which are useful for constructing a learning algorithm for monotone Boolean functions under the uniform distribution. A monotone Boolean function is called fair if it takes the value 1 on exactly half of its inputs. The first result proved in this paper is that a single variable function has the minimum correlation with the majority function among all fair monotone functions. This proves the conjecture by Blum et al. (1998, Proc. 39th FOCS, pp. 408–415) and improves the performance guarantee of the best known learning algorithm for monotone Boolean functions under the uniform distribution they proposed. Our second result is on the relationship between the influences and the average sensitivity of a monotone Boolean function. The influence of variable on f is defined as the probability that differs from where x is chosen uniformly from and means x with its ith bit flipped. The average sensitivity of f is defined as the sum of the influences over all variables . We prove that a somewhat unintuitive result which says if the influence of every variable on a monotone Boolean function is small, i.e., for some constant , then the average sensitivity of the function must be large, i.e., . We also discuss how to apply this result to the construction of a new learning algorithm for monotone Boolean functions. [Copyright &y& Elsevier]

Abstract: The strong Rabin number of a network of connectivity is the minimum so that for any nodes , of , there exist node-disjoint paths from to , respectively, whose maximal length is not greater than , where and are not necessarily distinct. In this paper, we show that the strong Rabin number of a -dimensional folded hypercube is , where is the diameter of the -dimensional folded hypercube. Each node-disjoint path we obtain has length not greater than the distance between the two end nodes plus two. This paper solves an open problem raised by Liaw and Chang. [Copyright &y& Elsevier]

Abstract: The centralizer of a set of words X is the largest set of words commuting with X: . It has been a long standing open question due to [J.H. Conway, Regular Algebra and Finite Machines, Chapman & Hall, London (1971).], whether the centralizer of any rational set is rational. While the answer turned out to be negative in general, see [M. Kunc, Proc. of ICALP 2004, Lecture Notes in Computer Science, Vol. 3142, Springer, Berlin, 2004, pp. 870–881.], we prove here that the situation is different for codes: the centralizer of any rational code is rational and if the code is finite, then the centralizer is finitely generated. This result has been previously proved only for binary and ternary sets of words in a series of papers by the authors and for prefix codes in an ingenious paper by [B. Ratoandromanana, RAIRO Inform. Theor. 23(4) (1989) 425–444.]—many of the techniques we use in this paper follow her ideas. We also give in this paper an elementary proof for the prefix case. [Copyright &y& Elsevier]

Abstract: We propose a new algebraic framework to discuss and classify recognizable tree languages, and to characterize interesting classes of such languages. Our algebraic tool, called preclones, encompasses the classical notion of syntactic -algebra or minimal tree automaton, but adds new expressivity to it. The main result in this paper is a variety theorem à la Eilenberg, but we also discuss important examples of logically defined classes of recognizable tree languages, whose characterization and decidability was established in recent papers (by Benedikt and Ségoufin, and by Bojańczyk and Walukiewicz) and can be naturally formulated in terms of pseudovarieties of preclones. Finally, this paper constitutes the foundation for another paper by the same authors, where first-order definable tree languages receive an algebraic characterization. [Copyright &y& Elsevier]

Abstract: This paper provides a fully abstract semantics for a variant of the concurrent object calculus. We define may testing for concurrent object components and then characterise it using a trace semantics inspired by UML interaction diagrams. The main result of this paper is to show that the trace semantics is fully abstract for may testing. This is the first such result for a concurrent object language. [Copyright &y& Elsevier]

Abstract: Explicit substitutions (ES) were introduced as a bridge between the theory of rewrite systems with binders and substitution, such as the -calculus, and their implementation. In a seminal paper Melliès observed that the dynamical properties of a rewrite system and its ES-based implementation may not coincide: he showed that a strongly normalising term (i.e. one which does not admit infinite derivations) in the -calculus may lose this status in its ES-based implementation. This paper studies normalisation for the latter systems in the general setting of higher-order rewriting: Based on recent work extending the theory of needed strategies to non-orthogonal rewrite systems we show that needed strategies normalise in the ES-based implementation of any orthogonal pattern higher-order rewrite system. [Copyright &y& Elsevier]

Abstract: This paper shows an asymptotically tight analysis of the Certified Write-All algorithm called AWT that was introduced by Anderson and Woll, SIAM J. Comput. 26 (1997) 1277, and a method for creating near-optimal instances of the algorithm. This algorithm is the best known deterministic algorithm that can be used to simulate n synchronous parallel processors on n asynchronous processors. The algorithm is instantiated with q permutations on , where q can be chosen from a wide range of values. When implementing a simulation on a specific parallel system with n processors, one would like to select the best possible value of q and the best possible q permutations, in order to maximize the efficiency of the simulation. This paper shows that work complexity of any instance of AWT is , where q is the number of permutations selected, and C is a value related to their combinatorial properties. The choice of q turns out to be critical for obtaining an instance of the AWT algorithm with near-optimal work. For any , and any large enough n, work of any instance of the algorithm must be at least . Under certain conditions, however, that q is about and for infinitely many large enough n, this lower bound can be nearly attained by instances of the algorithm that use certain q permutations and have work at most . The paper also shows a penalty for not selecting q well. When q is significantly away from , then work of any instance of the algorithm with this displaced q must be considerably higher than otherwise. [Copyright &y& Elsevier]

Abstract: The XOR Lemma states that a mapping is regular or balanced if and only if all the linear combinations of the component functions of the mapping are balanced Boolean functions. The main contribution of this paper is to extend the XOR Lemma to more general cases where a mapping may not be necessarily regular. The extended XOR Lemma has applications in the design of substitution boxes or S-boxes used in secret key ciphers. It also has applications in the design of stream ciphers as well as one-way hash functions. Of independent interest is a new concept introduced in this paper that relates the regularity of a mapping to subspaces. [Copyright &y& Elsevier]

In this paper, we introduce obnoxious effects into obnoxious facility location games on a line, where each agent i has a private location x i on a closed interval [ 0 , 1 ] and one facility will be built on a location y in the interval according to the bids of all the agents. In addition, there are two thresholds d 1 and d 2 in the utility function of each agent, where 0 ≤ d 1 ≤ d 2 ≤ 1 . Denote d ( y , x i ) = | y − x i | to be the distance between agent i and the facility on the location y . The utility function of agent i is 0 if d ( y , x i ) is at most d 1 ; 1 if d ( y , x i ) is at least d 2 ; otherwise a linear increasing function between 0 and 1. Each agent attempts to get the largest utility while the social welfare is to maximize the sum of all the agents' utilities. The classic obnoxious facility game [4,11] is a special case of our problem when d 1 = 0 and d 2 = 1 . In this work, we first study the hardness of approximate mechanism design on this generalized problem, which states that our problem cannot admit any deterministic strategy-proof mechanism with bounded approximation ratio if d 1 ≥ 1 2 . Then we limit the thresholds to some ranges, both deterministic and randomized strategy-proof mechanisms are studied, and the approximation ratios vary with the specific values of d 1 and d 2 . [ABSTRACT FROM AUTHOR]

The Lyndon factorization of a string w is a unique factorization ℓ 1 p 1 , … , ℓ m p m of w such that ℓ 1 , … , ℓ m is a sequence of Lyndon words that is monotonically decreasing in lexicographic order. In this paper, we consider the reverse-engineering problem on Lyndon factorization : Given a sequence S = ( ( s 1 , p 1 ) , … , ( s m , p m ) ) of ordered pairs of positive integers, find a string w whose Lyndon factorization corresponds to the input sequence S , i.e., the Lyndon factorization of w is in a form of ℓ 1 p 1 , … , ℓ m p m with | ℓ i | = s i for all 1 ≤ i ≤ m . Firstly, we show that there exists a simple O ( n ) -time algorithm if the size of the alphabet is unbounded, where n is the length of the output string. Secondly, we present an O ( n ) -time algorithm to compute a string over an alphabet of the smallest size. Thirdly, we show how to compute only the size of the smallest alphabet in O ( m ) time. Fourthly, we give an O ( m ) -time algorithm to compute an O ( m ) -size representation of a string over an alphabet of the smallest size. Finally, we propose an efficient algorithm to enumerate all strings whose Lyndon factorizations correspond to S . [ABSTRACT FROM AUTHOR]

The distinguishing index D ′ ( G ) of a graph G is the least number d such that G has an edge colouring with d colours that is preserved only by the identity automorphism. The distinguishing index of the Cartesian product of graphs was investigated by the authors and Kalinowski. They considered colourings with two colours only and obtained results that do not determine the distinguishing index for all the possible cases. In this paper we investigate colourings with d colours and determine the exact value of the distinguishing index of the Cartesian product K 1 , m □ K 1 , n for almost all m and n . In particular, we supplement the result of [6] for the case when 2 2 m + 1 − ⌈ m 2 ⌉ + 1 < n ≤ 2 2 m + 1 . We also observe the distinguishing index of the Cartesian product of two graphs in general does not have to depend on the size of the graphs and it can be arbitrarily small. [ABSTRACT FROM AUTHOR]

Two space efficient algorithms to solve the L C S k problem and L C S ≥ k problem are presented in this paper. The algorithms improve the time and space complexities of the algorithms of Benson et al. [4] . The space cost of the first algorithm to solve the L C S k problem is reduced from O ( n 2 ) to O ( k n ) , if the size of the two input sequences are both n . The time and space costs of the second algorithm to solve the L C S ≥ k problem are both improved. The time cost is reduced from O ( k n 2 ) to O ( n 2 ) , and the space cost is reduced from O ( n 2 ) to O ( k n ) . In the case of k = O ( 1 ) , the two algorithms are both linear space algorithms. [ABSTRACT FROM AUTHOR]

In this paper we present improved results on the problem of counting triangles in edge streamed graphs. For graphs with m edges and at least T triangles, we show that an extra look over the stream yields a two-pass streaming algorithm that uses O ( m ε 2.5 T polylog ( m ) ) space and outputs a ( 1 + ε ) approximation of the number of triangles in the graph. This improves upon the two-pass streaming tester of Braverman, Ostrovsky and Vilenchik, ICALP 2013, which distinguishes between triangle-free graphs and graphs with at least T triangle using O ( m T 1 / 3 ) space. Also, in terms of dependence on T , we show that more passes would not lead to a better space bound. In other words, we prove there is no constant pass streaming algorithm that distinguishes between triangle-free graphs from graphs with at least T triangles using O ( m T 1 / 2 + ρ ) space for any constant ρ ≥ 0 . [ABSTRACT FROM AUTHOR]

Solving polynomial systems with noise over F 2 is a fundamental problem in computer science, especially in cryptanalysis. ISBS is a new method for solving this problem based on the idea of incrementally solving the noisy polynomial systems and backtracking all the possible noises, and it has better performance than other methods in solving some problems generated from cryptanalysis. In this paper, some further researches on ISBS are presented. The structure and size of the search tree of ISBS are theoretically analyzed. Then two major improvements, artificial noise-bound strategy and s -direction approach, are proposed. Based on these improvements, a modified ISBS algorithm is implemented, and the experiments of solving the Cold Boot key recovery problems of the block cipher Serpent with symmetric noise, show that this modified algorithm is more efficient than the original one. [ABSTRACT FROM AUTHOR]

The concept of schema plays a vital role in the study of genetic algorithms. The effect of selection, simple crossover and mutation on schemata has already been studied rigorously by several researchers. In this paper a novel ternary crossover operator is introduced and its effects on the probability of survival of a schema are meticulously analyzed. A theorem regarding the effect of novel crossover operator on survival of schemata is proved and based on that the combined effect of novel crossover and mutation on probability of survival of a schema is established mathematically. [ABSTRACT FROM AUTHOR]

Just as ordinary hypergraphs are a generalization of graphs, directed hypergraphs (DH) are a natural generalization of digraphs. A DH consists of a set of vertices V and a set of hyperarcs H , where a hyperarc is a pair < S , v > , S non empty subset of V and v ∈ V . DHs have a variety of applications: they have been used to represent functional dependency in databases, Horn formulae in propositional logic, and–or graphs, context free grammars etc. In the paper, after providing a brief historical introduction on the notion of DH and some relevant applications, various problems regarding DHs are surveyed and analyzed. In particular we consider the complexity of the reachability problem (together with its application in the related satisfiability problem for Horn CNF formulae) and the computation of transitive closure and transitive reduction of directed hypergraphs (together with its application to the computation of minimum coverings for a set of functional dependencies). Finally a short introduction to the problem of computing shortest hyperpaths in directed hypergraphs is provided. [ABSTRACT FROM AUTHOR]

It was conjectured in 1992 that the 2-searcher, who has two flashlights, has the same searching capability as the ∞-searcher, who has an omni-directional light source. Park et al. proved this conjecture affirmatively in 2001, but their proof is rather complicated and not easy to understand. In this paper we present an alternative proof, which we believe is conceptually more transparent and easier to understand. For this purpose, we introduce a tool called the 2-link visibility diagram that represents 2-link visibility, which has other applications. [ABSTRACT FROM AUTHOR]

Given two disjoint vertex-sets, S = { s 1 , … , s k } and T = { t 1 , … , t k } in a graph, a paired many-to-many k-disjoint path cover between S and T is a set of pairwise vertex-disjoint paths { P 1 , … , P k } that altogether cover every vertex of the graph, in which each path P i runs from s i to t i . A family of hypercube-like interconnection networks, called restricted hypercube-like graphs , includes most non-bipartite hypercube-like networks found in the literature, such as twisted cubes, crossed cubes, Möbius cubes, recursive circulant G ( 2 m , 4 ) of odd m , etc. In this paper, we show that every m -dimensional restricted hypercube-like graph, m ≥ 5 , with at most f vertex and/or edge faults being removed has a paired many-to-many k -disjoint path cover between arbitrary disjoint sets S and T of size k each, subject to k ≥ 2 and f + 2 k ≤ m + 1 . The bound m + 1 on f + 2 k is the best possible. [ABSTRACT FROM AUTHOR]

At present, there are some linearly homomorphic signatures in the standard model, whose security is based on the RSA assumption and Diffie–Hellman assumption. But there are still no lattice-based linearly homomorphic signature in the standard model. How to construct it? It is proposed as a open problem by Freeman [12] . In this paper, we propose the first lattice-based linearly homomorphic signature in the standard model, which settle this open problem. [ABSTRACT FROM AUTHOR]

The paper contributes to the topic of (purely) catalytic P systems. Catalytic P systems represent the original and likely the simplest class of membrane computing models. It is known that (purely) catalytic P systems with two (respectively three) catalysts and one membrane can simulate any Minsky register machine and, hence, they are computationally complete. However, the problem of minimal size of such a universal catalytic P system remains open for about ten years. We improve known results about small catalytic P systems simulating register machines in three different modes (generating, accepting, computing functions). Together with some specific universal register machine [7] , one could eventually construct a small universal catalytic P system. As a consequence, we also improve the previous construction of a minimal catalytic P system generating a non-semilinear set, diminishing the number of necessary rules from 29 to 24. [ABSTRACT FROM AUTHOR]

In this paper we study the computational complexity of a generalized version of the logic puzzle Pete's Pike by Thinkfun [14] . It is shown that generalized Pete's Pike is PSPACE-complete. Moreover, we construct an infinite family of initial configurations with the property that the length of a shortest solution is superpolynomial in the size of the game. [ABSTRACT FROM AUTHOR]

In this paper, we show how to extend the notion of reducibility introduced by Girard for proving the termination of β -reduction in the polymorphic λ -calculus, to prove the termination of various kinds of rewrite relations on λ -terms, including rewriting modulo some equational theory and rewriting with matching modulo βη , by using the notion of computability closure . This provides a powerful termination criterion for various higher-order rewriting frameworks, including Klop's Combinatory Reductions Systems with simple types and Nipkow's Higher-order Rewrite Systems. [ABSTRACT FROM AUTHOR]

For a graph property Π , i.e., a family Π of graphs, the Connected Induced Π -Subgraph problem asks whether an input graph G contains k vertices V ′ such that the induced subgraph G [ V ′ ] is connected and satisfies property Π . In this paper, we study the parameterized complexity of Connected Induced Π -Subgraph for decidable hereditary properties Π , and give a nearly complete characterization in terms of whether Π includes all complete graphs, all stars, and all paths. As a consequence, we obtain a complete characterization of the parameterized complexity of our problem when Π is the family of H -free graphs for a fixed graph H with h ≥ 3 vertices: W[1]-hard if H is K h , K h ‾ , or K 1 , h − 1 ; and FPT otherwise. Furthermore, we also settle the parameterized complexity of the problem for many well-known families Π of graphs: FPT for perfect graphs, chordal graphs, and interval graphs, but W[1]-hard for forests, bipartite graphs, planar graphs, line graphs, and degree-bounded graphs. [ABSTRACT FROM AUTHOR]

The Dual Post Correspondence Problem asks, for a given word α , if there exists a non-periodic morphism g and an arbitrary morphism h such that g ( α ) = h ( α ) . Thus α satisfies the Dual PCP if and only if it belongs to a non-trivial equality set. Words which do not satisfy the Dual PCP are called periodicity forcing , and are important to the study of word equations, equality sets and ambiguity of morphisms. In this paper, a ‘prime’ subset of periodicity forcing words is presented. It is shown that when combined with a particular type of morphism it generates exactly the full set of periodicity forcing words. Furthermore, it is shown that there exist examples of periodicity forcing words which contain any given factor/prefix/suffix. Finally, an alternative class of mechanisms for generating periodicity forcing words is developed, resulting in a class of examples which contrast those known already. [ABSTRACT FROM AUTHOR]

Graph spanners are sparse subgraphs that preserve the distances of the original graph up to some approximation ratio (the spanner's stretch ). A number of algorithms are known for constructing sparse spanners with small multiplicative or additive stretch. Recently, algorithms were introduced for constructing fault-tolerant multiplicative spanners of general graphs. This paper addresses the analogous problem of constructing fault tolerant additive and ( μ , α ) -spanners for general graphs, and presents a number of (deterministic and randomized) construction algorithms for such spanners. [ABSTRACT FROM AUTHOR]