Characterization of normal forms possessing inverse in the λ-β-η-calculus

The aim of this paper is to generalize a result given by Curry and Feys, who have shown that the only regular combinators possessing inverse in the λ-β-η-calculus are the permutators, whose definition is p=λzλx₁…λx_n(zx_i1…x_in) for n?0 where i₁,…, i_r is a permutation of 1,…, n. Here we extend this characterization to the set of normal forms, showing that the only normal forms possessing inverse in the λ-βη-calculus are the “hereditarily finite permutators” (h.f.p.), whose recursive definition is: if n?0, P_j (1?j?n) are h.f.p. and i₁,…,i_n is a permutation of 1,…, n, then the normal form of P = λzλx₁…λx_n(z(P₁x_i1))… (P_nin) is an h.f.p.     

A generalization of the Schützenberger product of finite monoids

For each n?1, an n-ary product ? on finite monoids is constructed. This product has the following property: Let Σ be a finite alphabet and Σ¹ the free monoid generated by Σ. For i = 1, …,n, let A_i be a recognizable subset of Σ¹, M(A_i) the syntactic monoid of A_n and M(A₁?A_n) the syntactic monoid of the concatenation product A₁?A_n. Then M(A₁?A_n)< ? (M(A₁),…,M(A_n)). The case n = 2 was studied by Schützenberger. As an application of the generalized product, I prove the theorem of Brzozowski and Knast that the dot-depth hierarchy of star-free sets is infinite.     

Some characterizations of finitely specifiable implicational dependency families

Let r be a relation for the relation scheme R(A₁,A₂,…,A_n); then we define Dom(r) to be Dom_r(A₁)×Dom_r(A₂)×…×Dom_r(A_n), where Dom_r(A_i) for each i is the set of all ith coordinates of tuples of r. A relation s is said to be a substructure of the relation r if and only if Dom(s)∩r = s.The following theorems analogous to Tarski-Fraisse-Vaught's characterizations of universal classes are proved: (i) An implicational dependency family (ID-family) F over the relation scheme R is finitely specifiable if and only if there exists a finite number of relations r₁,r₂,…,r_m for R such that r ∈ F if and only if no r_i is isomorphic to a substructure of r. (ii) F is finitely specifiable if and only if there exists a natural number k such that r ∈ F whenever F contains all substructures of r with at most k elements.We shall use these characterizations to obtain a new proof for Hull's (1984) characterization of finitely specifiable ID-families.     

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.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

The formula of the solution for some classes of initial boundary value problems for the hyperbolic equation with two independent variables

A new representation is proved of the solutions of initial boundary value problems for the equation of the form u _xx (x, t) + r(x)u _x (x, t) ? q(x)u(x, t) = u _tt (x, t) + μ(x)u _t (x, t) in the section (under boundary conditions of the 1st, 2nd, or 3rd type in any combination). This representation has the form of the Riemann integral dependent on the x and t over the given section.     

Bounded solutions of nonlinear difference equations with advanced arguments

Sufficient conditions of existence and uniqueness of α-bounded and bounded solutions to the difference equation with advancedd arguments x(n + 1) = A(n)x(n) + B(n)x(σ₁(n)) + f(n, x(n), x(σ₂(n)), σ_i(n) ⩾ n + 1, i = 1,2, are given. It is proven that under certain conditions it is possible to find positive numbers R, μ, such that from every initial condition ξ satisfying ∥ξ∥ ⩽ R, a unique bounded solution, belonging to the ball ∥x∥ ⩽ μ, starts.     

The construction of mutually independent Hamiltonian cycles in bubble-sort graphs

A Hamiltonian cycle C=? u ₁, u ₂, …, u _n(G), u ₁ ? with n(G)=number of vertices of G, is a cycle C(u ₁; G), where u ₁ is the beginning and ending vertex and u _i is the ith vertex in C and u _i ≠u _j for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C ₁, C ₂, …, C _k } of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(B _n )=n?1 if n≥4, where B _n is the n-dimensional bubble-sort graph.     

How to improve mamdani's approach to fuzzy control

