Search

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [ABSTRACT FROM AUTHOR]

Presents an introduction to several articles published in the June 2005 issue of the "International Journal of Foundations of Computer Science."

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [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]

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]

Elaborates on the application of the concept of task scheduling in computer science. Advantages of dynamic scheduling; Scheduling scenarios for parallel computing systems.

No abstract received. [ABSTRACT FROM AUTHOR]

No abstract received. [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]

No abstract received. [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 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]

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]

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]

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 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]

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]

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 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]

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]

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]

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]

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]

Presents a series of literary papers from the U.S.-based Workshop on Advances in Parallel and Distributed Computational Models, published in the February 2003 issue of 'International Journal of Foundations of Computer Science.' Features of the workshop; Method for selecting literary papers for the issue.

We consider the following online scheduling problem. We are given a set of jobs, each having an integral release time and deadline, unit processing length, and a nonnegative real weight. In each time unit one job is to be scheduled, and the objective is to maximize the total value (weight) obtained by scheduling the jobs. This problem arises in the scheduling of packets in network switches supporting quality-of-service (QoS). Previous algorithms for this problem are 2-competitive. in this paper we propose a new algorithm that achieves an improved competitive ratio when the importance ratio is bounded. Specifically, for job weights within the range [1..B], our algorithm is 2 - 1/([lg B] + 2)-competitive, and the bound is tight. [ABSTRACT FROM AUTHOR]

In this paper, we consider procedures for logic and arithmetic operations with DNA molecules. We first show a DNA representation of n binary numbers of m bits, and propose a procedure to assign the same values for the representation. The representation enables addressing feature, and the procedure is applicable to n binary numbers of m bits in O(1) steps in parallel. Next, we propose a procedure for logic operations. The procedure enables any boolean operation whose input and output are defined by a truth table, and executes different kinds of boolean operations simultaneously for any pair of n binary numbers of m bits in O(1) lab steps using O(mn) DNA strands. Finally, we propose a procedure for additions of pairs of two binary numbers. The procedure executes O(n) additions of two m-bit binary numbers in O(1) steps using O(mn) DNA strands. [ABSTRACT FROM AUTHOR]

Given a pure state |ψ[sub N]>∈ℋ[sub N] of a quantum system composed of n qubits, where ℋ[sub N] is the Hilbert space of dimension N=2[sup n], this paper answers two questions: what conditions should the amplitudes in |ψ[sub N]> satisfy for this state to be separable (i) into a tensor product of n qubit states |ψ[sub 2]>[sub 0]⊗ |ψ[sub 2]>[sub 1] ⊗⋯⊗ |ψ[sub 2]>[sub n-1], and (ii), into a tensor product of two subsystems states |ψ[sub P]> ⊗ |ψ[sub Q]> with P=2[sup p] and Q=2[sup q] such that p+q=n? For both questions, necessary and sufficient conditions are proved, thus characterizing at the same time families of separable and entangled states of n qubit systems. A number of more refined questions about separability in n qubit systems can be studied on the basis of these results. [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]

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]

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]

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]

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]

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]

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]

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]

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]