Search

In essence, simple matrix grammars can be seen as sequences of context-free grammars, referred to as their components, which work in parallel. The present paper demonstrates that two-component simple matrix grammars are as powerful as ordinary matrix grammars. Then, it places three leftmost derivation restrictions upon these grammars and demonstrates that under two of these restrictions, simple matrix grammars are computational complete - that is, they are equivalent with Turing machines. From a historical perspective, concerning simple matrix grammars, the paper also makes several remarks that correct false statements published about them in the past. [ABSTRACT FROM AUTHOR]

This paper brings together two methods to compositionally verify the generalized non-blocking property, which is a weak liveness property to express the ability of concurrent systems to terminate under given preconditions. Appropriate notions of equivalence and refinement for the generalized nonblocking property are discussed, and abstraction rules to simplify finite-state automata accordingly are presented. The paper also presents a unique canonical automaton representation for all generalized nonblocking equivalent automata, which gives rise to more general means of abstraction and to effective decision procedures for generalized nonblocking equivalence. Experimental results demonstrate how abstraction rules and canonical automata can be combined to model-check large models of concurrent software. [ABSTRACT FROM AUTHOR]

Two words u and v are k -abelian equivalent if they contain the same number of occurrences of each factor of length at most k. This leads to a hierarchy of equivalence relations on words which lie properly in between the equality and abelian equality. The goal of this paper is to analyze Fine and Wilf's periodicity theorem with respect to these equivalence relations. Fine and Wilf's theorem tells exactly how long a word with two periods p and q can be without having the greatest common divisor of p and q as a period. Recently, the same question has been studied for abelian periods. In this paper we show that for k-abelian periods the situation is similar to the abelian case: In general, there is no bound for the lengths of such words, but the values of the parameters p, q and k for which the length is bounded can be characterized. In the latter case we provide nontrivial upper and lower bounds for the maximal lengths of such words. In some cases (e.g., for k = 2) we found the maximal length precisely. [ABSTRACT FROM AUTHOR]

It is known that if a Büchi context-free language (BCFL) consists of scattered words, then there is an integer n, depending only on the language, such that the Hausdorff rank of each word in the language is bounded by n. Every BCFL is a Muller context-free language (MCFL). In the first part of the paper, we prove that an MCFL of scattered words is a BCFL iff the rank of every word in the language is bounded by an integer depending only on the language. Then we establish operational characterizations of the BCFLs of well-ordered and scattered words. We prove that a language is a BCFL consisting of well-ordered words iff it can be generated from the singleton languages containing the letters of the alphabet by substitution into ordinary context-free languages and the ⍵-power operation. We also establish a corresponding result for BCFLs of scattered words and define expressions denoting BCFLs of well-ordered and scattered words. In the final part of the paper we give some applications. [ABSTRACT FROM AUTHOR]

The growing size of the multiprocessor system increases its vulnerability to component failures. It is crucial to locate and replace the faulty processors to maintain a system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all of the remaining vertices in the dual-cube DCn when the number of faulty vertices is up to twice or three times of the traditional connectivity. Based on this fault resiliency, this paper determines that the conditional diagnosability of DCn (n ≥ 3) under the comparison model is 3n − 2, which is about three times of the traditional diagnosability. [ABSTRACT FROM AUTHOR]

Abelian complexity in infinite words is a combinatorial tool which developed essentially during the last five years. In this paper, we undertake to establish connections between abelian complexity and uniform frequencies in infinite words. In particular, we focus on the binary case to link uniform equi-frequency with abelian complexity. We also provide various examples of infinite words to illustrate the absence of connection between usual complexity and abelian complexity. Some properties involving uniform recurrence are also given. [ABSTRACT FROM AUTHOR]

The aim of this paper is to give motivations for the development of operational semantics in membrane computing, and to survey existing proposals. In particular, the definitions are compared of three operational semantics available in the literature, namely a semantics proposed by Andrei, Ciobanu and Lucanu, another proposed by Busi, and another one proposed by the authors of the present paper. These definitions are different since they are given with different aims. However, we show that there is an operational correspondence among the three. [ABSTRACT FROM AUTHOR]