Fuzzy control is a methodology that translates “if”-“then” rules, A_ji (x₁) &…& A_jn(x_n) → B_j(u), formulated in terms of a natural language, into an actual control strategy u(x). Implication of uncertain statements is much more difficult to understand than “and,” “or,” and “not.” So, the fuzzy control methodologies usually start with translating “if”-“then” rules into statements that contain only “and,” “not,” and “or.” the first such translation was proposed by Mamdani in his pioneer article on fuzzy control. According to this article, a fuzzy control is reasonable iff one of the rules is applicable, i.e., either the first rule is applicable (A₁₁(x₁) &…& A_1n(x_n) & B₁(u)), or the second one is applicable, etc. This approach turned out to be very successful, and it is still used in the majority of fuzzy control applications. However, as R. Yager noticed, in some cases, this approach is not ideal: Namely, if for some x, we know what u(x) should be, and add this crisp rule to our rules, then the resulting fuzzy control for this x may be different from the desired value u(x). to overcome this drawback, Yager proposed to assign priorities to the rules, so that crisp rules get the highest priority, and use these priorities while translating the rules into a control strategy u(x). In this article, we show that a natural modification of Mamdani's approach can solve this problem without adding any ad hoc priorities. © 1995 John Wiley & Sons, Inc.     

On multiplication in algebraic extension fields

In this paper we characterize all algorithms for obtaining the coefficients of (Σ^n?1_i=0x_iuⁱ)(Σ^n?1_i=0y_iuⁱ) mod P(u), where P(u) is an irreducible po lynomial of degree n, which use 2n ? 1 multiplications. It is shown that up to equivalence, all such algorithms are obtainable by first obtaining the coefficients of the product of two polynomials, and then reducing modulo the irreducible polynomial.     

On selecting thek largest with median tests

LetW _itk(n) be the minimax complexity of selecting thek largest elements ofn numbersx ₁,x ₂,...,x _n by pairwise comparisonsx _i :x _j . It is well known thatW ₂(n) =n?2+ [lgn], andW _k (n) = n + (k?1)lg n +O(1) for all fixed k ≥ 3. In this paper we studyW′ _k (n), the minimax complexity of selecting thek largest, when tests of the form “Isx _i the median of {x _i ,x _j ,x _t }?” are also allowed. It is proved thatW′₂(n) =n?2+ [lgn], andW′ _k (n) =n + (k?1)lg₂ n +O(1) for all fixedk≥3.     

Sorting a sequence of strong kings in a tournament

A king in a tournament is a player who beats any other player directly or indirectly. According to the existence of a king in every tournament, Wu and Sheng [Inform. Process. Lett. 79 (2001) 297-299] recently presented an algorithm for finding a sorted sequence of kings in a tournament of size n, i.e., a sequence of players u₁,u₂,…,u_n such that u_i→u_i+1 (u_i beats u_i+1) and u_i is a king in the sub-tournament induced by {u_i,u_i+1,…,u_n} for each i=1,2,…,n−1. With each pair u,v of players in a tournament, let b(u,v) denote the number of third players used for u to beat v indirectly. Then, a king u is called a strong king if the following condition is fulfilled: if v→u then b(u,v)>b(v,u). In the sequel, we will show that the algorithm proposed by Wu and Sheng indeed generates a sorted sequence of strong kings, which is more restricted than the previous one.     

Two theorems concerning recognizable N-subsets of σ1

It is proved that the family of recognizable N-subsets is not closed under the operation sup, and that there exists even a DOL length sequence x₀, x₁, … such that, for any k,x_i ? x_i+1 ? … ? x_i+k holds true for some i and the cardinality of the set {n ∈ N|x_n > x_n+1} is infinite.     

Exact solution of mixed problems for variable coefficient one-dimensional diffusion equation

This paper deals with diffusion problems modeled by the equation a(t)u_xx = u_t, x > 0, t > 0, u(x, 0) = c(x) together with the boundary condition u(0, t) = b(t) or u_x(0, t) = b(t). By using Fourier transforms, existence conditions and exact solutions of the above mixed problems are given.     

Ring models for delay-differential systems

