Search

Abstract: This paper presents an object-oriented architecture for structural design software. The architecture’s novel features are the representation of an artifact with distinct levels of idealization, a hierarchy of classification within each of these levels, and the appropriate separation of software components. These enable seamless integration of geometric modeling and structural analysis in an interactive environment, extensibility of modeling and analysis capabilities, and integration of interactive multi-objective optimization. The paper presents a design environment implemented on the basis of the architecture, and demonstrates the benefits of refocusing engineering software from analysis to design. [Copyright &y& Elsevier]

Abstract: Faugère’s algorithm is one of the fastest algorithms to compute Gröbner bases. It uses two criteria namely the criterion and the IsRewritten criterion to detect the useless critical pairs (see Faugère (2002) ). The IsRewritten criterion has been used in the algorithm, but it has not been explicitly declared in the related paper. In this paper, we give first a complete proof for the IsRewritten criterion and then using a signature structure on Buchberger’s algorithm, we apply this criterion on Buchberger’s algorithm. We have implemented a new algorithm (based on the above results) in Maple to compute a Gröbner basis of a general ideal and we evaluate its performance via some examples. [Copyright &y& Elsevier]

Abstract: The 2-interval pattern problem, introduced in [Stéphane Vialette, On the computational complexity of 2-interval pattern matching problems Theoret. Comput. Sci. 312 (2–3) (2004) 223–249], models general problems with biological structures such as protein contact maps and macroscopic describers of secondary structures of ribonucleic acids. Given a set of 2-intervals and a model , the problem is to find a maximum cardinality subset of such that any two 2-intervals in satisfy , where is a subset of relations on disjoint 2-intervals: precedence , nest , and cross . The problem left unanswered at present is that of whether there is a polynomial time solution for the 2-interval pattern problem, when and all the support intervals of are disjoint. In this paper, we present a reduction from the clique problem to show that, in this case, the problem is NP-hard. The disjoint 2-interval pattern matching problem is to decide whether a disjoint 2-interval pattern (called the pattern) is a substructure of another disjoint 2-interval pattern (called the target). In general, the problem is NP-hard, but when there are restrictions on the form of the pattern, the problem can, in some cases, be solved in polynomial time. In particular, a polynomial time algorithm has been proposed (Gramm, WABI 2004 and IEEE/ACM TCBB 2004) for the case where the patterns are so-called crossing contact maps. In this paper we show that the problem is actually NP-hard and point out an error in the analysis of the above algorithm. 1 [1] The second part of this paper appeared in WABI’2006. [Copyright &y& Elsevier]

Abstract: Upward-closed sets of integer vectors enjoy the merit of having a finite number of minimal elements, which is behind the decidability of a number of Petri net related problems. In general, however, such a finite set of minimal elements may not be effectively computable. In this paper, we develop a unified strategy for computing the sizes of the minimal elements of certain upward-closed sets associated with Petri nets. Our approach can be regarded as a refinement of a previous work by Valk and Jantzen (in which a necessary and sufficient condition for effective computability of the set was given), in the sense that complexity bounds now become available provided that a bound can be placed on the size of a witness for a key query. The sizes of several upward-closed sets that arise in the theory of Petri nets as well as in backward-reachability analysis in automated verification are derived in this paper, improving upon previous decidability results shown in the literature. [Copyright &y& Elsevier]

Abstract: In this paper a proof outline logic is introduced for the partial correctness of multi-threaded object-oriented programs like in Java. The main contribution is a generalization of the Owicki& Gries proof method for shared-variable concurrency to dynamic thread creation. This paper also provides a formal justification of this generalization in terms of soundness and completeness proofs. [Copyright &y& Elsevier]

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

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

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

Several sampling criteria had been proposed for C 2 smooth surfaces such that the reconstructed meshes from point samples are homeomorphic to the original surfaces. In this paper, based on a widely used sample criterion, we present proofs that give the upper and lower bounds of mesh quality (in terms of several triangle aspect ratios) for the reconstructed mesh. To make the proposed theoretical bounds useful in practical applications with real-world point data, we propose a novel mesh reconstruction method that works in three steps: (1) approximate Delaunay mesh reconstruction; (2) point data upsampling and (3) hole filling. Finally, examples are presented, which illustrate the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Abstract: Minesweeper is a popular single player game. Various strategies have been suggested in order to improve the probability of winning the game. In this paper, we present an optimal strategy for playing Minesweeper on a graph when it is known that exactly one cell is mined. [Copyright &y& Elsevier]

