Weakly coprime factorization and state-feedback stabilization of discrete-time systems

The LQ-optimal state feedback of a finite-dimensional linear time-invariant system determines a coprime factorization NM ⁻¹ of the transfer function. We show that the same is true also for infinite-dimensional systems over arbitrary Hilbert spaces, in the sense that the factorization is weakly coprime, i.e., Nf, for every function f. The factorization need not be Bézout coprime. We prove that every proper quotient of two bounded holomorphic operator-valued functions can be presented as the quotient of two bounded holomorphic weakly coprime functions. This result was already known for matrix-valued functions with the classical definition gcd(N, M) = I, which we prove equivalent to our definition. We give necessary and sufficient conditions and further results for weak coprimeness and for Bézout coprimeness. We then establish a variant of the inner–outer factorization with the inner factor being “weakly left-invertible”. Most of our results hold also for continuous-time systems and many are new also in the scalar-valued case.     

A formal theory of matrix primeness

Primeness of nD polynomial matrices is of fundamental importance in multidimensional systems theory. In this paper we define a quantity which describes the “amount of primeness” of a matrix and identify it as the concept of grade in commutative algebra. This enables us to produce a theory which unifies many existing results, such as the Bézout identities and complementation laws, while placing them on a firm algebraic footing. We also present applications to autonomous systems, behavioural minimality of regular systems, and transfer matrix factorization. This work has been sponsored by EPSRC Grant No. GR/K 18504.     

Polynomial expansion of symmetric boolean functions by the table method

Conclusion The proposed method for polynomial expansion of SBF based on construction of the triangular tableT _n(π(F)) of local codes of its derivatives has the lowest computational complexity among known methods. Constructing the table only once, the method easily determines all the “residual” functions ϑ _rl ^km for various expansion parametersk andm. Another advantage of the method is its applicability for polynomial expansion of arbitrary BF and partially symmetric BF. In this case, the base of the “triangle” is the truth table of the arbitrary BF or the local code (including convolved local code) of the partially symmetric BF. The method can be successfully used for the synthesis of a wide class of digital networks. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 59–71, November–December, 1996.     

On solving large systems of polynomial equations appearing in discrete differential geometry

The paper describes methods for solving very large overdetermined algebraic polynomial systems on an example that appears from a classification of all integrable 3-dimensional scalar discrete quasilinear equations Q ₃=0 on an elementary cubic cell of the lattice ℤ³. The overdetermined polynomial algebraic system that has to be solved is far too large to be formulated. A “probing” technique, which replaces independent variables by random integers or zero, allows to formulate subsets of this system. An automatic alteration of equation formulating steps and equation solving steps leads to an iteration process that solves the computational problem. The text was submitted by the author in English.     

Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

On two versions of the Loomis–Sikorski Theorem for algebraic structures

We present two versions of the Loomis–Sikorski Theorem, one for monotone σ-complete generalized pseudo effect algebras with strong unit satisfying a kind of the Riesz decomposition property. The second one is for Dedekind σ-complete positive pseudo Vitali spaces with strong unit. For any case we can find an appropriate system of nonnegative bounded functions forming an algebra of the given type with the operations defined by points that maps epimorphically onto the algebra. The paper has been supported by the Center of Excellence SAS—Physics of Information—I/2/2005, the grant VEGA No. 2/6088/26 SAV, the Slovak Research and Development Agency under the contract No. APVV-0071-06, Slovak-Italian Project No. 15:“Algebraic and logical systems of soft computing”, and MURST, project “Analisi Reale”.     

Gaussian Laws for the Main Parameters of the Euclid Algorithms

We provide sharp estimates for the probabilistic behaviour of the main parameters of the Euclid Algorithms, both on polynomials and on integer numbers. We study in particular the distribution of the bit-complexity which involves two main parameters: digit-costs and length of remainders. We first show here that an asymptotic Gaussian law holds for the length of remainders at a fraction of the execution, which exhibits a deep regularity phenomenon. Then, we study in each framework—polynomials (P) and integer numbers (I)—two gcd algorithms, the standard one (S) which only computes the gcd, and the extended one (E) which also computes the Bezout pair, and is widely used for computing modular inverses. The extended algorithm is more regular than the standard one, and this explains that our results are more precise for the Extended algorithm: we exhibit an asymptotic Gaussian law for the bit-complexity of the extended algorithm, in both cases (P) and (I). We also prove that an asymptotic Gaussian law for the bit-complexity of the standard gcd in case (P), but we do not succeed obtaining a similar result in case (I). The integer study is more involved than the polynomial study, as it is usually the case. In the polynomial case, we deal with the central tools of the distributional analysis of algorithms, namely bivariate generating functions. In the integer case, we are led to dynamical methods, which heavily use the dynamical system underlying the number Euclidean algorithm, and its transfer operator. Baladi and Vallée (J. Number Theory 110(2):331–386, 2005) have recently designed a general framework for “distributional dynamical analysis”, where they have exhibited asymptotic Gaussian laws for a large family of parameters. However, this family does not contain neither the bit-complexity cost nor the size of remainders, and we have to extend their methods for obtaining our results. Even if these dynamical methods are not necessary in case (P), we explain how the polynomial dynamical system can be also used for proving our results. This provides a common framework for both analyses, which well explains the similarities and the differences between the two cases (P) and (I), for the algorithms themselves, and also for their analysis. An extended abstract of this paper can be found in Lhote and Vallée (Proceedings of LATIN’06, Lecture Notes in Computer Science, vol. 3887, pp. 689–702, 2006).     

