Search

The class of finite Sturmian words consists of words having particularly simple compressed representation, which is a generalization of the Fibonacci recurrence for Fibonacci words. The subword graphs of these words (especially their compacted versions) have a very special regular structure. In this paper we investigate this structure in more detail than in previous papers and show how several syntactical properties of Sturmian words follow from their graph properties. Consequently simple alternative graph-based proofs of several known facts are presented. The very special structure of subword graphs leads also to special easy algorithms computing some parameters of Sturmian words: the number of subwords, the critical factorization point, lexicographically maximal suffixes, occurrences of subwords of a fixed length, and right special factors. These algorithms work in linear time with respect to n, the size of the compressed representation of the standard word, though the words themselves can be of exponential size with respect to n. Some of the computed parameters can be also of exponential size, however we provide their linear size compressed representations. We introduce also a new concept related to standard words: Ostrowski automata. [ABSTRACT FROM AUTHOR]

The graph isomorphism problem is to check if two given graphs are isomorphic. Graph isomorphism is a well studied problem and numerous algorithms are available for its solution. In this paper we present algorithms for graph isomorphism that employ the spectra of graphs. An open problem that has fascinated many a scientist is if there exists a polynomial time algorithm for graph isomorphism. Though we do not solve this problem in this paper, the algorithms we present take polynomial time. These algorithms have been tested on a good collection of instances. However, we have not been able to prove that our algorithms will work on all possible instances. In this paper, we also give a new construction for cospectral graphs. [ABSTRACT FROM AUTHOR]

In this paper two concurrent versions of Brzozowski's deterministic finite automaton (DFA) construction algorithm are developed from first principles, the one being a slight refinement of the other. We rely on Hoare's CSP as our notation. The specifications that are proposed of the Brzozowski algorithm are in terms of the concurrent composition of a number of top-level processes, each participating process itself composed of several other concurrent processes. After considering a number of alternatives, this particular overall architectural structure seemed like a natural and elegant mapping from the sequential algorithm's structure. While we have carefully argued the reasons for constructing the concurrent versions as proposed in the paper, there are of course, a large range of alternative design choices that could be made. There might also be scope for a more fine-grained approach to updating sets or checking for similarity of regular expressions. At this stage, we have chosen to abstract away from these considerations, and leave their exploration for a subsequent step in our research. [ABSTRACT FROM AUTHOR]

In this research, a framework is proposed for answering the question: whether a dominant sequence exists for the multiple self-contained input streams destined for a computation provider running the requested applications concurrently. The framework is extended to find an optimal semidominant sequence for multiple input streams. This paper also shows that an existent universal dominant sequence can be formed by permuting a set of dominant input streams. In this paper, the neighbor-connected graph is first proposed to model the sequence problem of multiple input streams. Then, an algorithm with time complexity O(nLn) is proposed to determine the existence of a dominant data-receiving sequence, where L is the maximal length of the input streams plus one and n is the number of input streams. Examples of applying the framework to solve the sequence problems for several computation-intensive applications are also given. Furthermore, the framework is extended to find an optimal semidominant sequence using an algorithm with time complexity O(nLnlogδ*), where δ* is the maximal degree that the sequence diverges from all the optimal subsequences. Finally, the property of a universal dominant sequence is studied and the performance of the sequence is compared with those of other sequences. [ABSTRACT FROM AUTHOR]

This paper presents an exhaustive analysis of the problem of computing the Lp distance of two probabilistic automata. It gives efficient exact and approximate algorithms for computing these distances for p even and proves the problem to be NP-hard for all odd values of p, thereby completing previously known hardness results. It further proves the hardness of approximating the Lp distance of two probabilistic automata for odd values of p. Similar techniques to those used for computing the Lp distance also yield efficient algorithms for computing the Hellinger distance of two unambiguous probabilistic automata both exactly and approximately. A problem closely related to the computation of a distance between probabilistic automata is that of testing their equivalence. This paper also describes an efficient algorithm for testing the equivalence of two arbitrary probabilistic automata A1 and A2 in time O(|Σ|(|A1| + |A2|)3), a significant improvement over the previously best reported algorithm for this problem. [ABSTRACT FROM AUTHOR]

Degenerate primers are used to amplify a given set of genomic sequences using a technique called Multiplex Polymerase Chain Reaction (MP-PCR). The problem of minimizing the number of degenerate primers required to amplify a given set of DNA sequences, also known as the Degenerate Primer Design Problem (DPDP), has been extensively studied in the literature and proven to be NP-Complete. In this paper we present efficient algorithms for solving DPDP. For example, one of the algorithms we give in this paper is iterative and has a runtime of O(b|Σ|log|Σ|dn2mp) to select a set of p degenerate primers, each of given length l and degeneracy at most d, for n sequences each of length m in the input, the number of candidates retained in each iteration being b. Σ is the alphabet of the input strings. This is an improvement over the runtime of the best known prior algorithm, MIPS by Souvenir et al. [15], which has a runtime of O(bn3mp). We provide an experimental comparison of MIPS and our algorithms. [ABSTRACT FROM AUTHOR]

