extfieldsofstudy:
Computer Science
Physics

s2fieldsofstudy:
Computer Science
Physics

text:
Optimal Database Search: Waves and Catalysis

Grover's database search algorithm, although discovered in the context of quantum computation, can be implemented using any system that allows superposition of states. A physical realization of this algorithm is described using coupled simple harmonic oscillators, which can be exactly solved in both classical and quantum domains. Classical wave algorithms are far more stable against decoherence compared to their quantum counterparts. In addition to providing convenient demonstration models, they may have a role in practical situations, such as catalysis.

The algorithm evolves |s towards |t , by discrete rotations in the two-dimensional space formed by |s and |t , using the two reflection operators, U t is the binary oracle which flips the sign of target state amplitude, while −U s performs the reflection-inthe-mean operation. Solution to Eq.(3) determines the number of queries as (2Q + 1) sin −1 (1/ √ N ) = π/2 . (4) * Electronic address: E-mail: adpatel@cts.iisc.ernet.in (In practice, Q must be an integer, while Eq.(4) may not have an integer solution. In such cases, the algorithm is stopped when the state has evolved sufficiently close to, although not exactly equal to, |t . Then one finds the desired item with a high probability.) In the qubit implementation of the algorithm, one chooses N = 2 n and the items in the database are labeled with binary digits. Using a uniform superposition as the starting state, (H is the Hadamard operator), the implementation requires only O(log 2 N ) spatial resources [1]. It has been proved that this is the optimal algorithm for unsorted database search [2].
Several variations of this algorithm have been studied, using different physical realizations of the database items and the target query oracle. In the original algorithm, the states are encoded in an n-qubit register, and the oracle is a discrete binary operation (denoted by U t above). In the analogue version of the algorithm, the discrete unitary oracle is traded for a continuous time interaction Hamiltonian (it evolves the target state somewhat differently than the rest) that acts for the entire duration of the algorithm, and the number of queries is replaced by the time one has to wait for before finding the target state [3]. The wave version of the algorithm requires N distinct wave modes, instead of n qubits, but does not involve quantum entanglement at any stage [4]. Such a wave search has also been experimentally implemented using classical Fourier optics, with a phase-shift plate providing the oracle [5]. A classical coupled pendulum model of the analogue version of the algorithm has been described, where one of the pendulums is slightly different from the rest and the uniform superposition state |s is identified with the center-of-mass mode [6]. In what follows, I describe a binary oracle version of the wave search algorithm using identical coupled harmonic oscillators.

II. HARMONIC OSCILLATOR IMPLEMENTATION
A system of coupled harmonic oscillators is frequently studied in physics. It involves only quadratic forms, and hence can be solved exactly in both classical and quantum domains. This property makes it extremely useful in situations where cross-over between classical and quantum behaviour is to be analyzed. We shall first look at the classical system, and then observe that the quantum system essentially follows the same pattern.

A. Classical oscillators
Let the items in the database be represented by N identical harmonic oscillators. While they are oscillating in a specific manner, someone taps one of the oscillators (i.e. elastically reflects it by touching it). The task is to identify which of the oscillators has been tapped, without looking at the tapping. The optimization criterion is to design the system of oscillators, and their initial state, so as to make the identification as quickly as possible.
Grover's algorithm requires identical coupling between any pair of oscillators. This can be accomplished by coupling all the oscillators to a big oscillator, as shown in Fig.1. The big oscillator then becomes an intermediary between any pair of oscillators, with the same strength, since it is coupled to the center-of-mass mode. The Lagrangian for the whole system is With the center-of-mass displacement, x ≡ N i=1 x i /N , the Lagrangian can be rewritten as Ã Å Now we can fix the oscillator parameters to implement Grover's algorithm. In the algorithm, we are interested in the dynamics of the tapped oscillator. All the other oscillators (i.e. i = t) influence the dynamics of x t only through the combination x. The dynamics of (N − 2) linearly independent modes orthogonal to x t and x (they all have the form (x j =t −x k =t )) decouples from the modes of interest; we can drop them and effectively work in the 3-dimensional space of the modes {X, x, x t }. (In what follows, we shall first specify initial conditions such that all x i =t are identical and all the decoupled modes vanish. Subsequently, we will look at the general situation by adding back all the decoupled modes.) Choosing units of mass and time such that m = 1, k = 1, and in terms of the variables the effective Lagrangian becomes The potential energy terms in L eff are easily diagonalized, and yield the eigenvalues The corresponding eigenmodes are The initial uniform superposition state can be realized as all the oscillators moving together, while the big oscillator is at rest.
(We will consider situations with general initial conditions later.) The reflection operators correspond to shifting the appropriate oscillator phases by half a period.
The binary tapping oracle flips the sign of the target oscillator velocity, when its displacement is zero.
The binary tapping oracle can be realized as the elastic reflection illustrated in Fig.2. That implements U t in the velocity space, by reversing the target oscillator velocity at the instance when all the displacements vanish. Time evolution of the coupled oscillators redistributes the total kinetic energy, and that can implement the operator U s with a suitable choice of time interval and frequencies.
With the natural frequency of individual oscillators ω = k/m = 1, the reflection-in-the-mean operation requires ω ± to be rational numbers. Optimization means that they should be selected to make the dynamics of the whole system of oscillators have as small a period as possible. The solution is not unique. One set of solutions is (p is a positive integer) In these cases, in the absence of oracles, the dynamics of the whole system of oscillators has the period, T = 4π. The big oscillator returns to its initial rest state (X = 0,Ẋ = 0), whenever t is an integral multiple of 2π, i.e. after every half a period. Time evolution for the same interval of half a period reversesẋ, while leavinġ x t −ẋ unchanged, i.e. it implements the operator U s in the velocity space. Thus Grover's algorithm, Eq.(3), can be realized by applying the tapping oracle at every time interval ∆t = 2π.
A more interesting set of solutions is , K = 0 .
(14) In these cases, the big oscillator is not coupled to any support, and e − becomes a translation mode for the whole system of oscillators. The translation mode can be eliminated from the dynamics with the initial conditions Then, in the absence of oracles, the dynamics of the whole system of oscillators has the smallest possible period, T = 2π. After half a period, the big oscillator is back to its initial state,ẋ also returns to its initial value, whileẋ t −ẋ changes its sign. This is equivalent to applying −U s in the velocity space, and Grover's algorithm can be implemented by tapping the target oscillator at every time interval ∆t = π.
There is an important physical distinction between the quantum and the wave interpretations of the amplitude amplification process in Grover's algorithm-quantum probability is mapped to wave energy. The enhancement of the quantum amplitude increases the probability of finding the target state N -fold, while the enhancement of the wave amplitude increases the energy of the target oscillator N -fold. The well-known phenomenon of "beats" is responsible for energy transfer amongst coupled oscillators. The elastic reflection oracle does not change energy, and it is interesting to observe that the oscillator which is obstructed by tapping picks up energy.

B. Stability considerations
Now we can look at the behaviour of the wave implementation under general circumstances. First consider the initial conditions. Despite appearances, precise synchronization of oscillators is not an issue in the algorithm, because of the explicit coupling to the center-of-mass mode. For instance, the algorithm can be started off with an initial push to the big oscillator,Ẋ = B,ẋ i = 0, and the system of oscillators would evolve to the stagė X = 0,ẋ i = A. Furthermore, any arbitrary distribution of initial velocities of oscillators can be accommodated in the analysis by bringing back the (N − 2) decoupled modes. The decoupled modes have no effect whatsoever on the dynamics of the {X, x, x t } modes. Consequently, the algorithm is only modified to the extent that the energy amplification of the target oscillator is limited to the initial energy present in the {X, x, x t } modes, instead of being N -fold. Explicitly, the maximum gain is which can be substantial for the generic situation where the initialẋ t andẋ are of the same order of magnitude.
To extract the maximum gain, the algorithm must be stopped at a precise instant (i.e at a precise value of Q); otherwise the evolution continues in repetitive cycles. The state evolution in Grover's algorithm is a uniform rotation in the two dimensional |s -|t subspace. The average overlap of the target state, with the state |q(Q) after Q queries, is therefore | q(Q)|t | 2 av = sin 2 θ av = 1/2 .
Thus if the algorithm is stopped at a random instant, the energy gain on the average is half of its maximum value in Eq.(16)-which can still be substantially larger than 1.
Next consider the effect of damping [7]. The crucial ingredient in the algorithm is the coherence amongst the phases of the oscillators. That is governed by the frequencies of the oscillators, and is independent of the amplitudes. For a weakly damped oscillator, its amplitude changes linearly with the damping coefficient, while its frequency changes quadratically. The time evolution of the above implementation, therefore, remains essentially unaffected if the oscillators experience a small damping. The leading effect is a decrease in the energy amplification due to decaying amplitudes.
Among other variations, simultaneous scaling of masses and spring constants of the oscillators (i.e. m i = α i m and k i = α i k) does not alter the algorithm at all, since the scale factors can be absorbed by redefining x i . One can also contemplate some changes of global conditions that let the algorithm go through but change its physical interpretation. For example: (i) Application of simultaneous tapping oracle to more than one oscillator (with suitable changes in M and K) can focus the energy into the tapped oscillators. (ii) Interchange of initial and final states can run the algorithm backwards, whence the large initial energy of the target oscillator gets uniformly distributed among all oscillators. (iii) Elastic reflection of all but the target oscillator implements the oracle −U t in the velocity space, in which case it is the unobstructed oscillator that picks up energy.

