Fixed zeros in the model matching problem for systems over semirings

This paper studies “fixed zeros” of solutions to the model matching problem for systems over semirings. Such systems have been used to model queueing systems, communication networks, and manufacturing systems. The main contribution of this paper is the discovery of two fixed zero structures, which possess a connection with the extended zero semimodules of solutions to the model matching problem. Intuitively, the fixed zeros provides an essential component that is obtained from the solutions to the model matching problem. For discrete event dynamic systems modeled in max-plus algebra, a common Petri net component constructed from the solutions to the model matching problem can be discovered from the fixed zero structure.     

Bases in semilinear spaces over zerosumfree semirings

This paper investigates the cardinality of a basis and the characterizations of a basis in semilinear space of n-dimensional vectors over zerosumfree semirings. First, it discusses the cardinality of a basis and gives some necessary and sufficient conditions that each basis has the same number of elements. Then it presents some conditions that a set of vectors is a basis and that a set of linearly independent vectors can be extended to a basis. In the end, it shows a necessary and sufficient condition that two semilinear spaces are isomorphic.     

Factor and term ranks for matrix union over semirings

We consider the arithmetic properties of the factor-rank and term-rank functions for matrices over semirings. In particular, we investigate the sets of matrices that satisfy the extremes of inequalities for these rank functions of matrix union. The classification of the linear transformations that keep these sets invariant is obtained. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 9, No. 3, pp. 175–197, 2003.     

Fixed points of endomorphisms over special confluent rewriting systems

Cayley graphs of monoids defined through special confluent rewriting systems are known to be hyperbolic metric spaces which admit a compact completion given by irreducible finite and infinite words. In this paper, we prove that the fixed point submonoids for endomorphisms of these monoids which are boundary injective (or have bounded length decrease) are rational, with similar results holding for infinite fixed points. Decidability of these properties is proved, and constructibility is proved for the case of bounded length decrease. These results are applied to free products of cyclic groups, providing a new generalization for the case of infinite fixed points.     

Changing poles in the rational Lanczos method for the Hermitian eigenvalue problem

Applications such as the modal analysis of structures and acoustic cavities require a number of eigenvalues and eigenvectors of large‐scale Hermitian eigenvalue problems. The most popular method is probably the spectral transformation Lanczos method. An important disadvantage of this method is that a change of pole requires a complete restart. In this paper, we investigate the use of the rational Krylov method for this application. This method does not require a complete restart after a change of pole. It is shown that the change of pole can be considered as a change of Lanczos basis. The major conclusion of this paper is that the method is numerically stable when the poles are chosen in between clusters of the approximate eigenvalues. Copyright © 2001 John Wiley & Sons, Ltd.     

Fixed points of endomorphisms over special confluent rewriting systems

Cayley graphs of monoids defined through special confluent rewriting systems are known to be hyperbolic metric spaces which admit a compact completion given by irreducible finite and infinite words. In this paper, we prove that the fixed point submonoids for endomorphisms of these monoids which are boundary injective (or have bounded length decrease) are rational, with similar results holding for infinite fixed points. Decidability of these properties is proved, and constructibility is proved for the case of bounded length decrease. These results are applied to free products of cyclic groups, providing a new generalization for the case of infinite fixed points.     

Projective semimodules over semirings with valuations in nonnegative integers

We introduce semirings with valuations in nonnegative integers and prove that all projective semimodules over them are free.     

A graph-theoretic model to solve the approximate string matching problem allowing for translocations

In this paper, we study the approximate string matching problem under a string distance whose edit operations are translocations of equal length factors. We extend a graph-theoretic approach proposed by Rahman and Illiopoulos (2008) to model our problem. In the sequel, we devise efficient algorithms based on this model to solve a number of variants of the string matching problem with translocations.     

Bijective linear rank preservers for spaces of matrices over antinegative semirings

We classify the bijective linear operators on spaces of matrices over antinegative commutative semirings with no zero divisors which preserve certain rank functions such as the symmetric rank, the factor rank and the tropical rank. We also classify the bijective linear operators on spaces of matrices over the max-plus semiring which preserve the Gondran-Minoux row rank or the Gondran-Minoux column rank.     

Exact model matching of generalized state space systems