This paper studies the problem of orienting all edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be $\mathcal{NP}$-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, $\min \{\frac{w_{max}}{w_{min}},(2 - \varepsilon)\}$-approximation algorithm for the general case, where wmax and wmin are the maximum and the minimum weights of edges, respectively, and ε is some small positive real number that depends on the input. [ABSTRACT FROM AUTHOR]

In this paper, we discuss a simple, Monte Carlo algorithm for the problem of checking whether a Quantified Boolean Formula (QBF) in Conjunctive Normal Form (CNF), with at most two literals per clause has a model. The term k-CNF is used to describe boolean formulas in CNF, with at most /c literals per clause and the problem of checking whether a given k-CNF formula is satisfiable is called the k-SAT problem. A QBF is a boolean formula, accompanied by a quantifier string which imposes a linear ordering on the variables of that formula. The problem of finding a model for a QBF formula in CNF, with at at most k literals per clause is called the QkSAT problem. The QkSAT problem is PSPACE-complete, for k ≥ 3. However, the Q2SAT problem can be decided in polynomial time; the graph-based procedure, discussed in [1], is the first such algorithm for this problem. This procedure requires the construction of a global implication graph, corresponding to the input formula and searching for certain paths in this graph. Hence the complete set of clauses must be part of the input. We propose an incremental, randomized approach for the Q2SAT problem that is essentially local in nature, in that the complete clausal set need not be provided at any time, in the presence of a verifier. We show that the randomized algorithm can be analyzed as a one-dimensional random walk, with one reflecting barrier and one absorbing barrier. On a Q2SAT instance with in clauses on n variables, our coin-flipping algorithm runs in time O(n² V(m, n)), where V(m, n) is the time required to verify that a given model satisfies the formula. Additionally, if the instance is satisfiable, the probability that our algorithm fails to find a model is less than one half. The design and analysis of a randomized algorithm for a problem, is important from both the theoretical and the practical perspectives. Randomized approaches tend to be simple and elegant, thereby making the process of checking correctness, effortless as well. The randomized approach discussed in this paper lays the groundwork for analyzing a number of problems related to 2CNF formulas and directed graphs. We remark that our work in this paper is the first randomized algorithm for a class of QBFs. [ABSTRACT FROM AUTHOR]

Ant Colony Optimization (ACO) techniques can be successfully implemented to solve many combinatorial optimization problems. After the traveling salesman problem was successfully solved using the ACO technique, other researchers have concentrated on solving other problems like the quadratic assignment and the job-shop scheduling problems using the same technique. In this paper we use the ACO technique to route messages through an N×N Optical Multistage Interconnection Network (OMIN) allowing upto 'C' limited crosstalk's (conflicts between messages within a switch) where 'C' is a technology driven parameter and is always less than log2N. Messages with switch conflicts satisfying the crosstalk constraint are allowed to pass in the same group, but if there is any link conflict, then messages have to be routed in a different group. The focus is to minimize the number of passes required for routing allowing upto 'C' limited crosstalks in an N×N optical network. This routing problem is an NP-hard problem. In this paper we show how the ACO technique can be applied to the routing problem and compare the performance of the ACO technique to that of the degree-descending algorithm using simulation techniques. Finally the lower bound estimate on the minimum number of passes required is calculated and compared to the results obtained using the two algorithms discussed. The results obtained show that the ACO technique performs better than the degree-descending algorithm and is quite close to optimal algorithms to the problem. [ABSTRACT FROM AUTHOR]

Partitioned Optical Passive Stars (POPS) network has been presented recently as a desirable model of parallel computation. Several papers have been published that address fundamental problems on this architecture. The algorithms presented in this paper are valid for POPS(d,g) where d>g and use randomization. We present an algorithm that solves the problem of sparse enumeration sorting of d∊ keys in $\widetilde O(\frac{d}{g}\rceil+\log g)$ time and hence performs better than previous algorithms. We also present algorithms that allow us to do stable sorting of integers in the range [1,log n] and $[1, \frac{d}{g}]$ in $\widetilde O(\lceil \frac{d}{g}\rceil+\log n)$ time. When g=n∊, for any constant 0<∊<½ this allows us to do sorting of integers in the range [1,n] in $\widetilde O(\frac{1}{1-2\epsilon}(\lceil\frac{d}{g}\rceil+\log g))$ time. We finally use these algorithms to solve the problem of multiple binary search in the case where we have d∊ keys in $\widetilde O(\frac{d}{g}+\log g)$ time and in the case where we have integer keys in the range [1,n] in $\widetilde O(\frac{1}{1- 2\epsilon}(\lceil\frac{d}{g}\rceil+\log g))$ time, when g=n∊, for some constant 0<∊<½. [ABSTRACT FROM AUTHOR]