C. Quantum domain
The dynamics of harmonic oscillators is simple enough to permit exact quantum analysis as well. It is convenient to interpolate between classical and quantum domains using the coherent state formulation [8]. Coherent states are superpositions of the eigenstates, parametrized by a single complex variable α, They describe Gaussian wavepackets with minimal spread (i.e. displaced versions of the ground state eigenfunction), A coherent state with the initial condition α(t = 0) = α 0 has energyhω(|α 0 | 2 + 1 2 ), and the centre of its wavepacket performs the same simple harmonic motion as a classical particle would: The wavefunction of the state evolves according to while the explicit structure of the wavepacket is given by Thus the analysis of Section II.A can be carried over unchanged to the quantum domain, provided we can figure out how the tapping oracle works for the coherent states. The tapped oscillator corresponds to a particle moving in the half-oscillator potential The impenetrable wall at x = 0 is equivalent to enforcing the boundary condition ψ(x = 0) = 0. So the eigenstates of the half-oscillator are the same as those for the harmonic oscillator, with odd n. It is straightforward to ensure the node at x = 0 using the method of images, and the tapped oscillator coherent states become with the normalization constant C = (1 − e −2|α| 2 ) −1/2 . Tapping amounts to change-over between |α and | − α , which reverses x and p compared to the untapped motion. In addition, the wavefunction changes sign, which is the geometric phase corresponding to wave reflection. The evolution of a coherent state wavepacket undergoing reflection from the wall is depicted in Fig.3.

III. POSSIBLE APPLICATIONS
The oscillator based search process discussed above has the same algorithmic efficiency as the proposals of Refs. [4,5,6]-where it differs from them is in the actual physical implementation. Wave algorithms are classical, but they have not been explored much historically. The main reason is that they require exponentially more spatial resources compared to their digital counterparts,  (log 2 N ). On the other hand, they can reduce the number of oracle calls by exploiting superposition of states. Note that no algorithm based on Boolean logic, either with serial or with parallel implementation, can reduce the number of oracle calls for an unsorted database search to less than O(N ).
Quantum algorithms are superior to wave algorithms, because they can use superposition as well as reduce spatial resources. The reduction of spatial resources, however, comes with the cost that quantum algorithms have to work with entangled states. Quantum entanglement is far more sensitive to decoherence caused by environmental disturbances than mere superposition, and that has made physical implementations of quantum algorithms very difficult. On the other hand, superposition of classical waves can be fairly stable, even when a small amount of damping is present, and that can make wave implementations advantageous in specific physical contexts.
These comparisons suggest that wave algorithms fall in a regime inbetween classical and quantum algorithmsmore efficient than the former and more robust than the latter. They are likely to be useful in practical situations, where N is not very large and environmental disturbances are not negligible. Indeed it is worthwhile to systematically explore them, just like randomized algorithms have been [9].
In the specific case of the unsorted database search problem, the remarkable simplicity of the oscillator implementation makes one wonder about possible applications, besides constructing convenient demonstration models. The implementation of Ref. [6] has one oscillator with a frequency different from the rest, which gets singled out by dynamical evolution of the coupled system. In the present scenario, all oscillators are identical, but one of them is discretely tapped by an external agency and gets selected. I point out a physical situation below, that can fit such a scenario, and where involvement of new mechanisms can enhance our understanding of the observed phenomena.

A. Catalysis
The practically useful property of the wave search algorithm is that it focuses energy into one of the oscillator modes. There exist a large number of chemical reactions which, although not forbidden by energy conservation, are extremely slow because they have to pass through an intermediate state of high energy. In these reactions, the dominant term governing the reaction rate is the Boltzmann factor, exp(−E b /kT ), with the barrier energy in the exponent. Only a tiny fraction of the molecules in the tail of the thermal distribution are energetic enough to go over the barrier and complete the reaction. It is known that the rates of many such reactions can be enhanced by orders of magnitude by adding suitable catalysts (enzymes in case of biochemical reactions) to the reactants. The conventional explanation for the reaction rate enhancement, called transition state theory, is that the catalysts lower the energy of the intermediate state by modifying the chemical environment of the reactants.
The preceding analysis of the wave search algorithm suggests another mechanism for catalysis. Vibrations and rotations of molecules are ubiquitous harmonic oscillator modes. The catalyst can act as the big oscillator and focus energy of many modes into the reactant which faces the energy barrier. For example, the catalytic substrate can have many identical molecules of one reactant stuck to it and vibrating, the second reactant then comes drifting along and interacts with one of the stuck molecules, that molecule picks up energy from its neighbours and the reaction gets completed. In such a scenario, for maximum efficiency, the physical parameters (masses and spring constants) need to have specific values. But even without perfectly tuned parameters, there can be partial energy focusing that provides useful increase in the reaction rate. Whether this mechanism exists among the known catalysts, or whether we can design new type of catalysts that use this mechanism, is an open question.
The catalytic role of chemical environment vs. physical waves can be tested by isotopic substitution in the reactants, since isotopic substitution changes physical parameters without altering chemical properties. The conventional transition state theory has no mass dependence, so any isotope dependence of reaction rates is a signal of involvement of physical (in contrast to chemical) features in the process. Many examples of isotopic dependence of catalytic reaction rates have been discovered, and the effect is referred to as the "Westheimer effect" or the "kinetic isotope effect" [10]. The effect is the largest for substitution of hydrogen by deuterium, and has been extensively studied for the rupture of C-H/C-D bonds. The transition state theory has been found inadequate for theoretical understanding of the observations, and vibrationally enhanced quantum tunneling has been invoked as an alternative [11].
In this context, the oscillator based search process described above has two novel features to suggest yet another alternative: (i) The energy focusing mechanism enhances reaction rates beyond their naive classical values. This enhancement is both mass and temperature dependent, because the energy enhancement depends on the masses involved while the Boltzmann factor contains the temperature. (ii) The wavefunction sign-flip caused by reflection can switch between bonding and anti-bonding molecular orbitals, and thus help in the transfer of atoms. This feature is not related to either mass or temperature. It would be therefore worthwhile to explore the oscillator inspired catalytic mechanism with careful modeling of specific reactions.
In closing, I mention an intriguing possibility. I had constructed a quantum database search scenario for the DNA replication process, whose stumbling block was the maintenance of quantum coherence in presence of con-tinuous jostling of molecules [12]. It should be feasible to construct a wave database search scenario involving vibrational and rotational modes of the molecules. That would be far less troubled by decoherence effects, and make interpretation of the genetic language as optimal solution to the database search process likely.


Preface

A large class of computing systems can be specified and verified by abstracting away from the temporal aspects of their behavior. In real-time systems, instead, time issues become essential. Their correctness depends not only on which actions they can perform, but also on the action execution time. Due to their importance and design challenges, real-time systems have attracted the attention of a considerable number of computer scientists and engineers from various research areas.

Preface
A large class of computing systems can be specified and verified by abstracting away from the temporal aspects of their behavior. In real-time systems, instead, time issues become essential. Their correctness depends not only on which actions they can perform, but also on the action execution time. Due to their importance and design challenges, real-time systems have attracted the attention of a considerable number of computer scientists and engineers from various research areas.
This volume collects a set of papers accompanying the lectures of the fourth edition of the International School on Formal Methods for the Design of Computer, Communication and Software Systems (SFM). The school addressed the use of formal methods in computer science as a prominent approach to the rigorous design of computer, communication and software systems. The main aim of the SFM series is to offer a good spectrum of current research in foundations as well as applications of formal methods, which can be of help for graduate students and young researchers who intend to approach the field. SFM-04:RT was devoted to real-time systems. It covered formal models and languages for the specification, modeling, analysis, and verification of these timecritical systems, the expressiveness of such models and languages, as well as supporting tools and related applications in different domains.
The opening paper by Rajeev Alur and Parthasarathy Madhusudan provides a survey of the theoretical results concerning decision problems of reachability, language inclusion, and language equivalence for timed automata. The survey is concluded with a discussion of some open problems. Elmar Bihler and Walter Vogler's paper presents timed extensions of Petri nets with continuous and discrete time and a natural testing-based faster-than relation for comparing asynchronous systems. Several applications of the theory are also presented. Jos C.M. Baeten and Michel A. Reniers present the theory and application of classical process algebras extended with different notions of time and time passing and compare their expressiveness via embeddings and conservative extensions. The PAR communication protocol is considered as a case study. The expressiveness of existing timed process algebras that deal with temporal aspects by following very different interpretations is also the main theme of Diletta R. Cacciagrano and Flavio Corradini's paper. In addition, they compare the expressiveness of urgent, lazy and maximal progress tests. Mario Bravetti presents a theory of probabilistic timed systems where durations are expressed by generally distributed random variables. The theory supports the specification of both real-time and stochastic time during the design and analysis of concurrent systems. Bran Selic, instead, provides an overview of the foundations of the runtime semantics underlying the Unified Modeling Language (UML) as defined in revision 2.0 of the official OMG standard.
After these contributions on formal timed models, timed languages and their expressiveness, the volume includes the description of three significant tools supporting the specification, modeling, analysis and verification of real-time systems. Gerd Behrmann, Alexandre David and Kim G. Larsen's tutorial paper on the tool Uppaal provides an introduction to the implementation of timed automata in the tool, the user interface, and the usage of the tool. Reference examples and modeling patterns are also presented. Marius Bozga, Susanne Graf, Ileana Ober, Iulian Ober, and Joseph Sifak present an overview on the IF toolset, which is an environment for the modeling and validation of heterogeneous real-time systems. The toolset is built upon a rich formalism, the IF notation, allowing structured automata-based system representations. A case study concerning the Ariane-5 Flight Program is presented. Finally, Joost-Pieter Katoen, Henrik Bohnenkamp, Ric Klaren, and Holger Hermanns survey the language Modest, a modeling and description language for stochastic and timed systems, and its accompanying tool environment MOTOR. The modeling and analysis with this tool of a device-absence-detecting protocol in plug-and-play networks is reported in the paper.
We believe that this book offers a quite comprehensive view of what has been done and what is going on worldwide at present in the field of real-time models and languages for the specification, analysis, and verification of timecritical systems. We wish to thank all the lecturers and all the participants for a lively and fruitful school. We also wish to thank the whole staff of the University Residential Center of Bertinoro (Italy) for the organizational and administrative support, as well as the sponsors of the school -AICA and ONRG -for making it possible through the provision of grants to some of the participants.


