On renaming a set of clauses as a Horn set

Let S = {C₁, …, C_m} be a set of clauses in the propositional calculus and let n denote the number of variables appearing these clauses. We present and O(mn) time algorithm to test whether S can be renamed as a Horn set.     

On extended P4-reducible and extended P4-sparse graphs

A graph G was defined in [16] as P₄-reducible, if no vertex in G belongs to more than one chordless path on four vertices or P₄. A graph G is defined in [15] as P₄-sparse if no set of five vertices induces more than one P₄, in G. P₄-sparse graphs generalize both P₄-reducible and the well known class of p₄-free graphs or cographs. In an extended abstract in [11] the first author introduced a method using the modular decomposition tree of a graph as the framework for the resolution of algorithmic problems. This method was applied to the study of P₄-sparse and extended P₄-sparse graphs.

In this paper, we begin by presenting the complete information about the method used in [11]. We propose a unique tree representation of P₄-sparse and a unique tree representation of P₄-reducible graphs leading to a simple linear recognition algorithm for both classes of graphs. In this way we simplify and unify the solutions for these problems, presented in [16–19]. The tree representation of an n-vertex P₄-sparse or a P₄-reducible graph is the key for obtaining O(n) time algorithms for the weighted version of classical optimization problems solved in [20]. These problems are NP-complete on general graphs.

Finally, by relaxing the restriction concerning the exclusion of the C₅ cycles from P₄-sparse and P₄-reducible graphs, we introduce the class of the extended P4-sparse and the class of the extendedP₄-reducible graphs. We then show that a minimal amount of additional work suffices for extending most of our algorithms to these new classes of graphs.     

Bisector curves of planar rational curves

This paper presents a simple and robust method for computing the bisector of two planar rational curves. We represent the correspondence between the foot points on two planar rational curves C₁(t) and C₂(r) as an implicit curve (t,r)=0, where (t,r) is a bivariate polynomial B-spline function. Given two rational curves of degree m in the xy-plane, the curve (t,r)=0 has degree 4m−2, which is considerably lower than that of the corresponding bisector curve in the xy-plane.     

Generic Complexity of Finitely Presented Monoids and Semigroups

We study the generic properties of finitely presented monoids and semigroups, and the generic-case complexity of decision problems for them. We show that for a finite alphabet A of size at least 2 and positive integers k and m, the generic A-generated k-relation monoid and semigroup (defined using any of several stratifications) satisfies the small overlap condition C(m). It follows that the generic finitely presented monoid has a number of interesting semigroup-theoretic properties and, by a recent result of the author, admits a linear time solution to its word problem and a regular language of unique normal forms for its elements. Moreover, the uniform word problem for finitely presented monoids is generically solvable in polynomial time.     

Infinite words and biprefix codes

Let A be an alphabet and ƒ be a right infinite word on A. If ƒ is not ultimately periodic then there exists an infinite set {v_ii0} of (finite) words on A such that ƒ=v₀v₁…v_i…, {v_ii1} is a biprefix code and v_i≠v_j for positive integers i≠j.     

On canonical number systems

Let be such that d1,p_d=1,p₀2 and . We are proving in this note a new criterion for the pair to be a canonical number system. This enables us to prove that if p₂,…,p_d−1,∑_i=1^dp_i0 and p₀>2∑_i=1^d|p_i|, then is a canonical number system.     

Integral averages and oscillation of second-order nonlinear differential equations

We present some criteria for the oscillation of the second-order nonlinear differential equation

Full-size image

where a ε C¹([t₀, ∞)) is a nonnegative function, q ε C ([t₀, ∞)) are allowed to change sign on [t₀, ∞), ψ, f ε C¹ , ψ(x) > 0, xf(x) > 0, f′(x) ≥ 0 for x ≠ 0. These criteria are obtained by using a general class of the parameter functions H(t,s) in the averaging techniques and represent extension, as well as improvement of known oscillation criteria of Philos and Purnaras for the generalized Emden-Fowler equation.     

Infinite Convergent String-rewriting Systems and Cross-sections for Finitely Presented Monoids

