On zigzag permutations and comparisons of adjacent elements

Each permutation (a₁, a₂,…, a_n) of 1, 2,…, n determines a sequence of “<” and “>” relations determined by the relat holding between adjacent values (a_i, a_{i + 1}). A new and elementary algorithm is given, which, for every such pattern of “<”, “>” relations, computes the number of permutations with that pattern. The algorithm enables one to calculate (in bits) the amount of information gained by comparing all adjacent pairs of elements in a list. It also has a simple extension to circular patterns of relations.     

The complexity of preemptive scheduling given interprocessor communication delays

We discuss the problem of scheduling af set of independent tasks T, each t_i ϵ T of lenght ℓ_i ϵ Z⁺, on m identical processors. We allow preemption but assume a communication delay of time k ϵ N. Whenever a task is preempted from one processor to another, there must be a delay of at least k time units. We show that if k = 1, an optimal schedule can be found in polynomial time but if k ⩾ 2, the corresponding decision problem is NP-complete.     

Investigation of some probabilistic characteristics of one class of semi-Markov wandering with delaying screens

The process of semi-Markov wandering with delaying screens “b” and “a” (a > b > 0) is constructed by the given sequence of independent and identically distributed random vectors (ξ _i , η _i ), i ≥ 1. The integral equation for the Laplace transform by time and the Laplace-Stieltjes transform by the phase of its conditional distribution is derived. If the wandering occurs by a complicated Laplace distribution, the ergodic distribution of the process and its moments are found. Then, the integral equation for the generating function of the conditional distribution of the number of process steps at which it firstly reaches the level a is derived. When the wandering occurs by the simple Laplace distribution, its generating functions and moments are found.     

Further Towards a Triadic Calculus

Now we introduce the existential quantifier Σ (read “there is some …”) and the universal quantifier II (read “all,” or “everybody” or “everything”). Application of a quantifier to a triada gives a lower structure (a structure with a lower number of blanks). For example, H_jk = _iG_ijk reads “there is some who gives __ to __,” (S29) that is, a diadic structure.     

A bottom‐up algorithm for weight‐ and height‐bounded minimal partition of trees

Let T = (V,E) be a rooted tree with n edges. We associate a non‐negative weight w(v) with each vertex v in V. A q‐partition of T into q connected components T₁,...,T_q is obtained by deleting k = q‐1 edges of T, 1<=q<=n. Let w(T_i) denote the sum of the weights of the vertices in T_i. The height of 7] is denoted by h(T_i).

The following problem is considered: Given W, H>0, find a q‐partition satisfying w(T_i) <=W, height (T_i) <=,H (1<=i<=q) for which q is a minimum.

A bottom‐up polynomial time algorithm is given for this problem which has complexity 0(Hn), or independently of H, 0(height(T)n).     

A distribution-free geometric upper bound for the probability of error of a minimum distance classifier

An upperbound to the probability of error per class in a multivariate pattern classification is derived. The bound, given by

$\text{P(E|class w}{}_{\mathrm{i}}\text{)≤}\text{N}\text{R}{}^2{}_{\mathrm{i}}$

is derived with minimal assumptions; specifically the mean vectors exist and are distinct and the covariance matrices exist and are non-singular. No other assumptions are made about the nature of the distributions of the classes. In equation (i) N is the number of features in the feature (vector) space and R_i is a measure of the “radial neighbourhood” of a class. An expression for R_i is developed. A comparison to the multivariate Gaussian hypothesis is presented.     

Lumped model of a non-linear distributed system by finite element method

The finite element method has been used to find an approximate lumped parameter model of a non-linear distributed parameter system. A one dimensional non-linear dispersion system is considered. The space domain is divided into a finite set of k elements. Each element, has n nodes. Within each element the concentration is represented by C(x,t)^(e) = [N][C] ^T where [N] = [n₁(x),n₂(x), [tdot] n_n(x)] and [C] = [C₁(t),C₂(t), [tdot] C_n(t)]. By using Galerkin's criterion a set of (k × n ? n+ 1) first order differential equations are obtained for C_i(t). These equations are solved by an iterative method. The concepts are illustrated by an example taking five three-node elements in the space domain. The results are compared with those obtained by a finite difference method. It is shown that the finite element method can be used effectively in modelling of a distributed system by a lumped system.     