Nondeterministic LTAG Derivation Tree Extraction

In this paper we introduce a naive algorithm for nondeterminisctic LTAG derivation tree extraction from the Penn Treebank and the Proposition Bank. This algorithm is used in the EM models of LTAG Treebank Induction reported in (Shen and Joshi, 2004). Given the trees in the Penn Treebank with PropBank tags, this algorithm generates shared structures that allow efficient dynamic programming in the EM models.

Introduction
In recent years, the statistical approach has been successfully used in natural language processing (NLP). No matter which statistical model people use, a generative model or statistical machine learning, large corpora are always needed to train the models. For example, after the introduction of the Penn Treebank (PTB) (Marcus et al., 1994), a serial of improvements has been achieved on natural language parsing and shallow parsing tasks. In the field of Lexicalized Tree Adjoining Grammar (LTAG), the statistical approach has also been successfully employed in many LTAG-based NLP tasks, such as LTAG parsing (Chiang, 2000;Shen et al., 2003) and Supertagging (Joshi and Srinivas, 1994).
However, the lack of very large corpora based on LTAG prevents the statistical approach from being widely used in the field of LTAG. As we know, very large corpora are crucial to statistical NLP. In previous works, people managed to induce LTAG style grammars and LTAG based corpora from the PTB, and use them in their applications. Joshi and Srinivas (1994) first implemented a supertag corpus by extracting it from the PTB, using heuristic rules. Due to various limitations of this system, extracted supertags of the words in a sentence cannot always be successfully put together. Xia (2001) and Chen (2001) described deterministic systems that extract LTAG-style grammars from PTB. In their systems, the head percolation table (Magerman, 1995) and the PTB functional tags were used to solve ambiguities in extraction. Chiang (2000) reported a similar method to extract an LTAG like treebank from PTB, and used it in a statistical parser. Shen et al. (2003) employed a similar technique to induce an LTAG treebank, to be used in a parse reranking system.
In these LTAG grammar and treebank induction systems, deterministic rules were used to solve the ambiguities in the elementary tree extraction process. However, it is clear that deterministic rules are not enough to solve ambiguity in extraction, especially in the case of the argument-adjunct distinction (Paola and Leybold, 2001).

A Statistical Model
In (Shen and Joshi, 2004), we have proposed a statistical model for LTAG Treebank induction using the Expectation-Maximization (EM) algorithm (Dempster et al., 1977). The EM Algorithm is a general iterative method of search to find the maximum-likelihood estimate of the parameters of the hidden data from the observed data.
If we take the PTB as the observed data, then the LTAG derivation trees for the PTB trees can be treated as the hidden data. Then our goal is the find out the hidden structures, or LTAG derivation trees, with maximumlikelihood. Similar idea was previously employed in (Chiang and Bikel, 2002) in statistical parsing.
In (Shen and Joshi, 2004), several EM models were proposed for LTAG Treebank induction. In these models, linguistic knowledge is used to overcome EM's weakness that EM cannot guarantee to find a global optimum. By using linguistic knowledge, we can not only start the EM iteration from the point close to the global optimum in the first iteration, but also limit the search space of hidden derivation trees in the following rounds.
However in that paper, we did not give the details on how to employ the linguistic knowledge to constrain the search space. In this paper, we will introduce a novel algorithm that searches the space the derivation trees, respecting the linguistic constraints and maintaining the ambiguities in elementary tree extraction, for each given PTB tree. In this section, we first analyze the ambiguities existing in LTAG elementary tree extraction from PTB, and then we illustrate the linguistic information to be used in nondeterminisctic derivation extraction.

Ambiguities
Our analysis is mainly based on the work of (Xia, 2001) and (Chen, 2001). There are two kinds of ambiguities in LTAG elementary tree extraction, which are head competition and argument-adjunct distinction.
Given a deduction rule of Context Free Grammar (CFG) in the PTB, we need to find out which item on the right hand side of the rule is the lexical head of the item on the left hand side. For example, for rule VP → V NP, V is the head of VP. In (Xia, 2001) and (Chen, 2001), the so called head percolation table (Magerman, 1995) is used to determine the head item of each CFG rule in the PTB. Following the lexical heads in a tree, we can get the spines of elementary trees.
Argument-adjunct distinction is mainly to distinguish the arguments and adjuncts of a predicate. In (Xia, 2001) and (Chen, 2001), argument-adjunct distinction is solved with respect to the constituent tags and function tags in the PTB.
In their systems, these two kinds of ambiguities are solved deterministically as we described above. However, there exists a lot ambiguities that can not been solved easily. For example, in the sentence ... was named a nonexecutive director of this British industrial conglomerate extracted from the PTB, the NP dominating director has a function tag PRD, which means predicate. In this case there exists a head competition between director and named. As far as argument-adjunct distinction is concerned, the ambiguities are ubiquitous, which can only be solved with a lexicon, i.e. the hand-crafted XTAG English Grammar (XTAG-Group, 2001), with statistical methods.

Penn TreeBank
The input of our algorithm is a full bracketed PTB tree, as shown in Figure 1. The structure information is the main source of derivation tree extraction. We can simply regard a PTB tree as a derived tree in LTAG.
Besides the structure information, The Penn Treebank provides more information useful in LTAG derivation tree extraction, such as special information for the predicateargument structures. Although the PTB does not try to distinguish arguments and adjuncts, and treats them as arguments in general, it assigns functional tags for these arguments which help to to distinguish arguments and   Figure 1, functional tag SBJ means subject, TMP means temporal phrase, and CLR means closely related. This information was used in previous LTAG extraction systems and will also be used in our system too.

PropBank
We will also use the Penn Proposition Bank (Prop-Bank) (Kingsbury and Palmer, 2002) in our LTAG derivation tree extraction algorithm. The PropBank provides more information on the predicate-argument structures for the PTB data.
In the PropBank, each predicate is assigned with a tag of major sense defined on usage of the predicate. Each argument of this predicate is assigned with an argument ID with respect to the major sense of this predicate, as shown in Figure 2. We will use the argument tags in our extraction algorithm too.
What is worth mentioning is that, like the PTB, the PropBank does not distinguish arguments and adjuncts, and both are called arguments in the PropBank. Using  the PropBank tags, we can easily get all the arguments and adjuncts of a given predicate, but how to distinguish them is still a problem. This is the reason why we introduce the nondeterminisctic method in derivation tree extraction. The EM algorithms in (Shen and Joshi, 2004) are supposed to find out the global optimum over various selections.

Nondeterministic Derivation Tree Extraction
In this paper we will propose an algorithm to maintain the ambiguities in elementary tree extraction. For a given PTB tree, the derivation tree candidates serve as the search space used in the EM algorithm. A naive way is to represent all the candidate derivation trees one by one. However, a more efficient way to do this is to use shared structures. Therefore, we need an efficient way to represent all the LTAG derivation trees that meet the linguistic constraints, given a PTB tree. Then the EM algorithm can re-estimate expectation over all derivation tree candidates with less computational complexity by inside-outside algorithm as described in (Shen and Joshi, 2004).

Idea
We first give the idea of the extraction algorithm. The extraction consists of two phases, the bottom-up head competition phase and the top-down argument-adjunct distinction phase.
In the head-competition phase, we visit all the nodes throughout a PTB tree from bottom and look for the head candidates for every internal node. For each internal node, there will be several head candidates with respect to different triggering rules. For example, in the example given above, ... was named a nonexecutive director of this British industrial conglomerate, either the VP node anchored on named or the NP node anchored on director can be the head of the main S node with respect to different analyses.
If any head candidate is selected as the head for the parent node, the rest children nodes serve as • a leaf node to which an initial tree substitutes, • a leaf node to which an auxiliary tree adjoins, or • an internal node of the elementary tree for the head node.
No matter what it will be, these elementary trees are beneath the elementary tree for the head node, in any derivation tree for this PTB tree. Thus, we can use shared structure to represent all these situations; each non-head child nodes can be used in three way as described above.
To sum up, for each head candidate, we can use an index structure to represent all the possible sub-structures beneath this elementary tree in the derivation tree, and this index structure will be further used for one or several times by the upper nodes. So the goal of the head competition phase is to search for all the head candidates for each internal node and to generate an index structure the represent all the sub-structures beneath this point.
In the argument-adjunct distinction phase, we visit index structures in a top-down style, starting from the index structures of the root node. Keeping track of the head child, we first get the spine of the elementary for the main predicate. Then we use linguistic information to get all the possible operations with which other sub-trees are attached to the sister nodes on different levels along the spine. The possible attachment methods, i.e. substitution, adjunction or internal node, are recorded in the index structures. Then we do argument-adjunct distinction recursively on all the subtrees rooted on these sister nodes.
Now we explain what an index structure is. Each node in a PTB tree is associated with a set of index structures.

