Search

In this paper, we study the link between finite-dimensional Zinbiel algebras and combinatorial structures or (pseudo)digraphs determining which configurations are associated with those algebras. Some properties of Zinbiel algebras that can be read from their associated combinatorial structures are studied. We also analyze the isomorphism classes for each configuration associated with these algebras providing a new method to classify them and we compare our results with the current classifications of 2- and 3-dimensional Zinbiel algebras. We also obtain the 3-vertices combinatorial structures associated with such algebras. In order to complement the theoretical study, we have designed and performed the implementation of an algorithm which constructs and draws the (pseudo)digraph associated with a given Zinbiel algebra and, conversely, another procedure to test if a given combinatorial structure is associated with some Zinbiel algebra. [ABSTRACT FROM AUTHOR]

Aiming at the limitations of the algorithm of interval grey number, an improved algorithm is introduced in this paper. Firstly, the limitations of the algorithm of interval grey number are analyzed, such as irreversibility, virtual amplification, and non-closure. Then, according to the "using minimum information principle" and the algorithm of a real number and its internal requirements. an improved algorithm of interval grey number is given, and some properties of the improved algorithm of interval grey number are discussed. Finally, some examples are given to verify the effectiveness of the new algorithm. The results show that the improved algorithm of interval grey number overcomes the limitations Of tile existing algorithm, and the calculation examples show that the improved algorithm is feasible and effective. The research results further enrich the grey system theory and provide a theoretical basis for studying grey algebra. [ABSTRACT FROM AUTHOR]

In this paper, we focus on the link between evolution algebras and (pseudo)digraphs. We study some theoretical properties about this association and determine the properties of the (pseudo)digraphs associated with each type of evolution algebras. We also analyze the isomorphism classes for each configuration associated with these algebras providing a new method to classify them, and we compare our results with the current classifications of two‐ and three‐dimensional evolution algebras. In order to complement the theoretical study, we have designed and performed the implementation of an algorithm, which constructs and draws the (pseudo)digraph associated with a given evolution algebra and another procedure to study the solvability of a given evolution algebra. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of finding the generators of the solution space for a system of inequalities A ⊗ x ≥ x in max-plus algebra. It provides an improved algorithm which can be used to find a smaller set of generators for the solution space by skipping a large number of invalid generators. [ABSTRACT FROM AUTHOR]

In this paper we give an algorithm to generate all distributions of distinguishable objects to bins without repetition. Our algorithm generates each distribution in constant time. To the best of our knowledge, our algorithm is the first algorithm which generates each solution in O(1) time in the ordinary sense. As a byproduct of our algorithm, we obtain a new algorithm to enumerate all multiset partitions when the number of partitions is fixed and the partitions are numbered. In this case, the algorithm generates each multiset partitions in constant time (in the ordinary sense). Finally, we extend the algorithm to the case when the bins have priorities associated with them. Overall space complexity of the algorithm is O(mklgn), where there are m bins and the objects fall into k different classes. In a companion paper, the generation of all distributions of identical objects to bins is also considered. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider completely generalized nonlinear quasi-variational-like inclusions in Banach spaces and propose an Ishikawa type iterative algorithm for computing their approximate solutions by applying the new notion of -proximal mapping given in [R. Ahmad, A.H. Siddiqi, Z. Khan, Proximal point algorithm for generalized multi-valued nonlinear quasi-variational-like inclusions in Banach spaces, Appl. Math. Comput. 163 (2005) 295–308]. We prove that the approximate solutions obtained by the proposed algorithm converge to the exact solution of our quasi-variational-like inclusions. The results presented in this paper extend and improve the corresponding results of [R. Ahmad, A.H. Siddiqi, Z. Khan, Proximal point algorithm for generalized multi-valued nonlinear quasi-variational-like inclusions in Banach spaces, Appl. Math. Comput. 163 (2005) 295–308; X.P. Ding, F.Q. Xia, A new class of completely generalized quasi-variational inclusions in Banach spaces, J. Comput. Appl. Math. 147 (2002) 369–383; N.J. Huang, Generalized nonlinear variational inclusions with non-compact valued mappings, Appl. Math. Lett. 9(3) (1996) 25–29; A. Hassouni, A. Moudafi, A perturbed algorithm for variational inclusions, J. Math. Anal. Appl. 185(3) (1994) 706–712]. Some special cases are also discussed. [Copyright &y& Elsevier]