Minimierung des Rechenaufwandes bei Globalisierungen spezieller Iterationsverfahren vom Typ Minimales Residuum

Local iteration methods for the solution of nonlinear operator equationsT(x)=0 can be “globalized” by the method of embedding. This means that the initial valuex ₀ need not be in the neighbourhood of a solution \(\bar x\) . We restrict ourselves to a stepwise calculation — see [17] — where one solves the chain of problems:T(x, s _i )=0, 0=s ₀<s ₁<...<s _N =1 by a local iteration method with the solutionx _i?1 ofT(x, s _i?1)=0 used as initial vector forT(x, s _i )=0. In this paper we examine methods of minimal-residue-type. Results on the minimization of the whole effort by selection of an “optimal” step width can be obtained. Furthermore, a global convergence acceleration can be reached by suitable adaption of (linear) interpolation on the step width. The reslts obtained can be transferred without difficulties to any other local iteration method which is based on the principle contraction.     

On a Retrial Single-Server Queueing System with Finite Buffer and Multivariate Poisson Flow

We consider a single-server queueing system with a finite buffer, K input Poisson flows of intensities _i , and distribution functions B _i (x) of service times for calls of the ith type, . If the buffer is overflowed, an arriving call is sent to the orbit and becomes a repeat call. In a random time, which has exponential distribution, the call makes an attempt to reenter the buffer or server, if the latter is free. The maximum number of calls in the orbit is limited; if the orbit is overflowed, an arriving call is lost. We find the relation between steady-state distributions of this system and a system with one Poisson flow of intensity where type i of a call is chosen with probability _i / at the beginning of its service. A numerical example is given.     

Bandwidth packing

We model a server that allocates varying amounts of bandwidth to “customers” during service. Customers could be computer jobs with demands for storage bandwidth or they could be calls with demands for transmission bandwidth on a network link. Service times are constants, each normalized to 1 time unit, and the system operates in discrete time, with packing (scheduling) decisions made only at integer times. Demands for bandwidths are for fractions of the total available and are limited to the discrete set {1/k, 2/k, …, 1} wherek is a given parameter. More than one customer can be served at a time, but the total bandwidth allocated to the customers in service must be at most the total available. Customers arrive ink flows and join a queue. Thejth flow has rate λ _j and contains just those customers with bandwidth demandsj/k. We study the performance of the two packing algorithms First Fit and Best Fit, both allocating bandwidth by a greedy rule, the first scanning the queue in arrival order and the second scanning the queue in decreasing order of bandwidth demand. We determine necessary and sufficient conditions for stability of the system under the two packing rules. The average total bandwidth demand of the arrivals in a time slot must be less than 1 for stability under any packing rule, i.e., the condition $$\rho {\text{ : = }}\sum\limits_i {\lambda i\left( {i/k} \right)} {\text{< 1}}$$ must hold. We prove that if the arrival rates λ₁, …, λ _k?1 are symmetric, i.e., λ _i =λ _k?i for alli, 1 ≤i ≤k ? 1, theρ<1 is also sufficient for stability under both rules. Our Best Fit result strengthens an earlier result confined to Poisson flows and equal rates λ₁=…=λ _{k ? 1}, and does so using a far simper proof. Our First Fit result is completely new. The work here extends earlier results on bandwidth packing in multimedia communication systems, on storage allocation in computer systems, and on message transmission along slotted communication channels. It is not surprising thatρ<1 is sufficient under Best Fit, since in a congested system, Best Fit tends to serve two complementary (matched) customers in each time slot, with bandwidth demands beingi/k and (k ? i)/k for somei, 1 ≤i ≤k ? 1. It is not so obvious, however, thatρ<1 is also sufficient under First Fit. Interestingly, when the system becomes congested, First Fit exhibits a “self-organizing” property whereby an ordering of the queue by time of arrival becomes approximately the same as an ordering by decreasing bandwidth demand.     

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.     

General eigenvalue placement in linear control systems by output feedback