An Algorithm for Timing Verification of Systems Constrained by Min–max Inequalities

To determine the maximum separation between events for nonrepetitive systems with max and linear constraints, there are the “iterative tightening from above” (ITA) approach and the “iterative tightening from below” (ITB) approach. Since such systems can be formulated as systems constrained by min–max inequalities, this paper gives an algorithm named MMIMaxSep for solving min–max inequalities. The algorithm is a generalization and a mathematically elegant reformulation of Yen et al.’s MaxSeparation algorithm which uses the ITB approach. Our numerical experiments indicate that MMIMaxSep is very efficient. Moreover, MMIMaxSep has a unique advantage of being able to directly handle tree-represented min–max functions, and its complexity is closely related to the complexity of computing cycle time of min–max functions.

Behavioral controllability and coprimeness for pseudorational transfer functions

Controllability plays various crucial roles in behavioral system theory. While there exist several characterizations of this notion, in terms of the Bézout identity, image representation, direct sum decomposition, etc., its overall picture for infinite-dimensional systems still remains rather incomplete, in spite of various existing attempts. This article gives an extension of such results in a well-behaved class of infinite-dimensional systems, called pseudorational. A proper choice of an algebra makes the treatment more transparent. We establish equivalent conditions for controllability in terms of the Bézout identity, relationships with notions such as image representation and direct sum decompositions.     

Admissible simulation relations,set-valued feedback,and controlled invariance

This work is a continuation of the author’s study of simulation relations between nonlinear input–output systems with disturbances. Previously we derived a criterion under which a “pointwise” simulation condition implies simulation by so-called “admissible” inputs and disturbances (that is, inputs and disturbances that yield time-dependent vector fields satisfying C ¹ Carathéodory conditions). This criterion included a certain constant-rank assumption. In this paper we use the theory of set-valued mappings and differential inclusions to derive analogous results in which the constant-rank assumption is replaced by a compactness provision that augments the pointwise simulation condition. We illustrate our simulation results by deriving a sufficient condition for achieving global controlled invariance of a (possibly singular) nonlinear system through the use of a set-valued feedback law.     

Tree Expressions for Information Systems

The discernibility matrix is one of the most important approaches to computing positive region, reduct, core and value reduct in rough sets. The subject of this paper is to develop a parallel approach of it, called ＂tree expression＂. Its computational complexity for positive region and reduct is O（m^2 × n） instead of O（m × n^2） in discernibility-matrix-based approach, and is not over O（n^2） for other concepts in rough sets, where rn and n are the numbers of attributes and objects respectively in a given dataset （also called an ＂information system＂ in rough sets）. This approach suits information systems with n ≥ m and containing over one million objects.     

Orienting rewrite rules with the Knuth–Bendix order

We consider two decision problems related to the Knuth–Bendix order (KBO). The first problem is orientability: given a system of rewrite rules R, does there exist an instance of KBO which orients every ground instance of every rewrite rule in R. The second problem is whether a given instance of KBO orients every ground instance of a given rewrite rule. This problem can also be reformulated as the problem of solving a single ordering constraint for the KBO. We prove that both problems can be solved in the time polynomial in the size of the input. The polynomial-time algorithm for orientability builds upon an algorithm for solving systems of homogeneous linear inequalities over integers. We show that the orientability problem is P-complete. The polynomial-time algorithm for solving a single ordering constraint does not need to solve systems of linear inequalities and can be run in time O(n²). Also we show that if a system is orientable using a real-valued instance of KBO, then it is also orientable using an integer-valued instance of KBO. Therefore, all our results hold both for the integer-valued and the real-valued KBO.     

Generic Complexity of Presburger Arithmetic