Abstract: Recently, Durante and Jaworski (2008) [6] have proved that the class of absolutely continuous copulas with a given diagonal section is non-empty in case that the diagonal function is such that the set of points where this coincides with the identity function has null-measure. In this paper, we show that if we consider sub-diagonals (or super-diagonals), then the framework changes. Concretely, for each sub-diagonal function there exists an absolutely continuous copula having this function as sub-diagonal section. [Copyright &y& Elsevier]

Abstract: In this paper we obtain new conditions for the global existence and boundedness of solutions for nonlinear second-order equations of the form where is a real constant. The results are applicable to well-known Emden–Fowler and Lienard type equations. An illustrative example is also provided. [Copyright &y& Elsevier]

Abstract: This paper describes the theoretical principles of a verification method with proof scores in the CafeOBJ algebraic specification language. The verification method focuses on specifications with conditional equations and realizes systematic theorem proving (or interactive verification). The method is explained using a simple but instructive example, and the necessary theoretical foundations, which justify every step of the verification, are described with precise mathematical definitions. Some important theorems that result from the definitions are also presented. [Copyright &y& Elsevier]

Abstract: The stability of the stochastic 2-D systems in the sense is studied and some sufficient conditions about the stability are also given in this paper. [Copyright &y& Elsevier]

Abstract: Axiomatization of Physics (and science in general) has many drawbacks that are correctly criticized by opposing philosophical views of science. This paper shows that, by giving formal proofs a more prominent role in the formalization, many of the drawbacks can be solved and many of the opposing views are naturally conciliated. Moreover, this approach allows, by means of proof theory, to open new conceptual bridges between the disciplines of Physics and Computer Science. [Copyright &y& Elsevier]

Abstract: In this paper we continue the coalgebraization of the structure of multilattice. Specifically, we introduce a coalgebraic characterization of the notion of finitary multi (semi) lattice, a generalization of that of semilattice which arises naturally in several areas of computer science and provides the possibility of handling non-determinism. [Copyright &y& Elsevier]

Abstract: In this paper, we present a new method for fuzzy risk analysis based on the proposed new fuzzy ranking method for ranking generalized fuzzy numbers with different left heights and right heights. First, we present a fuzzy ranking method for ranking generalized fuzzy numbers with different left heights and right heights. The proposed method considers the areas of the positive side, the areas of the negative side and the centroid values of generalized fuzzy numbers as the factors for calculating the ranking scores of generalized fuzzy numbers with different left heights and right heights. It can overcome the drawbacks of the existing fuzzy ranking methods. Then, we propose a new method for fuzzy risk analysis based on the proposed fuzzy ranking method, where the evaluating values are represented by generalized fuzzy numbers. The proposed fuzzy risk analysis method provides us with a useful way for fuzzy risk analysis based on generalized fuzzy numbers with different left heights and right heights. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce and study polynomial graph transformability as a graph-transformational counterpart of the satisfiability problem of the propositional calculus. [Copyright &y& Elsevier]

Abstract: In this paper, we continue our study on state complexity of combined operations. We study the state complexities of , , , and for regular languages , . We obtain the exact bounds for these combined operations and show that the bounds are different from the mathematical compositions of the state complexities of their component individual operations. [Copyright &y& Elsevier]

Abstract: Partial words, or sequences over a finite alphabet that may have do-not-know symbols or holes, have been recently the subject of much investigation. Several interesting combinatorial properties have been studied such as the periodic behavior and the counting of distinct squares in partial words. In this paper, we extend the three-squares lemma on words to partial words with one hole. This result provides special information about the squares in a partial word with at most one hole, and puts restrictions on the positions at which periodic factors may occur, which is in contrast with the well known periodicity lemma of Fine and Wilf. [Copyright &y& Elsevier]

Abstract: Hybrid strategy, which generalizes a specific single-label algorithm while one or two data decomposition tricks are applied implicitly or explicitly, has become an effective and efficient tool to design and implement various multi-label classification algorithms. In this paper, we extend traditional binary support vector machine by introducing an approximate ranking loss as its empirical loss term to build a novel support vector machine for multi-label classification, resulting into a quadratic programming problem with different upper bounds of variables to characterize label correlation of individual instance. Further, our optimization problem can be solved via combining one-versus-rest data decomposition trick with modified binary support vector machine, which dramatically reduces computational cost. Experimental study on ten multi-label data sets illustrates that our method is a powerful candidate for multi-label classification, compared with four state-of-the-art multi-label classification approaches. [Copyright &y& Elsevier]

