Narrow Results

A new class of languages, called multi-push-down (mpd), that generalize the classical context-free (cf, or Chomsky type 2) ones is introduced. These languages preserve some important properties of cf languages: a generalization of the Chomsky-Schützenberger homomorphic characterization theorem, the Parikh theorem and a “pumping lemma” are proved. Multi-push-down languages are an AFL. Their recognizers are automata equipped with a multi-push-down tape. Multi-push-down languages form a hierarchy based on the number of push-down tapes.

We establish natural criteria under which normally iterable premice are iterable for stacks of normal trees. Let $\mathrm{\Omega }$ be a regular uncountable cardinal. Let $m<\omega$ and $M$ be an $m$-sound premouse and $\mathrm{\Sigma }$ be an $(m,\mathrm{\Omega }+1)$-iteration strategy for $M$ (roughly, a normal $(\mathrm{\Omega }+1)$-strategy). We define a natural condensation property for iteration strategies, inflation condensation. We show that if $\mathrm{\Sigma }$ has inflation condensation then $M$ is ${(m,\mathrm{\Omega },\mathrm{\Omega }+1)}^{\ast }$-iterable (roughly, $M$ is iterable for length $\le \mathrm{\Omega }$ stacks of normal trees each of length $<\mathrm{\Omega }$), and moreover, we define a specific such strategy ${\mathrm{\Sigma }}^{\mathrm{\text{st}}}$ and a reduction of stacks via ${\mathrm{\Sigma }}^{\mathrm{\text{st}}}$ to normal trees via $\mathrm{\Sigma }$. If $\mathrm{\Sigma }$ has the Dodd-Jensen property and $\mathrm{\text{card}}(M)<\mathrm{\Omega }$ then $\mathrm{\Sigma }$ has inflation condensation. We also apply some of the techniques developed to prove that if $\mathrm{\Sigma }$ has strong hull condensation (introduced independently by John Steel), and $G$ is $V$-generic for an $\mathrm{\Omega }$-cc forcing, then $\mathrm{\Sigma }$ extends to an $(m,\mathrm{\Omega }+1)$-strategy ${\mathrm{\Sigma }}^{+}$ for $M$ with strong hull condensation, in the sense of $V[G]$. Moreover, this extension is unique. We deduce that if $G$ is $V$-generic for a ccc forcing then $V$ and $V[G]$ have the same $\omega$-sound, $(\omega ,\mathrm{\Omega }+1)$-iterable premice which project to $\omega$.

We consider the number of passes a permutation needs to take through a stack if we only pop the appropriate output values and start over with the remaining entries in their original order. We define a permutation $\pi$ to be $k$-pass sortable if $\pi$ is sortable using $k$ passes through the stack. Permutations that are $1$-pass sortable are simply the stack sortable permutations as defined by Knuth. We define the permutation class of $2$-pass sortable permutations in terms of their basis. We also show all $k$-pass sortable classes have finite bases by giving bounds on the length of a basis element of the permutation class for any positive integer $k$. Finally, we define the notion of tier of a permutation $\pi$ to be the minimum number of passes after the first pass required to sort $\pi$. We then give a bijection between the class of permutations of tier $t$ and a collection of integer sequences studied by Parker [The combinatorics of functional composition and inversion, PhD thesis, Brandeis University (1993)]. This gives an exact enumeration of tier $t$ permutations of a given length and thus an exact enumeration for the class of $(t+1)$-pass sortable permutations. Finally, we give a new derivation for the generating function in [S. Parker, The combinatorics of functional composition and inversion, PhD thesis, Brandeis University (1993)] and an explicit formula for the coefficients.

In all of the routing protocols of Ad hoc networks, GPSR based on geographical information is a robust protocol with broad prospects. GPSR is composed of greedy algorithm and perimeter forwarding algorithm. While there are many packets need to be perimeter forwarded, it may produce lots of hops. This paper analyses perimeter forwarding firstly; and then puts forward an improving approach plus a stack in the memory of each forwarding node. The detailed steps are described in this paper to present the improved algorithm as well. Based on the theory demonstrations, we concluded that the improved algorithm can reduce routing hops and time complexity obviously. Furthermore, it can be implemented easily to improve routing performance. The innovation of this paper is that the time complexity is reduced by adding the space complexity.