This paper proposes a procedure to design fault tolerant algorithms for the R-Mesh and some of its restrictive variations. This procedure first identifies a healthy sub-mesh from a faulty model using the bypass and removal fault model. Then it uses scalable algorithms to simulate the larger faulty model on the resulting healthy sub-mesh. The algorithms for the bypass model tolerates n faults in an n×n R-Mesh (LR-Mesh) and runs in O(T log n) (O(T)) time, where T is the execution time on the original mesh without faults. For the removal model, we design fault tolerant algorithms for some interesting variations of the R-Mesh, specifically, the NXR-Mesh and the NXLR-Mesh. We propose the first scaling simulations for these models and present a simulation of the R-Mesh on the NXR-Mesh. The results of this paper enable us to consider certain reconfigurable models in a more practical environment than previously allowed. [ABSTRACT FROM AUTHOR]

This paper addresses multicasting and broadcasting in undirected WDM networks and QoS extensions of multicasting. It is given an undirected network G=(V, E), with Λ is the set of the available wavelengths in G, and associated with each edge, there is a subset of wavelengths on it. For a multicast request r=(s, D) with a source s and a set D of destinations, it is to find a tree rooted at s including all nodes in D such that the cost of the tree is minimized in terms of the cost of wavelength conversion at nodes and the cost of using wavelength on edges. This paper proves that multicasting in this model of networks is NP-Hard and cannot be approximated within a constant factor, unless P=NP. Furthermore, an auxiliary graph is constructed for the original WDM network, the multicasting is reduced to a group Steiner tree problem on the auxiliary graph and an approximate algorithm based on the group Steiner tree algorithm proposed by M. Charikar et al. with performance ratio of O(log[sup 2](nk) log log(nk) log p) is provided, where k=|Λ| and p=|D∪{s}|. At last, some QoS extensions of multicasting are discussed. [ABSTRACT FROM AUTHOR]

Chandra and Toueg proposed in 1993 a new approach to overcome the impossibility of reaching deterministically Consensus — and by corollary Atomic Broadcast — in asynchronous systems subject to crash failures. They augment the asynchronous system with a possibly Unreliable Failure Detector which provides some information about the operational state of processes. In this paper, we present an extension of the Consensus problem that we call Uniform Prefix Agreement. This extension enables all the processes to propose a flow of messages during an execution — instead of one as in the Consensus problem — and uses all these proposed messages to compose the decision value. Prefix Agreement is based on an Unreliable Failure Detector. We use repeated executions of Prefix Agreement to build an efficient Uniform Atomic Broadcast algorithm. This paper describes the Uniform Prefix Agreement and Uniform Atomic Broadcast algorithms, and provides proofs of their correctness. [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]&verbar;E&verbar;) 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]

We describe a hybrid pattern-matching algorithm that works on both regular and indeterminate strings. This algorithm is inspired by the recently proposed hybrid algorithm FJS and its indeterminate successor. However, as discussed in this paper, because of the special properties of indeterminate strings, it is not straightforward to directly migrate FJS to an indeterminate version. Our new algorithm combines two fast pattern-matching algorithms, ShiftAnd and BMS (the Sunday variant of the Boyer-Moore algorithm), and is highly adaptive to the nature of the text being processed. It avoids using the border array, therefore avoids some of the cases that are awkward for indeterminate strings. Although not always the fastest in individual test cases, our new algorithm is superior in overall performance to its two component algorithms — perhaps a general advantage of hybrid algorithms. [ABSTRACT FROM AUTHOR]

We consider in this paper systems modeled by timed automata. The timing bounds involved in the action guards and location invariants of our timed automata are not constants, but parameters. Those parametric timed automata allow the modelling of various kinds of timed systems, e.g. communication protocols or asynchronous circuits. We will also assume that we are given an initial tuple π0 of values for the parameters, which corresponds to values for which the system is known to behave properly. Our goal is to compute a constraint K0 on the parameters, satisfied by π0, guaranteeing that, under any parameter valuation satisfying K0, the system behaves in the same manner: for any two parameter valuations satisfying K0, the behaviors of the timed automata are (time-abstract) equivalent, i.e., the traces of execution viewed as alternating sequences of actions and locations are identical. We present an algorithm InverseMethod that terminates in the case of acyclic models, and discuss how to extend it to the cyclic case. We also explain how to combine our method with classical synthesis methods which are based on the avoidance of a given set of bad states. A prototype implementation has been done, and various experiments are described. [ABSTRACT FROM AUTHOR]

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [ABSTRACT FROM AUTHOR]

