The syntactic monoid of hairpin-free languages

The study of hairpin-free words has been initiated in the context of DNA computing. DNA strands that, theoretically speaking, are finite strings over the alphabet {A, G, C, T} are used in DNA computing to encode information. Due to the fact that A is complementary to T and G to C, DNA single strands that are complementary can bind to each other or to themselves in either intended or unintended ways. One of the structures that is usually undesirable for biocomputation, since it makes the affected DNA string unavailable for future interactions, is the hairpin: if some subsequences of a DNA single string are complementary to each other, the string will bind to itself forming a hairpin-like structure. This paper continues the theoretical study of hairpin-free languages. We study algebraic properties of hairpin-free words and hairpins. We also give a complete characterization of the syntactic monoid of the language consisting of all hairpin-free words over a given alphabet and illustrate it with an example using the DNA alphabet.     

Characterizing sets of jobs that admit optimal greedy-like algorithms

The “Priority Algorithm” is a model of computation introduced by Borodin, Nielsen and Rackoff ((Incremental) Priority algorithms, Algorithmica 37(4):295–326, 2003) which formulates a wide class of greedy algorithms. For an arbitrary set \mathbbS\mathbb{S} of jobs, we are interested in whether or not there exists a priority algorithm that gains optimal profit on every subset of \mathbbS\mathbb{S} . In the case where the jobs are all intervals, we characterize such sets \mathbbS\mathbb{S} and give an efficient algorithm (when \mathbbS\mathbb{S} is finite) for determining this. We show that in general, however, the problem is NP-hard.     

Characterizing minimal semantics-preserving slices of function-linear, free, liberal program schemas

A program schema defines a class of programs, all of which have identical statement structure, but whose functions and predicates may differ. A schema thus defines an entire class of programs according to how its symbols are interpreted. As defined in this paper, a slice of a schema is obtained from a schema by deleting some of its statements. We prove that given a schema S which is function-linear, free and liberal, and a slicing criterion defined by the final value of a given variable after execution of any program defined by S, the minimal slice of S which respects this slicing criterion contains only the symbols ‘needed’ by the variable according to the data dependence and control dependence relations used in program slicing, which is the symbol set given by Weiser’s static slicing algorithm. Thus this algorithm gives minimal slices for programs representable by function-linear, free, liberal schemas. We also prove a similar result with termination behaviour used as a slicing criterion. This strengthens a recent result, in which S was required to be linear, free and liberal, and termination behaviour as a slicing criterion was not considered.     

UN algorithme calculant le cardinal,fini ou infini,des demi-groupes de matrices

Let S be a finite set of matrices over a commutative field K. We give here an algorithm which decides whether the matrix semigroup H generated by S is finite; and in that case, our algorithm computes the cardinality of H.In other words, we can decide by an effective procedure whether a K-automaton is a finite automaton.     

Characterizing minimal semantics-preserving slices of predicate-linear, free, liberal program schemas

A program schema defines a class of programs, all of which have identical statement structure, but whose functions and predicates may differ. A schema thus defines an entire class of programs according to how its symbols are interpreted. A subschema of a schema is obtained from a schema by deleting some of its statements. We prove that given a schema S which is predicate-linear, free and liberal, such that the true and false parts of every if predicate satisfy a simple additional condition, and a slicing criterion defined by the final value of a given variable after execution of any program defined by S, the minimal subschema of S which respects this slicing criterion contains all the function and predicate symbols ‘needed’ by the variable according to the data dependence and control dependence relations used in program slicing, which is the symbol set given by Weiser’s static slicing algorithm. Thus this algorithm gives predicate-minimal slices for classes of programs represented by schemas satisfying our set of conditions. We also give an example to show that the corresponding result with respect to the slicing criterion defined by termination behaviour is incorrect. This complements a result by the authors in which S was required to be function-linear, instead of predicate-linear.     

The poset of retracts of a free monoid

The set of retracts of a free monoid F with the partial order of inclusion is investigated. This poset is a lattice if and only if F is generated by three or fewer elements. For a finitely generated free monoid F it is shown non-constructively that, for every submonoid S of F, the intersection of all retracts of F containing S is regular. A regular expression can be constructed for this intersection when S is regular. The submonoid generated by the set of all retracts of F contained in the regular submonoid S is also regular and constructable. This allows the decision to be made whether or not any given pair of retracts has a supremum or an infimum in the poset of retracts of F. The procedure yields regular expressions for such suprema and infima when they exist.     

On pseudoknot-bordered words and their properties