Abstract: Several methods have been developed to construct -free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu). All these automata can be obtained with quadratic time complexity, thus, the comparison criterion is usually the size of the resulting automaton. The methods that obtain the smallest automata (although, for general expressions, they are not comparable), are the follow and the partial derivatives methods. In this paper, we propose another method to obtain a -free automaton from a regular expression. The number of states of the automata we obtain is bounded above by the size of both the partial derivatives automaton and of the follow automaton. Our algorithm also runs with the same time complexity of these methods. [Copyright &y& Elsevier]

Abstract: Last few years have witnessed the development of various multi-objective evolutionary algorithms since they allow the generation of the overall Pareto front for multi-objective optimizations. With the problems in the real-world becoming more and more complex, however, no reported work in the literature focuses on the high-dimensional objective optimizations (HOPs). In this paper, we propose an evolutionary algorithm named HOEA (high-dimensional objective evolutionary algorithm) for HOPs. By adopting the concept of nonlinear definition for optimizing object, HOPs can be solved by HOEA, while the well-known multi-objective evolutionary algorithms work poorly on HOPs. We further analyze the nonlinear dynamic properties of HOEA on the basis of martingale theoretical framework. The theoretical results indicate that this new algorithm is indeed capable of achieving convergence. We also conduct experiments on HOEA with two representative test instances. The experimental results either confirm our theoretical results or show that the proposed algorithm is efficient and effective for HOPs. [Copyright &y& Elsevier]

Abstract: A widely accepted method to specify (possibly infinite) behaviour is to define it as the solution, in some process algebra, of a recursive specification, i.e., a system of recursive equations over the fundamental operations of the process algebra. The method only works if the recursive specification has a unique solution in the process algebra; it is well-known that guardedness is a sufficient requirement on a recursive specification to guarantee a unique solution in any of the standard process algebras. In this paper we investigate to what extent guardedness is also a necessary requirement to ensure unique solutions. We prove a theorem to the effect that all unguarded recursive specifications over have infinitely many solutions in the standard models for . In contrast, we observe that there exist recursive specifications over , necessarily involving parallel composition, that have a unique solution, or finitely many solutions in the standard models for . [Copyright &y& Elsevier]

Abstract: An -labeling of a graph is defined as a function from the vertex set into the nonnegative integers such that for any two vertices , , if and if , where is the distance between and in . The -labeling number of is the smallest number such that has an -labeling with . In this paper, we consider the graph formed by the skew product and converse skew product of two graphs, and give new upper bounds of the -labeling number, which improves the upper bounds obtained by Shao and Zhang [Z.D. Shao, D. Zhang, Improved upper bounds on the -labeling of the skew and converse skew product graphs, Theoret. Comput. Sci. 400 (2008) 230–233] in many cases. [Copyright &y& Elsevier]

Abstract: The PAC-learning model is distribution-independent in the sense that the learner must reach a learning goal with a limited number of labeled random examples without any prior knowledge of the underlying domain distribution. In order to achieve this, one needs generalization error bounds that are valid uniformly for every domain distribution. These bounds are (almost) tight in the sense that there is a domain distribution which does not admit a generalization error being significantly smaller than the general bound. Note however that this leaves open the possibility to achieve the learning goal faster if the underlying distribution is “simple”. Informally speaking, we say a PAC-learner is “smart” if, for a “vast majority” of domain distributions , does not require significantly more examples to reach the “learning goal” than the best learner whose strategy is specialized to . In this paper, focusing on sample complexity and ignoring computational issues, we show that smart learners do exist. This implies (at least from an information-theoretical perspective) that full prior knowledge of the domain distribution (or access to a huge collection of unlabeled examples) does (for a vast majority of domain distributions) not significantly reduce the number of labeled examples required to achieve the learning goal. [Copyright &y& Elsevier]

Abstract: This paper studies morphological connected operators. Particularly, it focuses on an adjacency constraint, as well as on the so-called set levelings. Some important findings are reported in this work. First, the relationships between the so-called adjacency stable operators and set levelings are investigated, and an equivalence is established. This permits to apply some properties to the related operator class. Second, the implications and limits of a property presented elsewhere that states that certain connected operators can be expressed as a sequential composition of an opening and a closing (and vice-versa) based on markers are treated. Then, a commutative property that involves alternated attribute filters is presented. In addition, other related expressions are discussed. [Copyright &y& Elsevier]