Antimirov and Mosses proposed a rewrite system for deciding the equivalence of two (extended) regular expressions. They argued that this method could lead to a better average-case algorithm than those based on the comparison of the equivalent minimal deterministic finite automata. In this paper we present a functional approach to that method, prove its correctness, and give some experimental comparative results. Besides an improved functional version of Antimirov and Mosses's algorithm, we present an alternative one using partial derivatives. Our preliminary results lead to the conclusion that, indeed, these methods are feasible and, most of the time, faster than the classical methods. [ABSTRACT FROM AUTHOR]

We address the problem of reducing the size of (nondeterministic, bottom-up) tree automata (TA) using suitable, language-preserving equivalences on the states of the automata. In particular, we propose the so-called composed bisimulation equivalence as a new language preserving equivalence. A composed bisimulation equivalence is defined in terms of two different relations, namely the upward and downward bisimulation equivalence. We provide simple and efficient algorithms for computing these relations. The notion of composed bisimulation equivalence is motivated by an attempt to obtain an equivalence that can provide better reductions than what currently known bisimulation-based approaches can offer, but which is not significantly more difficult to compute (and hence stays below the computational requirements of simulation-based reductions). The experimental results we present in the paper show that our composed bisimulation equivalence meets such requirements, and hence provides users of TA with a finer way to resolve the trade-off between the available degree of reduction and its cost. [ABSTRACT FROM AUTHOR]

Analysis of infinitary safety properties with automated compositional reasoning through learning is discussed in the paper. We consider the class of intuitionistically closed regular languages and show that it forms a Heyting algebra and is finitely approximatable. Subsequently, compositional proof rules can be verified automatically and learning algorithms for finitary regular languages suffice. We also establish an axiom to deduce circular compositional proof rules for the infinitary languages. [ABSTRACT FROM AUTHOR]

Wu, Lou, Lai and Chang proposed a multi-exponentiation algorithm using binary complements and the non-adjacent form. The purpose of this paper is to give a precise asymptotic analysis of the expected costs of this algorithm. It turns out that the complement operation does not have significant influence on the performance of the algorithm. [ABSTRACT FROM AUTHOR]

Let L ≥ 1, ε > 0 be real numbers, (M, d) be a finite metric space and (N, ρ) be a metric space. A query to a metric space consists of a pair of points and asks for the distance between these points. We study the number of queries to metric spaces (M, d) and (N, ρ) needed to decide whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ∊-far from being L-bilipschitz embeddable into N, ρ). When (M, d) is ∊-far from being L-bilipschitz embeddable into (N, ρ), we allow an o(1) probability of error (i.e., returning the wrong answer "L-bilipschitz embeddable"). However, no error is allowed when (M, d) is L-bilipschitz embeddable into (N, ρ). That is, algorithms with only one-sided errors are studied in this paper. When |M| ≤ |N| are both finite, we give an upper bound of $O(\sqrt{\frac{\ln |N|}{\epsilon |M|}}\, (|M|^2+|N|^2))$ on the number of queries for determining with one-sided error whether (M, d) is L-bilipschitz embeddable into (N, ρ) or ∊-far from being L-bilipschitz embeddable into (N, ρ). For the special case of finite |M| = |N|, the above upper bound evaluates to $O(|N|^{3/2} \sqrt {{{\ln |N|} \over \epsilon }} )$. We also prove a lower bound of Ω(|N|3/2) for the special case when |M| = |N| are finite and L = 1, which coincides with testing isometry between finite metric spaces. For finite |M| = |N|, the upper and lower bounds thus match up to a multiplicative factor of at most $\sqrt{\frac{\ln |N|}{\epsilon}}$, which depends only sublogarithmically in |N|. We also investigate the case when (N, ρ) is not necessarily finite. Our results are based on techniques developed in an earlier work on testing graph isomorphism. [ABSTRACT FROM AUTHOR]

A convertible authenticated encryption scheme allows a designated receiver to retrieve an authenticated ciphertext and convert the authenticated ciphertext into an ordinary signature. The receiver can prove the dishonesty of the sender to anyone if the sender repudiates his/her signature. Recently, many researchers have proposed convertible authenticated encryption schemes based on cryptological algorithms. In this paper, the authors shall present a new convertible authenticated encryption scheme based on the ElGamal cryptosystem. The proposed scheme is more efficient than Wu-Hsu's scheme in terms of computational complexity. [ABSTRACT FROM AUTHOR]