This paper studies the algebraic structure of linear systems defined over R[λ], the ring of polynomials in λ with real coefficients. Natural definitions of controllability and observability are introduced and properties of R[λ]-transfer matrix realizations are discussed. It is shown that (A_n×n,D_n×m) is a controllable R[λ]-matrix pair if and only if for each set of polynomialsβ₁,β₂,…,β_n, in R[λ] there exists an R[λ] feedback matrixF such that detsI?A?BF]=∏i=1n(s+β_i). By regarding λ as a suitably defined delay operator, it is explained how this result might be applied to delay-differential systems in order to control dynamic response.     

Interpolation that leads to the narrowest intervals and its application to expert systems and intelligent control

In many real-life situations, we want to reconstruct the dependencyy=f(x ₁,…, x_n) from the known experimental resultsx _i ^(k) , y^(k). In other words, we want tointerpolate the functionf from its known valuesy ^(k)=f(x ₁ ^(k) ,…, x _n ^(k) ) in finitely many points $\bar x^{(k)} = (x_1^{(k)} , \ldots ,x_n^{(k)} )$ , 1≤k≤N There are many functions that go through given points. How to choose one of them? The main goal of findingf is to be able to predicty based onx _i. If we getx _i from measurements, then usually, we only getintervals that containx _i. As a result of applyingf, we get an interval y of possible values ofy. It is reasonable to choosef for which the resulting interval is the narrowest possible. In this paper, we formulate this choice problem in mathematical terms, solve the corresponding problem for several simple cases, and describe the application of these solutions to intelligent control.     

Generalized dilations and the stabilization of uncertain systems via measurement feedback

We study the problem of semiglobally stabilizing uncertain nonlinear system

Full-size image

, with (A,B) in Brunowski form. We prove that if p₁(z,u,t)u and p₂(z,u,t)u are of order greater than 1 and 0, respectively, with “generalized” dilation δ_l(z,u)=(l¹⁻ⁿz₁,…,l⁻¹z_n−1,z_n,lu) and uniformly with respect to t, where z_i is the ith component of z, then we can achieve semiglobal stabilization via arbitrarily bounded linear measurement feedback.     

Information-theoretic characterizations of recursive infinite strings

Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the program-size complexity relative to n of its n-bit prefixes x_n. Meyer has shown that x is recursive iff ?c, ?n, K(x_n?n) ? c, and Loveland has shown that this is false if one merely stipulates that K(x_n?n) ? c for infinitely many n. We strengthen Meyer's theorem. From the fact that there are few minimal-size programs for calculating n given result, we obtain a necessary and sufficient condition for x to be recursive in terms of the absolute program-size complexity of its prefixes: x is recursive iff ?c, ?n, K(x_n) ? K(n) + c. Again Loveland's method shows that this is no longer a sufficient condition for x to be recursive if one merely stipulates that K(x_n) ? K(n) + c for infinitely many n.     

Disjoint paths in hypercubes with prescribed origins and lengths

Given (i) any k vertices u ₁, u ₂, …, u _k (1≤k<n) in the n-cube Q _n , where (u ₁, u ₂), (u ₃, u ₄), …, (u _2m?1, u _2m ) (m≤? k\2 ?) are edges of the same dimension, (ii) any k positive integers a ₁, a ₂, …, a _k such that a ₁, a ₂, …, a _2m are odd and a _2m+1, …, a _k are even, with a ₁+a ₂+···+a _k =2 ⁿ , and (iii) k subsets W ₁, W ₂, …, W _k of V(Q _n ) with |W _i |≤n?k and if a _i =1, then u _i ¬∈W _i , for 1≤i≤k, we show that there exist k vertex-disjoint paths P ₍₁₎, P ₍₂₎, …, P _(k) in Q _n where P _(i) contains a _i vertices, its origin is u _i , and its terminus is in V(Q _n )/ W _i , for 1≤i≤k. We also prove a similar result which extends two well-known results of Havel, [I. Havel On hamilton circuits and spanning trees of hypercubes, ?asopis pro P?stování Matematiky, 109 (1984), pp. 135–152.] and Nebeský, [L. Nebeský Embedding m-quasistars into n-cubes, Czech. Math. J. 38 (1988), pp. 705–712].