This paper considers an intra-molecular version of template-guided recombination (TGR), which has been studied in recent papers as an inter-molecular operation. We demonstrate that the intra-molecular TGR operations are distinct from previous intramolecular models for ciliate gene assembly, including the ld and hi operations. We examine the language-theoretic properties of intra-molecular TGR, including closure properties and solutions to language equations. [ABSTRACT FROM AUTHOR]

Hairpin completion is a formal operation inspired from DNA biochemistry. It is known that the (one step) hairpin completion of a regular language is linear context-free, but not regular in general. Further, it is decidable whether the (one step) hairpin completion of a regular language is regular. However, it is an open question whether the iterated hairpin completion of a regular language is regular, even if it is a singleton. If the word is a non-crossing α-word, there are results, but for crossing words there are no results. In this paper, we give necessary and sufficient conditions that the iterated hairpin completion of a given crossing (2, 2)-α-word in is regular. [ABSTRACT FROM AUTHOR]

This paper deals with insertability and mainly extractablity of codes. A code C is called insertable (or extractable) if the free submonoid C* generated by C satisfies if z, implies (or z, implies ). We show that a finite insertable code is a full uniform code. On the other hand there are many finite extractable codes which are not full uniform codes. We cannot still characterize the structures of infinite extractable codes. Here we give some results on the class of infix extractable codes. First, we consider a necessary and sufficient condition whether a given infix code C is extractable or not by using the syntactic graph of the code. Secondly, we investigate the extractability for the families of other related bifix codes. We newly define the bifix codes, called e(m)-codes and -codes, and refer to the extractability of them. [ABSTRACT FROM AUTHOR]

In this paper, a self-stabilizing algorithm is presented for finding the articulation points of a connected undirected graph on a distributed or network model of computation after O(n[SUP2]|E|) moves. The algorithm is resilient to transient faults and does not require initialization. A correctness proof of the algorithm is also presented. The paper concludes with remarks on issues such as the time complexity of the algorithm and open problems. [ABSTRACT FROM AUTHOR]

The Dual Post Correspondence Problem asks whether, for a given word α, there exists a pair of distinct morphisms σ,τ, one of which needs to be non-periodic, such that σ(α) = τ(α) is satisfied. This problem is important for the research on equality sets, which are a vital concept in the theory of computation, as it helps to identify words that are in trivial equality sets only. Little is known about the Dual PCP for words α over larger than binary alphabets, especially for so-called ratio-primitive examples. In the present paper, we address this question in a way that simplifies the usual method, which means that we can reduce the intricacy of the word equations involved in dealing with the Dual PCP. Our approach yields large sets of words for which there exists a solution to the Dual PCP as well as examples of words over arbitrary alphabets for which such a solution does not exist. [ABSTRACT FROM AUTHOR]

In this paper we extend the framework of reaction systems by introducing (extended) zoom structures which formalize a depository of knowledge of a discipline of science. The integrating structure of such a depository (which is a well-founded partial order) allows one to deal with the hierarchical nature of biology. This leads to the notion of an exploration system which consists of (1) a static part which is a depository of knowledge given by an extended zoom structure , and (2) a dynamic part given by a family of reaction systems . In this setup the depository of knowledge is explored by computations/processes provided by reaction systems from , where this exploration can use/integrate knowledge present on different levels (e.g., atomic, cellular, organism, species, ... levels). [ABSTRACT FROM AUTHOR]

This paper considers Rh-connectivity of the (n, k)-star graph Sn,k, denoted by κh(Sn,k). In this note, We determine κh(Sn,k) = n+h(k−2)−1 for 2 ≤ k ≤ n−1 and 0 ≤ h ≤ n−k. The results generalize the main result in proved by W. H. Yang et al. [Information Processing Letters, 110(2010), 1007-1011] for the R1-connectivity (κ1(Sn,k)) and R2-connectivity (κ2(Sn,k)). [ABSTRACT FROM AUTHOR]

The rupture degree of an incomplete connected graph G is defined by where w(G − S) denotes the number of components in the graph G − S and m(G − S) is the order of the largest component of G − S. This parameter can be used to measure the vulnerability of a graph. In this paper, some bounds consisted of the relationships between the rupture degree and some vulnerability parameters on the rupture degree of a graph are given. [ABSTRACT FROM AUTHOR]

