Embeddings ofPSL(2, 41) andPSL(2, 49) inE8(C)

We classify embeddings of the finite simple groups PSL(2, 41) andPSL (2, 49) into algebraic groups of type E₈in characteristic not dividing the orders of these respective groups. Lie theory and finite group theory point to families of elements in a group of typeE₈ over a finite field which might satisfy a presentation for our finite simple group. Techniques from computational representation theory identify all suitable systems of generators. We describe a number of methods of computation in Chevalley groups of type E₈.     

Optimal Control of the Sphere S n Rolling on E n

This paper investigates the optimal control problem concerning the sphere Sⁿ rolling without slipping on n-dimensional Euclidean space Eⁿ, n2. The differential equations governing the behaviour of the sphere constitute a sub-Riemannian distribution on the Lie group G=ⁿ×SO_n+1. Minimizing over the lengths of paths traced by the point of contact of the sphere yields an optimal control problem which is exploited using Noethers Theorem to derive a family of integrals of motion for the system. This family is then employed to prove that all optimizing trajectories are projections of normal extremals. The Lax form of the extremal equations gives rise to an additional family of integrals which is reminiscent of the Manakov integrals of motion for the free rigid body problem. Both families are required to show complete integrability if n=4.     

Local controllability of nonlinear systems

The local controllability of control systems with an arbitrary number of controls is considered, first on an open set and then at a given point; necessary conditions are derived concerning the Lie algebra T′ generated by the input vector fields, and applied to gradient systems.The main results are a geometric sufficient condition for local controllability at a point, and an equivalent condition based on the computation of Lie brackets, assuming T′ to be (n − 1)-dimensional.     

Approximate controllability of the n -th order infinite dimensional systems with controls delayed by the control devices

The main aim of this article is to derive general conditions for a few types of controllability at once for an arbitrary order abstract differential equation and arbitrary eigenvalues multiplicities, instead of conditions for fixed order equation and single eigenvalues. Another innovation of this article is taking into account delays caused by electronic control microcontrollers. This was possible thanks to analysis of the n-th order linear system in the Frobenius form, generating Jordan transition matrix of the confluent Vandermonde form. Using the explicit analytical form of the inverse confluent Vandermonde matrix enabled us to receive general conditions of different types of controllability for the infinite dimensional systems. We derived this analytical form of the inverse confluent Vandermonde matrix using new results from the linear algebra, presented in the paper by S. Hou and W. Pang, “Inversion of confluent Vandermonde matrices”, Int. J. Comput. Math. Appl., 43, pp. 1539–1547, 2002.     

Communicating processes,scheduling, and the complexity of nontermination

In this paper we study the computational complexity of the nontermination problem for systems of communicating processes with respect to five types of scheduling schemes, namely, round-robin, random, priority, first-come-first-served, and equifair schedules. We show that the problem is undecidable (₁-complete) with respect to round-robin, first-come-first-served, and priority scheduling; whereas it is decidable with respect to random and equifair scheduling. (Here ₁ denotes the set of languages whose complements are recursively enumerable.) For a restricted class of systems in which the communication channels between processes are of unit capacity, we show that the nontermination problem is solvable inO(k ² logn) nondeterministic space for round-robin, random, priority, and first-come-first-served scheduling, and inn ^{o(k 2}) nondeterministic time for equifair scheduling, wherek is the number of processes andn is the size of the maximal process. We are also able to establish a lower bound of ((k–59)/20*logn) nondeterministic space for all five types of scheduling schemes.     

Isochronous sets of invariant control systems

Let G be a connected Lie group with Lie algebra g and Σ=(G,D) a controllable invariant control system. A subset A⊂G is said to be isochronous if there exists a uniform time T_A>0 such that any two arbitrary elements in A can be connected by a positive orbit of Σ at exact time T_A. In this paper, we search for classes of Lie groups G such that any Σ has the following property: there exists an increasing sequence of open neighborhoods (V_n)_n≥0 of the identity in G such that the group can be decomposed in isochronous rings W_n=V_n+1−V_n. We characterize this property in algebraic terms and we show that three classes of Lie groups satisfy this property: completely solvable simply connected Lie groups, semisimple Lie groups and reductive Lie groups.     

A computational study of a family of nilpotent Lie algebras

This paper describes an algorithm to compute the law of the Lie algebra \mathfrakg_n\mathfrak{g}_{n} associated with the Lie group G _n , formed of all the n×n upper-unitriangular matrices. The goal of this paper is to show the algorithm that computes the law of \mathfrakg_n\mathfrak{g}_{n} and its implementation using the symbolic computation package MAPLE. In addition, the complexity of the algorithm is described.     