In this paper, we present efficient geometric algorithms for the discrete constrained 1-D K-means clustering problem and extend our solutions to the continuous version of the problem. One key clustering constraint we consider is that the maximum difference in each cluster cannot be larger than a given threshold. These constrained 1-D K-means clustering problems appear in various applications, especially in intensity-modulated radiation therapy (IMRT). Our algorithms improve the efficiency and accuracy of the heuristic approaches used in clinical IMRT treatment planning. [ABSTRACT FROM AUTHOR]

In order to represent, compute and reason with advanced data types like lists with a fixed length, finite sets or well scoped λ-terms one must go beyond the traditional treatment of data types as being inductive types and, instead, consider them as inductive families, or more precisely Strictly Positive Families (SPFs). We have previously shown that the grammar of strictly positive types (SPT) can be given as an inductively defined family. In the present paper we go one step further an show that the universe of SPFs can be encoded as an SPF. We show that SPFs can be used to represent and compute with a variety of advanced data types and that generic programs can be naturally written over the universe of SPFs. [ABSTRACT FROM AUTHOR]

Screening is an important task to convert a continuous-tone image into a binary image with pure black and white pixels. The main contribution of this paper is to show a new algorithm for cluster-dot screening using a local exhaustive search. Our new algorithm generates 2-cluster, 3-cluster, and 4-cluster binary images, in which all dots have at least 2, 3, and 4 pixels, respectively. The key idea of our new screening method is to repeat a local exhaustive search that finds the best binary pattern in small windows of size k × k in a binary image. The experimental results show that the local exhaustive search produces high quality and sharp cluster-dot binary images. We also present an hardware algorithm to accelerate the computation. Our hardware algorithm for a round of the local exhaustive search runs O(k2) clock cycles while the software implementation runs in O(2k2 w2) time, where (2w + 1) × (2w + 1) is the size of Gaussian filter. Thus, from theoretical point of view, our hardware algorithm achieves a speedup factor of O(w2). To show that our hardware algorithm is practically fast, we have implemented it on an FPGA. Our hardware algorithm achieved a speedup factor of up to 229 over the software implementation. [ABSTRACT FROM AUTHOR]

This paper focuses on the self-stabilizing leader election algorithm of Xu and Srimani [10] that finds a leader in a tree graph. The worst case execution time for this algorithm is O(N4), where N is the number of nodes in the tree. We show that the average execution time for this algorithm, assuming two different scenarios, is much lower than O(N4). In the first scenario, the algorithm assumes an equiprobable daemon and it only privileges a single node at a time. The average execution time for this case is O(N2). For the second case, the algorithm can privilege multiple nodes at a time. We eliminate the daemon from this algorithm by making random choices to avoid interference between neighboring nodes. The execution time for this case is O(N). We also show that for specific tree graphs, these results reduce even more. [ABSTRACT FROM AUTHOR]

Checkpoint is a designated place in a program at which normal process is interrupted specifically to preserve the status information necessary to allow resumption of processing at a later time. A checkpoint algorithm for mobile distributed systems needs to handle many new issues like: mobility, low bandwidth of wireless channels, lack of stable storage on mobile nodes, disconnections, limited battery power and high failure rate of mobile nodes. These issues make traditional checkpointing techniques unsuitable for such environments. Minimum-process coordinated checkpointing is an attractive approach to introduce fault tolerance in mobile distributed systems transparently. This approach is domino-free, requires at most two checkpoints of a process on stable storage, and forces only a minimum number of processes to checkpoint. But, it requires extra synchronization messages, blocking of the underlying computation or taking some useless checkpoints. In this paper, we design a minimum-process checkpointing algorithm for mobile distributed systems, where no useless checkpoint is taken. We reduce the blocking of processes by allowing the processes to do their normal computations, send messages and receive selective messages during their blocking period. [ABSTRACT FROM AUTHOR]

In this paper, we propose a solution for the problem of capturing an intruder in two popular interconnection topologies namely, the mesh and the torus. A set of agents collaborate to capture a hostile intruder in the network. While the agents can move in the network one hop at a time, the intruder is assumed to be arbitrarily fast i.e. it can traverse any number of nodes contiguously as far as there are no agents in those nodes. Here we consider a new version of the problem where each agent can replicate new agents when needed, i.e. the algorithm starts with a single agent and new agents are created on demand. We define a new class of algorithms for capturing an intruder. In particular, we propose two different algorithms on mesh and torus networks and we will later discuss about the merits of each algorithm based on some performance criteria. [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]