Recovering unknown inputs in oracles with as few queries as possible is one of the most basic problems in theoretical computer science. In this paper, we survey the classical and quantum query complexity of this problem for various types of oracles with different types of queries. [ABSTRACT FROM AUTHOR]

Professor Sheng Yu passed away on January 23, 2012, the first day of the Lunar New Year, the Year of the Dragon. He was only sixty-one years old. His death was a tremendous loss to his family, friends, colleagues, co-workers, co-authors, co-editors, members of conference program committees, students, the theoretical Computer Science Community and especially to his beloved wife, Lizhen. Through his teachings, international committee work, seminars and some 150 refereed publications, he left us a huge legacy of many interesting and important research contributions in the areas of the theory and implementation of automata and formal languages, fuzzy logic, object-oriented modeling methodologies, parallel processing for parallel programming languages, important software projects for automata theory research, the creation of the international Conference on Implementation and Application of Automata (CIAA) and a gallery of vivid memories of the wonderful times shared. He is remembered for his enormous energy, competence, diligence, anticipatory thoughtfulness, over-the-top generosity, measured politeness, noble sportsmanship and committed friendship. This paper, an extension of a talk with a similar title at DLT 2012, is an account how we are commemorating Sheng. [ABSTRACT FROM AUTHOR]

The abstract should summarize the context, content and conclusions of the paper in less than 200 words. It should not contain any reference citations or displayed equations. Typeset the abstract in 8 pt roman with baselineskip of 10 pt, making an indentation of 1.5 pica on the left and right margins. [ABSTRACT FROM AUTHOR]

Vectorial Boolean functions play an important role in cryptography. How to construct vectorial Boolean functions with good cryptographic properties is a nice problem that worth to be investigated. In this paper we present several constructions of balanced vectorial Boolean functions with high algebraic immunity, high(or optimum) algebraic degree, and very high nonlinearity. In some cases, the constructed functions also achieve optimum algebraic immunity. [ABSTRACT FROM AUTHOR]

Text mining from large scaled data is of great importance in computer science. In this paper, we consider fundamental problems on text mining from compressed strings, i.e., computing a longest repeating substring, longest non-overlapping repeating substring, most frequent substring, and most frequent non-overlapping substring from a given compressed string. Also, we tackle the following novel problem: given a compressed text and compressed pattern, compute the representative of the equivalence class of the pattern w.r.t. the text. We present algorithms that solve the above problems in time polynomial in the size of input compressed strings. The compression scheme we consider is straight line program (SLP) which has exponential compression, and therefore our algorithms are more efficient than any existing algorithms that require decompression of given SLPs. [ABSTRACT FROM AUTHOR]

This paper is a continuation of our research work on state complexity of combined operations. Motivated by applications, we study the state complexities of two particular combined operations: catenation combined with star and catenation combined with reversal. We show that the state complexities of both of these combined operations are considerably less than the compositions of the state complexities of their individual participating operations. [ABSTRACT FROM AUTHOR]

In this paper, we propose an approximation algorithm for the Fault-Tolerant Metric Facility Location problem which can be implemented in a distributed and asynchronous manner within O(n) rounds of communication, where n is the number of vertices in the network. Given a constant size set $\mathcal{R}$ which represents distinct levels of fault-tolerant requirements of all cities, as well as the two-part (facility and connection) cost of the optimal solution, i.e. F* + C*, the cost of our solution is no more than $|\mathcal{R}|\, \cdot \,F^* \, + \,2C^* $ for the general case, and less than F* + 2C* for the special case where all cities have a uniform connectivity requirement. Extensive numerical experiments showed that the quality of our solutions is comparable (within 4% error) to the optimal solution in practice. [ABSTRACT FROM AUTHOR]

The main contribution of this paper is to present an efficient parallel sorting "psort" compatible with the standard qsort. Our parallel sorting "psort" is implemented such that its interface is compatible with "qsort" in C Standard Library. Therefore, any application program that uses standard "qsort" can be accelerated by simply replacing "qsort" call by our "psort". Also, "psort" uses standard "qsort" as a subroutine for local sequential sorting. So, if the performance of "qsort" is improved by anyone in the open source community, then that of our "psort" is also automatically improved. To evaluate the performance of our "psort", we have implemented our parallel sorting in a Linux server with four Intel hexad-core processors (i.e. twenty four processor cores). The experimental results show that our "psort" is approximately 11 times faster than standard "qsort" using 24 processors. [ABSTRACT FROM AUTHOR]