Abstract: To better understand the numerous solutions related to watershed transform (WT), this paper shows the relationships between some discrete definitions of the WT, especially those based on image foresting transform (IFT) with/without lexicographic cost function, topographic distance (TD), local condition (LC), flooding (F), and minimum spanning forest (MSF). Some of these paradigms allow multiple solutions. The tie-zone (TZ) transform returns a unique solution from a set of multiple solutions of a given WT. We demonstrate that the TZ transform applied to the IFT-WT includes all the solutions predicted by the other paradigms. More precisely, the watershed line of TD-WT and F-WT are contained in the TZ of the IFT-WT, while the catchment basins of TD-WT or F-WT contain the basins of the TZ-IFT-WT. In addition, the TD-WT can be seen as the tie-zone transform of the LC-WT. Furthermore, any solution of LC-WT or MSF-WT is also solution of the IFT-WT. Finally, MSF-WT and IFT-WT have the same tie-zone transform. [Copyright &y& Elsevier]

Abstract: In this paper we establish the stability of the Pexiderized Goła̧b–Schinzel functional equation , under the condition that exists and is non-zero. [Copyright &y& Elsevier]

Abstract: In the first part of this paper we generalize results on common fixed points in ordered cone metric spaces obtained by I. Altun and G. Durmaz [I. Altun, G. Durmaz, Some fixed point theorems on ordered cone metric spaces, Rend. Circ. Mat. Palermo, 58 (2009) 319–325] and I. Altun, B. Damnjanović and D. Djorić [I. Altun, B. Damnjanović, D. Djorić, Fixed point and common fixed point theorems on ordered cone metric spaces, Appl. Math. Lett. (2009) doi:10.1016/j.aml.2009.09.016] by weakening the respective contractive condition. Then, the notions of quasicontraction and -quasicontraction are introduced in the setting of ordered cone metric spaces and respective (common) fixed point theorems are proved. In such a way, known results on quasicontractions and -quasicontractions in metric spaces and cone metric spaces are extended to the setting of ordered cone metric spaces. Examples show that there are cases when new results can be applied, while old ones cannot. [Copyright &y& Elsevier]

Abstract: It is well known that any metric space is paracompact. As a generalization of metric spaces, cone metric spaces play very important role in fixed point theory, computer science, and some other research areas as well as in general topology. In this paper, a theorem which states that any cone metric space with a normal cone is paracompact is proved. [Copyright &y& Elsevier]

Abstract: This paper presents methods for efficient recovery of accurate binocular disparity estimates in the vicinity of 3D surface discontinuities. Of particular concern are methods that impact coarse-to-fine, local block-based matching as it forms the basis of the fastest and the most resource efficient stereo computation procedures. A novel coarse-to-fine refinement procedure that adapts match window support across scale to ameliorate corruption of disparity estimates near boundaries is presented. Extensions are included to account for half-occlusions and colour uniformity. Empirical results show that incorporation of these advances in the standard coarse-to-fine, block matching framework reduces disparity errors by more than a factor of two, while performing little extra computation, preserving low complexity and the parallel/pipeline nature of the framework. Moreover, the proposed advances prove to be beneficial for CTF global matchers as well. [Copyright &y& Elsevier]

Abstract: Image denoising methods based on gradient dependent regularizers such as Rudin et al.’s total variation (TV) model often suffer the staircase effect and the loss of fine details. In order to overcome such drawbacks, this paper presents an adaptive total variation method based on a new edge indicator, named difference curvature, which can effectively distinguish between edges and ramps. With adaptive regularization and fidelity terms, the new model has the following properties: at object edges, the regularization term is approximate to the TV norm in order to preserve the edges, and the weight of the fidelity term is large in order to preserve details; in flat and ramp regions, the regularization term is approximate to the L2 norm in order to avoid the staircase effect, and the weight of the fidelity term is small in order to strongly remove the noise. Comparative results on both synthetic and natural images demonstrate that the new method can avoid the staircase effect and better preserve fine details. [Copyright &y& Elsevier]