Fischer and Rabin proved in (Proceedings of the SIAM-AMS Symposium in Applied Mathematics, vol. 7, pp. 27–41, 1974) that the decision problem for Presburger Arithmetic has at least double exponential worst-case complexity (for deterministic and for nondeterministic Turing machines). In Kapovich et al. (J. Algebra 264(2):665–694, 2003) a theory of generic-case complexity was developed, where algorithmic problems are studied on “most” inputs instead of set of all inputs. A question rises about existing of more efficient (say, polynomial) generic algorithm deciding Presburger Arithmetic on a set of closed formulas of asymptotic density 1. We prove in this paper that there is not an exponential generic decision algorithm working correctly on an input set of asymptotic density exponentially converging to 1 (so-called strongly generic sets).     

Generalized control systems,boundary control systems,and delayed control systems

We investigate the relationships between the three classes of systems mentioned in the title: we show that systems with delays in control are a special instance of boundary control systems, and a boundary control system produces a generalized control system when projected onto its (unstable) eigenspaces. We use this observation to investigate the action of feedback on the dynamical behavior of systems with boundary controls. In particular, the well-known fact that spectral controllability is necessary and sufficient for a system with delays in control to be stabilizable is derived from a general rather than from anad hoc method. This paper was written according to the programs of the GNAFA-CNR group, with the financial support of the Italian “Ministero della Pubblica Istruzione.”     

Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure

In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n ²) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Ω(n ²) entries of this matrix, no better bounds are possible for this class of algorithms. This work has been partially supported by the Sixth Framework Programme of the EU under contract number 507613 (Network of Excellence “EuroNGI: Designing and Engineering of the Next Generation Internet”), and number 001907 (“DELIS: Dynamically Evolving, Large Scale Information Systems”), and by the Italian Ministry of University and Research (Project “ALGO-NEXT: Algorithms for the Next Generation Internet and Web: Methodologies, Design and Experiments”). Portions of this paper have been presented at the 41st Annual Symp. on Foundations of Computer Science, 2000.     

An anytime revision operator for large and uncertain geographic data sets

 The environmental data are in general imprecise and uncertain, but they are located in space and therefore obey to spatial constraints. The “spatial analysis” is a (natural) reasoning process through which geographers take advantage of these constraints to reduce this uncertainty and to improve their beliefs. Trying to automate this process is a really hard problem. We propose here the design of a revision operator able to perform a spatial analysis in the context of one particular “application profile”: it identifies objects bearing a same variable bound through local constraints. The formal background, on which this operator is built, is a decision algorithm from Reiter [9]; then the heuristics, which help this algorithm to become tractable on a true scale application, are special patterns for clauses and “spatial confinement” of conflicts. This operator is “anytime”, because it uses “samples” and works on small (tractable) blocks, it reaggregates the partial revision results on larger blocks, thus we name it a “hierarchical block revision” operator. Finally we illustrate a particular application: a flooding propagation. Of course this is among possible approaches of “soft-computing” for geographic applications. On leave at: Centre de Recherche en Géomatique Pavillon Casault, Université Laval Québec, Qc, Canada – G1K 7P4 Université de Toulon et du Var, Avenue de l'Université, BP 132, 83957 La Garde Cedex, France This work is currently supported by the European Community under the IST-1999-14189 project.     

Approximation algorithms for shop scheduling problems with minsum objective: A correction

We present a correction to the paper, “Approximation algorithms for shop scheduling problems with minsum objective” (Journal of Scheduling 2002; 5:287–305) by Queyranne and Sviridenko. This correction provides a correct derivation of its 2eρ approximation result. Wenhua Li and Jinjiang Yuan: Project supported by NNSFC (Grant 10371112) and NSFHN (Grant 0411011200). Maurice Queyranne: Supported by research grants from NSERC, the Natural Sciences and Engineering Research Council of Canada.     

Expressing uniformity via oracles

We study under what circumstances different uniformity notions for Boolean circuits of logarithmic depth lead to the same complexity class. Our investigations are based on a characterization of uniformity in terms of oracle access to tally sets that is proved in the present paper:A-uniform circuits of logarithmic depth are of the same computational power asDLOGTIME-uniform circuits of logarithmic depth with oracle access to tally sets inA. This characterization does not only apply to classesA such as logarithmic space or polynomial time, but to all in some sense “well-behaved” classes and especially to all standard complexity classes. We present many applications for this characterization, among them upward separations, depth-uniformity tradeoffs, and inclusion-completeness results for tally languages. The first two authors were partially supported by DFG-La 618/1-1 and the third author was supported by DFG-SFB 0342 “KLARA.”