A self-stabilizing algorithm is a distributed algorithm that can start from any initial (legitimate or illegitimate) state and eventually converge to a legitimate state in finite time without being assisted by any external agent. In this paper, we propose a self-stabilizing algorithm for finding the 3-edge-connected components of an asynchronous distributed computer network. The algorithm stabilizes in O(dnΔ) rounds and every processor requires O(nlogΔ) bits, where Δ(≤ n) is an upper bound on the degree of a node, d(≤ n) is the diameter of the network, and n is the total number of nodes in the network. These time and space complexity are at least a factor of n better than those of the previously best-known self-stabilizing algorithm for 3-edge-connectivity. The result of the computation is kept in a distributed fashion by assigning, upon stabilization of the algorithm, a component identifier to each processor which uniquely identifies the 3-edge-connected component to which the processor belongs. Furthermore, the algorithm is designed in such a way that its time complexity is dominated by that of the self-stabilizing depth-first search spanning tree construction in the sense that any improvement made in the latter automatically implies improvement in the time complexity of the algorithm. [ABSTRACT FROM AUTHOR]

In the present paper, we propose P systems that work in a constant number of steps. We first propose two P systems for computing multiple input logic functions. An input of the logic functions is a set of n binary numbers of m bits, and an output is a binary number defined by the logic functions. The first and second P systems compute AND and EX-OR functions for the input, and both of the P systems work in a constant number of steps by using O(mn) types of objects, a constant number of membranes, and evolution rules of size O(mn). Next, we propose a P system for the addition of two binary numbers of m bits. The P system works in a constant number of steps by using O(m) types of objects, a constant number of membranes and evolution rules of size O(m2). We also introduce a P system that computes the addition of two vectors of n binary numbers of m bits by using the above P system as a sub-system. The P system for vector addition works in a constant number of steps by using O(mn) types of objects, a constant number of membranes, and evolution rules of size O(m2n). [ABSTRACT FROM AUTHOR]

The goal of this work is to study the portfolio problem which consists in finding a good combination of multiple heuristics given a set of a problem instances to solve. We are interested in a parallel context where the resources are assumed to be discrete and homogeneous, and where it is not possible to allocate a given resource (processor) to more than one heuristic. The objective is to minimize the average completion time over the whole set of instances. We extend in this paper some existing analysis on the problem. More precisely, we provide a new complexity result for the restricted version of the problem, then, we generalize previous approximation schemes. In particular, they are improved using a guess approximation technique. Experimental results are also provided using a benchmark of instances on SAT solvers. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of k-out-of-ℓ exclusion, a generalization of the mutual exclusion problem, in which there are ℓ units of a shared resource, and any process can request up to k units (1 ≤ k ≤ ℓ). A protocol is self-stabilizing if, starting from an arbitrary configuration, be it initial state or after a corrupted state, the protocol can start behaving normally within a finite time. We propose the first deterministic self-stabilizing distributed k-out-of-ℓ exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process. [ABSTRACT FROM AUTHOR]

We consider transition P systems as originally defined in the seminal paper of Gh. Păun, where he introduced the field of membrane computing. We show that it is decidable to determine, given a P system Π, whether it is strongly reversible (i.e., every configuration has at most one direct predecessor), resolving in the affirmative a recent open problem in the field. We also show that the set of all direct predecessors of a given configuration in a P system is an effectively computable semilinear set, which can effectively be expressed as a Presburger formula, strengthening an early result in the literature. We also prove other related results. [ABSTRACT FROM AUTHOR]

The paper summarizes recent knowledge about computational power of spiking neural P systems and presents a sequence of new more general results. The concepts of recognizer SN P systems and of uniform families of SN P systems provide a formal framework for this study. We establish the relation of computational power of spiking neural P systems with various limitations to standard complexity classes like P, NP, PSPACE and P/poly. [ABSTRACT FROM AUTHOR]