Abstract: This paper studies online scheduling of unit length jobs on a parallel batching machine with the help of lookahead. The objective is to maximize the number of early jobs. Denote by the size of each batch with in the unbounded batching and in the bounded batching. In the lookahead model, at a time instant , an online algorithm can foresee all jobs that will arrive in the time segment . When , we show that a simple greedy online algorithm (independent of the value of ) has a best possible competitive ratio of , where is the number of jobs. This means that lookahead is useless when . When , we establish the upper bounds (for ) and (for ) of competitive ratios, and provide an online algorithm of competitive ratios (for ) and (for ). [Copyright &y& Elsevier]

Abstract: Acyclic coloring problem is a specialized problem that arises in the efficient computation of Hessians. A proper edge coloring of a graph is called acyclic if there is no -colored cycle in . The acyclic edge chromatic number of is the least number of colors in an acyclic edge coloring of . Alon et al. conjectured that . In this paper, we consider the sufficient conditions for the planar graphs satisfying and . [Copyright &y& Elsevier]

Abstract: The concept of an automaton group generalizes easily to semigroups, and the systematic study of this area is beginning. This paper aims to contribute to that study. The basic theory of automaton semigroups is briefly reviewed. Various natural semigroups are shown to arise as automaton semigroups. The interaction of certain semigroup constructions with the class of automaton semigroups is studied. Semigroups arising from Cayley automata are investigated. Various open problems and areas for further research are suggested. [Copyright &y& Elsevier]

Abstract: The paper is devoted to demonstrating a randomized algorithm for determining a dominating set in a given graph having a maximum degree of five. The algorithm follows the Las Vegas technique. Furthermore, the concept of a 2-separated collection of subsets of vertices in graphs is used. The suggested algorithm is based on a condition of the upper bound of the cardinality of a local dominating set. If the condition is not satisfied, then the algorithm halts with an appropriate message. Otherwise, the algorithm determines the dominating set. The given algorithm is considered a polynomial-time approximation one. [Copyright &y& Elsevier]

Abstract: Let be a simple graph without isolated vertices. A vertex set is a paired-dominating set if every vertex in has a neighbor in and the induced subgraph has a perfect matching. In this paper, we investigate the approximation hardness of paired-domination in graphs. For weighted paired-domination, an approximation algorithm in general graphs and an exact dynamic programming style algorithm in trees are also given. [Copyright &y& Elsevier]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

Abstract: Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. A splicing system is defined by giving an initial set and a set of rules. Some unanswered questions are related to the computational power of circular splicing systems. In particular, a still open question is to find a characterization of circular languages generated by finite circular splicing systems (i.e., circular splicing systems with both and finite sets). In this paper we introduce a special class of the latter systems named marked systems. We prove that a marked system generates a regular circular language if and only if satisfies a special (decidable) property. As a consequence, we are able to characterize the structure of these regular circular languages. [Copyright &y& Elsevier]

Abstract: Let denote the number of -words of the form  with gap and denote the number of -words of the form  with length and gap , where is the length of the word . [S. Brlek, A. Ladouceur, A note on differentiable palindromes, Theoret. Comput. Sci. 302 (2003) 167–178] proved that -palindromes are characterized by the left palindromic closure of the prefixes of the well-known Kolakoski sequences and revealed an interesting perspective for understanding some of the conjectures. In fact, they found all infinite -palindromes and established for all , where is the set of positive integers. [Y.B. Huang, About the number of -words of form , Theoret. Comput. Sci. 393 (2008) 280–286] obtained for all and , and gave all -words of the form with gap less than 5, which imply , and . In this paper, we prove the following intriguing results: (1) If and then the first and last letters of the word are the same; (2) ; (3) For every positive integer , there exists a positive integer such that for all , if then if is odd and if is even, which would help us understand better the complexity of finite -words of the form . Moreover, we provide all twenty eight -words of the form . [Copyright &y& Elsevier]

Abstract: The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks can be viewed as the subclasses of the k-ary n-cubes include the cycle, the torus and the hypercube. A bipartite graph is Hamiltonian laceable if there exists a Hamiltonian path joining every two vertices which are in distinct partite sets. A bipartite graph G is strongly Hamiltonian laceable if it is Hamiltonian laceable and there exists a path of length N − 2 joining each pair of vertices in the same partite set, where N =|V(G)|. We prove that the k-ary n-cube is strongly Hamiltonian laceable for k is even and n ⩾2. [Copyright &y& Elsevier]

