On the absence of positive realness conditions in self-tuning regulators based on explicit criterion minimization

Local convergence properties of an adaptive control algorithm that, under suitable assumptions, is known to be globally convergent to the optimal LQ regulator, are studied. In this connection, it is shown that, as in more standard adaptive controllers, a “transfer function” H(q), depending on the innovation C(q)-polynomial, plays a central role. The peculiarity of the algorithm under consideration is that the special form of the corresponding H(q) implies its positive realness. The interest of this result is in the relationship that it allows one to establish between the algorithm under consideration and other adaptive controllers, viz. MUSMAR, whose local convergence properties are known to be described by the same H(q).     

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ?P such that $\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q)The min-sum k -clustering problem is to partition a metric space (P,d) into k clusters C ₁,…,C _k ⊆P such that ?_i=1^k?_{p,q ? Ci}d(p,q)\sum_{i=1}^{k}\sum_{p,q\in C_{i}}d(p,q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results.     

On simplifying assumptions of Runge-Kutta methods for index 2 differential algebraic problems

In this paper we show a result that ensures certain order for the local error Runge-Kutta methods for index 2 differential algebraic problems with the help of the simplifying conditionsB(p),C(q),D(r) andA ₁(s) for the differential component andB(p), C(q), andA ₂(s) for the algebraic component.     

Computing largest empty circles with location constraints

LetQ = {q₁, q₂,..., q_n} be a set ofn points on the plane. The largest empty circle (LEG) problem consists in finding the largest circleC with center in the convex hull ofQ such that no pointq _i εQ lies in the interior ofC. Shamos recently outlined anO(n logn) algorithm for solving this problem.⁽⁹⁾ In this paper it is shown that this algorithm does not always work correctly. A different approach is proposed here and shown to also result in anO(n logn) algorithm. The new approach has the advantage that it can also solve more general problems. In particular, it is shown that if the center ofC is constrained to lie in an arbitrary convexn-gon, an0(n logn) algorithm can still be obtained. Finally, an0(n logn +k logn) algorithm is given for solving this problem when the center ofC is constrained to lie in an arbitrary simplen-gonP. wherek denotes the number of intersections occurring between edges ofP and edges of the Voronoi diagram ofQ andk ?O(n ²).     

A remark on the complexity of consistent conjunctive query answering under primary key violations

A natural way for capturing uncertainty in the relational data model is by allowing relations that violate their primary key. A repair of such relation is obtained by selecting a maximal number of tuples without ever selecting two tuples that agree on their primary key. Given a Boolean query q, CERTAINTY(q) is the problem that takes as input a relational database and asks whether q evaluates to true on every repair of that database. In recent years, CERTAINTY(q) has been studied primarily for conjunctive queries. Conditions have been determined under which CERTAINTY(q) is coNP-complete, first-order expressible, or not first-order expressible. A remaining open question was whether there exist conjunctive queries q without self-join such that CERTAINTY(q) is in PTIME but not first-order expressible. We answer this question affirmatively.     

Metric Identities and the Discontinuous Spectral Element Method on Curvilinear Meshes

We study how to approximate the metric terms that arise in the discontinuous spectral element (DSEM) approximation of hyperbolic systems of conservation laws when the element boundaries are curved. We first show that the metric terms can be written in three forms: the usual cross product and two curl forms. The first curl form is identical to the “conservative” form presented by Thomas and Lombard [(1979), AIAA J. 17(10), 1030–1037]. The second is a coordinate invariant form. We prove that in two space dimensions, the typical approximation of the cross product form does satisfy a discrete set of metric identities if the boundaries are isoparametric and the quadrature is sufficiently precise. We show that in three dimensions, this cross product form does not satisfy the metric identities, except in exceptional circumstances. Finally, we present approximations of the curl forms of the metric terms that satisfy the discrete metric identities. Two examples are presented to illustrate how the evaluation of the metric terms affects the satisfaction of the discrete metric identities, one in two space dimensions and the other in three.     

Aperiodic propagation criteria for Boolean functions

We characterise the aperiodic autocorrelation for a Boolean function, f, and define the Aperiodic Propagation Criteria (APC) of degree l and order q. We establish the strong similarity between APC and the Extended Propagation Criteria (EPC) as defined by Preneel et al. in 1991, although the criteria are not identical. We also show how aperiodic autocorrelation can be related to the first derivative of f. We further propose the metric APC distance and show that quantum error correcting codes (QECCs) are natural candidates for Boolean functions with favourable APC distance.     

Asymptotic behavior of nonoscillatory solutions of neutral difference equations

The authors consider the m^th-order neutral difference equation D_m(y(n) + p(n)y(n − k) + q(n)f(y(σ(n))) = e(n), where m ≥ 1, {p(n)}, {q(n)}, {e(n)}, and {a₁(n)}, {a₂(n)}, …, {a_m−1(n)} are real sequences, a_i(n) > 0 for i = 1,2,…, m−1, a_m(n) ≡ 1, D₀z(n) = y(n)+p(n)y(n − k), D_iz(n) = a_i(n)ΔD_i−1z(n) for i = 1,2, …, m, k is a positive integer, {σ(n)} → ∞ is a sequence of positive integers, and R → R is continuous with u f(u) > 0 for u ≠ 0. In the case where {q(n)} is allowed to oscillate, they obtain sufficient conditions for all bounded nonoscillatory solutions to converge to zero, and if {q(n)} is a nonnegative sequence, they establish sufficient conditions for all nonoscillatory solutions to converge to zero. Examples illustrating the results are included throughout the paper.     

On the Advice Complexity of the k-server Problem Under Sparse Metrics

We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs. These algorithms require advice of (almost) linear size. We show that for graphs of size N and treewidth α, there is an online algorithm that receives O (n(log α + log log N))^* bits of advice and optimally serves any sequence of length n. We also prove that if a graph admits a system of μ collective tree (q, r)-spanners, then there is a (q + r)-competitive algorithm which requires O (n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, when provided with O (n log log N) bits of advice. On the other side, we prove that advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of length n even for the 2-server problem on a path metric of size N ≥ 3. Through another lower bound argument, we show that at least \(\frac {n}{2}(\log \alpha - 1.22)\) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 ≤ α < 2k.     

The q-derivative and applications to q-Szász Mirakyan operators

Abstract By using the properties of the q-derivative, we show that q-Szász Mirakyan operators are convex, if the function involved is convex, generalizing well-known results for q = 1. We also show that q-derivatives of these operators converge to q-derivatives of approximated functions. Futhermore, we give a Voronovskaya-type theorem for monomials and provide a Stancu-type form for the remainder of the q-Szász Mirakyan operator. Lastly, we give an inequality for a convex function f, involving a connection between two nonconsecutive terms of a sequence of q-Szász Mirakyan operators.     

Uniform computational complexity of the derivatives of C∞-functions

We discuss the uniform computational complexity of the derivatives of C^∞-functions in the model of Ko and Friedman (Ko, Complexity Theory of Real Functions, Birkhäuser, Basel, 1991; Ko, Friedman, Theor. Comput. Sci. 20 (1982) 323–352). We construct a polynomial time computable real function g∈C^∞[−1,1] such that the sequence $\text{{|g}{}^{\mathrm{(n)}}\text{(0)|}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is not bounded by any recursive function. On the other hand, we show that if f∈C^∞[−1,1] is polynomial time computable and the sequence of the derivatives of f is uniformly polynomially bounded, i.e., |f⁽ⁿ⁾(x)| is bounded by 2^p(n) for all x∈[−1,1] for some polynomial p, then the sequence $\text{{f}{}^{\mathrm{(n)}}\text{}}{}_{\mathrm{<mtext>n\in </mtext><mtext>N</mtext>}}$ is uniformly polynomial time computable.     

Efficient Algorithms for Highly Compressed Data: The Word Problem in Generalized Higman Groups Is in P

This paper continues the 2012 STACS contribution by Diekert, Ushakov, and the author as well as the 2012 IJAC publication by the same authors. We extend the results published there in two ways. First, we show that the data structure of power circuits can be generalized to work with arbitrary bases q≥2. This results in a data structure that can hold huge integers, arising by iteratively forming powers of q. We show that the properties of power circuits known for q=2 translate to the general case. This generalization is non-trivial and additional techniques are required to preserve the time bounds of arithmetic operations that were shown for the case q=2. The extended power circuit model permits us to conduct operations in the Baumslag-Solitar group BS(1,q) as efficiently as in BS(1,2). This allows us to solve the word problem in the generalization H ₄(1,q) of Higman’s group in polynomial time. The group H ₄(1,q) is an amalgamated product of four copies of the Baumslag-Solitar group BS(1,q) rather than BS(1,2) in the original group H ₄=H ₄(1,2). As a second result, we allow arbitrary numbers f≥4 of copies of BS(1,q), leading to an even more generalized notion of Higman groups H _f (1,q). We prove that the word problem of the latter can still be solved within the \({\mathcal {O}}(n^{6})\) time bound that was shown for H ₄(1,2).     

Fast multiplication of matrices over a finitely generated semiring

In this paper we show that n×n matrices with entries from a semiring R which is generated additively by q generators can be multiplied in time O(q²nω), where nω is the complexity for matrix multiplication over a ring (Strassen: ω<2.807, Coppersmith and Winograd: ω<2.376).We first present a combinatorial matrix multiplication algorithm for the case of semirings with q elements, with complexity , matching the best known methods in this class.Next we show how the ideas used can be combined with those of the fastest known boolean matrix multiplication algorithms to give an O(q²nω) algorithm for matrices of, not necessarily finite, semirings with q additive generators.For finite semirings our combinatorial algorithm is simple enough to be a practical algorithm and is expected to be faster than the O(q²nω) algorithm for matrices of practically relevant sizes.     

Routing equal-size messages on a slotted ring

We deal with the problem of routing messages on a slotted ring network in this paper. We study the computational complexity and algorithms for this routing by means of the results known in the literature for the multi-slot just-in-time scheduling problem. We consider two criteria for the routing problem: makespan, or minimum routing time, and diagonal makespan. A?diagonal is simply a schedule of ring links i=0,??,q?1 in q consecutive time slots, respectively. The number of diagonals between the earliest and the latest diagonals with non-empty packets is referred to as the diagonal makespan. For the former, we show that the optimal routing of messages of size k, is NP-hard in the strong sense, while an optimal routing when k=q can be computed in O(n ²log² n) time. We also give an O(nlogn)-time constant factor approximation algorithm for unit size messages. For the latter, we prove that the optimal routing of messages of size k, where k divides the size of the ring q, is NP-hard in the strong sense even for any fixed k??1, while an optimal routing when k=q can be computed in O(nlogn) time. We also give an O(nlogn)-time approximation algorithm with an absolute error 2q?k.     

On metric rigidity for some classes of codes

A code C in the n-dimensional metric space $ \mathbb{F}_q^n $ \mathbb{F}_q^n over the Galois field GF(q) is said to be metrically rigid if any isometry I: C → $ \mathbb{F}_q^n $ \mathbb{F}_q^n can be extended to an isometry (automorphism) of $ \mathbb{F}_q^n $ \mathbb{F}_q^n . We prove metric rigidity for some classes of codes, including certain classes of equidistant codes and codes corresponding to one class of affine resolvable designs.     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

CONFLUENT POSSIBILITY DISTRIBUTIONS AND THEIR REPRESENTATIONS

Possibilistic distributions admit both measures of uncertainty and (metric) distances defining their information closeness. For general pairs of distributions these measures and metrics were first introduced in the form of integral expressions. Particularly important are pairs of distributions p and q which have consonant ordering—for any two events x and y in the domain of discourse p(x)&lesseqqgtr; p(y) if and only if q(x) &lesseqqgtr; q(y). We call such distributions confluent and study their information distances.

This paper presents discrete sum form of uncertainty measures of arbitrary distributions, and uses it to obtain similar representations of metrics on the space of confluent distributions. Using these representations, a number of properties like additivity. monotonicity and a form of distributivity are proven. Finally, a branching property is introduced, which will serve (in a separate paper) to characterize axiomatically possibilistic information distances.     

Testing the Quality of Manufactured Disks and Balls

We consider the problem of testing the roundness of manufactured disks and balls using the finger probing model of Cole and Yap. The running time of our procedures depends on the quality of the object being considered. Quality is a parameter that is negative when the object is not sufficiently round and positive when it is. Quality values close to zero represent objects that are close to the boundary between sufficiently round and insufficiently round. When the object being tested is a disk and its center is known, we describe a procedure that uses O(n) probes and O(n) computation time. (Here n =| 1/q|, where q is the quality of the object.) When the center of the object is not known, a procedure using O(n) probes and O(n log n) computation time is described. When the object is a ball, we describe a procedure that requires O(n ²) probes and O(n ⁴) computation time. Lower bounds are also given that show that these procedures are optimal in terms of the number of probes used. These results extend previous results in two directions by relaxing some of the assumptions required by previous results and by extending these results for three-dimensional objects.