The implication of multivalued dependencies (MVDs) in relational databases has originally and independently been defined in the context of some fixed finite universe by Delobel, Fagin, and Zaniolo. Biskup observed that the original axiomatisation for MVD implication does not reflect the fact that the complementation rule is merely a means to achieve database normalisation. He proposed two alternative ways to overcome this deficiency: i) an axiomatisation that does represent the role of the complementation rule adequately, and ii) a notion of MVD implication in which the underlying universe of attributes is left undetermined together with an axiomatisation of this notion. In this paper we investigate multivalued dependencies with null values (NMVDs) as defined and axiomatised by Lien. We show that Lien's axiomatisation does not adequately reflect the role of the complementation rule, and extend Biskup's findings for MVDs in total database relations to NMVDs in partial database relations. Moreover, a correspondence between (minimal) axiomatisations in fixed universes that do reflect the property of complementation and (minimal) axiomatisations in undetermined universes is shown. [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]

A fundamental problem in music is to classify songs according to their rhythm. A rhythm is represented by a sequence of “Quick” (Q) and “Slow” (S) symbols, which correspond to the (relative) duration of notes, such that S = 2Q. In this paper, we present an efficient algorithm for locating the maximum-length substring of a music text t that can be covered by a given rhythm r. [ABSTRACT FROM AUTHOR]

In this paper, we present data structures and algorithms for efficiently constructing approximate automata. An approximate automaton for a regular language L is one which accepts at leastL. Such automata can be used in a variety of practical applications, including network security pattern matching, in which false-matches are only a performance nuisance. The construction algorithm is particularly efficient, and is tunable to yield more or less exact automata. [ABSTRACT FROM AUTHOR]

Membrane algorithms with subalgorithms inspired by simulated annealing are treated in this paper. Simulated annealing is inherently a kind of local search but it modifies a solution to a worse one with a probability determined by "temperature". The temperature of simulated annealing is changed according to "cooling schedule". On the other hand, the subalgorithm introduced here has constant temperature which is determined by the region where the subalgorithm is. It is called Brownian subalgorithm since the subalgorithm incorporates "thermal movement" of a solution in the search space but does not simulate "annealing". Computer simulations show that a membrane algorithm which has three regions and has a Brownian subalgorithm in each region can obtain very good approximate solutions for several benchmark problems of the traveling salesman problem. However, the algorithm, occasionally, gets quite bad solutions (twice as large as the optimum) for a problem. A membrane algorithm which has both Brownian and genetic subalgorithms never gets such a bad solution (only 8% worse than the optimum) for all problems examined, although, in average, it is not as good as the algorithm with Brownian only. The result indicates that membrane algorithm with subalgorithms under different approximate mechanisms may be robust under a wide range of problems. [ABSTRACT FROM AUTHOR]

A theory of representation of semiautomata by canonical words and equivalences was developed in [7]. That work was motivated by trace-assertion specifications of software modules, but its focus was entirely on the underlying mathematical model. In the present paper we extend that theory to automata with Moore and Mealy outputs, and show how to apply the extended theory to the specification of modules. In particular, we present a unified view of the trace-assertion methodology, as guided by our theory. We illustrate this approach, and some specific issues, using several nontrivial examples. We include a discussion of finite versus infinite modules, methods of error handling, some awkward features of the trace-assertion method, and a comparison to specifications by automata. While specifications by trace assertions and automata are equivalent in power, there are cases where one approach appears to be more natural than the other. We conclude that, for certain types of system modules, formal specification by automata, as opposed to informal state machines, is not only possible, but practical. [ABSTRACT FROM AUTHOR]

A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others. The paper offers the automata-theoretical description of Iliopoulos's ALL_BORDERS algorithm. The algorithm finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is an implementation of a finite state transducer of specific form. We describe how such a transducer can be constructed and what should be the input string like. The described transducer finds a set of lengths of all borders. Last but not least, we define approximate borders and show how to find all approximate borders of a string when we concern Hamming distance definition. Our solution of this problem is based on transducers again. This allows us to use analogy with automata-based pattern matching methods. Finally we discuss conditions under which the same principle can be used for other distance measures. [ABSTRACT FROM AUTHOR]

Sense of direction is a property of the edge-labeling of a network whose availability facilitates computations and often decreases their complexity. In this paper we consider the problem of providing a sense of direction to an anonymous, unoriented torus. The edges of the torus are initially labeled arbitrarily, and they have to be relabeled with a classical compass sense of direction. We first describe an algorithm where the relabeling of the edges is performed by a mobile agent that carries a token. The algorithm is optimal both in terms of number of tokens (with no tokens the task cannot be performed), and in terms of number of moves. We then show that the same technique can be used to orient the torus in the classical message-passing environment, thus obtaining an orientation algorithm that improves all the existing ones in this setting. [ABSTRACT FROM AUTHOR]