In this paper, by using the theories and methods of mathematical analysis and computer algebra, a new algorithm of symbolic integral was established, a new Maple procedure myint for it was established, too. And it was applied to the automatic proving the mean-value theorems for derivatives. The results indicated that the algorithm of symbolic integral had been established in this paper had advantage of simple idea, excellent property for operation and powerful competence. This would be useful for the problem of solving differential equations, automatic proving some mathematical theorems, and so on. [Copyright &y& Elsevier]

The aim of this paper is to exploit the algorithms of paper Experimental Math. 8 (1999) in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts.The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents.The idea of the second part is that an irreducible polynomial over Z might be reducible over Z /pZ for certain integer p. So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent over Z. [Copyright &y& Elsevier]

This paper discusses a mathematical concept of language that models both artificial and natural languages and thus provides a framework for a unified language processing methodology. This concept of a language is regarded as a communication tool that allows language users to develop knowledges, while interacting with their universe of discourse, and to communicate with each other, while exchanging knowledges. Criteria for consistent usage of a language are established using a Galois connection between language syntax and language semantics. Solutions to ambiguity, paraphrase, attitude, and other problems concerning the relationship between syntax and semantics are addressed. A general schema for language specification is introduced and algorithms that perform language generation and language analysis are discussed as universal tools defined by the specification schema. Language transformations performed by various kinds of translators are examined and correctness criteria of these translators are defined using the language Galois connection.The paper is structured as follows: Section 1 introduces the framework and justifies the necessity of a unified methodology for language processing. Section 2 presents the mathematical concept of a language. Section 3 illustrates the mathematical concept of a language with three kinds of language structures: natural language, logical language, and programming language. Section 4 discusses the algebraic mechanism of language specification that unifies the methodology for language processing tool development. Section 5 formalizes the criterion for the consistency of the language usage, defines the architecture of a unified language processing system, and shows how the consistency criteria for language usage can be employed as correctness criteria for the algorithms performing various language transformations. [Copyright &y& Elsevier]

Persistent homology with coefficients in a field $$\mathbb {F}$$ coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology. [ABSTRACT FROM AUTHOR]

In this paper, we show an algorithmic procedure to compute abelian subalgebras and ideals of a given finite-dimensional Leibniz algebra, starting from the non-zero brackets in its law. In order to implement this method, the symbolic computation package MAPLE 12 is used. Moreover, we also show a brief computational study considering both the computing time and the memory used in the two main routines of the implementation. Finally, we determine the maximal dimension of abelian subalgebras and ideals for 3-dimensional Leibniz algebras and 4-dimensional solvable ones over. [ABSTRACT FROM PUBLISHER]

An algorithm for finding the largest singular value of a nonnegative rectangular tensor was recently proposed by Chang, Qi, and Zhou [J. Math. Anal. Appl., 2010, 370: 284-294]. In this paper, we establish a linear convergence rate of the Chang-Qi-Zhou algorithm under a reasonable assumption. [ABSTRACT FROM AUTHOR]

Abstract: Many useful morphological filters are built as long concatenations of erosions and dilations: openings, closings, size distributions, sequential filters, etc. This paper proposes a new algorithm implementing morphological dilation and erosion of functions. It supports rectangular structuring element, runs in linear time w.r.t. the image size and constant time w.r.t. the structuring element size, and has minimal memory usage. It has zero algorithm latency and processes data in stream. These properties are inherited by operators composed by concatenation, and allow their efficient implementation. We show how to compute in one pass an Alternate Sequential Filter (ASF n ) regardless the number of stages n. This algorithm opens the way to such time-critical applications where the complexity and memory requirements of serial morphological operators represented a bottleneck limiting their usability. [Copyright &y& Elsevier]

In this paper, the maximal abelian dimension is computationally obtained for an arbitrary finite-dimensional Lie algebra, defined by its nonzero brackets. More concretely, we describe and implement an algorithm which computes such a dimension by running it in the symbolic computation package MAPLE. Finally, we also show a computational study related to this implementation, regarding both the computing time and the memory used. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents an agglomerative hierarchical clustering algorithm for spatial data. It discovers clusters of arbitrary shapes which may be nested. The algorithm uses a sweeping approach consisting of three phases: sorting is done during the preprocessing phase, determination of clusters is performed during the sweeping phase, and clusters are adjusted during the post processing phase. The properties of the algorithm are demonstrated by examples. The algorithm is also adapted to the streaming algorithm for clustering large spatial datasets. [Copyright &y& Elsevier]