Consider the time-invariant system E[xdot] = Ax + Bu, y = Cx where E is a square matrix that may be singular. The problem is to find constant matrices K and L, such that the feedback law u = Ky+L[ydot] yields x = exp (λt)v_i (where v_i is some constant vector) for some preassigned λ_i (i=l, 2, [tdot], r). This problem is equivalent to that of finding K and L which makes a preassigned λ _i an eigenvalue corresponding to the general eigenvalue problem {λ(E ? BLC) ? (A + BKC)}v=0. Using matrix generalized inverses, a method is developed for the construction of a linear system of equations from which the elements of K and L may be computed.     

A Model for Minimizing Active Processor Time

We introduce the following elementary scheduling problem. We are given a collection of n jobs, where each job J _i has an integer length ? _i as well as a set T _i of time intervals in which it can be feasibly scheduled. Given a parameter B, the processor can schedule up to B jobs at a timeslot t so long as it is “active” at t. The goal is to schedule all the jobs in the fewest number of active timeslots. The machine consumes a fixed amount of energy per active timeslot, regardless of the number of jobs scheduled in that slot (as long as the number of jobs is non-zero). In other words, subject to ? _i units of each job i being scheduled in its feasible region and at each slot at most B jobs being scheduled, we are interested in minimizing the total time during which the machine is active. We present a linear time algorithm for the case where jobs are unit length and each T _i is a single interval, assuming that jobs are given in sorted order. For general T _i , we show that the problem is NP-complete even for B=3. However when B=2, we show that it can be efficiently solved. In addition, we consider a version of the problem where jobs have arbitrary lengths and can be preempted at any point in time. For general B, the problem can be solved by linear programming. For B=2, the problem amounts to finding a triangle-free 2-matching on a special graph. We extend the algorithm of Babenko et al. (Proceedings of the 16th Annual International Conference on Computing and Combinatorics, pp. 120–129, 2010) to handle our variant, and also to handle non-unit length jobs. This yields an \(O(\sqrt{L} m)\) time algorithm to solve the preemptive scheduling problem for B=2, where L=∑ _i ? _i . We also show that for B=2 and unit length jobs, the optimal non-preemptive schedule has active time at most 4/3 times that of the optimal preemptive schedule; this bound extends to several versions of the problem when jobs have arbitrary length.     

Parallel complexity of logical query programs

We consider the parallel time complexity of logic programs without function symbols, called logical query programs, or Datalog programs. We give a PRAM algorithm for computing the minimum model of a logical query program, and show that for programs with the “polynomial fringe property,” this algorithm runs in time that is logarithmic in the input size, assuming that concurrent writes are allowed if they are consistent. As a result, the “linear” and “piecewise linear” classes of logic programs are inN C. Then we examine several nonlinear classes in which the program has a single recursive rule that is an “elementary chain.” We show that certain nonlinear programs are related to GSM mappings of a balanced parentheses language, and that this relationship implies the “polynomial fringe property;” hence such programs are inN C Finally, we describe an approach for demonstrating that certain logical query programs are log space complete forP, and apply it to both elementary single rule programs and nonelementary programs.     

Fine structure of a one-dimensional discrete point system

We consider a system of N points x ₁ < ... < x _N on a segment of the real line. An ideal system (crystal) is a system where all distances between neighbors are the same. Deviation from idealness is characterized by a system of finite differences ? _i ¹ = x _x+1 ? x _i , ? _i ^k+1 = ? _i+1 ^k ? ? _i ^k , for all possible i and k. We find asymptotic estimates as N ?? ??, k????, for a system of points minimizing the potential energy of a Coulomb system in an external field.     

Combined stiffening and in-plane boundary conditions effects on the buckling of circular cylindrical stiffened-shells