In this paper we consider a network where an intruder is moving "contaminating" the nodes it passes by, and we focus on the problem of decontaminating such a network by a team of mobile agents. The contamination/decontamination process has the following asynchronous dynamics: when the team is deployed all nodes are assumed to be contaminated, when an agent transits on a node, it will clean the node, when the node is left with no agent, the node will be recontaminated as soon as at least one of its neighbours is contaminated. We study the problem in asynchronous chordal ring networks and in tori. We consider two variations of the model: one where agents have only local knowledge, the other in which they have "visibility", i.e., they can "see" the state of their neighbouring nodes. We first derive lower bounds on the minimum number of agents necessary for the decontamination. In the case of chordal rings we show that the number of agents necessary to perform the cleaning does not depend on the size of the network; in fact it is linear in the length of the longest chord (provided that it is not too long). In the case of a torus, the minimum number of agents is equal to 2 · h, where h is the smallest dimension. We then propose optimal strategies for decontamination and we analyse the number of moves and the time complexity of the decontamination algorithms, showing that the visibility assumption allows us to decrease substantially both complexity measures. Another advantage of the "visibility model" is that agents move independently and autonomously without requiring any coordination. [ABSTRACT FROM AUTHOR]

Recent advances in scheduling and networking have paved the way for efficient exploitation of large-scale distributed computing platforms such as computational grids and huge clusters. Such infrastructures hold great promise for the highly resource-demanding task of verifying and checking large models, given that model checkers would be designed with a high degree of scalability and flexibility in mind. In this paper we focus on the mechanisms required to execute a high-performance, distributed, symbolic model checker on top of a large-scale distributed environment. We develop a hybrid algorithm for slicing the state space and dynamically distribute the work among the worker processes. We show that the new approach is faster, more effective, and thus much more scalable than previous slicing algorithms. We then present a checkpoint-restart module that has very low overhead. This module can be used to combat failures, the likelihood of which increases with the size of the computing plat-form. However, checkpoint-restart is even more handy for the scheduling system: it can be used to avoid reserving large numbers of workers, thus making the distributed computation work-efficient. Finally, we discuss for the first time the effect of reorder on the distributed model checker and show how the distributed system performs more efficient reordering than the sequential one. We implemented our contributions on a network of 200 processors, using a distributed scalable scheme that employs a high-performance industrial model checker from Intel. Our results show that the system was able to verify real-life models much larger than was previously possible. [ABSTRACT FROM AUTHOR]

For certain problems (for example, computing repetitions and repeats, data compression applications) it is not necessary that the suffixes of a string represented in a suffix tree or suffix array should occur in lexicographical order (lexorder). It thus becomes of interest to study possible alternate orderings of the suffixes in these data structures, that may be easier to construct or more efficient to use. In this paper we consider the "reconstruction" of a suffix array based on a given reordering of the alphabet, and we describe simple time- and space-efficient algorithms that accomplish it. [ABSTRACT FROM AUTHOR]

Music sequences can be treated as texts in order to perform music retrieval tasks on them. However, the text search problems that result from this modeling are unique to music retrieval. Up to date, several approaches derived from classical string matching have been proposed to cope with the new search problems, yet each problem had its own algorithms. In this paper we show that a technique recently developed for multipattern approximate string matching is flexible enough to be successfully extended to solve many different music retrieval problems, as well as combinations thereof not addressed before. We show that the resulting algorithms are average-optimal in many cases and close to average-optimal otherwise. Empirically, they are much better than existing approaches in many practical cases. [ABSTRACT FROM AUTHOR]

We study the problem of scheduling n jobs with release dates on m identical parallel batch machines to minimize the total weighted completion time of the jobs. A batch machine with capacity B (B < n) is able to process a batch of up to B jobs simultaneously and the time needed is equal to the maximum processing time among the jobs in the batch. This model is motivated by applications in the manufacturing of integrated circuits. In this paper, we present a polynomial time approximation scheme (PTAS) for this problem. [ABSTRACT FROM AUTHOR]