A finitely presented monoid has a decidable word problem if and only if it can be presented by some left-recursive convergent string-rewriting system if and only if it has a recursive cross-section. However, regular cross-sections or even context-free cross-sections do not suffice. This is shown by presenting examples of finitely presented monoids with decidable word problems that do not admit regular cross-sections, and that, hence, cannot be presented by left-regular convergent string-rewriting systems. Also examples of finitely presented monoids with decidable word problems are presented that do not even admit context-free cross-sections. On the other hand, it is shown that each finitely presented monoid with a decidable word problem has a finite presentation that admits a cross-section which is a Church–Rosser language. Finally we address the notion of left-regular convergent string-rewriting systems that are tractable.     

On the number of occurrences of all short factors in almost all words

We previously proved that almost all words of length n over a finite alphabet A with m letters contain as factors all words of length k(n) over A as n→∞, provided limsup_n→∞ k(n)/log n<1/log m.

In this note it is shown that if this condition holds, then the number of occurrences of any word of length k(n) as a factor into almost all words of length n is at least s(n), where lim_n→∞ log s(n)/log n=0. In particular, this number of occurrences is bounded below by C log n as n→∞, for any absolute constant C>0.     

O(log n) bimodality analysis

The bimodality of a population P can be measured by dividing its range into two intervals so as to maximize the Fisher distance between the resulting two subpopulations P₁ and P₂. If P is a mixture of two (approximately) Gaussian subpopulations, then P₁ and P₂ are good approximations to the original Gaussians, if their Fisher distance is great enough. Moreover, good approximations to P₁ and P₂ can be obtained by dividing P into small parts; finding the maximum-distance (MD) subdivision of each part; combining small groups of these subdivisions into (approximate) MD subdivisions of larger parts; and so on. This divide-and-conquer approach yields an approximate MD subdivision of P in O(log n) computational steps using O(n) processors, where n is the size of P.     

On deciding whether a monoid is a free monoid or is a group

Summary In general it is undecidable whether or not the monoid described by a given finite presentation is a free monoid or a group. However, these two decision problems are reducible to a very restricted form of the uniform word problem. So whenever a class of presentations is considered for which this restricted form of the uniform word problem is decidable, then the above decision problems become decidable. This holds in particular for the class of all presentations involving finite string-rewriting systems that are noetherian and confluent.     

Analytic numerical solution of coupled semi-infinite diffusion problems