Multienvironment probabilistic P systems provide a framework of specification for modeling population biology. It has been used to model real ecosystems in a comprehensible, modular and probabilistic way. However, simulators are needed for virtual experimentation. Hence, the development of correct simulation algorithms becomes a critical point. In this paper we present a formal verification of a new algorithm of simulation designed for this kind of probabilistic P systems. [ABSTRACT FROM AUTHOR]

This paper presents an approach to P system verification using the Spin model checker. It proposes a P system implementation in PROMELA, the modeling language accepted by SPIN. It also provides the theoretical background for transforming the temporal logic properties expressed for the P system into properties of the executable implementation. Furthermore, a comparison between P systems verification using SPIN and NUSMV is realized. The results obtained show that the PROMELA implementation is more adequate, especially for verifying more complex models, such as P systems that model ecosystems. [ABSTRACT FROM AUTHOR]

A language L is called the orthogonal shuffle of the language L1 with the language L2, along the trajectory set T if every word in L is uniquely obtained as the shuffle between a word in L1, a word in L2 along a trajectory word in T. In this paper we investigate properties of the orthogonal shuffle on trajectories, as well as several types of language equations using this language operation. As a corollary, we obtain several properties of orthogonal catenation, orthogonal literal shuffle and orthogonal insertion. [ABSTRACT FROM AUTHOR]

Reaction systems are a formal model of interactions between biochemical reactions. They consist of sets of reactions, where each reaction is classified by its set of reactants (needed for the reaction to take place), its set of inhibitors (each of which prevents the reaction from taking place), and its set of products (produced when the reaction takes place) - the set of reactants and inhibitors form the resources of the reaction. Each reaction system defines a (transition) function on its set of states. (States here are subsets of an a priori given set of biochemical entities.) In this paper we investigate properties of functions defined by reaction systems. In particular, we investigate how the power of defining functions depends on available resources, and we demonstrate that with small resources one can define functions exhibiting complex behavior. [ABSTRACT FROM AUTHOR]

Positioned eco-grammar systems (PEG systems, for short) were introduced in [9]. Motivation of introducing positioned eco-grammar systems is an attempt to describe interplay between evolving environment and community of agents living in this environment whereas we focus on the positions of agents in the environment. PEG systems bring a new view to investigating interplay between community of agents and environment. Our approach allows to study local changes in evolving environment caused by agents moreover the position of the agent is strictly given by special symbol and we are able to predict its behavior and control the evolution of environment as well. In this paper we compare generative power of the PEG systems with three types of pure (regulated) grammars. [ABSTRACT FROM AUTHOR]

Fine and Wilf's well-known theorem states that any word having periods p,q and length at least p+q-gcd(p,q) also has gcd(p,q) as a period. Moreover, the length p+q-gcd(p,q) is critical since counterexamples can be provided for shorter words. This result has since been extended to partial words, or finite sequences that may contain some "holes." More precisely, any partial word u with H holes having weak periods p,q and length at least the so-denoted lH(p,q) also has strong period gcd(p,q) provided u is not (H,(p,q))-special. This extension was done for one hole by Berstel and Boasson (where the class of (1,(p,q))-special partial words is empty), and for an arbitrary number of holes by Blanchet-Sadri. In this paper, we further extend these results, allowing an arbitrary number of weak periods. In addition to speciality, the concepts of intractable period sets and interference between periods play a role. [ABSTRACT FROM AUTHOR]

In this paper we introduce and study some new cooperation protocols for cooperating distributed (CD) grammar systems. These derivation modes depend on the number of different nonterminals present in the sentential form obtained when a component finished a derivation phase. This measure describes the competence of the grammar on the string (the competence is high if the number of the different nonterminals is small). It is also a measure of the efficiency of the grammar on the given string (a component is more efficient than another one if it is able to decrease the number of nonterminals in the string to a greater extent). We prove that if the underlying derivation mode is the t-mode derivation, then some variants of these systems determine the class of random context ET0L languages. If these CD grammar systems use the k step limited derivations as underlying derivation mode, then they are able to generate any recursively enumerable language. [ABSTRACT FROM AUTHOR]

This paper presents a new lower bound for the model-checking algorithm based on solving parity games due to Stevens and Stirling. We outline a family of games of linear size on which the algorithm requires exponential time. [ABSTRACT FROM AUTHOR]