The influence of in-plane boundary conditions on the critical loads of axially compressed simply supported stiffened cylindrical shells, stiffened by stringers and by combinations of rings and stringers is studied. It is observed that the axial restraint, u = 0, at the edges and the dimensions of either the stringers or the rings characterize the type of influence experienced. In shells stiffened by “medium” and “heavy” stringers the axial restraint is a predominant factor and the “weak in shear”, N_xφ = 0, B.Cs. have only a slight secondary effect. For such shells a “stiffening” effect is observed for SS2 and SS4 B.Cs. As the stringers become “weaker” the influence of the axial restraint diminishes and the isotropic or ring-stiffened like type of behavior, “sensitivity” to the vanishing of the circumferential restraint, overcomes the “stiffening” effect due to u = 0.In shells stiffened by combinations of rings and stringers the influence of the in-plane boundary conditions is governed by the relative magnitudes of the rings and stringers under consideration. Combinations of “heavy” stringers and “weak” rings behave like stringer-stiffened shells, exhibiting the “stiffening” effect due to u = 0 whereas shells stiffened by “heavy” rings and “light” stringers tend to behave like ring-stiffened shells, revealing their “sensitivity” to the “weak in shear” boundary conditions, N_xφ = 0.     

A virtual reality system for the treatment of stress-related disorders: A preliminary analysis of efficacy compared to a standard cognitive behavioral program

This paper presents preliminary efficacy data in a controlled study of the use of a virtual reality (VR) system for treating stress-related disorders (Post-Traumatic Stress Disorder, or PTSD; Pathological Grief, or PG; and Adjustment Disorders, or AD). “EMMA's World” is a VR application in which patients can explore negative experiences to the degree required for their specific therapeutic needs. To accomplish therapeutic goals, a series of virtual elements is customized to be meaningful to the user; the elements contain the fundamental emotional components that the person must confront. Thirty-nine participants diagnosed with PTSD (N=10), PG (N=16), and AD (N=13) were randomly assigned to a standard cognitive-behavioral program (CBT) (N=20) or a CBT program driven by EMMA's World (N=19). Participants were assessed before and after treatment. Measurements related to anxiety, depression and other emotions, maladjustment and interference were applied. Results indicate that CBT with EMMA's World was as effective as the standard CBT program for the treatment of these disorders, and the statistically significant differences (depression, relaxation intensity and social area interference) were in favor of EMMA's World. We expect VR to provide a positive alternative that will draw in clients who do not seek traditional forms of treatment.     

Computing the number of mergings with constraints

A merging of two ordered lists x₁,…,x_p and y₁,…:,y_q is said to be constrained if it must satisfy prescribed conditions form “x_i precedes y_j” and “y_r precedes x_s”. An algorithm is given for calculating the number of mergings which satisfy any given set of constraints. The algorithm has time complexity O(pq) but in many cases runs significantly faster. It is illustrated with examples which involve the Catalan and Fibonacci numbers.     

Utilization Based Schedulability Bounds for Age Constraint Process Sets in Real-Time Systems

Some real-time systems consist of a number of processes that operate under age constraints. In such systems, the maximum time from the start of process L _i in cycle k to the end in cycle k+1 must not exceed the age constraint A _i for that process. The age constraint can be met by using fixed priority scheduling and periods equal to A _i/2. However, this approach restricts the number of process sets which are schedulable. In this paper, we define a method for obtaining process periods other than A _i/2. The periods are calculated in such a way that the age constraints are met. Our approach is better in the sense that a larger number of process sets can be scheduled compared to using periods equal to A _i/2. The main results in this paper are a number of performance bounds on age constraint processes. These bounds show that there is a significant gain in worst case as well as in best case behavior by using periods other than A _i/2, particularly when there are a large number of processes in the system.     

Wireless emergency alerts: Public understanding,trust, and preferences following the 2021 US nationwide test

On August 11, 2021, the US Federal Emergency Management Agency and Federal Communications Commission (FCC) conducted the second national test of the wireless emergency alerts (WEA) system. The first test was conducted in 2018. This study offers an analysis of a nationwide survey (N = 1056) administered in the days immediately following the 2021 national test. The analysis indicates that a substantial number of respondents do not well understand the uses of the WEA system, especially the “National Alert” message class. However, more respondents believe that the “National Alert” message class label would signal more trustworthy information than the “Presidential Alert” message class label, a finding that bolsters the FCC's 2021 decision to abandon the “Presidential Alert” message class label. Despite a lack of accurate understanding of message classes and opt-out options, a substantial number of respondents trust the WEA system to work properly. A clear majority of respondents would appreciate device-based public education materials about the WEA system. The implications of the survey findings for WEA system management and public education are discussed.