We study a generalization of the classical notions of bordered and unbordered words, motivated by biomolecular computing. DNA strands can be viewed as finite strings over the alphabet {A, G, C, T}, and are used in biomolecular computing to encode information. Due to the fact that A is Watson–Crick complementary to T and G to C, DNA single strands that are Watson–Crick complementary can bind to each other or to themselves forming so-called secondary structures. Most of these secondary structures are undesirable for biomolecular computational purposes since the strands they involve cannot further interact with other strands. This paper studies pseudoknot-bordered words, a mathematical formalization of pseudoknot-like inter- and intra-molecular structures. In this context, pseudoknot-unbordered words model DNA or RNA strands that will be free of such secondary structures. We obtain several properties of pseudoknot-bordered and -unbordered words. We also address following problem: Given a pseudoknot-unbordered word u, does ${\{u\}}^{+}$ consist of pseudoknot-unbordered words only? We show that this is not generally true. We find that a sufficient condition for ${\{u\}}^{+}$ to consist of pseudoknot-unbordered words only is that u be not primitive. All of our results hold for arbitrary antimorphic involutions, of which the DNA Watson–Crick complementarity function is a particular case.     

Least Reflexive Points of Relations

Assume a partially ordered set (S, ≤) and a relation R on S. We consider various sets of conditions in order to determine whether they ensure the existence of a least reflexive point, that is, a least x such that xRx. This is a generalization of the problem of determining the least fixed point of a function and the conditions under which it exists. To motivate the investigation we first present a theorem by Cai and Paige giving conditions under which iterating R from the bottom element necessarily leads to a minimal reflexive point; the proof is by a concise relation-algebraic calculation. Then, we assume a complete lattice and exhibit sufficient conditions, depending on whether R is partial or not, for the existence of a least reflexive point. Further results concern the structure of the set of all reflexive points; among other results we give a sufficient condition that these form a complete lattice, thus generalizing Tarski’s classical result to the nondeterministic case.This research is supported by a grant from NSERC (Natural Sciences and Engineering Research Council of Canada).     

Wang tilings and distributed verification on anonymous torus networks

Considern ² processors arranged in ann × n torus network in which each processor is connected by direct communication channels with its four neighbours. This paper studies the followingverification problem on anonymousn × n torus networks: verify whether the network is oriented; that is, verify whether there is an agreement, among all processors, on a consistent channel labelling. The problem is to be solved by a distributed algorithm executed by the processors themselves. If processors can label their channels arbitrarily, then there are network labellings that are not oriented but, to the processors, are indistinguishable from ones that are oriented. Hence there is no deterministic distributed verification algorithm. However, a verification algorithm does exist if the initial labellings are suitably restricted. We describe the restrictions placed on the initial labellings by subsets of the permutation groupS ₄. We show that the existence of an algorithm for verification is equivalent to the existence of certain tilings of the torus with Wang tiles. Using this equivalence, we have determined the existence of a distributed algorithm for the verification problem for alln × n torus networks for an important class of restrictions, the subgroups ofS ₄.     

Subgraphs of 4-Regular Planar Graphs

We shall present an algorithm for determining whether or not a given planar graph H can ever be a subgraph of a 4-regular planar graph. The algorithm has running time O(|H|^2.5) and can be used to find an explicit 4-regular planar graph G⊃H if such a graph exists. It shall not matter whether we specify that H and G must be simple graphs or allow them to be multigraphs.     

Algorithmical determination of the topology of a real algebraic surface

We present an algorithm to compute the topology of a non-singular real algebraic surface S in RP³, that is the number of its connected components and a topological model for each of them. Our strategy consists in computing the Euler characteristic of each connected component by means of a Morse-type investigation of S or of a suitably constructed compact affine surface. This procedure can be used to determine the topological type of an arbitrary non-singular surface; in particular it extends an existing algorithm applicable only to surfaces disjoint from a line.     

Automatic Detection of Words Associations in Texts Based on Joint Distribution of Words Occurrences

In this article, we propose a novel approach for measuring word association based on the joint occurrences distribution in a text. Our approach relies on computing a sum of distances between neighboring occurrences of a given word pair and comparing it with a vector of randomly generated occurrences. The idea behind this assumption is that if the distribution of co‐occurrences is close to random or if they tend to appear together less frequently than by chance, such words are not semantically related. We devise a distance function S that evaluates the words association rate. Using S, we build a concept tree, which provides a visual and comprehensive representation of keywords association in a text. In order to illustrate the effectiveness of our algorithm, we apply it to three different texts, showing the consistency and significance of the obtained results with respect to the semantics of documents. Finally, we compare the results obtained by applying our proposed algorithm with the ones achieved by both human experts and the co‐occurrence correlation method. We show that our method is consistent with the experts' evaluation and outperforms with respect to the co‐occurrence correlation method.     

计算线段集合的相交直线及其最大存在范围

对给定的一个直线段集合S研究求与S中所有直线段都相交的直线的问题.设S中的线段满足一定的不交性假设,算法可回答是否存在与S中所有线段均相交的直线的问题.如果该直线存在,则求出这样的直线的最大存在范围——位于该范围内的每条直线都与S中的所有直线段相交.该算法的时间复杂性为O(n~*log,n),应用背景是模式匹配等领域.     

