Insertion languages

The operations of insertion ( ← ) and iterated insertion ( ←₁ ) are simple variants of Kleene's operations · and 1 [15] in a manner similar to the operations shuffle and iterated shuffle (see e.g. [13, 23, 20, 14]). Using the operation of iterated insertion, we can generate both the semi-Dyck and the two-sided Dyck languages from certain finite subsets of these languages. Thus the class of languages of the form $\text{S}{}^{\mathrm{\leftarrow }}{}^1$ for finite S forms a natural class of generalized Dyck languages. This class is equivalent to the class of pure unitary languages discussed in [6]. We investigate this class further, by examining for it the problems of equivalence, ambiguity, and determinism, all of which are easily decidable. On the other hand, we show that the problem “$\text{S}{}^{\mathrm{\leftarrow }}\text{1 ∩ T}{}^{\mathrm{\leftarrow }}\text{1 = {λ}?}$” is undecidable for finite, unambiguous S and T. Furthermore, by extending the regular expressions to include the operations ← and $\text{←}{}_1$, we obtain the class of insertion languages which generalizes both the regular languages and the Dyck languages, but is properly contained within the class of context-free languages. Our main result here is that the problem “$\text{L = ∑}{}^1\text{?}$” is undecidable for the class of insertion languages. From this result, it follows that the equivalence problem and the problem “IsL regular?” are also undecidable for this class.     

On nonstochastic languages and homomorphic images of stochastic languages