201
An index structure stores the following information: its lexical head, a set of attachment points, and a set of the references of index structures of attached subtrees.
After the head competition phase and argumentadjunct distinction phase, we get a shared forest composed of index structures, with which we can get all the possible derivation trees of a PTB tree as well as the corresponding elementary trees.

Algorithm
The following algorithm is used to find all candidate derivation trees and store them in shared structures. The input is a PTB tree with PropBank tags, and the result of the algorithm is a shared forest that represents all candidate derivation trees for this input PTB tree.

head competition (node n)
1.1 if (head-comp-done) return; 1.2 for each child of n, call head competition; 1.3 look for the candidate heads using linguistic constraints; 1.4 for each candidate, generate an index structure and associate it with n; 1.5 head-comp-done = true; 2. argument-adjunct distinction (node n) 2.1 if (arg-adj-done) return; 2.2 for each index structure of n, for each attachment candidate • refine attachment types; • call argument-adjunct distinction on the attached subtree; 2.3 arg-adj-done = true; Figure 3 shows the results after head competition. For this case, there is no ambiguity on head competition, so there is only one output. Otherwise shared structures are used to represent all the results.

Example
It is shown in Figure 3 that the result of the head competition does not distinguish arguments and adjuncts. The ambiguities are maintained in the single output in this case. Specifically, the PP subtree anchored on as can be either an argument or an adjunct. So do the NP subtrees for the subject, the object and the temporal phrase.
After the argument-adjunct distinction phase, ambiguities on the subject, the object and the temporal phrase are solved with respect to the templates defined on context, in a way similar to (Xia, 2001;Chen, 2001). However, the argument-adjunct ambiguity on the PP node is still maintained in the final output of the algorithm.

Discussion
In the previous sections, we did not cover the following two special situations in derivation tree extraction.

• Coordination
In order to handle auxiliary predicate structure, we introduce a stack structure to maintain a head chain as described in (Chen, 2001). Since we have used the PropBank tags, we can easily recognize the predicateargument relation between an argument associated with a sister node and a head in the stack.
Coordination is another important case in derivation extraction. In our current implementation, we use the first item in a coordination phrase as the head, and treat the rest items as adjuncts. For example, in the phrase red and blue, red is the head, blue attaches to and, and and adjoins to red. We are still working on the treatment of coordination. One solution is to follow the approach described in (Sarkar and Joshi, 1996).
Theoretically, the number of the index structures grows exponentially with respect to the height of a tree. However, our experiments show that it does not grow that fast, thanks to the linguistic constraints used in head competition.
By using rich PropBank features, we can almost solve the ambiguities in head competition. The only thing that we need to take care of is the different analyses of head word in PropBank and LTAG. In some cases, PropBank and LTAG select different words as head. However, this problem can be solved with templates. For example, in the following example, thought is the head for the whole sentence in PropBank, while come is the head in LTAG analysis.
• John thought Mary didn't come yet.

Experiments
The nondeterminisctic LTAG derivation extraction algorithm was used in the EM models reported in (Shen and Joshi, 2004). With the algorithm given in that paper, about 12,000 elementary trees were extracted from the Penn Treebank. The experiments in (Shen and Joshi, 2004) showed that the number of the elementary trees was reduced to about 10,000 with several rounds of EM training.
It also noted in (Shen and Joshi, 2004) that some simple EM models reported in that paper prefer elementary trees of lower frequency, which is undesirable for grammar extraction. In our future research, we will incorporate the hand crafted XTAG English Grammar (XTAG-Group, 2001) in the EM models. Some XTAG Grammar based EM models were proposed in (Shen and Joshi, 2004) as future work.

Conclusions
In this paper we have introduced a naive algorithm for nondeterminisctic LTAG derivation tree extraction from the Penn Treebank and the PropBank, which is an extension of the deterministic methods in (Xia, 2001) and (Chen, 2001). The algorithm will be used in the EM models of LTAG Treebank Induction. The shared structures generated by this nondeterminisctic algorithm allow efficient expectation computation via dynamic programming in the EM algorithm.


extfieldsofstudy:
Mathematics
Computer Science

text:
A class of one-dimensional MDS convolutional codes

A class of one-dimensional convolutional codes will be presented. They are all MDS codes, i. e., have the largest distance among all one-dimensional codes of the same length n and overall constraint length delta. Furthermore, their extended row distances are computed, and they increase with slope n-delta. In certain cases of the algebraic parameters, we will also derive parity check matrices of Vandermonde type for these codes. Finally, cyclicity in the convolutional sense will be discussed for our class of codes. It will turn out that they are cyclic if and only if the field element used in the generator matrix has order n. This can be regarded as a generalization of the block code case.

Introduction
The main task of coding theory is the construction of powerful codes. This applies equally well to block codes and convolutional codes. In either case codes are required to have good error-correcting properties, i. e. a large distance, and an efficient decoding algorithm.
In block coding theory this goal has been achieved best by the class of Reed-Solomon codes along with their efficient algebraic decoding algorithm. These codes are in particular MDS (maximum distance separable), meaning that they have the largest distance possible among all codes with the same length and dimension. On the other hand there are convolutional codes, and despite their frequent and successful use in engineering practice, their mathematical theory is still in the beginnings. The algebraic theory of this class of codes has been initiated with the paper [2] of Forney and has seen a considerable development ever since.
In particular, quite some efforts have been made in the area of constructing convolutional codes with large distance. The first group of the according papers appeared in the seventies of the last century. In [10,13,11] quasi-cyclic block codes have been used in order to construct convolutional codes with good distance. The relation between the weights of the block codewords and the convolutional codewords is made by the weight-retaining property. This topic has been resumed later on in [22] where the ideas have been used to construct MDS convolutional codes with (almost) arbitrary algebraic parameters. Other more recent attempts of constructing good convolutional codes try to impose additional algebraic structure on the convolutional codes themselves. In [1] methods from algebraic geometry are used in order to construct convolutional codes of Goppa type. In the paper [8] system theoretic methods are used in order to analyze codes with optimal column distances. Finally, in [7] ideas from the seventies [16,18] have been resumed in order to impose a type of cyclicity on convolutional codes. The investigations of these cyclic convolutional codes have been continued in [5,4]. We will explain the notion of cyclicity later in Section 4 of this paper. At this moment we restrict ourselves to mentioning that cyclicity for convolutional codes is a more general notion than just the natural invariance of the code under cyclic shift.
In the present paper we will combine the two main lines mentioned above. We will present a class of one-dimensional codes that are not only MDS but also have extended row distances increasing with slope n − δ (where n is the length of the code and δ the overall constraint length). We will also compare the required field size needed for the construction with the field sizes of other constructions known in the literature. It will turn out that our field sizes are smaller for many parameters than what has been used before. For one set of parameters the field size is even only one above the theoretic minimum. In addition to these distance computations and field size investigations, we will also discuss the algebraic structure of these codes. As it turns out, for certain algebraic parameters the presented codes are cyclic in the sense mentioned above. In this case the codes can in fact be regarded as a generalization of (one-dimensional) Reed-Solomon codes. They even have a polynomial parity check matrix of Vandermonde type, showing that this class of codes are closely related to some of the codes given in [1].
The paper is organized as follows. In the rest of the introduction we will collect the preliminaries about convolutional codes. In Section 2 we will present the class of codes via their generator matrices along with their (extended row) distances and compare the field size to results from the literature. In Secton 3 various parity check matrices with Vandermonde structure are presented. In Section 4 we will introduce the notion of cyclicity for convolutional codes as it has been investigated in [7]. We will show that in a certain (to be expected) case our codes are cyclic, and we will present various representations of the codes. We will close with some open problems.
We end this introduction with the basic notions of convolutional coding theory. Convolutional codes are certain submodules of F[z] n , where F is a finite field. Before presenting the definition we wish to recall that each submodule S of F[z] n is free and therefore can be written as where k is the rank of S and G ∈ F[z] k×n is a matrix containing a basis of S. Hence, the matrix G is unique up to left multiplication by a matrix from Gl k (F[z]). Moreover, by resorting to the Smith normal form one easily shows that G is right-invertible, i. e., GG = I k for some matrixG ∈ F[z] n×k , if and only if the submodule im G is a direct summand of the module F[z] n . This in turn is equivalent to the existence of a matrix H ∈ F[z] (n−k)×n such that im G = ker H T := {v ∈ F[z] n | vH T = 0}. Using the theory of polynomial matrices it is easily seen that we may assume H to be right-invertible. Then it is unique up to left multiplication by a matrix from Gl n−k (F[z]). Obviously, the matrix H generates the dual module, i. e., im This makes all of the following notions well-defined.
k×n is a rightinvertible matrix such that δ = max{deg γ | γ is a k-minor of G}. We call G a generator matrix of the code. The number n is called the length, k is the dimension, and δ is called the overall constraint length of the code. Each right-invertible matrix H ∈ F[z] (n−k)×n satisfying C = ker H T is called a parity check matrix of C.
Thus, the convolutional codes of length n are the direct summands of F[z] n . It is worth mentioning that a code with overall constraint length zero can be regarded as a block code. In the coding literature a right invertible matrix is often called basic [2, p. 730] or delay-free and non-catastrophic, see [14, p.1102]. Sometimes in the literature convolutional codes are defined as subspaces of the vector space F((z)) n of vector valued Laurent series over F, see for instance [14] and [2]. However, as long as one restricts to right invertible generator matrices it does not make a difference whether one works in the context of infinite message and codeword sequences or finite ones, see also [20,19].
The most important concept for a code is its distance. It measures the error-correcting capability, hence the quality, of the code. The definition of the distance of a convolutional code is straightforward. For a polynomial vector v = N j=0 v j z j ∈ F[z] n the weight is defined as wt(v) = N j=0 wt(v j ), where wt(v j ) denotes the usual Hamming weight of v j ∈ F n . Then the (free) distance of a code C ⊆ F[z] n with generator matrix G ∈ F[z] k×n is given as Just like for block codes there exist quite some bounds on the distance of convolutional codes. One of them is the generalized Singleton bound [21,Thm. 2.2]. It states that the distance d of a code with parameters (n, k, δ) over any field satisfies d ≤ S(n, k, δ) := (n − k) δ k + 1 + δ + 1.