Abstract: The coefficient of fragmentability of a class of graphs measures the proportion of vertices that need to be removed from the graphs in the class in order to leave behind bounded sized components. We have previously given bounds on this parameter for the class of graphs satisfying a given constant bound on maximum degree. In this paper, we give fragmentability bounds for some classes of graphs of bounded average degree, as well as classes of given thickness, the class of -colourable graphs, and the class of n-dimensional cubes. In order to establish the fragmentability results for bounded average degree, we prove that the proportion of vertices that must be removed from a graph of average degree at most in order to leave behind a planar subgraph (in fact, a series-parallel subgraph) is at most , provided or the graph is connected and . The proof yields an algorithm for finding large induced planar subgraphs and (under certain conditions) a lower bound on the size of the induced planar subgraph it finds. This bound is similar in form to the one we found for a previous algorithm we developed for that problem, but applies to a larger class of graphs. [Copyright &y& Elsevier]

Abstract: The longest common subsequence (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we introduce new variants of LCS problem and present efficient algorithms to solve them. In particular we introduce the notion of gap constraints in the LCS problems. For the LCS problem with fixed gap, we first present a naive algorithm runs in time, where is the total number of ordered pairs of positions at which the two strings match and is the fixed gap constraint. We then improve the running time to using some novel techniques. Furthermore, we present an algorithm that is independent of and runs in time. Using these techniques, we also present a new algorithm to solve the original LCS problem. Additionally, we modify our algorithms to handle elastic and rigid gaps. We also apply the notion of rigidness to the original LCS problem and modify the traditional dynamic programming solution to handle the rigidness presenting a algorithm to solve the problem. Finally, we also improve the solution to Rigid Fixed Gap LCS to . Notably, in all of the above cases, we assume that the two given strings are of equal length i.e. . But our results can be easily extended to handle two strings of different length. [Copyright &y& Elsevier]

A successive method of descending degree has been presented by Guo, Liu and Jia in 2002 to judge whether or not a matrix is a generalized diagonally dominant matrix. In this paper, an alternative approach and comments on one of their examples are provided. Numerical examples are given to illustrate the algorithm processing. [ABSTRACT FROM AUTHOR]

Abstract: In the present paper, an efficient algorithm for connectivity analysis of moderately sized distribution networks has been suggested. Algorithm is based on generation of all possible minimal system cutsets. The algorithm is efficient as it identifies only the necessary and sufficient conditions of system failure conditions in n-out-of-n type of distribution networks. The proposed algorithm is demonstrated with the help of saturated and unsaturated distribution networks. The computational efficiency of the algorithm is justified by comparing the computational efforts with the previously suggested appended spanning tree (AST) algorithm. The proposed technique has the added advantage as it can be utilized for generation of system inequalities which is useful in reliability estimation of capacitated networks. [Copyright &y& Elsevier]

This paper deals with the issue of developing efficient algorithms for reconfiguring two-dimensional VLSI arrays linked by four-port switches in the presence of faulty processing elements (PEs). The proposed algorithm reroutes the arrays with faults in both row and column directions at the same time. Unlike previous work, the compensation technique to replace the faulty PE is not restricted to the adjacent rows of the excluded row. Instead, we consider the neighbor rows of any faulty PE for compensation purposes. The nonfaulty PEs lying in the excluded rows are also effectively utilized to form the maximal target arrays, making the proposed algorithm more efficient in terms of both the percentages of harvest and the degradation of VLSI arrays for random and clustered faults. Empirical study shows that the improvement in harvest increases with increasing fault size and is more notable for maximal square target arrays than for maximal target arrays. Our investigations show that the improvement can be up to 8 percent and 23 percent for a 256 × 256 VLSI array with random faults of size 25 percent for maximal target arrays and for maximal square target arrays, respectively. [ABSTRACT FROM AUTHOR]

Abstract: For many scientists working with digital topographic data, extracting lineaments or linear features is an important step in structuring and analyzing raw data. A ridge axis, which represents the top a mountain ridge, is one of the most important topographic features used in a wide variety of applications. Algorithms and software for automating the extraction of ridges or ridge axes from DEMs are, however, still not easily available or not widely acceptable. In this paper, we present a user-friendly Visual Basic program that automates the extraction of the ridge axis system from DEM data, based on the profile-recognition and polygon-breaking algorithm (PPA). An important feature of PPA is that it takes a global approach, as opposed to the local neighborhood operators used in many other algorithms. Each segment detected by PPA considers not only relations with contiguous neighboring grid points, but also strives to preserve the continuity of the global trend. This is an attempt to simulate human operators, who always factor in the overall trend of the lineament before delineating its local parts. PPA starts by connecting all points in a neighborhood that can possibly lie on the ridge axis, thus forming a belt of polygons in the first step. Next, a polygon breaking process eliminates unwanted segments according to the assumption that a ridge segment cannot be the side of any closed polygon, and that the result should be a purely dendritic line pattern. Finally, a branch-reduction process is executed to eliminate all parallel false ridges that remained due to the conservative approach taken in the first step. Results indicate that PPA is reasonably successful in picking out ridges that would have been identified manually by experts. In addition to providing a detailed user interface for executing PPA, several modifications were made to significantly improve the computational efficiency of PPA, as compared to the original version published in 1998. The source codes are provided for free download on the website listed above. [Copyright &y& Elsevier]

A realizer of a triangulated plane graph G is a partition of interior edges of G, satisfying some conditions. The realizer has many applications, including graph drawing algorithms. Given a triangulated plane graph G, no algorithm to generate all realizers of G is known. In this paper, we first give an algorithm to generate all realizers. We first define a left canonical ordering for the vertices of an input graph, then show that there is a bijection between the left canonical orderings and realizers. Based on the bijection, we give an algorithm to generate all realizers. The algorithm generates each realizer in O(n) time without duplications, where n is the number of vertices in the graph. © 2006 Wiley Periodicals, Inc. Electron Comm Jpn Pt 2, 89(7): 40–47, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/ecjb.20276 [ABSTRACT FROM AUTHOR]

Abstract: Algebraic surfaces–which are frequently used in geometric modelling–are represented either in implicit or parametric form. Several techniques for parametrizing a rational algebraic surface as a whole exist. However, in many applications, it suffices to parametrize a small portion of the surface. This motivates the analysis of local parametrizations, i.e., parametrizations of a small neighborhood of a given point of the surface . In this paper we introduce several techniques for generating such parametrizations for nonsingular cubic surfaces. For this class of surfaces, it is shown that the local parametrization problem can be solved for all points, and any such surface can be covered completely. [Copyright &y& Elsevier]

Abstract: In this paper, by using the theories and methods of mathematics analysis, ordinary differential equation and computer algebra, a reliable algorithm for solving ordinary differential equation (ODE) was established, and a new Maple procedure mechodeproc was established, too. The results of the examples indicated that the procedure mechodeproc based on Taylor polynomial method was simple and effective, and could provide an accuracy approximate solution or exact solution of the ordinary differential equation. This would be useful for solving differential equation. [Copyright &y& Elsevier]

Abstract: In this paper, by using theories of stochastic process and computer algebra, a reliable algorithm for computing the high-order transition probability matrix of finite Markov chain is established, a new mechanical procedure markovproc is established, too. The procedure markovproc give not only the exact expression of the Markov chains, but also the limiting probability. Some examples are presented to illustrate the implementation of the algorithm. [Copyright &y& Elsevier]

Abstract: The main results of the paper are two dual algorithms bijectively mapping the set of spanning trees with internal activity 1 and external activity 0 of an ordered graph onto the set of acyclic orientations with adjacent unique source and sink. More generally, these algorithms extend to an activity-preserving correspondence between spanning trees and orientations. For certain linear orderings of the edges, they also provide a bijection between spanning trees with external activity 0 and acyclic orientations with a given unique sink. This construction uses notably an active decomposition for orientations of a graph which extends the notion of components for acyclic orientations with unique given sink. [Copyright &y& Elsevier]

Abstract: Let be a finite group. It is easy to compute the character of corresponding to a given complex representation, but much more difficult to compute a representation affording a given character. In part this is due to the fact that a class of equivalent representations contains no natural canonical representation. Although there is a large literature devoted to computing representations, and methods are known for particular classes of groups, we know of no general method which has been proposed which is practical for any but small groups. We shall describe an algorithm for computing an irreducible matrix representation which affords a given character of a given group . The algorithm uses properties of the structure of which can be computed efficiently by a program such as GAP, theoretical results from representation theory, theorems from group theory (including the classification of finite simple groups), and linear algebra. All results in this paper have been implemented in the GAP package REPSN. [Copyright &y& Elsevier]

In this paper, we consider a map labeling problem where the points to be labeled are restricted on a line. It is known that the 1d-4P and the 1d-4S unit-square label placement problem and the Slope-4P unit-square label placement problem can both be solved in linear time and the Slope-4S unit-square label placement problem can be solved in quadratic time in Ref. [8]. We extend the result to the following label placement problem: Slope-4P fixed-height (width) label or elastic label placement problem and present a linear time algorithm for it provided that the input points are given sorted. We further show that if the points are not sorted, the label placement problems have a lower bound of Ω(n log n), where n is the input size, under the algebraic computation tree model. Optimization versions of these point labeling problems are also considered. [ABSTRACT FROM AUTHOR]

DTD has been widely used as the schema language for XML documents. A DTD describes the structure of a collection of similar XML documents. The consistency problem of XML DTDs concerns the question that given a DTD D, if there exists any finite XML document that conforms to D. This issue is important because one wants to know whether a DTD specification is meaningful. In this paper, we formalize the notion of the consistency of DTDs, identify a sufficient and necessary condition for a DTD to be consistent, and propose a linear algorithm, DTDCon, for the consistency checking problem. [Copyright &y& Elsevier]

In this paper, we propose a semi-numerical algorithm for computing absolute factorization of multivariate polynomials. It is based on some properties appearing after a generic change of coordinate. Using numerical computation, Galois group action and rational approximation, this method provides an efficient probabilistic algorithm for medium degrees. Two implementations are presented and compared to other algorithms. [Copyright &y& Elsevier]

In this paper, we introduce and study a new class of generalized nonlinear implicit quasivariational inclusions for set-valued mappings. We construct some new iterative algorithms for this generalized nonlinear implicit quasivariational inclusions for set-valued mappings without compactness. We prove the existence of solutions for this generalized nonlinear implicit quasivariational inclusions for set-valued mappings without compactness and the convergence of iterative sequences generated by the algorithms. We also give an application to generalized nonlinear implicit variational inequalities. [ABSTRACT FROM AUTHOR]

Checking regularity (or singularity) of interval matrices is a known NP-hard problem. In this paper a general algorithm for checking regularity/singularity is presented which is not a priori exponential. The algorithm is based on a theoretical result according to which regularity may be judged from any single component of the solution set of an associated system of linear interval equations. Numerical experiments (with interval matrices up to the size n = 50) confirm that this approach brings an essential decrease in the amount of operations needed. [ABSTRACT FROM AUTHOR]

In past studies, the digital straight-line segment is defined as a figure approximating the straight-line segment in the continuous space, by grid points in the discrete space. Because of this definition, the properties of the segment vary depending on the approximation process, which prevented the development of a general discussion. For this problem, the authors introduced a topology into the discrete space, and defined the digital straight-line segment using only the topology. As a result, the digital straight-line segment can be defined generally for various spaces and topologies, and the properties of the segment can be analyzed. In this paper, the properties of the digital straight-line segment are analyzed based on the 5-neighborhood concept. As the first step, the assertion that characterizes the digital straight-line segment, as well as five equivalent assertions are presented. Then, it is shown that by using those assertions, the corresponding segment generation algorithm can easily be obtained, and the figure generated by the segment generation algorithm which is known in the CG technology is the same as the proposed digital straight-line segment. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(6): 16–26, 1998 [ABSTRACT FROM AUTHOR]

This paper discusses the problems of finding one of the largest similar substructures in tree Tb to tree Ta, where both Ta and Tb are rooted and ordered trees (RO-trees) or unrooted and cyclically ordered trees (CO-trees). A maximal closest common ancestor mapping and a largest similar substructure in Tb to Ta based on this mapping are defined and two algorithms are proposed for finding one of the largest similar substructures for RO-trees and that for CO-trees. The time and space complexities of the algorithm for RO-trees are OT(NaNb) and OS(NaNb), respectively; and those of the algorithm for CO-trees are OT(mambNaNb) and OS((ma + mb)NaNb), respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(2): 92–104, 1997 [ABSTRACT FROM AUTHOR]

Assume that G is an undirected planar graph and the edge length of G is nonnegative real number. When k terminal pairs are specified on two specified face boundaries, this paper gives an algorithm that derives the "noncrossing paths" with the minimum sum of lengths that connects the respective terminal pairs. By the noncrossing paths is meant the paths which do not cross on the plane, although the point or the edge may be shared. The computation time of the proposed algorithm is O(n log n), where n is the number of points on the planar graph G; k need not to be a constant. [ABSTRACT FROM AUTHOR]