The problem of exact model matching for generalized state space (GSS) systems via pure proportional state and output feedback is studied. The following two major issues are resolved here for the first time: The necessary and sufficient conditions for the problem to have a solution and the general analytical expressions for the exact modelmatching controller matrices. The important case of left invertible systems is treated separately wherein simple solutions are established for the above two major issues and results on structural properties of the closed-loop system are reported. Known results on model matching of regular systems are derived as a special case of the GSS systems results, thus unifying the solution of the exact model-matching problem of regular and singular systems.The work described in this paper has been partially funded by the General Secretariat for Research and Technology of the Greek Ministry of Industry, Research, and Technology and by the Heracles General Cement Company of Greece.     

Fixed points and matching points in partitions

The Ramanujan Journal - We study fixed points in integer partitions viewed, respectively, as weakly increasing or weakly decreasing structures. A fixed point is a point with value i in position i....     

Generalized model matching and (F,G)-invariant submodules for linear systems over rings

A generalized version of the exact model matching problem (GEMMP) is considered for linear multivariable systems over an arbitrary commutative ring K with identity. Reduced forms of this problem are introduced, and a characterization of all solutions and minimal order solutions is given, both with and without the properness constraint on the solutions, in terms of linear equations over K and K-modules. An approach to the characterization of all stable solutions is presented which, under a certain Bezout condition and a freeness condition, provides a parametrization of all stable solutions. The results provide an explicit parametrization of all solutions and all stable solutions in case K is a field, without the Bezout condition. This is achieved through a very simple characterization and a generalization to an arbitrary field K of the “fixed poles” of the model matching problem in terms of invariant factors of a certain polynomial matrix. The results also show that whenever the GEMMP has a solution, there exist solutions whose poles can be chosen arbitrarily as far as they contain the “fixed poles” with the right multiplicities (in the algebraic closure of K). Implications of these results in regard to inverse systems are shown. Equivalent simpler forms (in state space form) of the problem are shown to be obtainable. A theory of finitely generated (F,G)-invariant submodules for linear systems over rings is developed, and the geometric equivalent of the model matching problem—the dynamic cover problem—is formulated, to which the results of the previous sections provide a solution in the reduced case.     

A maximum stable matching for the roommates problem

The stable roommates problem is that of matchingn people inton/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called a complete stable matching. It is known that a complete stable matching may not exist. Irving proposed anO(n ²) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present anO(n ²) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.This research was supported by National Science Council of Republic of China under grant NSC 79-0408-E009-04.     

Note on cardinality of bases in semilinear spaces over zerosumfree semirings

A necessary and sufficient condition under which all bases in a semilinear space of n-dimensional vectors over zerosumfree semirings have exactly n elements is established.     

Optimal model matching problem for stochastic signals with an unknown fast decreasing spectral density

Doklady Mathematics -     

FFT-based algorithms for the string matching with mismatches problem

The string matching with mismatches problem requires finding the Hamming distance between a pattern P of length m and every length m substring of text T with length n. Fischer and Paterson's FFT-based algorithm solves the problem without error in O(σnlogm), where σ is the size of the alphabet Σ [SIAM–AMS Proc. 7 (1973) 113–125]. However, this in the worst case reduces to O(nmlogm). Atallah, Chyzak and Dumas used the idea of randomly mapping the letters of the alphabet to complex roots of unity to estimate the score vector in time O(nlogm) [Algorithmica 29 (2001) 468–486]. We show that the algorithm's score variance can be substantially lowered by using a bijective mapping, and specifically to zero in the case of binary and ternary alphabets. This result is extended via alphabet remappings to deterministically solve the string matching with mismatches problem with a constant factor of 2 improvement over Fischer–Paterson's method.     

Uniform disturbance localization with simultaneous uniform exact model matching for linear time-varying analytic systems

The problem of uniform disturbance localization with simultaneousuniform exact model matching for linear time-varying analyticsystems via static state feedback is investigated, for the firsttime. The primary feature of the approach used is that it reducesthe problem to that of solving a nonhomogeneous algebraic systemof equations. From this system is obtained a set of necessaryand sufficient conditions for the solvability of the problem,and a general analytical expression for all admissible controllers.