The Parallel Random Access Machine is a very strong model of parallel computing that has resisted cost-efficient implementation attempts for decades. Recently, the development of VLSI technology has provided means for indirect on-chip implementation, but there are different variants of the PRAM model that provide different performance, area and power figures and it is not known how their implementations compare to each others. In this paper we measure the performance and estimate the cost of practical implementations of four PRAM models including EREW, Limited Arbitrary CRCW, Full Arbitrary CRCW, Full Arbitrary Multioperation CRCW on our Eclipse chip multiprocessor framework. Interestingly, the most powerful model shows the lowest simulation cost and highest performance/area and performance/power figures. [ABSTRACT FROM AUTHOR]

The leader election problem is unsolvable for some anonymous networks. A leader election algorithm for anonymous networks thus elects a leader whenever it is possible; if it is impossible, the algorithm reports this fact. This paper investigates the space complexity of the leader election problem in anonymous networks, where the space complexity is measured by the size (in the number of bits) of memory per processor used by a leader election algorithm. We first observe that Ω(M + log d) bits are necessary and then show that O(n log d) bits are sufficient to construct a leader election algorithm that works on any network, where n, d and M are the number of processors, the maximum number of adjacent processors, and the maximum size (in bits) of a message, respectively. We next show that, for any arbitrarily fixed constant n, O(1) bits are sufficient to construct a leader election algorithm that works in any network of size n. [ABSTRACT FROM AUTHOR]

A pure morphic sequence is a right-infinite, symbolic sequence obtained by iterating a letter-to-word substitution. For instance, the Fibonacci sequence and the Thue–Morse sequence, which play an important role in theoretical computer science, are pure morphic. Define a coding as a letter-to-letter substitution. The image of a pure morphic sequence under a coding is called a morphic sequence. A sequence x is called uniformly recurrent if for each finite subword u of x there exists an integer l such that u occurs in every l-length subword of x. The paper mainly focuses on the problem of deciding whether a given morphic sequence is uniformly recurrent. Although the status of the problem remains open, we show some evidence for its decidability: in particular, we prove that it can be solved in polynomial time on pure morphic sequences and on automatic sequences. In addition, we prove that the complexity of every uniformly recurrent, morphic sequence has at most linear growth: here, complexity is understood as the function that maps each positive integer n to the number of distinct n-length subwords occurring in the sequence. [ABSTRACT FROM AUTHOR]

We present a semiformal model of anonymous communication with several participants performing several anonymous actions on several messages, e.g. in digital pseudosignatures. The goal is to design a model having enough expressive power to model simple as well as very complex anonymous communication patterns. Our model concentrates on anonymity of a sender, a receiver, and on the relationship anonymity. However, the model is easy to adopt to other types of anonymity. A special anonymous channel formalism is introduced and extensively explored in this paper. The formalism builds on the top of so-called estimation procedure which takes knowledge of the adversary and processes it to find anonymous participants. Some other, already published, models of anonymity, e.g. the model of Hughes and Shmatikov or of Halpern and O'Neill, are compatible with our model – they could be used as building blocks together with (or instead of) our estimation procedure. Therefore, the tools developed for those models can be easily adapted to be used with our model. We use protocol runs and an observational equivalence on the runs which is induced by adversary's knowledge. This is a well developed area of the theoretical computer science and many tools developed therein can be adapted to work with our model. Our model is also open to many additional features, e.g. the possibility to include probability distributions on anonymity sets. [ABSTRACT FROM AUTHOR]

This paper is aimed at designing efficient parallel matrix-product algorithms for homogeneous master-worker platforms. While matrix-product is well-understood for homogeneous 2D-arrays of processors, there are two key hypotheses that render our work original and innovative: — Centralized data. We assume that all matrix files originate from, and must be returned to, the master. The master distributes both data and computations to the workers. Typically, our approach is useful in the context of speeding up MATLAB or SCILAB clients running on a server (which acts as the master and initial repository of files). — Limited memory. Because we investigate the parallelization of large problems, we cannot assume that full matrix panels can be stored in the worker memories and re-used for subsequent updates. The amount of memory available in each worker is expressed as a given number of buffers, where a buffer can store a square block of matrix elements. These square blocks are chosen so as to harness the power of Level 3 BLAS routines; they are of size 80 or 100 on most platforms. We have devised efficient algorithms for resource selection (deciding which workers to enroll) and communication ordering (both for input and result messages), and we report a set of MPI experiments conducted on a platform at the University of Tennessee. [ABSTRACT FROM AUTHOR]