Uniform finite generation of compact Lie groups

Consider a compact connected Lie group G and the corresponding Lie algebra . Let {X₁,…,X_m} be a set of generators for the Lie algebra . We prove that G is uniformly finitely generated by {X₁,…,X_m}. This means that every element KG can be expressed as K=e^Xt₁e^Xt₂···e^Xt_l, where the indeterminates X are in the set {X₁,…,X_m}, , and the number l is uniformly bounded. This extends a previous result by F. Lowenthal in that we do not require the connected one dimensional Lie subgroups corresponding to the X_i, i=1,…,m, to be compact. We link the results to the existence of universal logic gates in quantum computing and discuss the impact on bang bang control algorithms for quantum mechanical systems.     

On global controllability of discrete-time control systems

Let x_n+1=exp(A+uB)x_n be a discrete-time control system which is obtained by discretizing a continuous-time bilinear system. This paper gives sufficient conditions on the matricesA andB for global controllability of this system. These conditions are similar to those of Jurdjevic and Kupka [JK1] for the continuous-time case.This research was partially supported by CNPq Grant No. 301060/94-0.     

Average-case analysis of the Modified Harmonic algorithm

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i } _i=1 ^k where theN _i 's have a joint multinomial distribution for eachn= _i=1 ^k ,N _i . LetE(f ₁) O andE(f ₂) 0. Then lim_n E(max(_{f 1},f ₂ ))/n = lim _n max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.     

Motion control of drift-free, left-invariant systems on Lie groups

In this paper we address the constructive controllability problem for drift-free, left-invariant systems on finite-dimensional Lie groups with fewer controls than state dimension. We consider small (ϵ) amplitude, low-frequency, periodically time-varying controls and derive average solutions for system behavior. We show how the pth-order average formula can be used to construct open-loop controls for point-to-point maneuvering of systems which require up to (p-1) iterations of Lie brackets to satisfy the Lie algebra controllability rank condition. In the cases p=2,3, we give algorithms for constructing these controls as a function of structure constants that define the control authority, i.e., the actuator capability, of the system. The algorithms are based on a geometric interpretation of the average formulas and produce sinusoidal controls that solve the constructive controllability problem with O(ϵ^P) accuracy in general (exactly if the Lie algebra is nilpotent). The methodology is applicable to a variety of control problems and is illustrated for the motion control problem of an autonomous underwater vehicle with as few as three control inputs     

Average-case analysis of the Modified Harmonic algorithm

In this paper we analyze the average-case performance of the Modified Harmonic algorithm for on-line bin packing. We first analyze the average-case performance for arbitrary distribution of item sizes over (0,1]. This analysis is based on the following result. Letf ₁ andf ₂ be two linear combinations of random variables {N _i } _i=1 ^k where theN _i 's have a joint multinomial distribution for eachn=σ _i=1 ^k ,N _i . LetE(f ₁) ≠ O andE(f ₂)≠ 0. Then lim_{n →}∞E(max(_{f 1},f ₂ ))/n = lim _n →∞ max(E(f ₁),E(f ₂))/n. We then consider the special case when the item sizes are uniformly distributed over (0,1]. For specific values of the parameters, the Modified Harmonic algorithm turns out to be better than the other two linear-time on-line algorithms—Next Fit and Harmonic—in both the worst case as well as the average case. We also obtain optimal values for the parameters of the algorithm from the average-case standpoint. For these values of the parameters, the average-case performance ratio is less than 1.19. This compares well with the performance ratios 1.333. and 1.2865. of the Next Fit algorithm and the Harmonic algorithm, respectively.     

On singularities of flat affine systems with n states and n−1 controls

We study the set of intrinsic singularities of flat affine systems with n?1 controls and n states using the notion of Lie‐Bäcklund atlas, previously introduced by the authors. For this purpose, we prove two easily computable sufficient conditions to construct flat outputs as a set of independent first integrals of distributions of vector fields: the first one in a generic case, namely, in a neighborhood of a point where the n?1 control vector fields are independent and the second one at a degenerate point where p?1 control vector fields are dependent of the n?p others, with p>1. After introducing the Γ‐accessibility rank condition, we show that the set of intrinsic singularities includes the set of points where the system does not satisfy this rank condition and is included in the set where a distribution of vector fields introduced in the generic case is singular. We conclude this analysis by three examples of apparent singularities of flat systems in generic and nongeneric degenerate cases.     