A class of one-dimensional MDS codes
In this section we present a construction of one-dimensional MDS convolutional codes. The distance will be computed straightforwardly. We will then compare our results with constructions known from the literature. Thereafter we will also compute the extended row distances. We will derive that they are increasing with a slope of n − δ.
Theorem 2.1 Let n ∈ N and 0 ≤ δ ≤ n − 1 and let q be a prime power such that n ≤ q − 1. Put F := F q and choose an element α ∈ F such that ord(α) ≥ n. Define and let C := im G ⊆ F[z] n . Then G is right invertible, i. e., the submodule C is a convolutional code, and dist(C) = n(δ + 1). In other words, C is an MDS code with parameters (n, 1, δ).
Notice that for δ = 0 the code is simply the n-fold repetition (block) code over F and the assertions are obvious.
Proof: In order to show that G is right invertible, we have to prove that the entries of the matrix G are coprime. In other words, it needs to be proven that the polynomials have no common root in any extension fieldF of F. In order to see this, assume β ∈F is such a common root. Then β, αβ, . . . , α n−1 β are roots of δ ν=0 z ν . Since β = 0 and ord(α) ≥ n, these numbers are pairwise different and δ < n leads to a contradiction.
, where t ≥ 0 and u 0 = 0 = u t , and put for ν = 0, . . . , δ + t. Notice that for ν ≤ δ the first row, G ν , ofG ν is nonzero while for ν ≥ t the last row, G ν−t , is nonzero. Since u 0 = 0 = u t this will provide us with a good estimate of the weight of v ν for these indices. In order to see this, note that for each index ν the nonzero rows ofG ν are consecutive and form a matrix of the type This will now be used for counting the weight of the vectors v ν for ν ∈ {0, . . . , δ, t, . . . , δ+t}.

case: t > δ
In this case the indices 0, . . . , δ, t, . . . , δ + t are all different and we havẽ and all displayed rows G ℓ are nonzero. Thus, using (2.2), and therefore where the last inequality follows from δ < n.
Remark 2.2 It is not hard to see that the matrix G in (2.1) is also right-invertible for all δ ≥ n for which ord(α) ∤ δ + 1. Examples show that these codes often have a large distance, too, but are not MDS in general. However, we can not provide any general result in this case.
We would like to comment on the field size required for the construction of the MDS codes in Theorem 2.1. In [11,Lemma 1] and [5,Thm. 3.7] it has been shown that if C is an (n, 1, δ)-MDS code over F q then q ≥ δ + 1. In Theorem 2.1 the field size q satisfies q ≥ n + 1 ≥ δ + 2. Thus, in the case n = ord(α) = q − 1 and δ = n − 1 our field size is just one above the lower bound given above. As to our knowledge it is not known in general whether there exist (n, 1, n − 1)-MDS codes over F n (in the case where n is a prime power).
We also would like to compare our results with previous constructions of MDS codes.
In [11] MDS codes with parameters (n, 1, δ) for certain combinations have been constructed. However, these combinations are different from ours. For instance, the result in [11, Thm. p. 580] does not contain the case of (q − 1, 1, q − 2)-MDS codes over F q and no On the other hand, the construction of that theorem allows the construction of a (17, 1, 20)-MDS code over F 32 which is not part of our Theorem 2.1. In [23] a construction of (n, 1, δ)-MDS codes is given over fields F q where q > δn+1. Except for the case δ = 1 this is a considerably bigger field size than ours where q ≥ n + 1. However, the construction in [23] works for all δ and not just for δ < n.
Another construction of MDS codes is given in [22]. Therein, MDS codes with (almost) arbitrary parameters (n, k, δ) are constructed over fields F q of size q ≥ δn 2 k(n−k) + 2. The construction is based on cyclic block codes with large distance. In the case k = 1 this again amounts to a considerably bigger field than in our construction. Alternatively, one can also see directly that our codes are not derived from good cyclic block codes in the sense of [22], i. e., the polynomial g = n j=1 z j−1 G j (z n ) derived from G = G 1 (z), . . . , G n (z) does not generate a good cyclic block code in general.
We want to go into more details about the weight distribution of these codes and therefore give also lower bounds for the extended row distances. The extended row distances have been introduced in [12, p. 541] and are very closely related to the trellis structure of the code and thus to its performance. Details on the importance of these distance parameters can be found in [12] 1 . The jth extended row distance amounts to the minimum weight of all paths through the state diagram starting at the zero state and which reach the zero state after exactly j steps for the first time. In other words, it is the minimum weight of all atomic codewords of degree j − 1 (i. e., length j) in the sense of [15]. The details are also explained in [9,Sec. 3.10]. In our case where the dimension of the code is k = 1, the atomic codewords are easily described. We will confine ourselves to the following property. It follows readily from the fact that the last δ coefficients of the message u ∈ F[z] make up the current state in the state diagram.
. Then the following are equivalent.
(i) The codeword uG is atomic (i. e., the associated path through the state diagram does not pass through the zero state except for its starting and end point). (ii) The polynomial u ∈ F[z] does not have δ consecutive zero coefficients.
Having this property in mind, the jth extended row distance of the code C = im G is defined to bê Notice that deg(u) = j − δ − 1 implies deg(uG) = j − 1 and thus the associated path has length j. As for the index notation we diverge somewhat from the paper [12] where the index j equals the degree of the associated codewords while in our case it reflects the length.
Hence the extended row distances are bounded from below by a linear function with slope n − δ.
Before we prove this result we wish to mention that in a certain sense this result is the best one can expect. As Equation (2.7) below shows, the "middle" coefficients of a codeword are contained in an (n, δ + 1)-block code. The distance of this code is therefore a lower bound for the slope. In our case this code has optimum distance n − δ, therefore the weight of codewords increases at least linearly in the length with slope n − δ. However, in specific cases certain constellations of consecutive coefficients of the generator matrix might even allow a better row distance. After the proof we will present examples for both cases, where the estimate in Proposition 2.4 is actually an identity and where it is a strict inequality.