In this paper, we present a fully distributed process to collect and distribute the minimal connected component (MCC) fault information so that the shortest-path between a source and its destination can always be found in the corresponding information-based routing via routing decisions made at each intermediate node. Considering the communication cost in the above information distribution, a more practical implementation is provided with a low number of nodes involved in the information propagation. The experimental results show substantial improvement of our approach in terms of the success rate in finding the shortest-path and the average path length. [ABSTRACT FROM AUTHOR]

In this paper, we study some periodicity concepts on words. First, we extend the notion of full tilings which was recently introduced by Karhumäki, Lifshits, and Rytter to partial tilings. Second, we investigate the notion of quasiperiods and show in particular that the set of quasiperiodic words is a context-sensitive language that is not context-free, answering a conjecture by Dömösi, Horváth and Ito. [ABSTRACT FROM AUTHOR]

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. In this paper, we find this number for the alternating group graphs, Cayley graphs generated by 2-trees and the (n,k)-arrangement graphs. Moreover, we classify all the optimal solutions. [ABSTRACT FROM AUTHOR]

In this paper, the descriptional complexity of extended finite splicing systems is studied. These systems are known to generate exactly the class of regular languages. Upper and lower bounds are shown relating the size of these splicing systems, defined as the total length of the rules and the initial language of the system, to the size of their equivalent minimal nondeterministic finite automata (NFA). In addition, an accepting model of extended finite splicing systems is studied. Using this variant one can obtain systems which are more than polynomially more succinct than the equivalent NFA or generating extended finite splicing system. [ABSTRACT FROM AUTHOR]

For a string w ∈ {0,1, 2,..., d-1}*, let vald(w) denote the integer whose base d representation is the string w and let MSDd(x) denote the most significant or the leading digit of a positive integer x when x is written as a base d integer. Hirvensalo and Karhumäki [9] studied the problem of computing the leading digit in the ternary representation of 2x ans showed that this problem has a polynomial time algorithm. In [16], some applications are presented for the problem of computing the leading digit of AB for given inputs A and B. In this paper, we study this problem from a formal language point of view. Formally, we consider the language Lb,d,j = {w|w ∈ {0,1, 2,..., d-1}*, 1 ≤ j ≤ 9, MSDb(dvalb(w))) = j} (and some related classes of languages) and address the question of whether this and some related languages are context-free. Standard pumping lemma proofs seem to be very difficult for these languages. We present a unified and simple combinatorial technique that shows that these languages are not unambiguous context-free languages. The Benford-Newcomb distribution plays a central role in our proofs. [ABSTRACT FROM AUTHOR]

As is well-known, Axel Thue constructed an infinite word over a 3-letter alphabet that contains no squares, that is, no nonempty subwords of the form xx. In this paper we consider a variation on this problem, where we try to avoid approximate squares, that is, subwords of the form xx' where |x| = |x'| and x and x' are "nearly" identical. [ABSTRACT FROM AUTHOR]

Bideterministic automata are deterministic automata with the property of their reversal automata also being deterministic. Bideterministic automata have previously been shown to be unique (up to an isomorphism) minimal NFAs with respect to the number of states. In this paper, we show that in addition to state minimality, bideterministic automata are also transition-minimal NFAs. However, as this transition minimality is not necessarily unique, we also present the necessary and sufficient conditions for a bideterministic automaton to be uniquely transition-minimal among NFAs. These results are obtained using the notion of the universal automaton. We also present some properties of the universal automaton. Furthermore, we show that bideterministic automata are transition-minimal ∊-NFAs. [ABSTRACT FROM AUTHOR]

In this paper finite state recognizers are considered as unary tree recognizers with unary operational symbols. We introduce translation recognizers of a tree recognizer, which are finite state recognizers whose operations are the elementary translations of the underlying algebra of the considered tree recognizer. In terms of translation recognizers we give general conditions under which a class of recognizable tree languages with a given property can be determined by a class of monoids determining the class of string languages having the same property. [ABSTRACT FROM AUTHOR]