Dynamic maintenance of planar digraphs, with applications

We show that a planarst-graphG admits two total orders on the setVE F, whereV, E, andF are respectively the set of vertices, edges, and faces ofG, with ¦V¦ =n. Assuming thatG is to be dynamically modified by means of insertions of edges and expansions of vertices (and their inverses), we exhibit anO(n)-space dynamic data structure for the maintenance of these orders such that an update can be performed in timeO(logn). The discovered structural properties of planarst-graphs provide a unifying theoretical underpinning for several applications, such as dynamic point location in planar monotone subdivisions, dynamic transitive-closure query in planarst-graphs, and dynamic contact-chain query in convex subdivisions. The presented techniques significantly outperform previously known solutions of the same problems.This work was carried out at the University of Illinois and was supported in part by National Science Foundation Grant ECS-84-10902 and by the Joint Services Electronics Program under Contract N00014-84-C-0149.     

Four rendezvous problems for n non-identical simple-integral plants

Four rendezvous problems for n non-identical simple-integral plants (K ₁/s, K₂/s,[tdot],K_n/s), with a common input x(t) = A_mi^m u(t), m = 0,1,2,[tdot], and initial output conditions of (ξ₁,ξ₂,[tdot], ξ_n), are studied in this paper. These rendezvous problems, generally speaking, are concerned with transferring the n plants outputs to meet one another in a finite time (at a. fixed target or on a non-stationary one).     

Discrete-time linear periodic systems: A note on the reachability and controllability interval length

Discrete-time linear systems with periodic coefficients of period T are considered in this paper. The reachability and controllability indices at time t for periodic systems, μ_rt and μ_ct, are defined. It is shown that the reachability [controllability] subspace at time t does coincide with the reachability [controllability] subspace over the interval (t − μ_rt,T, t) [(t, t + μ_ct.,T)] and properly includes the reachability [controllability] subspace over the interval (t −(μ_rt−1) T, t) [(t, t +(μ_cr−1)T)].     

Economy of description by parsers,DPDA's,and PDA's

It is shown that there is a sequence of languages E₁, E₂,… such that every correct prefix parser (one which detects errors at the earliest possible moment, e.g., LR or LL parsers) for E_n has size 2^cn, yet a deterministic PDA recognizing E_n exists and has size O(n²). There is another easily described sequence of languages N₁, N₂,… for which N has a nondeterministic PDA of size O(n²), but no deterministic PDA of size less than 2^cn. It is shown moreover, that this latter gap can be made arbitrarily large for different sequences of languages.     

A note on generalized Euler numbers and polynomials

In this paper we construct new generalized Euler polynomials and generalized Euler numbers attached to χ. We investigate some of the properties that are related to generalized Euler polynomials. We also derive the existence of a specific interpolation function that interpolates generalized Euler polynomials at negative integers. Finally, we investigate computationally the roots of the generalized Euler polynomials E _{n, χ}(x) for values of the index n.     

Necessary conditions for exact controllability with a finite-dimensional input space

We derive necessary conditions for exact controllability of infinite-dimensional systems described by , where the generator A has a Riesz basis of eigenvectors and the input space is finite-dimensional. These conditions are in terms of the eigenvalues of A and the degree of unboundedness of B, but no further information about B is needed. Our results easily imply lack of exact controllability for a wide range of distributed parameter systems. It is known from partial differential equation (PDE) examples that the addition of damping into an exactly controllable second order system can destroy exact controllability. We discuss the effect of damping on such systems using our general conditions. We also give simple new proofs for results about the lack of exact controllability of hyperbolic systems in more than one space dimension.     

On the effective generation of set elements within specified ranges

A recursive functiong is augmenting ifg(n) n for alln. Ag-constructor for a setA is a Turing machine that on inputn outputs some element ofA betweenn andg(n), inclusive, if such an element exists. Ag-generator forA outputs all elements ofA betweenn andg(n). Ag-detector merely determines whether there exist any elements in the given range. Total constructors (generators, detectors) always halt, and indicate whether or not any elements exist in the set in the given range; partial machines need not halt in the event that no such elements exist.We characterize the classes of sets having each of these types of machines. We also establish that the problems of determining, for a given recursively enumerable setA and augmenting functiong, whetherA has a total or partialg-generator or a totalg-constructor or detector are all ₃-complete; and we determine, for fixedg, the relationships among the classes of sets having these different types of machines.Part of this work was done while the author was an AT&T Bell Labs Scholar at the Computer Science Department of the University of Rochester.