Thus it remains to consider the coefficients
and v is atomic, the vector ( In the following examples we consider various cases of the parameters n and δ in Theorem 2.1. We computed the exact weight distribution (see [15,Sec. 3]) of the codes using Maple.
In this case one can show that the weight distribution is given by (see, e. g., [9, Sec. 3.10] and [15]) meaning that all atomic codewords of length j have weight 2 + 2j and that there exist 3 j−1 of such codewords for each j ≥ 2. As a consequence, the estimate in Proposition 2.4 is an equality, i. e.,d r j = 2 + 2j. One can also present explicitly an atomic codeword of length j and weight 2 + 2j. Indeed, it can be shown directly that wt ( j−2 i=0 z i )G = 2 + 2j for each j ≥ 2. (2) Let δ = 1, char(F) = 2 and n be arbitrary. Then it is easy to see that wt ( j−2 i=0 z i )G = 2 + j(n − 1) for each j ≥ 2, hence the estimate in Proposition 2.4 is an identity.
(3) Let δ = 2 and, again, n = 3, F = F 4 . Then G as defined in Theorem 2.1 is given by In this case the weight distribution is meaning, for instance, that there are 36 atomic codewords of length five, 9 of which have weight 11 and 14, respectively, and 18 have weight 13. Using induction it is easy to see that in the series expansion for each j ≥ 3 the coefficient of L j is divisible by W 6+j but not by W 7+j . Hence,d r j = 6 + j, and, like in (2), the estimate in Proposition 2.4 is an equality. Again, in this case one has wt ( j−3 i=0 z i )G = 6 + j for each j ≥ 3.
(4) In general however, the inequality for the jth extended row distance is not an equality and the growth rate can even be better. This happens for instance for n = 3, δ = 2 and F = F 8 with, of course, ord(α) = 7. In this case the weight distribution of the code in Theorem 2.1 is where each sum "+ . . ." is meant to contain only higher powers of W . This shows that the weight distribution is even better than the lower bound given in Proposition 2.4.

Parity check matrices with Vandermonde structure
In this section we will derive two types of parity check matrices for the codes of Theorem 2.1 in the case where ord(α) = n = δ + 1, one of them being minimal in the sense of [3, p. 459].
Both reveal a type of Vandermonde structure for these codes.
The condition ord(α) = n is necessary for the theorem to be true. As can easily be checked the product GH T is, in general, not zero if ord(α) > n.
Proof: (1) For j = 1, . . . , n let H (j) ∈ F[z] (n−1)×(n−1) be the submatrix of H obtained by omitting the jth column. Then, due to the Vandermonde structure of H, we obtain Since ord(α) = n, the last factor is nonzero for each j. But then the first factors show the coprimeness of the maximal minors of H, and thus H is right-invertible [14, Thm. A.1].
(2) Let G be given as above. Then for j = 1, . . . , n the jth entry G j is of the form where for the last equality we used ord(α) = n. Thus, Now we can prove GH T = 0. For easier indexing we will write down the sums of the matrix product backwards. Then we have to show that This is equivalent to In order to see this, compute Notice that for fixed µ = 0, . . . , j we have µ + 1 ∈ {1, . . . , j + 1} and j ≤ n − 2 yields α µ+1 = 1 due to ord(α) = n. Therefore, One should notice that the parity check matrix H is highly non-minimal, i. e., it is not a minimal basis for the dual code C ⊥ (for the notion of minimal basis see [3, p. 459] with 0 ≤ r ≤ s ≤ n − 1, i. e., with fewer rows than the matrix in Theorem 3.1, do not in general lead to good codes, even if ord(α) = n. This can easily be seen by running a few examples using, for instance, Maple. However, one should also notice the close relation of these matrices to those appearing in [1, Exa. 4.1]. In that paper methods from algebraic geometry are used to construct convolutional codes of Goppa type. A few examples of such matrices, but with different linear factors in the entries, are presented in [1] which are generator matrices of MDS convolutional codes. A deeper understanding as to whether there is a relation between the distance of the codes ker H T or im H and the Vandermonde structure of H must be considered as one of the main tasks in algebraic convolutional coding theory. It might also have some impact on the possibility of algebraic decoding of these codes.

Remark 3.2
With completely different methods it is possible to prove that also in the general case 0 ≤ δ < n = ord(α), the codes from Theorem 2.1 have a parity check matrix of a (somewhat modified) Vandermonde type. Indeed, in that case such a matrix is given by Hence H is right invertible and satisfies GH T = 0. The proof of this statement needs more detailed methods from the theory of cyclic convolutional codes as derived in [7] and will be omitted.
At the end of this section we will return to the case where δ = n − 1 and present a minimal parity check matrix, i. e., a right-invertible matrix with minimal row degrees in the sense of [3, p. 459] or [9,Sec. 2.5]. It shows that the dual code of im G has Forney index 1 (counted (n − 1) times) 2 and thus is a compact code in the sense of [14,Cor. 4.3]. Then H min is minimal and right-invertible and G H T min = 0, where G is again as in Theorem 3.1 (2). Hence in the case where ord(α) = n = δ + 1 the matrix H min is a parity check matrix of the code given in Theorem 2.1.
Proof: We use again the representation (3.1) for the matrix G. Writing down the sums of the product GH T min backwards again we obtain But the last expression is zero for all j = 1, . . . , n − 1 as we have shown in (3.3). From this we obtain that im H min ⊆ ker G T = (im G) ⊥ . Hence H min = BĤ, whereĤ is a parity check matrix of the code im G and B is some polynomial matrix. By [3,Thm. 3] the overall constraint length of imĤ is n − 1, too. On the other hand it is seen directly, that, firstly, the matrix H min has full row rank k and that, secondly, the overall constraint length of im H min is the sum of the row degrees of H min because the highest coefficient matrix of H min is a Vandermonde matrix with full row rank, see also [3, p. 495

Cyclicity
In this section we will show that for positive overall constraint length the codes given in Theorem 2.1 are cyclic if and only if ord(α) = n. Cyclic convolutional codes have been studied in detail in [7]. The first investigations in this direction have been made in the seventies by Piret [16] and Roos [18]. In both papers it has been shown (with different methods and in different contexts) that cyclicity of convolutional codes must not be understood in the usual sense, i. e. invariance under the cyclic shift, if one wants to go beyond the theory of cyclic block codes. As a consequence, Piret suggested a more complex notion of cyclicity which then has been further generalized by Roos. In both papers some nontrivial examples of cyclic convolutional codes in this new sense are presented along with their distances. All this indicates that the new notion of cyclicity seems to be the appropriate one in the convolutional case. Recently, in the paper [7] an algebraic theory of cyclic convolutional codes has been established which goes well beyond the results of the seventies. On the one hand it leads to a nice, yet nontrivial, generalization of the theory of cyclic block codes, on the other hand it gives a very powerful toolbox for constructing such codes. We will now give a very brief introduction into cyclicity for convolutional codes before investigating this additional structure for the codes of Theorem 2.1.
Just like for cyclic block codes we assume from now on that the length n and the field size |F| are coprime. Recall that a block code C ⊆ F n is called cyclic if it is invariant under the cyclic shift, i. e.
for all (v 0 , . . . , v n−1 ) ∈ F n . This is the case if and only if C is an ideal in the quotient ring identified with F n in the canonical way via In order to extend this situation to the convolutional setting, we have to replace the vector space F n by the free module F[z] n := { N ν=0 z ν v ν | N ∈ N 0 , v ν ∈ F n } and, consequently, the ring A by the polynomial ring A[z] := N ν=0 z ν a ν N ∈ N 0 , a ν ∈ A over A. Then we can extend the mapping p above coefficientwise to polynomials, thus p N ν=0 z ν v ν = N ν=0 z ν p(v ν ) where, of course, v ν ∈ F n and thus p(v ν ) ∈ A for all ν. At this point it is quite natural to declare a convolutional code C ⊆ F[z] n cyclic if it is invariant under the cyclic shift, i. e., if (4.1) holds true for all (v 0 , . . . , v n−1 ) ∈ F[z] n . Since, just like for block codes, the cyclic shift in F[z] n corresponds to multiplication by x in A[z], this amounts to the same as saying that C is called cyclic if p(C) is an ideal in A[z]. However, it has been shown in [16,Thm. 3.12] and [18,Thm. 6] that each convolutional code that is cyclic in this sense has overall constraint length zero, thus is a block code. An elementary proof can be found at [7,Prop. 2.7]. Due to this result Piret [16] introduced a different notion of cyclicity for convolutional codes which then was further generalized by Roos [18]. This concept is based on some automorphism of the F-algebra A. Thus, let Aut F (A) be the group of all F-automorphisms on A. It is clear that each automorphism σ ∈ Aut F (A) is uniquely determined by the single value σ(x) ∈ A, but not every choice for σ(x) determines an automorphism on A.
The main idea of Piret was to impose a new ring structure on A[z] and to declare a code cyclic if it is a left ideal with respect to that ring structure. The new structure is in general non-commutative and based on an (arbitrarily chosen) F-automorphism on A. In detail, this looks as follows.
A few comments are in order. First notice that, unless σ is the identity, the indeterminate z does not commute with its coefficients. Due to this very specific non-commutativity the ring A[z; σ] is also called a skew-polynomial ring. Since σ| F = id F , the classical polynomial ring F[z] is a commutative subring of A[z; σ], too. As a consequence, A[z; σ] is a left and right F[z]-module and it can easily be seen that the mapping p in (2) above is an isomorphism of left F[z]-modules. In the special case where σ = id A the ring A[z; σ] is the classical commutative polynomial ring and due to the results mentioned earlier this does not result in any convolutional codes other than block codes. In many cases where σ is not the identity there do indeed exist cyclic convolutional codes with positive overall constraint length. Characterizations along with several examples (actually all optimal with respect to their free distances) have been presented in [7,5,4]. Another class of such codes is given by some of the codes of Theorem 2.1. Indeed, we have the following. Proposition 4.2 Let n be a positive integer coprime with |F| and let α ∈ F be such that ord(α) = n. Furthermore, let δ ∈ N 0 and G be as in (2.1). Then the F-algebra homomorphism σ : A −→ A defined by σ(x) = αx is an F-automorphism on A and the submodule C = im G is σ-cyclic. In particular, if δ < n, then C is a cyclic MDS convolutional code.
Remember that only for specific values of δ these submodules are actually convolutional codes, i. e., the matrix G is right-invertible, see also Remark 2.2. Recall also from the last section that in the case ord(α) = n > δ the codes can be described by a certain Vandermonde parity check matrix. Therefore, in this case the codes have quite a rich structure.
Proof: First of all, since (αx) i , i = 0, . . . , n − 1 are linearly independent over F and (αx) n = 1, the mapping σ as defined above is indeed an automorphism on A. Consider now the submodule C = im G where G = δ ν=0 z ν 1 α ν α 2ν . . . α (n−1)ν . We have to prove that p(C) is a left ideal in A[z; σ]. Since p(C) is a left F[z]-module, it suffices to show that p(C) is closed with respect to left multiplication by x. Thus, consider the image of G under the mapping p, i. e., define (4.5) Now it suffices to show that p −1 (xg) ∈ im G, or, stated differently, that xg is a left F[z]multiple of g. But this can easily be seen since This result proves in particular that if ord(α) = n, then the codes in Theorem 2.1 are cyclic. In the sequel we want to show even more. Indeed, we will prove that the condition ord(α) = n is even necessary and sufficient for the codes of Theorem 2.1 to be cyclic with respect to some F-automorphism.
To this end we need some more details about the coefficient ring A. Due to the coprimeness of n and |F|, this ring is a direct product of fields. Indeed, let where π 1 , . . . , π r ∈ F[x] are irreducible, monic, and pairwise different. Then the Chinese Remainder Theorem tells us that ψ : A −→ K 1 × . . . × K r , a −→ a mod π 1 , . . . , a mod π r , (4.7) where K k = F[x]/ π k , is an isomorphism if × r i=1 K i is endowed with componentwise addition and multiplication. Notice that K k ∼ = K l if and only if deg x π k = deg x π l . The elements ε (k) := ψ −1 0, . . . , 0, 1, 0, . . . , 0 for k = 1, . . . , r (4.8) (where 0 and 1 have to be understood as the elements 0 mod π l and 1 mod π l in K l ) are particularly important since they form the uniquely determined set of primitive idempotents in A. The idempotents are pairwise orthogonal, thus ε (k) ε (l) = 0 for k = l. Observe that for any a ∈ A the products ε (l) a single out the various components of a. Precisely, ψ(ε (l) a) = (0, . . . , 0, a mod π l , 0, . . . , 0) for any l = 1, . . . , r. Therefore, ε (1) a + . . . + ε (r) a is a decomposition of a ∈ A just like the one in (4.7) and in the sequel we will use this representation rather than that from (4.7).
It is straightforward to see that a given automorphism σ ∈ Aut F (A) induces a permutation on the set of primitive idempotents. More precisely, σ(ε (k) ) = ε (l) for some l such that deg x π k = deg x π l . (4.9) The following example will be important for our purposes.
Proof: The if-part as well as the additional statement have been proven in Proposition 4.2. "Only-if-part": Let C = im G be σ-cyclic for some σ ∈ Aut F (A). Let x n − 1 = r i=1 π i be the prime factorization of x n − 1 such that π 1 = x − 1. Denoting the idempotents by ε (1) , . . . , ε (r) we have in particular ε (1) = 1 n x n −1 x−1 = 1 n n−1 i=0 x i . By assumption ord(α) ≥ n and we have to show that ord(α) = n, hence that r = n and, up to ordering, π i = x − α i−1 for i = 1, . . . , n. By assumption, p(C) is the left ideal generated by g as given in (4.5). Since rank C = 1, the generator matrix G is unique up to a nonzero constant in F. Thus, the generator of the left ideal is also unique up to a constant factor and, along with [7,Cor. 4.13 and Thm. 4.15(b)], this shows that the polynomial g is reduced in the sense of [7,Def. 4.9(b)]. Moreover, since the code is one-dimensional we obtain from [7, Thm. 7.13] that g = ε (k) g for some k = 1, . . . , r such that deg π k = 1. In particular we have g 0 = ε (k) g 0 for the constant coefficient g 0 of g. Since (4.5) yields g 0 = nε (1) and ε (k) ε (1) = 0 for k > 1, we conclude k = 1, thus g = ε (1) g. Therefore, where g ν is the coefficient of z ν in g. Hence, g ν = σ ν (ε (1) )g ν for all ν = 0, . . . , δ. Moreover, since δ > 0 we have σ(ε (1) ) = ε (1) for otherwise the code would have overall constraint length zero, see [4,Lemma 3.4]. Consider now the coefficient g 1 = n−1 i=0 (αx) i . The equation g 1 = σ(ε (1) )g 1 along with σ(ε (1) ) = ε (1) and the orthogonality of the idempotents implies ε (1) g 1 = 0. Substituting x = 1, we obtain n−1 i=0 α i = 0. But then n−1 i=0 α i (α−1) = α n − 1 = 0 which along with the assumption ord(α) ≥ n implies ord(α) = n. 2 We want to close the paper with yet another representation of the cyclic codes considered so far. In [7,Prop. 7.10] it has been shown that a polynomial g ∈ A[z; σ] with the property g = ε (k) g for some k = 1, . . . , r generates an ideal that is a convolutional code, i. e., a direct summand in the left F[z]-module A[z; σ], if and only if g = ε (k) u for some unit u ∈ A[z; σ]. More details about this can be found in [4]. From Example 4.3 we can easily derive how such a unit looks like in the case of the equivalent conditions of Theorem 4.4 if δ is not too big.
The representation on the right hand side of (a) justifies to call these codes one-dimensional Reed-Solomon convolutional codes.
In the paper [4] representations of cyclic codes via units like on the right hand side of (b) above have been studied in detail. Therein, it has been investigated as to which algebraic parameters (field size, dimension, overall constraint length, and Forney indices) can be realized by cyclic convolutional codes. In particular, a construction of certain compact cyclic convolutional codes (i. e., all Forney indices are the same) has been derived. However, no distance results have been obtained in that context. As has been shown in [6] the presentation as on the right hand side of (a) seems to be more suitable for a generalization to codes of higher dimension with good distance.

Open Problems
We have presented a class of one-dimensional convolutional codes with maximum possible distance. In the specific case where ord(α) = n these codes are cyclic and have a Vandermonde parity check matrix. Without using explicitly Vandermonde matrices, but highly the theory of cyclic convolutional codes, first attempts are currently under investigation of how to generalize the construction of cyclic convolutional codes with large distance to higher dimensions, see [6]. In general, we consider it most important to understand whether Vandermonde structure of a cyclic convolutional code can be exploited for distance computations and algebraic decoding algorithms. We think that the one-dimensional cyclic MDS codes with their rich structure as presented in this paper might be a good starting point in this regard.


extfieldsofstudy: Mathematics Biology Physics Medicine

s2fieldsofstudy:
Computer Science
Mathematics

text:
Exact Asymptotic Results for a Model of Sequence Alignment

Finding analytically the statistics of the longest common subsequence (LCS) of a pair of random sequences drawn from c alphabets is a challenging problem in computational evolutionary biology. We present exact asymptotic results for the distribution of the LCS in a simpler, yet nontrivial, variant of the original model called the Bernoulli matching (BM) model which reduces to the original model in the large c limit. We show that in the BM model, for all c, the distribution of the asymptotic length of the LCS, suitably scaled, is identical to the Tracy-Widom distribution of the largest eigenvalue of a random matrix whose entries are drawn from a Gaussian unitary ensemble. In particular, in the large c limit, this provides an exact expression for the asymptotic length distribution in the original LCS problem.

Finding analytically the statistics of the longest common subsequence (LCS) of a pair of random sequences drawn from c alphabets is a challenging problem in computational evolutionary biology. We present exact asymptotic results for the distribution of the LCS in a simpler, yet nontrivial, variant of the original model called the Bernoulli matching (BM) model which reduces to the original model in the c → ∞ limit. We show that in the BM model, for all c, the distribution of the asymptotic length of the LCS, suitably scaled, is identical to the Tracy-Widom distribution of the largest eigenvalue of a random matrix whose entries are drawn from a Gaussian unitary ensemble. In particular, in the c → ∞ limit, this provides an exact expression for the asymptotic length distribution in the original LCS problem. Sequence alignment is one of the most useful quantitative methods used in evolutionary molecular biology [1][2][3]. The goal of an alignment algorithm is to search for similarities in patterns in different sequences. A classic and much studied alignment problem is the so called 'longest common subsequence' (LCS) problem. The input to this problem is a pair of sequences α = {α 1 , α 2 , . . . , α i } (of length i) and β = {β 1 , β 2 , . . . , β j } (of length j). For example, α and β can be two random sequences of the 4 base pairs A, C, G, T of a DNA molecule, e.g., α = {A, C, G, C, T, A, C} and β = {C, T, G, A, C}. A subsequence of α is an ordered sublist of α (entries of which need not be consecutive in α), e.g, {C, G, T, C}, but not {T, G, C}. A common subsequence of two sequences α and β is a subsequence of both of them. For example, the subsequence {C, G, A, C} is a common subsequence of both α and β. There can be many possible common subsequences of a pair of sequences. The aim of the LCS problem is to find the longest of such common subsequences. This problem and its variants have been widely studied in biology [4][5][6][7], computer science [8][9][10]2], probability theory [11][12][13][14][15][16] and more recently in statistical physics [17][18][19]. A particularly important application of the LCS problem is to quantify the closeness between two DNA sequences. In evolutionary biology, the genes responsible for building specific proteins evolve with time and by finding the LCS of the same gene in different species, one can learn what has been conserved in time. Also, when a new DNA molecule is sequenced in vitro, it is important to know whether it is really new or it already exists. This is achieved quantitatively by measuring the LCS of the new molecule with another existing already in the database.
For a pair of fixed sequences of length i and j respectively, the length L i,j of their LCS is just a number. However, in the stochastic version of the LCS problem one compares two random sequences drawn from c alphabets and hence the length L i,j is a random variable.
A major challenge over the last three decades has been to determine the statistics of L i,j [11][12][13][14][15]. For equally long sequences (i = j = n), it has been proved that L n,n ≈ γ c n for n ≫ 1, where the averaging is performed over all realizations of the random sequences. The constant γ c is known as the Chvátal-Sankoff constant which, to date, remains undetermined though there exists several bounds [12,14,15], a conjecture due to Steele [13] that γ c = 2/(1 + √ c) and a recent proof [16] that γ c → 2/ √ c as c → ∞. Unfortunately, no exact results are available for the finite size corrections to the leading behavior of the average L n,n , for the variance, and also for the full probability distribution of L n,n . Thus, despite tremendous analytical and numerical efforts, exact solution of the random LCS problem has, so far, remained elusive. Therefore it is important to find other variants of this LCS problem that may be analytically tractable.
Computationally, the easiest way to determine the length L i,j of the LCS of two arbitrary sequences of lengths i and j (in polynomial time ∼ O(ij)) is via using the recursive algorithm [2,19] subject to the initial conditions L i,0 = L 0,j = L 0,0 = 0. The variable η i,j is either 1 when the characters at the positions i (in the sequence α) and j (in the sequence β) match each other, or 0 if they do not. Note that the variables η i,j 's are not independent of each other. To see this consider the simple example -matching of two strings α = AB and β = AA. One has by definition: η 1,1 = η 1,2 = 1 and η 2,1 = 0. The knowledge of these three variables is sufficient to predict that the last two letters will not match, i.e., η 2,2 = 0. Thus, η 2,2 can not take its value independently of η 1,1 , η 1,2 , η 2,1 . These residual correlations between the η i,j variables make the LCS problem rather complicated. Note however that for two random sequences drawn from c alphabets, these cor-relations between the η i,j variables vanish in the c → ∞ limit. A simpler but natural variant of this LCS problem is the Bernoulli matching (BM) model where one ignores the correlations between η i,j 's for all c [19]. The BM model reduces to the original LCS problem only in the c → ∞ limit. The length L BM i,j of the BM model satisfies the same recursion relation in Eq. (1) except that η i,j 's are now independent and each drawn from the bimodal distribution: p(η) = (1/c)δ η,1 + (1 − 1/c)δ η,0 . The BM model, though simpler than the original LCS problem, is still nontrivial due to the nonlinear recursion relation in Eq. (1). Using the cavity method of spin glass physics [20], the asymptotic behavior of the average length in the BM model was determined analytically [19], , same as the conjectured value of the Chvátal-Sankoff constant γ c for the original LCS model. However, other properties such as the variance or the distribution of L BM n,n remained untractable even in the BM model.
The purpose of this Letter is to present an exact asymptotic formula for the distribution of the length L BM n,n in the BM model for all c. Our main result is that for large n, where χ is a random variable with a n-independent distribution, Prob(χ ≤ x) = F TW (x) which is the well studied Tracy-Widom distribution for the largest eigenvalue of a random matrix with entries drawn from a Gaussian unitary ensemble [21]. For a detailed form of the function F TW (x), see [21]. We show that for all c, This allows us to calculate the average including the subleading finite size correction term and the variance of L BM n,n for large n, where one can use the known exact values [21], χ = −1.7711 . . . and χ 2 − χ 2 = 0.8132 . . .. In particular, we note that in the limit c → ∞, Eqs. In the BM model, the length L BM i,j can be interpreted as the height of a surface over the 2-d (i, j) plane constructed via the recursion relation in Eq. (1). A typical surface, shown in Fig. (1a), has terrace-like structures. It is useful to consider the projection of the level lines separating the adjacent terraces whose heights differ by 1 (see Fig.2) onto the 2-d (i, j) plane. Note that, by the rule Eq. (1), these level lines never overlap each other, i.e., no two paths have any common edge. The statistical weight of such a projected 2-d configuration is the product of weights associated with the vertices of the 2d plane. There are five types of possible vertices with nonzero weights as shown in Fig.2, where p = 1/c and q = 1 − p. Since the level lines never cross each other, the weight of the first vertex in Fig. (2) is 0.  Fig.(1a). The adjacent table shows the weights of all vertices on the 2-d plane.
Consider first the limit c → ∞ (i.e., p → 0). The weights of all allowed vertices are 1, except the ones shown by black dots in Fig.(2), whose associated weights are p → 0. The number N of these black dots inside a rectangle of area A = ij can be easily estimated. For large A and p → 0, this number is Poisson distributed with the mean N = pA. The Bethe ansatz analysis shows that BM corresponds to the sector of the 5-vertex model [22] where the density α of empty edges in a row of vertical edges is close to the boundary α ≈ 1 − . The careful examination of the free energy near this boundary allows one to conclude that the leading contribution in p (for p → 0) to N comes exactly from the line of phase transitions in a 5-vertex model. The subleading corrections to N are of order ∼ p 3/2 and are ensured by small deviations from the critical line being beyond the Poisson approximation [23].
The height L BM i,j is just the number of level lines N inside this rectangle of area A = ij. The problem of estimating N has recently appeared in a number of interface models such as a polynuclear growth model [24] and a ballistic deposition model [25]. By using a mapping to the longest increasing subsequence (LIS) of the equally likely permutations of a set of integers and then, by applying a celebrated result due to Baik, Deift and Johansson (BDJ) [26], it was shown [24,25] that the number of level lines N inside the rectangle (for large A), appropriately scaled, has a limiting behavior, where χ is a random variable with Tracy-Widom distribution. Using N = pA = ij/c, one then obtains in the limit p → 0, In particular, for large equal length sequences i = j = n, we get for c → ∞ Note that since the BM and the original LCS model are equivalent in the limit c → ∞, the exact results in Eqs. (6)-(7) also hold for the LCS model. Note that only the leading behavior of the average L n,n was known before [16] in the c → ∞ limit of the original LCS model. For finite c, while the above mapping to the LIS problem still works, the corresponding permutations of the LIS problem are not generated with equal probability and hence one can no longer use the BDJ results. To make progress for finite c, we map the BM model exactly to a 3-d anisotropic directed percolation (ADP) model first considered by Rajesh and Dhar [27]. This ADP model can further be mapped to a (1 + 1)-d directed polymer problem studied by Johansson [28]. For this specific directed polymer problem, Johansson derived exact asymptotic result for the distribution of the polymer energy. Translating these results back to the BM model, we derive our main results in Eqs. (3)- (5). Note that the recursion relation in Eq. (1) can also be viewed as a (1 + 1)-d directed polymer problem [18,19] and some asymptotic results (such as the O(n 2/3 ) behavior of the variance of L n,n for large n) can be obtained using the arguments of universality [18]. However, this does not provide precise results for the full distribution which are obtained here.
Let us consider a directed bond percolation on a simple cubic lattice. The bonds are occupied with probabilities p x , p y , and p z along the x, y and z axes and are all directed towards increasing coordinates. Imagine a source of fluid at the origin which spreads along the occupied directed bonds. The sites that get wet by the fluid form a 3-d cluster. In the ADP problem, the bond occupation probabilities are anisotropic, p x = p y = 1 (all bonds aligned along the x and y axes are occupied) and p z = p. Hence, if the point (x, y, z) gets wet by the fluid then all the points (x ′ , y ′ , z) on the same plane with x ′ ≥ x and y ′ ≥ y also get wet. Such a wet cluster is compact and can be characterized by its bounding surface height h(x, y) as shown in Fig.(1b). It is not difficult to see that the height h(x, y) satisfies the following recursion relation [27], where ξ i,j 's are i.i.d. random variables taking nonnegative integer values with Prob(ξ i,j = k) = (1 − p) p k for k = 0, 1, 2, . . .. One can also interpret the height h(x, y) in Eq. (8) as the energy of a directed polymer in the (x − y) plane. Precisely this particular version of the polymer problem was studied by Johansson [28] who obtained the asymptotic distribution of the height for large x and y, where q = 1 − p, χ is a random variable with a Tracy-Widom distribution. While the terrace-like structures of the ADP surface look similar to the BM surfaces (compare Figs.(1a) and (1b)), there is an important difference between the two. In the ADP model, the level lines separating two adjacent terraces can overlap with each other [27], which does not happen in the BM model. However, by making the following change of coordinates in the ADP model [27] ζ = x + h(x, y); η = y + h(x, y) one gets a configuration of the surface where the level lines no longer overlap. Moreover, it is not difficult to show that the projected 2-d configuration of level lines of this shifted ADP surface has exactly the same statistical weight as the projected 2-d configuration of the BM surface. Denoting the BM height byh(x, y) = L BM x,y , one then has the identity,h(ζ, η) = h(x, y), which holds for each configuration. Using Eq. (10), one can rewrite this identity as Thus, for any given height function h(x, y) of the ADP model, one can, in principle, obtain the corresponding height functionh(x, y) for all (x, y) of the BM model by solving the nonlinear equation (11). This is however very difficult in practice. Fortunately, one can make progress for large (x, y) where one can replace the integer valued discrete heights by continuous functions h(x, y) and h (x, y). Using the notation ∂ x ≡ ∂/∂x it is easy to derive from Eq. (10) the following pair of identities, In a similar way, one can show that We then observe that Eqs. (12) and (13) are invariant under the simultaneous transformations Since the height is built up by integrating the derivatives, this leads to a simple result for large ζ and η, χ, (16) where p = 1/c and q = 1 − 1/c. For equal length sequences x = y = n, Eq. (16) then reduces to Eq. (3).
Thus the discrepancy falls off as a power law for large ζ, indicating that indeed our solution is asymptotically exact. We have also performed numerical simulations of the BM model using the recursion relation in Eq. (1) for c = 2, 4, 9, 16, 100. Our preliminary results [23] for relatively small system sizes (up to n = 5000) are consistent with our exact results in Eqs. (3)-(5). The Tracy-Widom distribution of the random matrix theory has appeared recently in a number of problems [21,29,28,24,25]. In this Letter, we have shown that it also describes the asymptotic distribution of the length of the longest common subsequence in a sequence matching problem. While a possible link between the two problems was speculated before [29], a precise connection, so far, was missing and is provided here.