Abstract: In this paper we generalize the notion of an -symmetric word, from an antimorphic involution, to an arbitrary involution as follows: a nonempty word is said to be -symmetric if for some words . We propose the notion of -twin-roots of an -symmetric word . We prove the existence and uniqueness of the -twin-roots of an -symmetric word, and show that the left factor and right factor of any factorization of as , can be expressed in terms of the -twin-roots of . In addition, we show that for any involution , the catenation of the -twin-roots of equals the primitive root of . We also provide several characterizations of the -twin-rots of a word, for being a morphic or antimorphic involution. [Copyright &y& Elsevier]

Abstract: Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that allow the representation of conflicting signals or alternative evolutionary histories in a single diagram. Recently the Quartet-Net or “QNet” method was introduced, a method for computing a special kind of phylogenetic network called a split network from a collection of weighted quartet trees (i.e. phylogenetic trees with 4 leaves). This can be viewed as a quartet analogue of the distance-based Neighbor-Net (NNet) method for constructing outer-labeled planar split networks. In this paper, we prove that QNet is a consistent method, that is, we prove that if QNet is applied to a collection of weighted quartets arising from a circular split weight function, then it will return precisely this function. This key property of QNet not only ensures that it is guaranteed to produce a tree if the input corresponds to a tree, and an outer-labeled planar split network if the input corresponds to such a network, but also provides the main guiding principle for the design of the method. [Copyright &y& Elsevier]

Abstract: This paper approaches the combinatorial problem of Thue freeness for partial words. Partial words are sequences over a finite alphabet that may contain a number of “holes”. First, we give an infinite word over a three-letter alphabet which avoids squares of length greater than two even after we replace an infinite number of positions with holes. Then, we give an infinite word over an eight-letter alphabet that avoids longer squares even after an arbitrary selection of its positions are replaced with holes, and show that the alphabet size is optimal. We find similar results for overlap-free partial words. [Copyright &y& Elsevier]

Abstract: Coordination languages and models promote the idea of separating computation and interaction aspects. As for traditional concurrency models, the question of safely replacing an agent by another one in any interacting context naturally appears. This paper proposes two tools to answer that question. On the one hand, a fully abstract semantics allows us to identify two processes which behave similarly in any context. On the other hand, a refinement theory allows us to compare processes that appear to be different in view of the fully abstract semantics but which satisfy the substitutability property: if the implementation refines the specification and if is deadlock free, for some context , then is also deadlock free. Both theories are novel, are exposed in the context of our timed coordination languages but may actually be transposed in the context of almost any data-driven coordination language. [Copyright &y& Elsevier]

Abstract: There is an impedance mismatch between message-passing concurrency and virtual machines, such as the JVM. VMs usually map their threads to heavyweight OS processes. Without a lightweight process abstraction, users are often forced to write parts of concurrent applications in an event-driven style which obscures control flow, and increases the burden on the programmer. In this paper we show how thread-based and event-based programming can be unified under a single actor abstraction. Using advanced abstraction mechanisms of the Scala programming language, we implement our approach on unmodified JVMs. Our programming model integrates well with the threading model of the underlying VM. [Copyright &y& Elsevier]

Abstract: This paper studies the delay-interval-dependent stability of the equilibrium point of a general class of recurrent neural networks with time-varying delays that may exclude zero. By constructing the appropriate Lyapunov–Krasovskii functional, two sufficient conditions ensuring the global asymptotic stability of the equilibrium point of such networks with interval-time-varying delays are established. The present results, together with two numerical examples, show that the equilibrium points of the considered networks may be globally asymptotically stable in some delay interval(s) even though the equilibrium points of the corresponding delay-free recurrent neural networks are not globally asymptotically stable. [Copyright &y& Elsevier]

Abstract: Robust exponential stability for interval Cohen–Grossberg neural networks with time varying delay has received increasing interest in recent years. In this paper, some new criteria are derived using linear matrix inequality, matrix norm and Halanay inequality techniques. Compared with the existing results, these new criteria are not conservative and are convenient to check. Three numerical examples are used to show the effectiveness of the obtained results. [Copyright &y& Elsevier]

Abstract: The Longest Common Subsequence (LCS) is a well studied problem, having a wide range of implementations. Its motivation is in comparing strings. It has long been of interest to devise a similar measure for comparing higher dimensional objects, and more complex structures. In this paper we study the Longest Common Substructure of two matrices and show that this problem is -hard. We also study the Longest Common Subforest problem for multiple trees including a constrained version, as well. We show -hardness for unordered trees in the constrained LCS. We also give polynomial time algorithms for ordered trees and prove a lower bound for any decomposition strategy for trees. [Copyright &y& Elsevier]