A competent memetic algorithm for complex scheduling

We face the job shop scheduling problem with sequence dependent setup times and makespan minimization by memetic algorithm. This algorithm combines a classic genetic algorithm with a local searcher. The performance of the local searcher relies on the combination of a tabu search algorithm with a neighborhood structure termed N ^S that are thoroughly described and analyzed. Also, two evolution models are considered: Lamarckian and Baldwinian evolution. We report results from an experimental study across conventional benchmark instances showing that the proposed algorithm outperforms the current state-of-the-art methods and that Lamarckian evolution is better than Baldwinian evolution.     

A vertex-first parametric algorithm for polyhedron blending

This paper enhances the conventional parametric algorithms for polyhedron blending, by strategically inverting the edges-first approach to vertex-first, so that matching the vertex blending surface (using a triangular or tensor product Bézier surface, or an S-patch) with the edge blending surfaces (generated by Hartmann method) becomes essentially easier. Based on a study of cross boundary derivatives (those of S-patches are deduced herein), G^g-continuity between all the above surfaces and the primary planar faces is achieved by a novel trick as a first step: assigning the vertex, some edge points and some face points to be the proper control points. This still leaves enough free parameters usable for changing the blending configuration. The new algorithm is illustrated with two practical examples involving miscellaneous vertices up to 6-edge convex–concave.     

A REVIEW OF TREE CONVEX SETS TEST

A collection of sets may have some interesting properties which help identify efficient algorithms for constraint satisfaction problems and combinatorial auction problems. One of the properties is tree convexity. A collection S of sets is tree convex if we can find a tree T whose nodes are the union of the sets of S and each set of S is the nodes of a subtree of T . This concept extends that of row convex sets each of which is an interval over a total ordering of the elements of the union of these sets. An interesting problem is to find efficient algorithms to test whether a collection of sets is tree convex. It is not known before if there exists a linear time algorithm for this test. In this paper, we review the materials that are the key to a linear algorithm: hypergraphs, a characterization of tree convex sets and the acyclic hypergraph test algorithm. Some typos in the original paper of the acyclicity test are corrected here. Some experiments show that the linear algorithm is significantly faster than a well‐known existing algorithm.     

Algorithms for derivation of structurally stable Hamiltonian signed graphs

A graph S_p,q,n refers to a signed graph with p nodes and q edges with n being the number of negative edges. We introduce two theorems to facilitate identification of the complete set of balanced signed graph configurations for any p-node Hamiltonian signed graph in terms of p, q and n. This allows for the development of computational procedures to efficiently determine the structural stability of a signed graph. This is potentially useful for the planning and analysis of complex situations or scenarios which can be depicted as signed graphs. Through the application of the theorems, the state of balance of a signed graph structure or its affinity towards balance can be determined in a more time-efficient manner compared to any explicit enumeration algorithm.     

Polynomial time algorithms for sentences over number fields

We call a sentence if and only if ρ is logically equivalent to a sentence of the form xyψ(x, y), where ψ(x, y) is a quantifier free formula constructed with logical and arithmetical symbols. Now let be a sentence in conjunctive or disjunctive normal form. We show that given an arbitrary algebraic number field K there is a polynomial time algorithm to decide whether is true in K or not. We also show that ther are polynomial time algorithms to decide whether or not is true in every algebraic number field or every radical extension field of Q.     

Eigenschaften der von linearen Automaten erkennbaren Worte

Summary The paper investigates the set of words accepted by a linear sequential machine M and the algebraic structure of this set. If M is nonsingular a strong relationship exists between this set and the transition group of the accepting automaton. Thus the algebraic structure of this group is used to describe some properties of the set of accepted words. If M is nilpotent, in addition, an algorithm is given which in a direct way generates just the words accepted by M.     

Optimal Adaptive Broadcasting with a Bounded Fraction of Faulty Nodes

We consider broadcasting among n processors, f of which can be faulty. A fault-free processor, called the source, holds a piece of information which has to be transmitted to all other fault-free processors. We assume that the fraction f/n of faulty processors is bounded by a constant γ<1 . Transmissions are fault free. Faults are assumed to be of the crash type: faulty processors do not send or receive messages. We use the whispering model: pairs of processors communicating in one round must form a matching. A fault-free processor sending a message to another processor becomes aware of whether this processor is faulty or fault free and can adapt future transmissions accordingly. The main result of the paper is a broadcasting algorithm working in O( log n) rounds and using O(n) messages of logarithmic size, in the worst case. This is an improvement of the result from [17] where O ((log n) ² ) rounds were used. Our method also gives the first algorithm for adaptive distributed fault diagnosis in O( log n) rounds. Received May 1997; revised May 1998.