A convex grid drawing of a plane graph G is a drawing of G on the plane such that all vertices of G are put on grid points, all edges are drawn as straight-line segments without any edge-intersection, and every face boundary is a convex polygon. In this paper we give a linear-time algorithm for finding a convex grid drawing of every 4-connected plane graph G with four or more vertices on the outer face. The size of the drawing satisfies W + H ≤ n - 1, where n is the number of vertices of G, W is the width and H is the height of the grid drawing. Thus the area W · H is at most ⌈(n - 1)/2⌉ · ⌊(n - 1)/2⌋. Our bounds on the sizes are optimal in a sense that there exist an infinite number of 4-connected plane graphs whose convex drawings need grids such that W + H = n - 1 and W · H = ⌈(n - 1)/2⌉ · ⌊(n - 1)/2⌋. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of testing an arbitrary digraph G = (V,E) for upward planarity. In particular we describe two fixed-parameter tractable algorithms for testing the upward planarity of G. The first algorithm that we present can test the upward planarity of G in O(2t · t! · |V|2)-time where t is the number of triconnected components of G. The second algorithm that we present uses a standard technique known as kernelisation and can test the upward planarity of G in O(|V|2 + k4 · (2k)!)-time, where k = |E| - |V|. [ABSTRACT FROM AUTHOR]

Well-orderly tree is a powerful technique capable of deriving new results in graph encoding, graph enumeration and graph generation [3, 5]. In this paper, by using well-orderly trees, we prove that any plane graph G with n vertices has a visibility representation with height $\le \lfloor\frac{4n-1}{5}\rfloor$, which can be constructed in linear time. This improves the best previous bound of $\le \lfloor\frac{5n}{6}\rfloor$. [ABSTRACT FROM AUTHOR]

In this paper we propose constant-time parallel algorithms for implementing the message-passing decoder of LDPC codes on a two dimensional R-Mesh and an LARPBS. The R-Mesh and LARPBS are dynamically reconfigurable models that provide hardware reuse and flexibility to problem changes. The same hardware can implement the decoder in both probability and logarithm domains over different channels. Moreover, to decode an alternate code, we may simply set up the required connections between the bit-nodes and check-nodes by modifying the initialization phase of the proposed algorithms. No extra wiring or hardware changes are required, as compared to other existing approaches. We illustrate that the R-Mesh and the LARPBS are efficient models for parallel implementation of the decoder in terms of time complexity, flexibility to problem changes and simplicity of routing messages. We also demonstrate that it is possible to optimally scale large block code sizes down to a smaller, available machine size if using an LR-Mesh or HVR-Mesh, two variants of the R-Mesh model. [ABSTRACT FROM AUTHOR]

We study the fully compressed pattern matching problem (FCPM problem): Given ${\mathcal T}$ and ${\mathcal P}$ which are descriptions of text T and pattern P respectively, find the occurrences of P in Twithout decompressing ${\mathcal T}$or ${\mathcal P}$. This problem is rather challenging since patterns are also given in a compressed form. In this paper we present an FCPM algorithm for simple collage systems. Collage systems are a general framework representing various kinds of dictionary-based compressions in a uniform way, and simple collage systems are a subclass that includes LZW and LZ78 compressions. Collage systems are of the form $\langle {\mathcal D}, {\mathcal S} \rangle$, where ${\mathcal D}$ is a dictionary and ${\mathcal S}$ is a sequence of variables from ${\mathcal D}$. Our FCPM algorithm performs in $O(\|{\mathcal D}\|^2 + mn \log |{\mathcal S}|)$ time, where $n = |{\mathcal T}| = \|{\mathcal D}\| + |{\mathcal S}|$ and $m = |{\mathcal P}|$. This is faster than the previous best result of O(m2n2) time. [ABSTRACT FROM AUTHOR]

Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar three-step approach, based on an initial division of the suffixes of x into two sets: Step 1 sorts the first set using recursive reduction of the problem, Step 2 determines the order of the suffixes in the second set based on the order of the suffixes in the first set, and Step 3 merges the two sets together. To optimize such an algorithm either for space or time, it may not be sufficient to optimize one of the three steps, since in doing so, one might increase the resources required for the others to an unacceptable extent. Franek, Lu, and Smyth introduced two-pattern strings as a generalization of Sturmian strings. Like Sturmian strings, two-pattern strings are generated by iterated morphisms, but they exhibit a much richer structure. In this paper we show that the suffixes of two-pattern strings can be sorted in linear time using a variant of the three-step approach outlined above, but without the need for recursion. It turns out that, given the order of the suffixes in a two-pattern string, one can almost directly list in linear time all the suffixes of its expansion under a two-pattern morphism. [ABSTRACT FROM AUTHOR]

We present three linear algorithms for as many formulations of the problem of finding motifs with gaps. The three versions of the problem are distinct in that they assume different constraints on the size of the gaps. The outline of the algorithm is always the same, although this is adapted each time to the specific problem, while maintaining a linear time complexity with respect to the input size. The approach we suggest is based on a re-writing of the text that uses a new alphabet made of labels representing words of the original input text. The computational complexity of the algorithm allows the use of it also to find long motifs. The algorithm is in fact general enough that it could be applied to several variants of the problem other than those suggested in this paper. [ABSTRACT FROM AUTHOR]