In this paper, we consider coupled semi-infinite diffusion problems of the form u_t(x, t)− A² u_xx(x,t) = 0, x> 0, t> 0, subject to u(0,t)=B and u(x,0)=0, where A is a matrix in , and u(x,t), and B are vectors in . Using the Fourier sine transform, an explicit exact solution of the problem is proposed. Given an admissible error and a domain D(x₀,t₀)={(x,t);0≤x≤x₀, t≥t₀ > 0, an analytic approximate solution is constructed so that the error with respect to the exact solution is uniformly upper bounded by in D(x₀, t₀).     

C- and C-continuous spline-interpolation of a regular triangular net of points

The investigations focus on the construction of a C^k-continuous (k=0,1,2) interpolating spline-surface for a given data set consisting of points P_ijk arranged in a regular triangular net and corresponding barycentric parameter triples (u_i,v_j,w_k). We try to generalize an algorithm by A.W. Overhauser who solved the analogous problem for the case of a univariate data set. As a straightforward generalization does not work out we adapt the Overhauser-construction. We use some blending of basic surfaces with uniquely determined basic functions. This yields a spline-surface with a polynomial parametric representation which display C¹- or C²-continuity along the common curve of two adjacent sub-patches. Local control of the emerging spline surface is provided which means moving one data point P changes only some of the sub-patches around P and does not affect regions lying far away.     

Nonlinear robust stabilization of multi-parameter families of systems

We show that given any family of asymptotically stabilizable LTI systems depending continuously on a parameter that lies in some subset [a₁,b₁]××[a_p,b_p] of , there exists a C⁰ time-varying state feedback law v(t,x) (resp. a C⁰ time-invariant feedback law v(x)) which robustly globally exponentially stabilizes (resp. which robustly stabilizes, not asymptotically) the family. Further, if these systems are obtained by linearizing some nonlinear systems, then v(t,x) locally exponentially stabilizes these nonlinear systems. Finally, v(t,x) globally exponentially stabilizes any time-varying system which switches “slowly enough” between the given LTI systems.     

On some dynamical subsets of the rauzy fractal

Let ( ,(+1)_n) be the adic system associated to the substitution: 1 → 12,…,(n − 1) → 1n, n → 1. In Sirvent (1996) it was shown that there exist a subset Cⁿ of and a map h_n: C → Cⁿ such that the dynamical system (C, h_n) is semiconjugate to ( ). In this paper we compute the Hausdorff and Billingsley dimensions of the geometrical realizations of the set Cⁿ on the (n− l)-dimensional torus. We also show that the dynamical system (Cⁿ,h_n) cannot be realized on the (n − 1)-torus.     

Constructible functions in cellular automata and their applications to hierarchy results

We investigate time-constructible functions in one-dimensional cellular automata (CA). It is shown that (i) if a function t(n) is computable by an O(t(n)−n)-time Turing machine, then t(n) is time constructible by CA and (ii) if two functions are time constructible by CA, then the sum, product, and exponential functions of them are time constructible by CA. As an application, it is shown that if t₁(n) and t₂(n) are time constructible functions such that lim_n→∞ t₁(n)/t₂(n) = 0 and t₁(n)n, then there is a language which can be recognized by a CA in t₂(n) time but not by any CA in t₁(n) time.     

Simultaneous H2/H∞ optimal control The state feedback case

A simultaneous H₂/H_∞ control problem is considered. This problem seeks to minimize the H₂ norm of a closed-loop transfer matrix while simultaneously satisfying a prescribed H_∞ norm bound on some other closed-loop transfer matrix by utilizing dynamic state feedback controllers. Such a problem was formulated earlier by Rotea and Khargonekar (Automatica, 27, 307–316, 1991) who considered only so called regular problems. Here, for a class of singular problems, necessary and sufficient conditions are established so that the posed simultaneous H₂/H_∞ problem is solvable by using state feedback controllers. The class of singular problems considered have a left invertible transfer function matrix from the control input to the controlled output which is used for the H₂ norm performance measure. This class of problems subsumes the class of regular problems.     

Heaps and heapsort on secondary storage

A heap structure designed for secondary storage is suggested that tries to make the best use of the available buffer space in primary memory. The heap is a complete multi-way tree, with multi-page blocks of records as nodes, satisfying a generalized heap property. A special feature of the tree is that the nodes may be partially filled, as in B-trees. The structure is complemented with priority-queue operations insert and delete-max. When handling a sequence of S operations, the number of page transfers performed is shown to be O(∑_{i = 1}^S(1/P) log_(M/P)(N_i/P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N_i, the number of records in the heap prior to the ith operation (assuming P 1 and S> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑_{i = 1}^S log₂ N_i). Using the suggested data structure we obtain an optimal external heapsort that performs O((N/P) log_(M/P)(N/P)) page transfers and O(N log₂ N) comparisons in the worst case when sorting N records.     

Biinfinite words with maximal recurrent unbordered factors

A finite non-empty word z is said to be a border of a finite non-empty word w if w=uz=zv for some non-empty words u and v. A finite non-empty word is said to be bordered if it admits a border, and it is said to be unbordered otherwise. In this paper, we give two characterizations of the biinfinite words of the form ^ωuvu^ω, where u and v are finite words, in terms of its unbordered factors.

The main result of the paper states that the words of the form ^ωuvu^ω are precisely the biinfinite words w=a₋₂a₋₁a₀a₁a₂ for which there exists a pair (l₀,r₀) of integers with l₀<r₀ such that, for every integers ll₀ and rr₀, the factor a_la_l0a_r0a_r is a bordered word.

The words of the form ^ωuvu^ω are also characterized as being those biinfinite words w that admit a left recurrent unbordered factor (i.e., an unbordered factor of w that has an infinite number of occurrences “to the left” in w) of maximal length that is also a right recurrent unbordered factor of maximal length. This last result is a biinfinite analogue of a result known for infinite words.