Using a simple method we find some nonstochastic and stochastic languages related to the Dyck sets and to the languages $\text{{wcw¦w in {a, b}}{}^1\text{}}$ and $\text{{wcw}{}^{\mathrm{R}}\text{¦w in {a, b}}{}^1\text{}}$. Using the theory of uniformly distributed sequences, we present a sufficient condition for a one-letter language to be nonstochastic. Among the applications is the result that {a^p¦p is a prime} is nonstochastic. We also study the images of stochastic and rational stochastic languages under nonerasing and arbitrary homomorphisms as well as their relations to some well-known families. Finally, we introduce a large class of bounded languages and show that it is contained in /of_∩ (DUP) = the smallest intersection-closed AFL containing $\text{DUP}\text{= {a}{}^{\mathrm{n}}\text{b}{}^{\mathrm{n}}\text{¦n in N}}$, which is a subfamily of /oK(/oL_Q = the image of the family of rational stochastic languages under nonerasing homomorphisms.     

Flip-pushdown automata with k pushdown reversals and E0L systems are incomparable

We prove that any propagating E0L system cannot generate the language {w#w|w∈{0,1}^?}$\{w\mathrm{\#}w|w\in {\{0,1\}}^{?}\}$. This result, together with some known ones, enables us to conclude that the flip-pushdown automata with k pushdown reversals, i.e., the pushdown automata with the ability to flip the pushdown, and E0L systems are incomparable. This result solves an open problem stated by Holzer and Kutrib in 2003.     

Unbounded solutions of quasi-linear difference equations

We study positive increasing solutions of the nonlinear difference equation $\text{δ(a}{}_{\mathrm{n}}\text{φ}{}_{\mathrm{p}}\text{(δχ}{}_{\mathrm{n}}\text{))=b}{}_{\mathrm{n}}\text{f(χ}{}_{\mathrm{n+1}}\text{,}\text{φ}{}_{\mathrm{p}}\text{(u)=|u|}{}^{\mathrm{p-2}}\text{u,}\text{p>1}$ where {a_n}, {b_n} are positive real sequences for n ≥ 1, fR → R is continuous with uf(u) > 0 for u ≠ 0. A full characterization of limit behavior of all these solutions in terms of a_n, b_n is established. Examples, showing the essential role of used hypotheses, are also included. The tools used are the Schauder fixed-point theorem and a comparison method based on the reciprocity principle.     

computer aided intuition in abstract algebra

Two examples are given in which the computer was used to supplement intuition in abstract algebra. In the first example, the computer was used to search Cayley tables of 4 element groupoids to find those which are 5-associative but not 4-associative. (n-associative means that the product of any n elements is independent of the way the factors are grouped by parentheses.) The computer generated examples suggested the existence of n element groupoids which are (2^n?2+1)-associative but not (2^n-2)-associative, for each integer n≧4.In the second example, the computer counted the numbers g₂(m) of invertible 2×2 matrices with entries chosen from the ring Z_mof integers, for m = 2, 3, 4,…, 18. The insight gained from these results led to a proof that there are

invertible n×n matrices over Z_m.Some applications to graduate and undergraduate instruction are indicated.     

The complexity of a multiprocessor task assignment problem without deadlines

We construct a sequence of monotone Boolean functions h_n :{0, 1}ⁿ→{0, 1}ⁿ, such that the monotone complexity of h_n is of order $\text{n}{}^2\text{log n}$. This result includes the largest known lower bound of this kind. Previously there were an $\text{Ω(n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{)}$ bound for the Boolean matrix product, an $\text{Ω(n}{}^{\mathrm{<mtext>5</mtext><mtext>3</mtext>}}\text{)}$ bound for Boolean sums and an $\text{Ω(}\text{n}{}^2\text{log}{}^2\text{n}\text{)}$ bound by the author for the same functions h_n. This new lower bound is proved by new methods which probably will turn out to be useful also for other problems.     

Some remarks on a conjecture in parameter adaptive control

A.S. Morse has raised the following question: Do there exist differentiable functions

$\text{f:R}{}^2\text{→ R}\text{and}\text{g:R}{}^2\text{→ R}$

with the property that for every nonzero real number λ and every (x₀, y₀) ∈ $\text{R}$² the solution (x(t),y(t)) of

$\text{x}\text{?}\text{(t) = x(t) + λf(x(t),y(t))}$

,

$\text{y}\text{?}\text{(t) = g(x(t),y(t))}$

,

$\text{x(0) = x}{}_0\text{, y(0) = y}{}_0$

, is defined for all t ? 0 and satisfies

$\text{lim}\text{t → + ∞}$

and y(t) is bounded on [0,∞)? We prove that the answer is yes, and we give explicit real analytic functions f and g which work. However, we prove that if f and g are restricted to be rational functions, the answer is no.     

An optimal triangulation for second-order elliptic problems

Let Ω be a polygonal domain in $\text{R}{}^{\mathrm{n}}$, τ_h an associated triangulation and u_h the finite element solution of a well-posed second-order elliptic problem on (Ω, τ_h). Let M = {M_i}^{p + q}_{i = 1} be the set of nodes which defines the vertices of the triangulation τ_h: for each i,$\text{M}{}_{\mathrm{i}}\text{= {x}{}_{\mathrm{i}}{}^{\mathrm{l}}\text{¦1 ? l ?n}}$ in Rⁿ. The object of this paper is to provide a computational tool to approximate the best set of positions M? of the nodes and hence the best triangulation $\text{}\text{?}\text{gt}{}_{\mathrm{h}}$ which minimizes the solution error in the natural norm associated with the problem.The main result of this paper are theorems which provide explicit expressions for the partial derivatives of the associated energy functional with respect to the coordinates x_i^l, 1 ? l ? n, of each of the variable nodes M_i, i = 1,…, p.     

Finding the nucleolus of any n-person cooperative game by a single linear program

In this paper we show a new method for calculating the nucleolus by solving a unique minimization linear program with O(4ⁿ)$O(4^n)$ constraints whose coefficients belong to {−1,0,1}$\{-1,0,1\}$. We discuss the need of having all these constraints and empirically prove that they can be reduced to O(_kmax2ⁿ)$O(k_{\mathit{max}}{2}^n)$, where k_max is a positive integer comparable with the number of players. A computational experience shows the applicability of our method over (pseudo)random transferable utility cooperative games with up to 18 players.     

The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages

Seki et al. (Theor. Comput. Sci. 88(2):191–229, 1991) showed that every m-multiple context-free language L is weakly 2m-iterative in the sense that either L is finite or L contains a subset of the form \(\{ u_{0} w_{1}^{i} u_{1} \cdots w_{2m}^{i} u_{2m} \mid i \in \mathbb {N}\}\) , where w ₁?w _2n ≠ε. Whether every m-multiple context-free language L is 2m-iterative, that is to say, whether all but finitely many elements z of L can be written as z=u ₀ w ₁ u ₁?w _2m u _2m with w ₁?w _2m ≠ε and \(\{ u_{0} w_{1}^{i} u_{1} \cdots w_{2m}^{i} u_{2m} \mid i \in \mathbb {N}\} \subseteq L\) , has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.     

Matrix equations over rings

The main purpose of this work is to establish necessary conditions and sufficient conditions for the existence of a solution of matrix equations whose coefficient matrices have elements belonging to the ring $\text{R=}\text{C}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}$ of polynomials in n variables with complex coefficients and the ring $\text{R=}\text{R}\text{[z}{}_1\text{,z}{}_2\text{,…z}{}_{\mathrm{n}}\text{]}{}^{\mathrm{n}}$ of rational functions a(z₁,z₂,…z_n)b(z₁,z₂,…,z_n)^?1 with real coefficients and b(z₁,z₂,…,z_n)≠0 for all (z₁,z₂,…,z_n) in Rⁿ. Results obtained are useful in multidimensional systems theory and elsewhere.     

Three symmetric solutions of lidstone boundary value problems for difference and partial difference equations

We consider the boundary value problem $\text{δ}{}^{\mathrm{2m}}\text{y(k-m)=f(y(k),δ}{}^2\text{y(k-1),…,δ}{}^{\mathrm{2i}}\text{y(k-1),…,δ}{}^{\mathrm{2(m-1)}}\text{y(k-(m-1)))}\text{kϵ{a+1,…,b+1},}\text{δ}{}^{\mathrm{2i}}\text{y(a+1-m)=δ}{}^{\mathrm{2i}}\text{y(b+1+m-2i)=0,}\text{0≤i≤m-1,}$ where m ≥ 1 and (−1)^m f R^m → [0, ∞) is continuous. By using Amann and Leggett-Williams' fixed-point theorems, we develop growth conditions on f so that the boundary value problem has triple positive symmetric solutions. The results obtained are then applied in the investigation of radial solutions for certain partial difference equation subject to Lidstone type conditions.