\documentclass[11pt]{article}
\usepackage{jair}
\usepackage{theapa}
\usepackage{amssymb}
\usepackage{psfrag} 
\usepackage{graphicx} 

\jairheading{21}{2004}{287-317}{06/03}{03/04}
\ShortHeadings{IDL-Expressions: A Formalism for Finite Languages}
{Nederhof \& Satta}
\firstpageno{287}

\sloppy

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%MACROS%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\sep}{\,\mid\,}
\newcommand{\eat}[1]{}
\newcommand{\myspace}{\mbox{}\hspace{1em}}

\newcommand{\order}[1]{{\cal O}({#1})}
\newcommand{\sorder}[1]{{\it o}({#1})}
\newcommand{\size}[1]{\left | {#1} \right |}

\newcommand{\nonterm}{{\it N}}
\newcommand{\myterm}{{\mit\Sigma}}
\newcommand{\ep}{\varepsilon}
\newcommand{\symbolep}{\cal E}

\newcommand{\de}{\rightarrow}

\newcommand{\der}{\Rightarrow}
\newcommand{\derg}[1]{\der_{{#1}}}
\newcommand{\derm}{\der^{*}}
\newcommand{\derp}{\der^{+}}
\newcommand{\derpg}[1]{\der^{+}_{{#1}}}
\newcommand{\dermg}[1]{\der^{*}_{{#1}}}

\newcommand{\bul}{\mathrel{\bullet}}
\newcommand{\nat}{\mathbb{N}}

% aux functions
\newcommand{\mycomb}{{\sf comb}}
\newcommand{\mylockh}{{\sf lock}}
\newcommand{\myrank}{{\sf rank}}
\newcommand{\mycut}{{\sf cut}}
\newcommand{\myfreecut}{\mbox{{\sf 0-cut}}}
\newcommand{\myfreecutsub}{\mbox{{\scriptsize\sf 0-cut}}}
\newcommand{\mywidth}{{\sf width}}
\newcommand{\myfreewidth}{\mbox{{\sf 0-width}}}
\newcommand{\lstsep}{\diamond}

% IDL-expr stuff
\newcommand{\mychoose}{\vee}
\newcommand{\mymix}{\|}
\newcommand{\mylock}{\times}
\newcommand{\bottom}{\perp}
\newcommand{\numop}[1]{\#_{\it op}({#1})}
\newcommand{\numsym}[1]{\#_s({#1})}
\newcommand{\vcut}{\hat{V}}
\newcommand{\vunlock}{V^{(\overline{\rm L})}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{prop}{Proposition}

\newcommand{\proof}{\noindent {\em Proof.\hspace{1em}}}
\newcommand{\olproof}{{\em Outline of the proof.\hspace{1em}}}
%\newcommand{\closeproof}{\mbox{\hspace{1em}\rule{.45em}{.45em}}}
\newcommand{\closeproof}{\mbox{\hspace{1em}{\footnotesize $\Box$}}}
\newcommand{\closeproofns}{\mbox{\hspace{1em}\rule{.45em}{.45em}}}

\renewcommand{\labelenumi}{\rm{(\roman{enumi})}}
\renewcommand{\labelenumii}{\rm{(\alph{enumii})}}

\psfrag{0}{$0$}
\psfrag{1}{$1$}
\psfrag{vs}{$v_s$}
\psfrag{ve}{$v_e$}
\psfrag{v0}{$v_0$}
\psfrag{v1}{$v_1$}
\psfrag{v2}{$v_2$}
\psfrag{v3}{$v_3$}
\psfrag{v4}{$v_4$}
\psfrag{v5}{$v_5$}
\psfrag{v6}{$v_6$}
\psfrag{v7}{$v_7$}
\psfrag{v8}{$v_8$}
\psfrag{v9}{$v_9$}
\psfrag{v10}{$v_{10}$}
\psfrag{v11}{$v_{11}$}
\psfrag{v12}{$v_{12}$}
\psfrag{v13}{$v_{13}$}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%MACROS%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

\title{IDL-Expressions: \\
      A Formalism for Representing and Parsing \\
      Finite Languages in Natural Language Processing}

\author{\name Mark-Jan Nederhof \email markjan@let.rug.nl \\
	\addr Faculty of Arts, University of Groningen \\
	P.O.\ Box 716 \\
	NL-9700 AS Groningen, The Netherlands 
	\AND
	\name Giorgio Satta \email satta@dei.unipd.it \\
	\addr Dept. of Information Engineering, University of Padua \\
	via Gradenigo, 6/A \\
	I-35131 Padova, Italy}

\maketitle

\begin{abstract}
  We propose a formalism for representation of finite languages, 
  referred to as the class of {\em IDL-expressions\/}, 
  which combines concepts that were only considered in isolation in 
  existing formalisms.
  The suggested applications are in natural language processing, 
  more specifically in surface natural language generation and 
  in machine translation, where
  a sentence is obtained by first generating a 
  large set of candidate sentences, represented in a compact way,
  and then filtering such a set through a parser.
  We study several formal properties of IDL-expressions and 
  compare this new formalism with more standard ones.  We also 
  present a novel parsing algorithm for IDL-expressions
  and prove a non-trivial upper bound on its time complexity.
\end{abstract}

\section{Introduction}
\label{s:intro}

In natural language processing, more specifically in 
applications that involve natural language generation, 
the task of {\em surface generation} consists in the 
process of generating an output sentence in a target 
language, on the basis of some input representation 
of the desired meaning for the output sentence.
During the last decade, a number of new approaches for 
natural language surface generation have been put forward, 
called {\em hybrid approaches}.  Hybrid approaches make use of
symbolic knowledge in combination with
statistical techniques that have recently been 
developed for natural language processing.
Hybrid approaches therefore share many advantages with 
statistical methods for natural language processing, such
as high accuracy, wide 
coverage, robustness, portability and scalability.

Hybrid approaches are typically based on two processing phases, 
described in what follows
(\citeR{KN95,LA98,BA00} report examples of applications
of this approach in real world generation systems).
In the first phase one generates a large set of candidate sentences
by a relatively simple process. 
This is done on the
basis of an input sentence in some source language
in case the process is embedded within a machine translation system, 
or more generally on the basis of some logical/semantic representation,
called {\em conceptual structure\/}, 
which denotes the meaning that the output sentence should convey.
This first phase involves no or only few intricacies of the target 
language, and the set of candidate sentences may contain
many that are ungrammatical or that can otherwise be seen 
as less desirable than others.
In the second phase one or more preferred sentences are selected
from the collection of candidates, exploiting some form of syntactic
processing that more heavily relies on properties of the target
language than the first phase.
This syntactic processing
may involve language models as simple as bigrams or it
may involve more powerful models such as those based on 
context-free grammars, which typically perform with 
higher accuracy on this task
(see for instance work presented by~\citeR{CH01} and references therein).  

In hybrid approaches, the generation of the candidate set
typically involves a symbolic grammar that 
has been quickly hand-written,
and is quite small and easy to maintain.  
Such a grammar cannot therefore account for all of the intricacies 
of the target language.  For instance, 
frequency information for synonyms and collocation information 
in general is not encoded in the grammar.  Similarly, 
lexico-syntactic and selectional constraints
for the target language might not be fully specified, as is 
usually the case with small and mid-sized grammars.
Furthermore, there might also be some underspecification stemming from
the input conceptual structure.  This is usually the case if
the surface generation module is embedded into a larger architecture for 
machine translation, and the source language 
is underspecified for features such as definiteness, time 
and number.  Since inferring the missing information 
from the sentence context is a very difficult task, the surface generation
module usually has to deal with underspecified knowledge. 

All of the above-mentioned problems are well-known 
in the literature on natural language
surface generation, and are usually 
referred to as ``lack of knowledge''
of the system or of the input. 
As a consequence of these problems, 
the set of candidate sentences generated in the first phase
may be extremely large.   
In real world generation systems, candidate sets have been
reported to contain as many as $10^{12}$ sentences~\cite{LA00}. 
As already explained, the second processing phase in hybrid approaches 
is intended to reduce these huge sets to subsets containing only a few 
sentences.
This is done by exploiting knowledge about the target language
that was not available in the first phase. 
This additional knowledge can often be obtained through automatic extraction
from corpora, which requires considerably less effort
than the development of hand-written, purely symbolic systems.

Due to the extremely large size of the set of candidate sentences,
the feasibility of hybrid approaches to surface natural language generation
relies on
\begin{itemize}
\item
the compactness of the representation of a set of candidate sentences
that in real world systems might be as large as $10^{12}$; and
\item
the efficiency of syntactic processing of the stored set.
\end{itemize}

Several solutions have been adopted in existing hybrid systems
for the representation of the set of candidate sentences. 
These include bags of words~\cite{BR90a} and bags of 
complex lexical representations~\cite{BE92,BR92,WH92}, 
word lattices~\cite{KN95,LA98,BA00}, and 
non-recursive context-free grammars~\cite{LA00}.
As will be discussed in detail in Section~\ref{s:bag}, 
word lattices and non-recursive context-free grammars allow 
encoding of precedence constraints and choice among different words, 
but they both lack a primitive for representing strings
that are realized by combining a collection of words in an arbitrary order. 
On the other hand, bags of words allow the encoding of free
word order, but in such a representation one cannot directly express
precedence constraints and choice among different words. 

In this paper we propose a new representation that combines 
all of the above-mentioned primitives.
This representation consists of {\em IDL-expressions}.
In the term IDL-expression,
`I' stands for ``interleave'', which pertains to phrases that may
occur interleaved, allowing freedom on word order
(a precise definition of this notion will be provided in the next section);
`D' stands for ``disjunction'', which allows choices of words or phrases;
`L' stands for ``lock'', which is used to constrain the application 
of the interleave operator.
We study some interesting properties of this representation, 
and argue that the expressivity of the formalism 
makes it more suitable than the alternatives discussed above
for use within hybrid architectures for surface natural 
language generation.
We also associate IDL-expressions with {\em IDL-graphs\/}, 
an equivalent representation that can be more easily interpreted
by a machine, and develop a dynamic programming algorithm for 
parsing IDL-graphs using a context-free grammar.  
If a set of candidate sentences is 
represented as an IDL-expression or IDL-graph, the algorithm can be used to 
filter out ungrammatical sentences from the set, or to rank 
the sentences in the set according to their likelihood, 
in case the context-free grammar assigns weights to derivations. 
While parsing is traditionally defined for input consisting 
of a single string, we here conceive parsing as a process that 
can be carried out on an input device 
denoting a language, i.e., a set of strings.  

There is a superficial similarity between 
the problem described above of representing finite sets in 
surface generation, and a different research topic, often 
referred to as discontinuous parsing.  
In discontinuous parsing one seeks to relax the definition of 
context-free grammars in order to represent the syntax
of languages that exhibit constructions
with uncertainty on word or constituent order
(see for instance work reported
by~\citeR{DA02} and references therein). 
In fact, some of the operators we use in IDL-expressions 
have also been exploited in recent work on discontinuous parsing. 
However, the parsing problem for discontinuous grammars and 
the parsing problem for IDL-expressions are quite
different: in the former, we are given a grammar with 
productions that express uncertainty on constituent order, and 
need to parse an input string whose symbols are totally ordered;
in the latter problem 
we are given a grammar with total order on the constituents
appearing in each production, and need to parse an input  
that includes uncertainty on word and constituent order. 

This paper is structured as follows. 
In Section~\ref{s:bag} we give a brief overview of existing
representations of finite languages that have
been used in surface generation components.
We then discuss some notational preliminaries in Section~\ref{s:notation}.
In Section~\ref{s:idl-expr} we introduce IDL-expressions
and define their semantics.
In Section~\ref{s:idl-graph} we associate with IDL-expressions 
an equivalent but more procedural representation, 
called IDL-graphs.  We also introduce the important notion of 
cut of an IDL-graph, which will be exploited later by our algorithm. 
In Section~\ref{s:parser} we briefly discuss the Earley algorithm, 
a traditional method for parsing a string using a context-free grammar,
and adapt this algorithm to work on finite languages encoded 
by IDL-graphs. 
In Section~\ref{s:compl} we prove a non-trivial upper bound 
on the number of cuts in an IDL-graph, and on this basis we 
investigate the computational complexity of our parsing algorithm.  
We also address some implementational issues. 
We conclude with some discussion in Section~\ref{s:discussion}.



\section{Representations of Finite Languages}
\label{s:bag}

In this section we analyze and compare existing representations of finite
languages that have been adopted in surface generation 
components of natural language  systems. 

Bags (or multisets) of words have been used in 
several approaches to surface generation. They 
are at the basis of the generation component 
of the statistical machine translation 
models proposed by~\citeA{BR90a}.  
Bags of complex lexical signs have also been used in the machine 
translation approach described by~\citeA{BE92} and~\citeA{WH92}, 
called shake-and-bake. 
As already mentioned, bags are a very succinct representation 
of finite languages, since they allow encoding of more than
exponentially many strings in the size of a bag itself. 
This power comes at a cost, however.   Deciding whether some
string encoded by an input bag can be parsed by 
a CFG is NP-complete~\cite{BR92}.  It is not difficult to 
show that this result still holds in the case of a regular grammar or,
equivalently, a regular expression.  An NP-completeness
result involving bags has also been presented by~\citeA{KN99},
for a related problem where the parsing grammar is 
a probabilistic model based on bigrams.

As far as expressivity is concerned, bags of words have 
also strict limitations.  These structures lack
a primitive for expressing choices among
words.  As already observed in the introduction, this is 
a serious problem in natural language generation, where alternatives
in lexical realization must be encoded in the presence of
lack of detailed knowledge of the target language.
In addition, bags of words usually do not come with precedence 
constraints.  However, in natural language applications these constraints
are very common, and are usually derived from 
knowledge about the target language or, in the case of machine
translation, from the parsing tree of the source string.
In order to represent these constraints, extra machinery must 
be introduced.  For instance,~\citeA{BR90a} impose, 
for each word in the bag, a probabilistic
distribution delimiting its position in the target string, 
on the basis of the original position of the source word 
in the input string to be translated.  In the shake and bake approach, 
bags are defined over functional structures, each 
representing complex lexical information from which constraints
can be derived.  Then the parsing algorithm for bags is 
interleaved with a constraint propagation algorithm to filter out 
parses \cite<e.g., as done by>{BR92}.
As a general remark, 
having different layers of representation requires 
the development of more involved parsing algorithms, 
which we try to avoid in the new proposal
to be described below.

An alternative representation of finite languages is the class of
acyclic deterministic finite automata, also called word lattices.
This representation has often been used in hybrid approaches
to surface generation~\cite{KN95,LA98,BA00},
and more generally in natural language applications where 
some form of uncertainty comes with the input, 
as for instance in speech recognition~\cite[Section 7.4]{JU00}.
Word lattices inherit from standard regular expressions
the primitives expressing concatenation and disjunction, and thereby
allow the encoding of precedence constraints
and word disjunction in a direct way. 
Furthermore, word lattices can be efficiently parsed by means of CFGs,
using standard techniques for lattice parsing~\cite{AU95}.  
Lattice parsing requires cubic time
in the number of states of the input finite automaton and linear time in the size
of the CFG.  Methods for lattice parsing can all be traced back
to~\citeA{BA64}, who prove that the class of context-free languages is
closed under intersection with regular languages. 

One limitation of word lattices and finite automata in general is the
lack of an operator for free word order.
As we have already
discussed in the introduction, this is a severe limitation for hybrid
systems, where free word order in sentence realization is needed in case
the symbolic grammar used in the first phase fails to provide ordering
constraints.  
To represent strings
where a bag of words can occur in every possible order, one has
to encode each string through an individual path within the lattice.
In the general case, this requires an amount of space that is more
than exponential in the size of the bag.  From this perspective, 
the previously mentioned polynomial time result for parsing 
is to no avail, since the input structure to the parser might already be 
of size more than exponential in the size of the 
input conceptual structure. 
The problem of free word order in lattice structures 
is partially solved by~\citeA{LA98} 
by introducing an external recasting mechanism that preprocesses the input 
conceptual structure. 
This has the overall effect that phrases normally represented
by two independent sublattices can now be generated one embedded 
into the other, therefore partially mimicking the interleaving of 
the words in the two phrases.
However, this is not enough to treat free word order in its full generality. 

A third representation of finite languages, 
often found in the literature on compression theory~\cite{NM97},
is the class of non-recursive CFGs. 
A CFG is called {\em non-recursive\/} if no nonterminal 
can be rewritten into a string containing the nonterminal itself.
It is not difficult to see that such grammars can only generate 
finite languages.  Non-recursive CFGs have recently been exploited 
in hybrid systems~\cite{LA00}.%
\footnote{\citeA{LA00} 
uses the term ``forests'' for non-recursive 
CFGs, which is a different name for the same concept~\cite{BI89}.} 
This representation inherits all the 
expressivity of word lattices, and thus can encode 
precedence constraints as well as disjunctions.  In addition, 
non-recursive CFGs can achieve much smaller encodings
of finite languages than word lattices.
This is done by uniquely encoding certain sets
of substrings that occur repeatedly through a 
nonterminal that can be reused in several places. 
This feature turns out to be very useful for natural 
language applications, as shown by experimental results
reported by~\citeA{LA00}.

Although non-recursive CFGs can be more compact representations
than word lattices, 
this representation still lacks a primitive for 
representing free word order.  
In fact, a CFG generating the finite language of all permutations 
of $n$ symbols must have size at least exponential in $n$.%
\footnote{An unpublished proof of 
this fact has been personally communicated to the authors by 
Jeffrey Shallit and Ming-wei Wang.}
In addition, the problem of deciding whether some string 
encoded by a non-recursive CFG can be parsed by a general CFG 
is PSPACE-complete~\cite{NE04}. 

{}From the above discussion, one can draw the following conclusions.  
In considering the range of possible encodings for finite 
languages, we are interested in measuring (i)~the compactness of the
representation, and (ii)~the efficiency 
of parsing the obtained representation by means of a CFG. 
At one extreme we have the naive solution of enumerating
all strings in the language, and then independently parsing each 
individual string using a traditional string parsing algorithm. 
This solution is obviously unfeasible, since no
compression at all is achieved and so the overall amount of time 
required might be exponential in the size of
the input conceptual structure. Although word lattices are a more
compact representation, when free word order
needs to be encoded we may still have representations
of exponential size
as input to the parser, as already discussed. 
At the opposite extreme, we have solutions like bags of words
or non-recursive CFGs, which allow very compact representations,
but are still very demanding in parsing time requirements.  
Intuitively, this can be explained by considering that 
parsing a highly compressed finite language requires 
additional bookkeeping with respect to the string case. 
What we then need to explore is some trade-off between these solutions, 
offering interesting compression factors at the expense of
parsing time requirements that are provably polynomial in the 
cases of interest.  As we will show in the sequel of this paper, 
IDL-expressions have these required properties and are 
therefore an interesting solution to the problem. 



\section{Notation}
\label{s:notation}

In this section we briefly recall some basic notions from
formal language theory. For more details we refer the reader
to standard textbooks~\cite<e.g.,>{HA78}.

For a set $\Delta$, $\size{\Delta}$ denotes the number of elements in
$\Delta$; for a string $x$ over some alphabet, 
$\size{x}$ denotes the length of $x$.  
For string $x$ and languages (sets of strings) $L$ and $L'$,
we let $x \cdot L = \{ xy \sep y \in L\}$ and  
$L \cdot L' = \{ xy \sep x \in L, \, y \in L' \}$.  
We remind the reader that a string-valued 
function $f$ over some alphabet $\myterm$
can be extended to a homomorphism over $\myterm^\ast$ by letting 
$f(\ep) = \ep$ and $f(ax) = f(a)f(x)$ for $a \in \myterm$ and 
$x \in \myterm^\ast$.  We also let $f(L) = \{ f(x) \sep  x \in L\}$.

We denote a {\em context-free grammar\/} (CFG) by a 4-tuple 
$G = (\nonterm, \myterm, P, S)$,
where $\nonterm$ is a finite set of nonterminals,
$\myterm$ is a finite set of terminals, with
$\myterm \cap \nonterm = \emptyset$, 
$S \in \nonterm$ is a special symbol called the start symbol, 
and $P$ is a finite set of productions having the form 
$A \de \gamma$, with $A \in \nonterm$ 
and $\gamma \in (\myterm \cup \nonterm)^*$.
Throughout the paper we assume the following conventions: 
$A, B, C$ denote nonterminals, $a, b, c$ denote terminals, 
$\alpha, \beta,\gamma, \delta$ denote strings in 
$(\myterm \cup \nonterm)^*$ and $x, y, z$ denote strings in $\myterm^*$.

The derives relation is denoted $\derg{G}$ and its
transitive closure $\derpg{G}$.
The language generated by grammar
$G$ is denoted $L(G)$.  The size of $G$ is defined as 
\begin{eqnarray}
\size{G} & = & \sum_{(A \de \alpha) \in P} \, \size{A\alpha}.
\end{eqnarray}




\section{IDL-Expressions}
\label{s:idl-expr}

In this section we introduce the class of IDL-expressions
and define a mapping from such expressions to sets of strings. 
Similarly to regular expressions, IDL-expressions generate
sets of strings, i.e., languages.  
However, these languages are always finite.  
Therefore the 
class of languages generated by IDL-expressions is a proper
subset of the class of regular languages. 
As already discussed in the introduction,
IDL-expressions combine language operators that were only considered 
in isolation in previous representations of finite languages 
exploited in surface natural language generation. 
In addition, some of these operations have been 
recently used in the discontinuous parsing literature, 
for the syntactic description of (infinite) languages with 
weak linear precedence constraints.
IDL-expressions represent 
choices among words or phrases and their relative ordering
by means of the standard concatenation 
operator `$\cdot$' from regular expressions, along with 
three additional operators to be discussed in what follows. 
All these operators take as arguments one or more 
IDL-expressions, and combine the strings 
generated by these arguments in different ways.
\begin{itemize}

\item
Operator `$\mymix$', called {\bf interleave}, 
interleaves strings resulting from its argument expressions. 
A string $z$ results from the interleaving of 
two strings $x$ and $y$ whenever $z$ is composed of all and only 
the occurrences of symbols in $x$ and $y$, 
and these symbols appear within $z$ in the same relative 
order as within $x$ and $y$.
As an example, consider strings {\tt abcd} and {\tt efg}.
By interleaving these two strings we obtain, 
among many others, the strings {\tt abecfgd}, 
{\tt eabfgcd} and {\tt efabcdg}. 
In the formal language literature, this operation has also 
been called `shuffle', as for instance by~\citeA{DA89}. 
In the discontinuous parsing literature
and in the literature on head-driven phrase-structure grammars 
(HPSG,~\citeR{PO94}) the interleave operation is also called 
`sequence union'~\cite{RE89} or `domain union'~\cite{RE94}.  
The interleave operator also occurs 
in an XML tool described by~\citeA{VL03}.

\item
Operator `$\mychoose$', called {\bf disjunction}, 
allows a choice between strings resulting 
from its argument expressions. 
This is a standard operator from regular expressions, 
where it is more commonly written as `$+$'. 

\item
Operator `$\mylock$', called {\bf lock}, takes a single 
IDL-expression as argument.  This operator
states that no additional material can be interleaved
with a string resulting from its argument.
The lock operator has been previously used in the 
discontinuous parsing literature, as for instance 
by~\citeA{DA02,GO97a,RA99a,SU99}.  
In that context, the operator was called `isolation'. 
\end{itemize}
The interleave, disjunction and lock operators will 
also be called I, D and L operators, respectively. 
As we will see later, the combination of the I and L operators
within IDL-expressions provides much of the power of 
existing formalisms to represent free word order, 
while maintaining computational 
properties quite close to those of regular expressions
or finite automata.

As an introductory example, we discuss the following 
IDL-expression, defined over the word alphabet 
\{{\tt piano}, {\tt play}, {\tt must}, {\tt necessarily}, 
{\tt we}\}.

\begin{eqnarray}
\label{e:example}
\mymix(
  \mychoose( {\tt necessarily},\, {\tt must} ), \;
  {\tt we}\, \cdot \, {\mylock\!({\tt play} \, \cdot \, {\tt piano})}
).
\end{eqnarray}
IDL-expression~(\ref{e:example}) says that words {\tt we}, 
{\tt play} and {\tt piano}
must appear in that order in any of the generated strings, as specified by
the two occurrences of the concatenation operator.  
Furthermore, the use of the lock operator states that no 
additional words can ever appear in between {\tt play} and {\tt piano}.  
The disjunction operator expresses the choice between words 
{\tt necessarily} and {\tt must}.  Finally, the interleave 
operator states that the word resulting from the 
first of its arguments must be inserted into the sequence
{\tt we}, {\tt play}, {\tt piano}, in any of the available
positions.  Notice the interaction with the lock operator, which, 
as we have seen, makes unavailable 
the position in between {\tt play} and {\tt piano}.
Thus the following sentences, among others, can be generated by 
IDL-expression~(\ref{e:example}):
\begin{quote}
{\tt
necessarily we play piano \\
must we play piano \\
we must play piano \\
we play piano necessarily}.
\end{quote}
However, the following sentences cannot be generated by 
IDL-expression~(\ref{e:example}):
\begin{quote}
{\tt
we play necessarily piano \\
necessarily must we play piano}.
\end{quote}
The first sentence is disallowed through the use of the lock operator, 
and the second sentence is impossible because 
the disjunction operator states that exactly one of the arguments 
must appear in the sentence realization.
We now provide a formal definition of the class of IDL-expressions. 

\begin{definition}
Let $\myterm$ be some finite alphabet and let $\symbolep$
be a symbol not in $\myterm$.
An {\/\bf IDL-expression} over $\myterm$ is a string $\pi$
satisfying one of the following conditions:
\begin{enumerate}
\item
$\pi = a$, with $a \in \myterm \cup \{ \symbolep \}$;
\item 
$\pi = \mylock(\pi')$, with $\pi'$ an IDL-expression;
\item
$\pi = \mychoose(\pi_1, \pi_2, \ldots, \pi_n)$,
with $n \geq 2$ and $\pi_i$ an IDL-expression for 
each $i$, $1 \leq i \leq n$;
\item
$\pi = \mymix(\pi_1, \pi_2, \ldots,$ $\pi_n)$, 
with $n \geq 2$ and $\pi_i$ an IDL-expression for 
each $i$, $1 \leq i \leq n$;
\item 
$\pi = \pi_1 \cdot \pi_2$, with $\pi_1$ and $\pi_2$ 
both IDL-expressions. 
\end{enumerate}
\end{definition}
We take the infix operator `$\cdot$' to be right associative, 
although in all of the definitions in this paper, disambiguation 
of associativity is not relevant and can be taken arbitrarily.
We say that IDL-expression $\pi'$ is a subexpression of 
$\pi$ if $\pi'$ appears as an argument of some operator in $\pi$.

We now develop a precise semantics for IDL-expressions.  
The only technical difficulty in doing so arises with the proper
treatment of the lock operator.%
\footnote{If we were to add the Kleene star, then 
infinite languages can be specified, and interleave and lock
can be more conveniently defined using derivatives~\cite{BR64}, 
as noted before by~\citeA{VL03}.}
Let $x$ be a string over $\myterm$.
The basic idea below is to use a new symbol~$\lstsep$, 
not already in $\myterm$. 
An occurrence of $\lstsep$ between two terminals indicates
that an additional string can be inserted at that position.
As an example, if $x = x' \lstsep x'' x'''$ with $x'$, $x''$
and $x'''$ strings over $\myterm$, and if we need
to interleave $x$ with a string $y$, then we may get as a result
string $x' y x'' x'''$ but not string $x' \lstsep x'' y x'''$. 
The lock operator corresponds to the 
removal of every occurrence of $\lstsep$ from a string. 

More precisely, strings in $(\myterm \cup \{\lstsep\})^*$ will be used to
represent sequences of strings over $\myterm$; symbol
$\lstsep$ is used to separate the strings in the sequence.
Furthermore, we introduce a string homomorphism $\mylockh$ 
over $(\myterm \cup \{\lstsep\})^\ast$ by letting
$\mylockh(a)=a$ for $a\in \myterm$ and
$\mylockh(\lstsep)=\epsilon$. 
An application of $\mylockh$ to an input sequence 
can be seen as the operation 
of concatenating together all of the strings in the sequence.

We can now define the basic operation $\mycomb$, which plays an 
important role in the sequel.
This operation composes two sequences $x$ and $y$ of strings,
represented as explained above, 
into a set of new sequences of strings.  This is done by interleaving 
the two input sequences in every possible way. 
Operation $\mycomb$ makes use of an auxiliary operation
$\mycomb'$, which also constructs interleaved sequences out of 
input sequences $x$ and $y$, 
but always starting with the first string in its first argument $x$.
As any sequence in $\mycomb(x,y)$ must start with a string from
$x$ or with a string from $y$,
$\mycomb(x,y)$ is the union of $\mycomb'(x,y)$ and $\mycomb'(y,x)$.
In the definition of $\mycomb'$, we distinguish the case
in which $x$ consists of a single string and the case in which 
$x$ consists of at least two strings. 
In the latter case, the tail of an output sequence can be obtained
by applying $\mycomb$ recursively on the tail of sequence $x$ 
and the complete sequence $y$.
For $x, y \in (\myterm \cup \{\lstsep\})^*$,
we have:
\begin{eqnarray*}
\mycomb(x,y) & = & \mycomb'(x,y) \cup \mycomb'(y,x) \\
\mycomb'(x,y) & = & 
\left\{ 
  \begin{array}{l}
  \{x \lstsep y \}, \;\; \mbox{if } x \in \myterm^*;  \\
  \{x' \lstsep \} \cdot \mycomb(x'',y), \\ 
    \;\; \mbox{if there are } x'\in \myterm^* \mbox{ and } x'' \\
    \;\; \mbox{such that } x=x'\lstsep x''.
  \end{array} \right.
\end{eqnarray*}
As an example, let $\myterm = \{{\tt a}, {\tt b}, {\tt c}, {\tt d}, {\tt e}\}$ and 
consider the two sequences ${\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt c}$
and ${\tt d}\lstsep {\tt e}$. Then we have
\begin{eqnarray*}
\lefteqn{\mycomb({\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt c}, {\tt d}\lstsep {\tt e}) = } \\
&& \{ {\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt c}\lstsep {\tt d}\lstsep {\tt e}, 
{\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt d}\lstsep {\tt c}\lstsep {\tt e}, 
{\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt d}\lstsep {\tt e}\lstsep {\tt c}, \\
&& {\tt a}\lstsep {\tt d}\lstsep {\tt b}{\tt b}\lstsep {\tt c}\lstsep {\tt e}, 
{\tt a}\lstsep {\tt d}\lstsep {\tt b}{\tt b}\lstsep {\tt e}\lstsep {\tt c}, 
{\tt a}\lstsep {\tt d}\lstsep {\tt e}\lstsep {\tt b}{\tt b}\lstsep {\tt c}, \\
&& {\tt d}\lstsep {\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt c}\lstsep {\tt e},
{\tt d}\lstsep {\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt e}\lstsep {\tt c},
{\tt d}\lstsep {\tt a}\lstsep {\tt e}\lstsep {\tt b}{\tt b}\lstsep {\tt c}, \\
&& {\tt d}\lstsep {\tt e}\lstsep {\tt a}\lstsep {\tt b}{\tt b}\lstsep {\tt c} \}.
\end{eqnarray*}
For languages $L_1, L_2$ we define 
$\mycomb(L_1, L_2) = \cup_{x \in L_1, y \in L_2} \, \mycomb(x, y)$.
More generally, for languages 
$L_1, L_2, \ldots, L_d$, $d \geq 2$, we define
$\mycomb_{i=1}^d  \, L_i = \mycomb(L_1, L_2)$ for $d = 2$, 
and $\mycomb_{i=1}^d L_i = \mycomb(\mycomb_{i=1}^{d-1} \, L_i, L_d )$ 
for $d > 2$. 

\begin{definition}
\label{d:sem}
Let $\myterm$ be some finite alphabet.
Let $\sigma$ be a function mapping IDL-expressions 
over $\myterm$ into subsets of $(\myterm \cup \{\lstsep\})^\ast$, 
specified by the following conditions: 
\begin{enumerate}
\item
$\sigma(a) = \{a\}$ for $a \in \myterm$,
and $\sigma(\symbolep) = \{\ep\}$; 
\item
$\sigma(\mylock(\pi)) = \mylockh(\sigma(\pi))$;
\item 
$\sigma(\mychoose(\pi_1, \pi_2, \ldots, \pi_n))
   = \cup_{i=1}^n \sigma(\pi_i)$;
\item 
$\sigma(\mymix(\pi_1, \pi_2, \ldots, \pi_n))
  = \mycomb_{i=1}^n \sigma(\pi_i)$;
\item
$\sigma(\pi \cdot \pi') = \sigma(\pi) \lstsep \sigma(\pi')$. 
\end{enumerate}
The set of strings that satisfy an IDL-expression $\pi$, written $L(\pi)$, 
is given by $L(\pi) = \mylockh(\sigma(\pi))$.
\end{definition}

As an example for the above definition, we show how
the interleave operator can be used in an IDL-expression
to denote the set of all strings realizing permutations of 
a given bag of symbols.  
Let $\myterm = \{{\tt a}, {\tt b}, {\tt c} \}$. 
Consider a bag 
$\langle{\tt a}, {\tt a}, {\tt b}, {\tt c}, {\tt c} \rangle$ and IDL-expression 
\begin{eqnarray}
\label{e:perm}
\mymix( {\tt a}, {\tt a}, {\tt b}, {\tt c}, {\tt c} ). 
\end{eqnarray}
By applying Definition~\ref{d:sem} to IDL-expression~(\ref{e:perm}), we 
obtain in the first few steps
\begin{eqnarray*}
\sigma({\tt a}) & = & \{ {\tt a} \}, \\ 
\sigma({\tt b}) & = & \{ {\tt b} \}, \\
\sigma({\tt c}) & = & \{ {\tt c} \}, \\
\sigma(\mymix( {\tt a}, {\tt a})) & = & \mycomb(\{{\tt a}\}, \{{\tt a}\}) 
  \  = \ \{ {\tt a \lstsep a} \}, \\
\sigma(\mymix( {\tt a}, {\tt a}, {\tt b})) & = &
\mycomb(\{{\tt a \lstsep a}\}, \{{\tt b}\}) 
  \ = \ \{ {\tt b \lstsep a \lstsep a}, {\tt a \lstsep b \lstsep a}, 
           {\tt a \lstsep a \lstsep b} \}.
\end{eqnarray*}
In the next step we obtain $3 \times 4$ sequences of length $4$,
each using all the symbols from bag 
$\langle{\tt a}, {\tt a}, {\tt b}, {\tt c} \rangle$. 
One more application of the $\mycomb$ operator, on this set and 
set $\{ {\tt c} \}$, provides all possible sequences of singleton strings
expressing permutations of symbols in bag
$\langle{\tt a}, {\tt a}, {\tt b}, {\tt c}, {\tt c} \rangle$.
After removing symbol $\lstsep$ throughout, 
which conceptually turns sequences of strings into undivided strings,
we obtain the desired language
$L(\mymix( {\tt a}, {\tt a}, {\tt b}, {\tt c}, {\tt c} ))$
of permutations of bag 
$\langle{\tt a}, {\tt a}, {\tt b}, {\tt c}, {\tt c} \rangle$.

To conclude this section, we compare 
the expressivity of IDL-expressions with that of 
the formalisms discussed in Section~\ref{s:bag}. We do 
this by means of a simple example.
In what follows, we use the alphabet \{{\tt NP}, {\tt PP}, 
{\tt V}\}.  These symbols denote units standardly used in  
syntactic analysis of natural language, and stand for, respectively, 
noun phrase, prepositional phrase and verb.  Symbols
{\tt NP}, {\tt PP} and {\tt V} should be rewritten into 
actual words of the language, but we use these as 
terminal symbols to simplify the presentation. 
Consider a language having the subject-verb-object (SVO) order 
and a sentence having the structure
\begin{center}
{\tt [$_{\tt S}$ NP$_{\tt 1}$ V NP$_{\tt 2}$]}, 
\end{center}
where {\tt NP$_{\tt 1}$} realizes the subject position and 
{\tt NP$_{\tt 2}$} realizes the object position. 
Let {\tt PP$_{\tt 1}$} and {\tt PP$_{\tt 2}$} be 
phrases that must be inserted in the above sentence as modifiers. 
Assume that we know that the language at hand does not
allow modifiers to appear in between the verbal and 
the object positions. 
Then we are left with $3$ available positions for the realization 
of a first modifier, out of the $4$ positions in our string. 
After the first modifier is inserted within the string, we have 
$5$ positions, but only $4$ are available 
for the realization of a second modifier, because of our assumption. 
This results in a total of $3 \times 4 = 12$ possible sentence realizations. 

A bag of words for these sentences is unable
to capture the above constraint on the positioning of modifiers.
At the same time, a word lattice 
for these sentences would contain $12$ distinct paths, 
corresponding to the different realizations of the modifiers
in the basic sentence. 
Using the IDL formalism, we can easily capture the desired 
realizations by means of the IDL-expression:
\begin{eqnarray*}
\mymix( {\tt PP}_{\tt 1},\, {\tt PP}_{\tt 2},\, 
        {\tt NP}_{\tt1}\, \cdot \, 
            \mylock\!({\tt V}\, \cdot \, {\tt NP}_{\tt 2}) ).
\end{eqnarray*}
Again, note the presence of the lock operator, which
implements our restriction against modifiers
appearing in between the verbal and the object position, 
similarly to what we have done in IDL-expression~(\ref{e:example}). 

Consider now a sentence with a subordinate clause, having the structure
\begin{center}
{\tt
[$_{\tt S}$ NP$_{\tt 1}$ V$_{\tt 1}$ NP$_{\tt 2}$
[$_{\tt S'}$ NP$_{\tt 3}$ V$_{\tt 2}$ NP$_{\tt 4}$]]},
\end{center}
and assume that modifiers {\tt PP}$_{\tt 1}$ and {\tt PP}$_{\tt 2}$ 
apply to the main clause, while 
modifiers {\tt PP}$_{\tt 3}$ and {\tt PP}$_{\tt 4}$
apply to the subordinate clause.  
As before, we have $3 \times 4$ possible realizations 
for the subordinate sentence. 
If we allow main clause modifiers to appear
in positions before the subordinate clause as well as
after the subordinate clause,
we have $4 \times 5$ possible realizations for the main sentence.
Overall, this gives a total of $3 \times 4^2 \times 5 = 240$ 
possible sentence realizations. 

Again, a bag representation for these sentences is unable
to capture the above restrictions on word order, and would
therefore badly overgenerate.
Since the main sentence modifiers could be placed 
after the subordinate clause, we need to record 
for each of the two modifiers of the main clause whether 
it has already been seen,
while processing the $12$ possible realizations of the
subordinate clause.
This increases
the size of the representation by a factor of $2 \times 2 = 4$.
On the other hand, the desired 
realizations can be easily captured by means of the IDL-expression:
\begin{eqnarray*}
\mymix( {\rm PP}_1,\, {\rm PP}_2,\, 
        {\rm NP}_1\, \cdot \, 
            \mylock\!({\rm V}_1\, \cdot \, {\rm NP}_2)\, \cdot \,
            \mylock\!(\mymix( {\rm PP}_3,\, {\rm PP}_4,\, 
            {\rm NP}_3\, \cdot \, \mylock\!({\rm V}_2\, \cdot \, {\rm NP}_4 
            )) )).
\end{eqnarray*}
Note the use of embedded lock operators (the two rightmost occurrences). 
The rightmost and the leftmost occurrences of the lock 
operator implement our restriction against modifiers 
appearing in between the verbal and the object position. 
The occurrence of the lock operator in the middle of the 
IDL-expression prevents any of the 
modifiers {\tt PP}$_{\tt 1}$ and {\tt PP}$_{\tt 2}$ 
from modifying elements appearing within the subordinate clause. 
Observe that when we generalize the above examples by embedding 
$n$ subordinate clauses, the corresponding word lattice 
will grow exponentially in $n$, while the IDL-expression has
linear size in $n$. 


\section{IDL-Graphs}
\label{s:idl-graph}

Although IDL-expressions may be easily composed by linguists,
they do not allow a direct algorithmic interpretation for
efficient recognition of strings.
We therefore define an equivalent but lower-level 
representation for IDL-expressions, which we call IDL-graphs. 
For this purpose, we exploit a specific kind of edge-labelled 
acyclic graphs with ranked nodes.  We first introduce 
our notation, and then define the encoding function from 
IDL-expressions to IDL-graphs. 

The graphs we use are denoted by tuples
$(V, E, v_s, v_e, \lambda, r)$, where:
\begin{itemize}
\item 
$V$ and $E$ are finite sets of vertices and edges, respectively; 
\item 
$v_s$ and $v_e$ are special vertices in $V$ called
the {\bf start} and the {\bf end} vertices, respectively;
\item 
$\lambda$ is the edge-labelling function, mapping
$E$ into the alphabet $\myterm \cup \{ \ep, \hbox{$\vdash,$} \dashv \}$; 
\item
$r$ is the vertex-ranking function, mapping $V$ to
$\nat$, the set of non-negative integer numbers.
\end{itemize}
Label $\ep$ indicates that an edge does
not consume any input symbols.  
Edge labels $\vdash$ and $\dashv$
have the same meaning, but they additionally encode 
that we are at the start or end, respectively, of 
what corresponds to an I operator. 
More precisely, let $\pi$ be an IDL-expression headed by an occurrence
of the I operator and let $\gamma(\pi)$ be the associated IDL-graph. 
We use edges labelled by
$\vdash$ to connect the start vertex of $\gamma(\pi)$ with the start
vertices of all the subgraphs encoding the arguments of I.  Similarly, we
use edges labelled by $\dashv$ to connect all the end vertices of the
subgraphs encoding the arguments of I with the end vertex of
$\gamma(\pi)$.
Edge labels $\vdash$ and $\dashv$ are needed 
in the next section to distinguish occurrences of the I 
operator from occurrences of the D and L operators. 
Finally, the function $r$ ranks each vertex according to 
how deeply it is embedded into (the encoding of)
expressions headed by an occurrence of the L operator. 
As we will see later, this information is 
necessary for processing ``locked'' vertices with the 
correct priority. 

We can now map an IDL-expression into the corresponding IDL-graph. 
\begin{definition}
\label{d:graph}
Let $\myterm$ be some finite alphabet, and let $j$ 
be a non-negative integer number.  
Each IDL-expression $\pi$ over $\myterm$
is associated with some graph 
$\gamma_j(\pi) = (V, E, v_s, v_e, \lambda, r)$
specified as follows:
\begin{enumerate}

\item
if $\pi = a$, $a \in \myterm \cup \{\symbolep\}$, 
let $v_s, v_e$ be new nodes; 
we have  
  \begin{enumerate}
  \item
  $V = \{v_s, v_e\}$, 
  \item
  $E = \{(v_s, v_e)\}$,
  \item 
  $\lambda((v_s, v_e)) = a$ for $a \in \myterm$ and
  $\lambda((v_s, v_e)) = \ep$ for $a = \symbolep$,
  \item 
  $r(v_s)=r(v_e)=j$;
  \end{enumerate}

\item
if $\pi = \mylock(\pi')$ with 
$\gamma_{j+1}(\pi') = 
(V', E', v'_{s}, v'_{e}, \lambda', r')$, 
let $v_s, v_e$ be new nodes; 
we have  
  \begin{enumerate}
  \item
  $V = V' \cup \{v_s, v_e\}$, 
  \item 
  $E = E' \cup \{(v_{s}, v'_{s}), (v'_{e}, v_{e})\}$, 
  \item 
  $\lambda(e) = \lambda'(e)$ for $e \in E'$, 
  $\lambda((v_{s}, v'_{s})) = \lambda((v'_{e}, v_{e})) = \ep$,
  \item 
  $r(v)=r'(v)$ for $v \in V'$, $r(v_s)=r(v_e)=j$;
  \end{enumerate}

\item
if $\pi = \mychoose(\pi_1, \pi_2, \ldots, \pi_n)$ with 
$\gamma_j(\pi_i) = 
(V_i, E_i, v_{i,s}, v_{i,e}, \lambda_i, r_i)$,
$1 \leq i \leq n$, 
let $v_s, v_e$ be new nodes; 
we have  
  \begin{enumerate}
  \item
  $V = \cup_{i=1}^n V_i \cup \{v_s, v_e\}$, 
  \item
  $E = \cup_{i=1}^n E_i \cup \{(v_s, v_{i,s}) \sep 1 \leq i \leq n \}
  \cup \{(v_{i,e}, v_e) \sep 1 \leq i \leq n \}$, 
  \item 
  $\lambda(e) = \lambda_i(e)$ for $e \in E_i$, 
  $\lambda((v_s, v_{i,s})) = \lambda((v_{i,e}, v_e)) = \ep$ 
  for $1 \leq i \leq n$,
  \item 
  $r(v)=r_i(v)$ for $v \in V_i$, $r(v_s)=r(v_e)=j$;
  \end{enumerate}

\item
if $\pi = \mymix(\pi_1, \pi_2, \ldots, \pi_n)$ with
$\gamma_j(\pi_i) = 
(V_i, E_i, v_{i,s}, v_{i,e}, \lambda_i,r_i)$,
$1 \leq i \leq n$, 
let $v_s, v_e$ be new nodes; 
we have  
  \begin{enumerate}
  \item
  $V = \cup_{i=1}^n V_i \cup \{v_s, v_e\}$, 
  \item
  $E = \cup_{i=1}^n E_i \cup \{(v_s, v_{i,s}) \sep 1 \leq i \leq n \}
  \cup \{(v_{i,e}, v_e) \sep 1 \leq i \leq n \}$, 
  \item
  $\lambda(e) = \lambda_i(e)$ for $e \in E_i$, 
  $\lambda((v_s, v_{i,s})) = \; \vdash$ and
  $\lambda((v_{i,e}, v_e)) = \; \dashv$ for $1 \leq i \leq n$, 
  \item 
  $r(v)=r_i(v)$ for $v \in V_i$, $r(v_s)=r(v_e)=j$;
  \end{enumerate}

\item
if $\pi = \pi_1 \cdot \pi_2$ with 
$\gamma_j(\pi_i) = 
(V_i, E_i, v_{i,s}, v_{i,e}, \lambda_i,r_i)$, 
$i \in \{1, 2\}$, 
let $v_s = v_{1,s}$ and $v_e = v_{2,e}$; 
we have
  \begin{enumerate}
  \item
  $V = V_1 \cup V_2$, 
  \item 
  $E = E_1 \cup E_2 \cup \{(v_{1,e}, v_{2,s})\}$, 
  \item 
  $\lambda(e) = \lambda_i(e)$ for $e \in E_i$ for $i\in \{1, 2\}$,
  $\lambda((v_{1,e}, v_{2,s})) = \ep$, 
  \item 
  $r(v) = r_i(v)$ for $v \in V_i$, $i \in \{1, 2\}$.
  \end{enumerate}

\end{enumerate}
We let $\gamma(\pi) = \gamma_0(\pi)$.
An {\/\bf IDL-graph} is a graph that has the form 
$\gamma(\pi)$ for some IDL-expression $\pi$ over~$\myterm$.
\end{definition}
Figure~\ref{f:IDL-example} presents the IDL-graph $\gamma(\pi)$,
where $\pi$ is IDL-expression~(\ref{e:example}).

\begin{figure}[tb]
\rule{\textwidth}{0.5pt} 
\begin{center}
% magnification 70%
\includegraphics[scale=.95]{playpiano.eps}
\end{center}
\caption{The IDL-graph associated with the IDL-expression
\mbox{\hspace*{1cm}} 
$\mymix(
  \mychoose( {\tt necessarily},\, {\tt must} ),  
  {\tt we}\, \cdot \, {\mylock\!({\tt play} \, \cdot \, {\tt piano})}
)$.
}\label{f:IDL-example} 
\rule{\textwidth}{0.5pt}
\end{figure}

We now introduce the important notion of cut of an IDL-graph.  This
notion is needed to define the language described by an IDL-graph, 
so that we can talk about equivalence between IDL-expressions and 
IDL-graphs.  At the same time, this notion will play a crucial role 
in the specification of our parsing algorithm for IDL-graphs in the 
next section. 
Let us fix some IDL-expression $\pi$ and let 
$\gamma(\pi) = (V, E, v_s, v_e, \lambda, r)$ be the associated IDL-graph. 
Intuitively speaking, a cut through $\gamma(\pi)$
is a set of vertices that we might reach simultaneously when traversing 
$\gamma(\pi)$ from the start vertex to the end vertex, 
following the different branches as prescribed by 
the encoded I, D and L operators, 
and in an attempt to produce a string of $L(\pi)$.

In what follows we view $V$ as a finite alphabet, 
and we define the set $\vcut$ to contain those strings over $V$
in which each symbol occurs at most once.
Therefore $\vcut$ is a finite set and 
for each string $c \in \vcut$ we have $\size{c} \leq \size{V}$. 
If we assume that the outgoing edges of each vertex in an IDL-graph 
are linearly ordered, we can represent
cuts in a canonical way by means of strings in $\vcut$
as defined below. 

Let $r$ be the ranking function associated with $\gamma(\pi)$.
We write $c[v_1\cdots v_m]$ to denote a string $c \in \vcut$
satisfying the following conditions:
\begin{itemize}
\item
$c$ has the form  $x v_1\cdots v_m y$ with $x, y \in \vcut$ and 
$v_i \in V$ for $1 \leq i \leq m$; {\em and}
\item
for each vertex $v$ within $c$ and for each $i$, $1 \leq i \leq m$,
we have $r(v) \leq r(v_i)$. 
\end{itemize} 
In words, $c[v_1\cdots v_m]$ indicates that vertices $v_1,\ldots, v_m$ 
occur adjacent in $c$ and have the maximal rank among all vertices 
within string $c$.
Let $c[v_1\cdots v_m] = x v_1\cdots v_m y$ be a string 
defined as above and let $v'_1\cdots v'_{m'} \in \vcut$
be a second string such that no symbol $v'_i$, $1 \leq i \leq m'$, 
appears in $x$ or $y$.
We write $c[v_1\cdots v_m := v'_1\cdots v'_{m'}]$ to denote
the string $x v'_1 \cdots v'_{m'} y \in \vcut$.

The reason we distinguish the vertices with maximal rank from those
with lower rank is that the former correspond with subexpressions that
are nested deeper within subexpressions headed by the L operator.
As a substring originating within the scope of an occurrence
of the lock operator cannot be interleaved with symbols originating
outside that scope, we should terminate the processing of all vertices
with higher rank before resuming processing of those with lower rank.

We now define a relation that plays a crucial role
in the definition of the notion of cut, as well as in
the specification of our parsing algorithm.

\begin{definition}
\label{d:delta}
Let $\myterm$ be some finite alphabet,
let $\pi$ be an IDL-expression over $\myterm$, and let
$\gamma(\pi)=(V, E, v_{s}, v_{e}, \lambda, r)$
be its associated IDL-graph.
The relation 
$\Delta_{\gamma(\pi)} \subseteq \vcut \times (\myterm \cup \{ \ep \}) \times \vcut$
is the smallest satisfying all of the following conditions:
\begin{enumerate}

\item 
for each $c[v] \in \vcut$ and $(v,v') \in E$ with 
$\lambda((v,v')) =  X \in \myterm \cup \{\ep\}$, we have 
\begin{eqnarray}
(c[v],X,c[v := v']) & \in & \Delta_{\gamma(\pi)};
\label{e:trans1}
\end{eqnarray}

\item 
for each $c[v] \in \vcut$ with the outgoing edges of $v$ being exactly
$(v,v_1),\ldots, (v,v_n) \in E$, in this order, and with
$\lambda((v,v_i)) =\ \vdash$, $1 \leq i \leq n$, we have
\begin{eqnarray}
(c[v],\ep,c[v := v_1\cdots v_n]) & \in & \Delta_{\gamma(\pi)};
\label{e:trans2}
\end{eqnarray}

\item 
for each $c[v_1\cdots v_n] \in \vcut$ with the incoming edges 
of some $v \in V$ being exactly $(v_1,v),\ldots, (v_n,v)\in E$, 
in this order, and with 
$\lambda((v_i,v))=\ \dashv$, $1 \leq i \leq n$, we have
\begin{eqnarray}
(c[v_1\cdots v_n],\ep,c[v_1\cdots v_n := v]) & \in & \Delta_{\gamma(\pi)}.
\label{e:trans3}
\end{eqnarray}

\end{enumerate}
\end{definition}
Henceforth, we will abuse notation by writing $\Delta_{\pi}$ 
in place of $\Delta_{\gamma(\pi)}$.
Intuitively speaking, relation $\Delta_\pi$ will be used to 
simulate a one-step move over IDL-graph $\gamma(\pi)$.
Condition~(\ref{e:trans1}) refers to moves that 
follow a single edge in the graph, 
labelled by a symbol from the alphabet or by the empty string.
This move is exploited, e.g., upon visiting a vertex
at the start of a subgraph that encodes an IDL-expression
headed by an occurrence of the D operator.  In this case, each 
outgoing edge represents a possible next move,
but at most one edge can be chosen. 
Condition~(\ref{e:trans2}) refers to moves that simultaneously 
follow all edges emanating from the vertex at hand.  
This is used when
processing a vertex at the start of a subgraph that encodes an 
IDL-expression headed by an occurrence of the I operator.  In fact, 
in accordance with the given semantics,
all possible argument expressions must be evaluated in parallel
by a single computation.
Finally, Condition~(\ref{e:trans3}) refers to a move that 
can be read as the complement of the previous type of move.

Examples of elements in $\Delta_{\pi}$ in the case of 
Figure~\ref{f:IDL-example} are
$(v_s, \ep, v_0v_6)$ following Condition~(\ref{e:trans2}) and
$(v_5v_{13}, \ep, v_e)$ following Condition~(\ref{e:trans3}),
which start and end the evaluation of the occurrence of the I operator.
Other elements are
$(v_0v_6, \ep, v_1v_6)$, $(v_1v_9, {\tt play}, v_1v_{10})$
and $(v_1v_{13}, {\tt necessarily}, v_2v_{13})$
following Condition~(\ref{e:trans1}).
Note that, e.g., $(v_1v_{10}, {\tt necessarily}, v_2v_{10})$
is {\em not\/} an element of $\Delta_{\pi}$,
as $v_9$ has higher rank than $v_1$.

We are now ready to define the notion of cut. 

\begin{definition}
\label{d:cut}
Let $\myterm$ be some finite alphabet,
let $\pi$ be an IDL-expression over $\myterm$, and let
$\gamma(\pi)=(V, E, v_{s}, v_{e}, \lambda, r)$
be its associated IDL-graph.
The set of all {\bf cuts} of $\gamma(\pi)$, written $\mycut(\gamma(\pi))$, 
is the smallest subset of $\vcut$ satisfying the following conditions:
\begin{enumerate}
\item
string $v_s$ belongs to $\mycut(\gamma(\pi))$;
\item
for each $c \in \mycut(\gamma(\pi))$ and $(c, X, c') \in \Delta_\pi$, 
string $c'$ belongs to  $\mycut(\gamma(\pi))$.
\end{enumerate}
\end{definition}
Henceforth, we will abuse notation by writing $\mycut(\pi)$ for
$\mycut(\gamma(\pi))$. As already remarked, we can interpret a cut 
$v_1 v_2 \cdots v_k \in \mycut(\pi)$, $v_i \in V$ for $1 \leq i \leq k$, 
as follows. 
In the attempt to generate a string in $L(\pi)$, 
we traverse several paths of the IDL-graph
$\gamma(\pi)$.  This corresponds to the ``parallel'' 
evaluation of some of the subexpressions of $\pi$, and 
each $v_i$ in $v_1 v_2 \cdots v_k$ refers to one
such subexpression.  Thus, $k$ provides the number of 
evaluations that we are carrying out in parallel at the
point of the computation represented by the cut.
Note however that, when drawing a straight line across 
a planar representation of an IDL-graph, separating the start vertex 
from the end vertex, the set of vertices that we can 
identify is not necessarily a cut.\footnote{%
The pictorial representation mentioned above
comes close to a different definition of 
cut that is standard in the literature on 
graph theory and operating research.  
The reader should be aware that this standard graph-theoretic
notion of ``cut'' is different from the one introduced in this paper.}
In fact, as we have already explained when discussing
relation $\Delta_\pi$, only one path is followed
at the start of a subgraph that encodes an IDL-expression 
headed by an occurrence of the D operator.  
Furthermore, 
even if several arcs are to be followed 
at the start of a 
subgraph that encodes an IDL-expression
headed by an occurrence of the I operator, 
some combinations of vertices will not satisfy the definition of cut
when there are L operators within those argument expressions. 
These observations will be more precisely addressed in Section~\ref{s:compl}, 
where we will provide a mathematical analysis of 
the complexity of our algorithm.

Examples of cuts in the case of 
Figure~\ref{f:IDL-example} are
$v_s$, $v_e$, $v_0v_6$, $v_1v_6$, $v_3v_6$, $v_0v_7$, etc.
Strings such as $v_1v_3$ are {\em not\/} cuts, as $v_1$ and $v_3$ belong
to two disjoint subgraphs with sets of vertices $\{v_1,v_2\}$
and $\{v_3,v_4\}$, respectively, each of which corresponds to a different
argument of an occurrence of the disjunction operator.

Given the notion of cut, we can associate a finite language 
with each IDL-graph and talk about equivalence with IDL-expressions. 
Let $\pi$ be an IDL-expression over $\myterm$, and let
$\gamma(\pi) = (V, E, v_{s}, v_{e}, \lambda, r)$ be the 
associated IDL-graph. Let also $c, c' \in \mycut(\pi)$ and 
$w \in \myterm^\ast$.  We write $w \in L(c, c')$ if there 
exists $q \geq \size{w}$, $X_i \in \myterm \cup \{\ep\}$, 
$1 \leq i \leq q$, and $c_i \in \mycut(\pi)$, $0 \leq i \leq q$,
such that $X_1 \cdots X_q = w$, $c_0 = c$, $c_q = c'$ and 
$(c_{i-1}, X_i, c_i) \in \Delta_\pi$ for $1 \leq i \leq q$.   
We also assume that $L(c, c) = \{ \ep \}$. 
We can then show that $L(v_s, v_e) = L(\pi)$, i.e., the language 
generated by the IDL-expression $\pi$ is the same as the language 
that we obtain in a traversal of the IDL-graph $\gamma(\pi)$,
as described above, starting from cut $v_s$ and ending
in cut $v_e$. The proof of this property is
rather long and does not add much
to the already provided intuition underlying the definitions in this
section; therefore we will omit it.

We close this section with an informal discussion 
of relation $\Delta_\pi$ and the associated notion of cut. 
Observe that Definition~\ref{d:delta} and 
Definition~\ref{d:cut} implicitly define
a nondeterministic finite automaton.
Again, we refer the reader to~\citeA{HA78} for a 
definition of finite automata.
The states of the automaton are the cuts in $\mycut(\pi)$
and its transitions are given by the elements of $\Delta_\pi$.
The initial state of the automaton is the cut $v_s$,
and the final state is the cut $v_e$.
It is not difficult to see that from every state of the automaton
one can always reach the final state.  
Furthermore, the language recognized by such an automaton is precisely the 
language $L(v_s, v_e)$ defined above. 
However, we remark here that such an automaton will never be
constructed by our parsing algorithm, as emphasized in the next
section.




\section{CFG Parsing of IDL-Graphs}
\label{s:parser}

We start this section with a brief overview
of the Earley algorithm~\cite{EA70}, a well-known tabular method
for parsing input strings according to a given CFG.  We then 
reformulate the Earley algorithm in order to parse IDL-graphs.
As already mentioned in the introduction, while parsing is
traditionally defined for input consisting of a single string, we
here conceive parsing as a process that can be carried out on an input
device representing a language, i.e., a set of strings.  

Let $G = (\nonterm, \myterm, P, S)$ be a CFG, and let 
$w = a_1 \cdots a_n \in \myterm^\ast$
be an input string to be parsed.
Standard implementations of the Earley algorithm~\cite{GR76} 
use so called parsing items to record partial results of the parsing process
on $w$. A parsing item has the form $[A \de \alpha \bul \beta, i, j]$, 
where $A \de \alpha \beta$ is a production of $G$ and 
$i$ and $j$ are indices identifying a substring 
$a_{i+1} \cdots a_j$ of $w$.  Such a parsing item is constructed
by the algorithm if and only if there exist a string 
$\gamma \in (\nonterm \cup \myterm)^\ast$ and two 
derivations in $G$ having the form 
\[
\begin{array}{rll}
S & \dermg{G} & a_1 \cdots a_i A \gamma \\
 & \derg{G} & a_1 \cdots a_i \alpha \beta \gamma; \\
\alpha & \dermg{G} & a_{i+1} \cdots a_j.
\end{array}
\]
The algorithm accepts $w$ if and only if it can construct an 
item of the form $[S \de \alpha \bul,0,n]$, for some
production $S \de \alpha$ of $G$.
Figure~\ref{f:sEarley} provides an abstract specification 
of the algorithm expressed as a deduction system, 
following~\citeA{SH95}.  Inference rules specify 
the types of steps that the algorithm can apply in 
constructing new items.

\begin{figure}[t]
\rule{\columnwidth}{0.5pt} 

% initializer
\begin{eqnarray}
\label{a:sini}
\frac{%
\begin{array}{l}
\mbox{ }
\end{array}
}{
[S \de\ \bul \alpha,0,0]
}
\left\{ \begin{array}{l}
S \de \alpha
\end{array} \right.
\end{eqnarray}

% predictor
\begin{eqnarray}
\label{a:spred}
\frac{%
\begin{array}{l}
[A \de \alpha \bul B \beta,i,j]
\end{array}
}{
[B \de\ \bul\gamma,j,j]
}
\left\{ \begin{array}{l}
B \de \gamma 
\end{array} \right.
\end{eqnarray}

% scanner 
\begin{eqnarray}
\label{a:sscan}
\frac{%
\begin{array}{l}
[A \de \alpha \bul a \beta,i,j]
\end{array}
}{
[A \de \alpha a \bul \beta,i,j+1]
}
\left\{ \begin{array}{l}
a = a_{j+1}
\end{array} \right.
\end{eqnarray}

% completer
\begin{eqnarray}
\label{a:scompl}
\frac{%
\begin{array}{l}
[A \de \alpha \bul B \beta,i,j] \\
{}[B \de \gamma\bul,j,k]
\end{array}
}{
[A \de \alpha B \bul \beta,i,k]
}
\end{eqnarray}

\caption{Abstract specification of the parsing algorithm of Earley
for an input string $a_1 \cdots a_n$. The algorithm accepts $w$ if 
and only if it can construct an item of the form 
$[S \de \alpha \bul,0,n]$, for some production $S \de \alpha$ of $G$.}
\label{f:sEarley}
\rule{\columnwidth}{0.5pt} 
\end{figure}

Rule~(\ref{a:sini}) in Figure~\ref{f:sEarley} serves as
an initialization step, constructing all items that can
start analyses for productions with the start symbol $S$ in the
right-hand side.  Rule~(\ref{a:spred}) is very similar in 
purpose: it constructs all items that can
start analyses for productions with nonterminal $B$ in the
left-hand side, provided that $B$ is the next nonterminal 
in some existing item for which an analysis is to be found.
Rule~(\ref{a:sscan}) matches a terminal $a$ in an item
with an input symbol, and the new item signifies that a larger part
of the right-hand side has been matched to a larger part of the input.
Finally, Rule~(\ref{a:scompl}) combines two partial analyses, the
second of which represents an analysis for symbol $B$, by which 
the analysis represented by the first item can be extended.

We can now move to our algorithm for IDL-graph parsing using a CFG.  
The algorithm makes use of relation $\Delta_\pi$ from
Definition~\ref{d:delta}, but this does not mean that the relation is
fully computed before invoking the algorithm.  We instead compute
elements of $\Delta_\pi$ ``on-the-fly'' when we first visit a cut, and
cache these elements for possible later use.  This has the advantage
that, when parsing an input IDL-graph, our algorithm processes
only those portions of the graph that represent prefixes of strings
that are generated by the CFG at hand.  In practical cases, the input
IDL-graph is never completely unfolded, 
so that the compactness of the
proposed representation is preserved to a large extent. 

An alternative way of viewing our algorithm is this. 
We have already informally discussed in Section~\ref{s:idl-graph}
how relation $\Delta_\pi$ implicitly defines
a nondeterministic finite automaton 
whose states are the elements of $\mycut(\pi)$
and whose transitions are the elements of $\Delta_\pi$. 
We have also mentioned that such an automaton 
precisely recognizes the finite language $L(\pi)$. 
{}From this perspective, our algorithm can be seen as a standard lattice parsing 
algorithm, discussed in Section~\ref{s:bag}.
What must be emphasized here is that we do not precompute 
the above finite automaton prior to parsing.  
Our approach consists in a lazy evaluation of the 
transitions of the automaton, 
on the basis of a demand on the part of the parsing process. 
In contrast with our approach, full expansion of
the finite automaton before parsing has several disadvantages.
Firstly, although a finite automaton generating a finite language 
might be considerably smaller 
than a representation of the language itself consisting of a
list of all its elements, it is 
easy to see that there are cases
in which the finite automaton might have size 
exponentially larger than the corresponding 
IDL-expression (see also the discussion 
in Section~\ref{s:bag}).  
In such cases, full expansion destroys the compactness of IDL-expressions,
which is the main motivation for the use of our formalism in hybrid surface 
generation systems, as discussed in the
introduction.  Furthermore, full expansion of the automaton is also 
computationally unattractive, since it may lead to unfolding of
parts of the input IDL-graph that will never be processed
by the parsing algorithm.

Let $G = (\nonterm, \myterm, P, S)$ be a CFG and let 
$\pi$ be some input IDL-expression. 
The algorithm uses parsing items of the form 
$[A \de \alpha \bul \beta,c_1,c_2]$, with
$A \de \alpha \beta$ a production in $P$ and 
$c_1, c_2 \in \mycut(\pi)$. 
These items have the same meaning as those used 
in the original Earley algorithm, 
but now they refer to strings in the languages 
$L(v_s,c_1)$ and $L(c_1, c_2)$, where
$v_s$ is the start vertex of IDL-graph $\gamma(\pi)$.
(Recall from Section~\ref{s:idl-graph} that $L(c, c')$, 
$c, c' \in \mycut(\pi)$,
is the set of strings whose symbols can be consumed
in any traversal of $\gamma(\pi)$ starting
from cut $c$ and ending in cut $c'$.)
We also use items of the forms $[c_1,c_2]$
and $[a, c_1,c_2]$, $a \in \myterm$, $c_1, c_2 \in  \mycut(\pi)$.
This is done in order to by-pass traversals of $\gamma(\pi)$ 
involving a sequence of zero or more triples of the form
$(c_1, \ep, c_2)\in \Delta_\pi$, followed by a triple 
of the form $(c_1, a, c_2)\in \Delta_\pi$.
Figure~\ref{f:Earley} presents an abstract specification 
of the algorithm, again using a set of inference rules.  
The issues of control flow and implementation 
are deferred to the next section. 

\begin{figure}[tbp]
\rule{\columnwidth}{0.5pt} 

% initializer
\begin{eqnarray}
\label{a:ini}
\frac{%
\begin{array}{l}
\mbox{ }
\end{array}
}{
[S \de\ \bul \alpha, v_s, v_s]
}
\left\{ \begin{array}{l}
S \de \alpha
\end{array} \right.
\end{eqnarray}

% predictor
\begin{eqnarray}
\label{a:pred}
\frac{%
\begin{array}{l}
[A \de \alpha \bul B \beta,c_1,c_2]
\end{array}
}{
[B \de\ \bul\gamma,c_2,c_2]
}
\left\{ \begin{array}{l}
B \de \gamma 
\end{array} \right.
\end{eqnarray}

% scanner start
\begin{eqnarray}
\label{a:scan-st}
\frac{%
\begin{array}{l}
[A \de \alpha \bul a \beta,c_1,c_2]
\end{array}
}{
[c_2,c_2]
}
\end{eqnarray}

% scanner end
\begin{eqnarray}
\label{a:scan-end}
\frac{%
\begin{array}{l}
[A \de \alpha \bul a \beta,c_1,c_2] \\
{}[a, c_2, c_3]
\end{array}
}{
[A \de \alpha a \bul \beta,c_1,c_3]
}
\end{eqnarray}

% completer
\begin{eqnarray}
\label{a:compl}
\frac{%
\begin{array}{l}
[A \de \alpha \bul B \beta,c_1,c_2] \\
{}[B \de \gamma\bul,c_2,c_3]
\end{array}
}{
[A \de \alpha B \bul \beta,c_1,c_3]
}
\end{eqnarray}

% epsilon move
\begin{eqnarray}
\label{a:ep}
\frac{%
\begin{array}{l}
[c_1,c_2] 
\end{array}
}{
[c_1,c_3]
}
\left\{ \begin{array}{l}
(c_2,\epsilon,c_3) \in \Delta_\pi
\end{array} \right.
\end{eqnarray}

% terminal move
\begin{eqnarray}
\label{a:term}
\frac{%
\begin{array}{l}
[c_1,c_2]
\end{array}
}{
[a, c_1,c_3]
}
\left\{ \begin{array}{l}
(c_2,a,c_3) \in \Delta_\pi, \\
a \in \myterm
\end{array} \right.
\end{eqnarray}

% epsilon end
\begin{eqnarray}
\label{a:ep-S}
\frac{%
\begin{array}{l}
[S \de \alpha\bul,c_0,c_1] 
\end{array}
}{
[S \de \alpha\bul,c_0,c_2]
}
\left\{ \begin{array}{l}
(c_1,\epsilon,c_2) \in \Delta_\pi
\end{array} \right.
\end{eqnarray}

\caption{An abstract specification of the parsing 
algorithm for IDL-graphs.
The algorithm accepts the IDL-graph $\gamma(\pi)$ if and only if
some item having the form $[S \de \alpha \bul, v_s, v_e]$
can be derived by the inference rules, 
where $S \de \alpha$ is a production of $G$ and 
$v_s$ and $v_e$ are the start and end vertices
of $\gamma(\pi)$, respectively.  
}
\label{f:Earley}
\rule{\columnwidth}{0.5pt} 
\end{figure}

In what follows, let $v_s$ and $v_e$ be the start and end 
vertices of IDL-graph $\gamma(\pi)$, respectively.  
Rules~(\ref{a:ini}), (\ref{a:pred}) and~(\ref{a:compl}) 
in Figure~\ref{f:Earley}
closely resemble Rules~(\ref{a:sini}), (\ref{a:spred}) 
and~(\ref{a:scompl}) of the original Earley algorithm, 
as reported in Figure~\ref{f:sEarley}. 
Rules~(\ref{a:scan-st}), (\ref{a:ep}) and~(\ref{a:term})
have been introduced for the purpose of efficiently computing
traversals of $\gamma(\pi)$ involving a sequence of zero or more 
triples of the form $(c_1, \ep, c_2)\in\Delta_\pi$, followed by a triple 
of the form $(c_1, a, c_2)\in\Delta_\pi$, as already mentioned. 
Once one such traversal has been computed, 
the fact is recorded through some item of the form $[a, c_1, c_2]$,
avoiding later recomputation. 
Rule~(\ref{a:scan-end}) closely resembles
Rule~(\ref{a:sscan}) of the original Earley algorithm.
Finally, by computing traversals of $\gamma(\pi)$ 
involving triples of the form $(c_1, \ep, c_2)\in \Delta_\pi$ only, 
Rule~(\ref{a:ep-S}) may derive
items of the form $[S \de \alpha \bul, v_s, v_e]$; 
the algorithm accepts the input IDL-graph if and only if any such item
can be derived by the inference rules.

We now turn to the discussion of the correctness
of the algorithm in Figure~\ref{f:Earley}.  
Our algorithm derives a parsing item 
$[A \de \alpha \bul \beta, c_1, c_2]$ if and only if
there exist a string $\gamma \in (\nonterm \cup \myterm)^\ast$, 
integers $i, j$ with $0 \leq i \leq j$, and 
$a_1 a_2 \cdots a_j \in \myterm^\ast$
such that the following conditions are all satisfied:
\begin{itemize}
\item 
$a_1 \cdots a_i \in L(v_s, c_1)$;
\item
$a_{i+1} \cdots a_j \in L(c_1, c_2)$; {\em and}
\item 
there exist two derivations in $G$ of the form
\[
\begin{array}{rll}
S & \dermg{G} &  a_1 \cdots a_i A \gamma \\
 & \derg{G} & a_1 \cdots a_i \alpha \beta \gamma \\
\alpha & \dermg{G} & a_{i+1} \cdots a_j.
\end{array}
\]
\end{itemize}
The above statement closely resembles the existential condition 
previously discussed for the original Earley algorithm, and can 
be proved using arguments similar to those presented 
for instance by~\citeA{AH72} and by~\citeA{GR76}; 
we will therefore omit a complete proof here.  
Note that the correctness of the 
algorithm in Figure~\ref{f:Earley} directly follows from 
the above statement, by taking item $[A \de \alpha \bul \beta, c_1, c_2]$
to be of the form $[S \de \alpha \bul, v_s, v_e]$ for some 
production $S \de \alpha$ from $G$. 


\section{Complexity and Implementation}
\label{s:compl}

In this section we provide a computational analysis of our parsing
algorithm for IDL-graphs.  The analysis is based on the development
of a tight upper bound on the number of possible cuts admitted
by an IDL-graph. We also discuss two possible implementations 
for the parsing algorithm.

We need to introduce some notation.  
Let $\pi$ be an IDL-expression
and let $\gamma(\pi) = (V, E, v_s, v_e, \lambda, r)$ 
be the associated IDL-graph. 
A vertex $v \in V$ is called L-free in $\gamma(\pi)$ if, 
for every subexpression $\pi'$ of $\pi$
such that $\gamma_j(\pi') = (V', E', v'_s, v'_e, \lambda', r')$
for some $j$, $V' \subseteq V$, $E' \subseteq E$, and such that $v \in V'$, 
we have that $\pi'$ is not of the form $\mylock(\pi'')$.
In words, a vertex is L-free in $\gamma(\pi)$ if it 
does not belong to a subgraph of $\gamma(\pi)$ 
that encodes an IDL-expression headed by an L operator. 
When $\gamma(\pi)$ is understood from the context, 
we write L-free in place of L-free in $\gamma(\pi)$. 
We write $\myfreecut(\pi)$ to denote the set of all cuts
in $\mycut(\pi)$ that only contain vertices that are L-free 
in $\gamma(\pi)$.
We now introduce two functions that will be used later in the 
complexity analysis of our algorithm. 
For a cut $c \in \mycut(\pi)$ we write $\size{c}$ to denote the 
length of $c$, i.e., the number of vertices in the cut.

\begin{definition}
\label{d:width}
Let $\pi$ be an IDL-expression. 
Functions $\mywidth$ and $\myfreewidth$ are specified as follows:
\begin{eqnarray*}
\mywidth(\pi) & = & \max_{c \in \mycut(\pi)}\,\size{c}, \\
\myfreewidth(\pi) 
  & = & \max_{c \in \myfreecutsub(\pi)}\,\size{c}.
\end{eqnarray*}
\end{definition}

\noindent
Function $\mywidth$ provides
the maximum length of a cut through $\gamma(\pi)$.
This quantity 
gives the maximum number of subexpressions of $\pi$ that 
need to be evaluated in parallel when generating a string in $L(\pi)$.   
Similarly, function $\myfreewidth$ provides the maximum length of a cut 
through $\gamma(\pi)$ that only includes L-free nodes.

Despite the fact that $\mycut(\pi)$ is always a finite set, 
a computation of functions $\mywidth$ and $\myfreewidth$
through a direct computation of $\mycut(\pi)$ and $\myfreecut(\pi)$
is not practical, since these sets may have exponential 
size in the number of vertices of
$\gamma(\pi)$.  The next characterization 
provides a more efficient way to compute the above functions, 
and will be used in the proof of Lemma~\ref{l:ncut} below. 

\begin{lemma}
\label{l:width}
Let $\pi$ be an IDL-expression. The quantities $\mywidth(\pi)$  
and $\myfreewidth(\pi)$ satisfy the following equations:
\begin{enumerate}

\item 
if $\pi = a$, $a \in \myterm \cup \{\symbolep\}$, we have
\begin{eqnarray*}
\mywidth(\pi) & = & 1, \\
\myfreewidth(\pi) & = & 1; 
\end{eqnarray*}

\item
if $\pi = \mylock(\pi')$ we have 
\begin{eqnarray*}
\mywidth(\pi) & = & \mywidth(\pi'), \\
\myfreewidth(\pi) & = & 1; 
\end{eqnarray*}

\item
if $\pi = \mychoose(\pi_1, \pi_2, \ldots, \pi_n)$ we have 
\begin{eqnarray*}
\mywidth(\pi) & = & \max_{i=1}^n \, \mywidth(\pi_i), \\
\myfreewidth(\pi) & = & \max_{i=1}^n \, \myfreewidth(\pi_i); 
\end{eqnarray*}

\item
if $\pi = \mymix(\pi_1, \pi_2, \ldots, \pi_n)$ we have 
\begin{eqnarray*} 
\mywidth(\pi) & = & \max_{j=1}^n \; (\mywidth(\pi_j) + 
  \sum_{i:1 \leq i \leq n \wedge i \neq j} \; \myfreewidth(\pi_i)), \\
\myfreewidth(\pi) & = & \sum_{j=1}^{n} \; \myfreewidth(\pi_j);  
\end{eqnarray*} 

\item
if $\pi = \pi_1 \cdot \pi_2$ we have 
\begin{eqnarray*}
\mywidth(\pi) & = & \max \, \{ \mywidth(\pi_1),\, \mywidth(\pi_2) \}, \\
\myfreewidth(\pi) & = & \max \, \{ \myfreewidth(\pi_1),\, 
		\myfreewidth(\pi_2) \}.
\end{eqnarray*}

\end{enumerate}
\end{lemma}

\proof 
All of the equations in the statement of the lemma 
straightforwardly follow from the definitions of 
$\Delta_\pi$ and $\mycut(\pi)$
(Definitions~\ref{d:delta} and~\ref{d:cut}, respectively). 
Here we develop at length only two cases 
and leave the remainder of the proof to the reader. 
In what follows we assume that $\gamma(\pi) = (V, E, v_s, v_e, \lambda, r)$.

In case $\pi = \mychoose(\pi_1, \pi_2, \ldots, \pi_n)$, let 
$\gamma(\pi_i) = (V_i, E_i, v_{i,s}, v_{i,e}, \lambda_i, r_i)$, 
$1 \leq i \leq n$.  From Definition~\ref{d:delta} we have 
$(v_s, \ep, v_{i,s}) \in \Delta_\pi$ and $(v_{i,e}, \ep, v_e) \in \Delta_\pi$, 
for every $i$, $1 \leq i \leq n$. 
Thus we have $\mycut(\pi) = \cup_{i=1}^n \mycut(\pi_i)\cup \{v_s, v_e\}$
and, since both $v_s$ and $v_e$ are L-free in $\gamma(\pi)$, 
$\myfreecut(\pi) = \cup_{i=1}^n \myfreecut(\pi_i)\cup \{v_s, v_e\}$.
This provides the relations in~(iii).

In case $\pi = \mymix(\pi_1, \pi_2, \ldots, \pi_n)$, let 
$\gamma(\pi_i) = (V_i, E_i, v_{i,s}, v_{i,e}, \lambda_i, r_i)$, 
$1 \leq i \leq n$.  From Definition~\ref{d:delta} we have 
$(v_s, \ep, v_{1,s} \cdots v_{n,s}) \in \Delta_\pi$ 
and $(v_{1,e} \cdots v_{n,e}, \ep, v_e) \in \Delta_\pi$.
Thus every $c \in \mycut(\pi)$ must belong to $\{v_s, v_e\}$
or must have the form $c = c_1 \cdots c_n$ with 
$c_i \in \mycut(\pi_i)$ for $1 \leq i \leq n$. 
Since both $v_s$ and $v_e$ are L-free in $\gamma(\pi)$, we immediately derive
\begin{eqnarray*}
\myfreecut(\pi) & = & \{v_s, v_e\} \cup 
\myfreecut(\pi_1) \cdots \myfreecut(\pi_n),
\end{eqnarray*}
and hence 
$\myfreewidth(\pi) = \sum_{j=1}^n \; \myfreewidth(\pi_j)$.  
Now observe that, for each $c = c_1 \cdots c_n$ specified as above
there can never be indices $i$ and $j$, $1 \leq i, j \leq n$ and
$i \neq j$, and vertices $v_1$ and $v_2$ occurring in $c_i$
and $c_j$, respectively, 
such that neither $v_1$ nor $v_2$ are L-free in $\gamma(\pi)$.

We thereby derive
\begin{eqnarray*}
\mycut(\pi) & = & \{v_s, v_e\} \cup \\
 && \mycut(\pi_1) \myfreecut(\pi_2) \cdots \myfreecut(\pi_n) \cup \\
 && \myfreecut(\pi_1) \mycut(\pi_2) \cdots \myfreecut(\pi_n) \cup \\
 && \; \; \vdots \\
 && \myfreecut(\pi_1) \myfreecut(\pi_2) \cdots \mycut(\pi_n).
\end{eqnarray*}
Hence we can write 
$\mywidth(\pi) = \max_{j=1}^n \; (\mywidth(\pi_j) + 
\sum_{i:1 \leq i \leq n \wedge i \neq j} \; \myfreewidth(\pi_i))$.~\closeproof

Now consider quantity $\size{\mycut(\pi)}$,
i.e., the number of different cuts 
in IDL-graph~$\gamma(\pi)$.
This quantity is obviously bounded from above by
$\size{V}^{\mywidth(\pi)}$.  
We now derive a tighter upper bound on this quantity. 

\begin{lemma}
\label{l:ncut}
Let $\myterm$ be a finite alphabet,
let $\pi$ be an IDL-expression over $\myterm$, and let
$\gamma(\pi)=(V, E, v_{s}, v_{e}, \lambda, r)$ be its associated IDL-graph.
Let also $k = \mywidth(\pi)$.  We have 
\begin{eqnarray*}
\size{\mycut(\pi)} & \leq & \left (\frac{\size{V}}{k} \right )^k. 
\end{eqnarray*}
\end{lemma}

\proof
We use below the following inequality. 
For any integer $h \geq 2$ and real values $x_i > 0$, $1 \leq i \leq h$,
we have
\begin{eqnarray}
\prod_{i=1}^{h} \ x_i & \leq & 
  \left (\frac{\sum_{i=1}^{h} \ x_i}{h} \right )^h. 
\label{e:uniform}
\end{eqnarray}
In words, (\ref{e:uniform}) states that the geometric 
mean is never larger than the arithmetic mean. 

We prove~(\ref{e:uniform}) in the following equivalent form. 
For any real values $c>0$ and $y_i$, $1 \leq i \leq h$ and $h \geq 2$, 
with $y_i > -c$ and $\sum_{i=1}^{h}\, y_i = 0$, we have 
\begin{eqnarray}
\prod_{i=1}^{h}\, (c + y_i) & \leq & c^h. 
\label{e:uniformprime}
\end{eqnarray}
We start by observing that if the $y_i$ are all 
equal to zero, then we are done. 
Otherwise there must be $i$ and $j$ with $1 \leq i, j \leq h$
such that $y_i y_j < 0$.  Without loss of generality, we
assume $i=1$ and $j=2$.  
Since $y_i y_j < 0$, we have
\begin{eqnarray} 
(c + y_1) (c + y_2) =  c (c + y_1 + y_2) + y_1 y_2 < c(c + y_1 + y_2).
\end{eqnarray} 
Since $\prod_{i=3}^{h}\, (c + y_i) > 0$, we have
\begin{eqnarray}
(c + y_1) (c + y_2) \prod_{i=3}^{h}\, (c + y_i) & < &
  c (c + y_1 + y_2) \prod_{i=3}^{h}\, (c + y_i).
\label{e:first}
\end{eqnarray}

We now observe that the right-hand side of~(\ref{e:first}) 
has the same form as the left-hand side of~(\ref{e:uniformprime}), 
but with fewer $y_i$ that are non-zero.  We can therefore iterate the 
above procedure, until all $y_i$ become zero valued. 
This concludes the proof of~(\ref{e:uniform}). 

Let us turn to the proof of the statement of the lemma. 
Recall that each cut $c \in \mycut(\pi)$ is a string over 
$V$ such that no vertex in $V$ has more than one occurrence in $c$, 
and $c$ is canonically represented, i.e., no other permutation of the 
vertices in $c$ is a possible cut.  
We will later prove the following claim.

\noindent
{\em Claim\/}.  Let $\pi$, $V$ and $k$ be as in the statement 
of the lemma.   We can partition $V$ into subsets 
$V[\pi,j]$, $1 \leq j \leq k$, having the following property.
For every $V[\pi,j]$, $1 \leq j \leq k$, and every pair of distinct
vertices $v_1, v_2 \in V[\pi,j]$, $v_1$ and $v_2$ do not occur together 
in any cut $c \in \mycut(\pi)$.

\noindent
We can then write 
\[
\begin{array}{rcll}
\size{\mycut(\pi)} & \leq & \prod_{j=1}^{k}\, \size{V[\pi,j]} 
    & \mbox{(by our claim and the canonical} \\
 &&& \mbox{representation of cuts)} \\
 & \leq & \left (\frac{\sum_{j=1}^{k}\, \size{V[\pi,j]}}{k} \right )^k
    & \mbox{(by~(\ref{e:uniform}))} \\
 & = & \left (\frac{\size{V}}{k} \right )^k. &
\end{array}
\]

To complete the proof of the lemma we now need to prove our claim above.
We prove the following statement, which is a slightly 
stronger version of the claim.
We can partition set $V$ into subsets
$V[\pi,j]$, $1 \leq j \leq k = \mywidth(\pi)$, 
having the following two properties:
\begin{itemize}
\item
for every $V[\pi,j]$, $1 \leq j \leq k$, and every pair of distinct
vertices $v_1, v_2 \in V[\pi,j]$, $v_1$ and $v_2$ do not occur together 
in any cut $c \in \mycut(\pi)$;
\item
all vertices in $V$ that are L-free in $\gamma(\pi)$ 
are included in some $V[\pi,j]$, $1 \leq j \leq \myfreewidth(\pi)$.
(In other words, the sets $V[\pi,j]$, 
$\myfreewidth(\pi) < j \leq \mywidth(\pi)$, 
can only contain vertices that are not L-free in $\gamma(\pi)$.)
\end{itemize}
In what follows we use induction on $\numop{\pi}$, the number of
operator occurrences (I, D, L and concatenation) appearing within
$\pi$.  

\noindent
{\em Base:\/} $\numop{\pi} = 0$.  
We have $\pi = a$, with $a \in \myterm \cup \{ \symbolep \}$, 
and $V = \{v_s, v_f\}$.  
Since $\mywidth(\pi) = 1$, we set $V[\pi,1] = V$.
This satisfies our claim, since $\mycut(\pi) = \{v_s, v_f\}$, 
all vertices in $V$ are L-free in $\gamma(\pi)$ 
and we have $\myfreewidth(\pi) = 1$. 

\noindent
{\em Induction:\/} $\numop{\pi} > 0$.  We distinguish among
three possible cases. 

\noindent
Case~1: $\pi = \mychoose(\pi_1, \pi_2, \ldots, \pi_n)$.
Let $\gamma(\pi_i) = (V_i, E_i, v_{i,s}, v_{i,e}, \lambda_i, r_i)$, 
$1 \leq i \leq n$.  
By Lemma~\ref{l:width} we have 
$\mywidth(\pi) = \max_{i=1}^{n}\,\mywidth(\pi_i)$.
For each $i$, $1 \leq i \leq n$, let us define 
$V[\pi_i,j] = \emptyset$ for every $j$ 
such that $\mywidth(\pi_i) < j \leq \mywidth(\pi)$.
We can then set 
\[
\begin{array}{rcl}
V[\pi,1] & = & (\cup_{i=1}^n \, V[\pi_i,1]) \cup \{v_s, v_e\}; \\
V[\pi,j] & = & \cup_{i=1}^n \, V[\pi_i,j], \;\;\;
  \mbox{for $2 \leq j \leq \mywidth(\pi)$}.  
\end{array}
\]
The sets $V[\pi,j]$ define a partition of $V$, since
$V = (\cup_{i=1}^n \, V_i) \cup \{v_s, v_e\}$ and,
for each $i$, the sets $V[\pi_i,j]$ define a partition of $V_i$ by 
the inductive hypothesis. 
We now show that such a partition satisfies the two conditions 
in our statement. 

Let $v_1$ and $v_2$ be two distinct vertices in some $V[\pi,j]$.
We have already established in the proof of Lemma~\ref{l:width}
that $\mycut(\pi) = (\cup_{i=1}^n \, \mycut(\pi_i)) \cup \{v_s, v_e\}$.
If either $v_1$ or $v_2$ 
belongs to the set $\{ v_s, v_e \}$, 
then $v_1$ and $v_2$ cannot occur in the same cut in $\mycut(\pi)$, 
since the only cuts in $\mycut(\pi)$ with vertices 
in the set $\{ v_s, v_e \}$ are $v_s$ and $v_e$.
Let us now consider the case $v_1, v_2 \in \cup_{i=1}^n \, V_i$.
We can distinguish two subcases.
In the first subcase, there exists
$i$ such that $v_1, v_2 \in V[\pi_i,j]$. 
The inductive hypothesis states that $v_1$
and $v_2$ cannot occur in the same cut in $\mycut(\pi_i)$, and 
hence cannot occur in the same cut in $\mycut(\pi)$. 
In the second subcase, $v_1 \in V[\pi_i,j]$ 
and $v_2 \in V[\pi_{i'},j]$ for distinct $i$ and $i'$.
Then $v_1$ and $v_2$ must belong to different graphs
$\gamma(\pi_i)$ and $\gamma(\pi_{i'})$, and hence 
cannot occur in the same cut in $\mycut(\pi)$. 

Furthermore, every vertex in $\cup_{i=1}^n \, V_i$ 
that is L-free in some $\gamma(\pi_{i})$ belongs
to some $V[\pi_i,j]$ with $1 \leq j \leq \myfreewidth(\pi_i)$, by the 
inductive hypothesis.  Since 
$\myfreewidth(\pi) = \max_{i=1}^{n}\,\myfreewidth(\pi_i)$
(Lemma~\ref{l:width}) we can state that 
all vertices in $V$ that are L-free in $\gamma(\pi)$
belong to some $V[\pi,j]$,
$1 \leq j \leq \myfreewidth(\pi)$.

\noindent
Case~2: $\pi = \mylock(\pi')$ or $\pi = \pi_1 \cdot \pi_2$.
The proof is almost identical to that of
Case~1, with $n=1$ or $n=2$, respectively.

\noindent
Case~3: $\pi = \mymix(\pi_1, \pi_2, \ldots, \pi_n)$.  
Let $\gamma(\pi_i) = (V_i, E_i, v_{i,s}, v_{i,e}, \lambda_i, r_i)$, 
$1 \leq i \leq n$.  
By Lemma~\ref{l:width} we have 
\begin{eqnarray*}
\myfreewidth(\pi) & = & \sum_{j=1}^n  \; \myfreewidth(\pi_j),  \\
\mywidth(\pi) & = & \max_{j=1}^n \; (\mywidth(\pi_j) + 
  \sum_{i:1 \leq i \leq n \wedge i \neq j} \; \myfreewidth(\pi_i)).
\end{eqnarray*}
The latter equation can be rewritten as
\begin{eqnarray}
\mywidth(\pi) & = & \sum_{j=1}^n \; \myfreewidth(\pi_j)\ \  + \ \ 
   \max_{j=1}^n \, (\mywidth(\pi_j) - \myfreewidth(\pi_j)).
\label{e:casetwo}
\end{eqnarray}
For each $i$ with $1 \leq i \leq n$, let us define 
$V[\pi_i,j] = \emptyset$ for every $j$ with 
$\mywidth(\pi_i) < j \leq \mywidth(\pi)$.
We can then set 
\[
\begin{array}{rcl} 
V[\pi,1] & = & V[\pi_1,1] \cup \{v_s, v_e\}; \\
V[\pi,j] & = & V[\pi_1,j], 
  \;\;\; \mbox{for $2 \leq j \leq \myfreewidth(\pi_1)$}; \\
V[\pi, \myfreewidth(\pi_1) + j] & = & V[\pi_2,j],  
  \;\;\; \mbox{for $1 \leq j \leq \myfreewidth(\pi_2)$}; \\
  & \vdots & \\
V[\pi, \sum_{i=1}^{n-1} \, \myfreewidth(\pi_i) + j] & = & V[\pi_n, j], 
  \;\;\; \mbox{for $1 \leq j \leq \myfreewidth(\pi_n)$};\hspace*{2cm} \\
V[\pi,\sum_{i=1}^n \, \myfreewidth(\pi_i) + j] & = 
  & \cup_{i=1}^n V[\pi_i, \myfreewidth(\pi_i) + j], \\
\lefteqn{\;\;\;\mbox{for $1 \leq j \leq \max_{j=1}^n 
    (\mywidth(\pi_j) - \myfreewidth(\pi_j)).$}}
\end{array}
\]
The sets $V[\pi,j]$ define a partition of $V$, since
$V = (\cup_{i=1}^n \, V_i) \cup \{v_s, v_e\}$ and,
for each $i$, the sets $V[\pi_i,j]$ define a partition 
of $V_i$ by the inductive hypothesis. 
We now show that such a partition satisfies both 
conditions in our statement. 

Let $v_1$ and $v_2$ be distinct vertices in some $V[\pi,j]$,
$1 \leq j \leq n$. 
We have already established in the proof of Lemma~\ref{l:width}
that a cut $c$ in $\mycut(\pi)$ either belongs to $\{v_s, v_e\}$
or else must have the form $c = c_1 \cdots c_n$ with 
$c_i \in \mycut(\pi_i)$ for $1 \leq i \leq n$. 
As in Case~1, if either $v_1$ or $v_2$ 
belongs to the set $\{ v_s, v_e \}$, 
then $v_1$ and $v_2$ cannot occur in the same cut in $\mycut(\pi)$, 
since the only cuts in $\mycut(\pi)$ with vertices 
in the set $\{ v_s, v_e \}$ are $v_s$ and $v_e$.
Consider now the case in which $v_1, v_2 \in \cup_{i=1}^n \, V_i$.
We distinguish two subcases.

In the first subcase, there exists $i$ such that 
$v_1, v_2 \in V[\pi_i,j]$.  
If there exists a cut $c \in \mycut(\pi)$ such that $v_1$ and $v_2$
both occur within $c$, then $v_1$ and $v_2$ must 
both occur within some $c' \in \mycut(\pi_i)$. But this 
contradicts the inductive hypothesis on $\pi_i$.

In the second subcase, $v_1 \in V[\pi_{i'},j']$ 
and $v_2 \in V[\pi_{i''},j'']$, for distinct $i'$ and $i''$.
Note that this can only happen if 
$\myfreewidth(\pi) < j \leq \mywidth(\pi)$,
$\myfreewidth(\pi_{i'}) < j' \leq \mywidth(\pi_{i'})$ and 
$\myfreewidth(\pi_{i''}) < j'' \leq \mywidth(\pi_{i''})$,
by our definition of the partition of $V$ and by~(\ref{e:casetwo}).
By the inductive hypothesis on $\pi_{i'}$ and $\pi_{i''}$, 
$v_1$ is not L-free in $\gamma(\pi_{i'})$
and $v_2$ is not L-free in $\gamma(\pi_{i''})$, 
which means that both $v_1$ and $v_2$ occur within the
scope of some occurrence of the lock operator. 
Note however that $v_1$ and $v_2$ cannot occur within the scope
of the same occurrence of the lock operator, since they 
belong to different subgraphs $\gamma(\pi_{i'})$ and $\gamma(\pi_{i''})$.
Assume now that there exists a cut $c \in \mycut(\pi)$ 
such that $v_1$ and $v_2$ both occur within $c$.  This
would be inconsistent with the definitions of $\Delta_\pi$ and cut
(Definitions~\ref{d:delta} and~\ref{d:cut}, respectively) since
two vertices that are not L-free and that are not
within the scope of the same occurrence of the lock operator
cannot belong to the same cut. 

Finally, it directly follows from the definition of
our partition on $V$ and from the inductive hypothesis on the $\pi_i$
that all vertices in $V$ that are L-free in $\gamma(\pi)$
belong to some $V[\pi,j]$ with 
$1 \leq j \leq \myfreewidth(\pi)$.
This concludes the proof of our statement.~\closeproof

The upper bound reported in Lemma~\ref{l:ncut} is tight.
As an example, for any $i \geq 1$ and $k \geq 2$, 
let $\myterm_{i,k} = \{ a_1, \ldots, a_{i \cdot k} \}$.
Consider now the class of IDL-expressions
$$
\pi_{i,k} = \mymix(a_1 a_2 \cdots a_i, a_{i+1} a_{i+2} \cdots a_{2i}, \ldots,
  a_{i\cdot(k-1)+1} a_{i\cdot(k-1)+2} \cdots a_{i \cdot k}).
$$
Let also $V_{i,k}$ be the vertex set of the IDL-graph $\gamma(\pi_{i,k})$.
It is not difficult to see that $\size{V_{i,k}} = 2 \cdot i \cdot k + 2$, 
$\mywidth(\pi_{i,k}) = k$ and 
$$
\size{\mycut(\pi_{i,k})} = (2 \cdot i)^k + 2
 \leq (2\cdot i + \frac{2}{k})^k,
$$
where the inequality results from our upper bound.  
The coarser upper bound presented before Lemma~\ref{l:ncut} would give 
instead $\size{\mycut(\pi_{i,k})} < (2 \cdot i \cdot k + 2)^k$.

We can now turn to the discussion of the worst case running time for
the algorithm in Figure~\ref{f:Earley}.  To simplify the presentation,
let us ignore for the moment any term that solely depends on the input
grammar $G$.

To store and retrieve items $[A \de \alpha \bul \beta,c_1,c_2]$, 
$[a, c_1,c_2]$ and $[c_1,c_2]$
we exploit some data structure $T$ and access 
it using cut $c_1$ and cut $c_2$ as indices.
In what follows we make the assumption that each access operation on $T$
can be carried out in an amount of time 
$\order{d(k)}$, where $k = \mywidth(\pi)$
and $d$ is some function that depends on the 
implementation of the data structure itself, to be discussed later. 
After we access $T$ with some pair $c_1$, $c_2$, an array is returned
of length proportional to $\size{G}$.  Thus, from such an array we can
inquire in constant time whether a given item has already been 
constructed.

The worst case time complexity is dominated by the 
rules in Figure~\ref{f:Earley} that involve the 
maximum number of cuts,
namely rules like~(\ref{a:compl}) with three cuts each. 
The maximum number of different calls to these rules
is then proportional to $\size{\mycut(\pi)}^3$.  
Considering our assumptions on $T$, 
the total amount of time that is charged to the 
execution of all these rules is then $\order{d(k) \size{\mycut(\pi)}^3}$. 
As in the case of the standard Earley algorithm, 
when the working grammar $G$ is taken into account
we must include a factor of $\size{G}^2$, which can
be reduced to $\size{G}$ using techniques 
discussed by~\citeA{GR80}. 

We also need to consider the amount of time required 
by the construction of relation $\Delta_\pi$,
which happens on-the-fly, as already 
discussed.  This takes place
at Rules~(\ref{a:ep}), (\ref{a:term}) and (\ref{a:ep-S}).  
Recall that elements of relation $\Delta_\pi$ have the form 
$(c_1, X, c_2)$ with $c_1, c_2 \in \mycut(\pi)$ and
$X \in \myterm \cup \{ \ep \}$.  
In what follows, we view $\Delta_\pi$ as a directed graph
whose vertices are cuts, and thus refer to elements of 
such a relation as (labelled) arcs. 
When an arc in $\Delta_\pi$ 
emanating from a cut $c_1$ with label $X$ is visited for the first time,
then we compute this arc and the reached cut, and cache 
them for possible later use.  However, in case the reached 
cut $c_2$ already exists because
we had previously visited an arc $(c'_1, X', c_2)$,
then we only cache the new arc. 
For each arc in $\Delta_\pi$, all the above can be easily 
carried out in time $\order{k}$, where $k = \mywidth(\pi)$.
Then the total time required by the 
on-the-fly construction of relation $\Delta_\pi$ 
is $\order{k \size{\Delta_\pi}}$.  For later use, we now
express this bound in terms of quantity $\size{\mycut(\pi)}$.
{}From the definition of $\Delta_\pi$ we can easily see that 
there can be no more than one arc between any two cuts, and 
therefore $\size{\Delta_\pi} \leq \size{\mycut(\pi)}^2$.
We obviously have $k \leq \size{V}$.  Also, it is not 
difficult to prove that $\size{V} \leq \size{\mycut(\pi)}$,
using induction on the number of operator occurrences appearing within $\pi$. 
We thus conclude that, in the worst case, the total time required by the 
on-the-fly construction of relation $\Delta_\pi$ 
is $\order{\size{\mycut(\pi)}^3}$.

{}From all of the above observations we can conclude that, in the 
worst case, the algorithm in Figure~\ref{f:Earley} takes an amount of time 
$\order{\size{G} d(k) \size{\mycut(\pi)}^{3}}$. 
Using Lemma~\ref{l:ncut}, we can then state the following theorem.
\begin{theorem}
\label{t:main}
Given a context-free grammar $G$ and
an IDL-graph $\gamma(\pi)$ with vertex set $V$ 
and with $k = \mywidth(\pi)$, the algorithm in Figure~\ref{f:Earley} 
runs in time 
$\order{\size{G} d(k) (\frac{\size{V}}{k})^{3k}}$.
\end{theorem}

We now more closely consider the choice of the data structure $T$ and 
the issue of its implementation.  We discuss two possible solutions. 
Our first solution can be used when $\size{\mycut(\pi)}$ is small
enough so that we can store $\size{\mycut(\pi)}^2$ pointers 
in the computer's random-access memory. 
In this case we can implement $T$ as a square array
of pointers to sets of our parsing items.  
Each cut in $\mycut(\pi)$ is then uniquely encoded
by a non-negative integer, and such integers are used to 
access the array.  This solution in practice comes down 
to the standard implementation of the Earley algorithm
through a parse table, as presented by~\citeA{GR80}.  We then 
have $d(k) = \order{1}$ and our algorithm has
time complexity $\order{\size{G} (\frac{\size{V}}{k})^{3k}}$.  

As a second solution, when $\size{\mycut(\pi)}$ is quite large,
we can implement $T$ as a trie~\cite{Gusfield:97}.
In this case each cut 
is treated as a string over 
set $V$, viewed as an alphabet,
and we look up string $c_1 \# c_2$ in $T$ 
($\#$ is a symbol not in $V$) in order to retrieve
all items involving cuts $c_1$ and $c_2$ that have been induced so far. 
We then obtain $d(k) = \order{k}$ and our algorithm has
time complexity $\order{\size{G} k (\frac{\size{V}}{k})^{3k}}$.  

The first solution above is faster than the second one by a factor of $k$.  
However, the first solution has the obvious disadvantage 
of expensive space requirements, 
since not all pairs of cuts might correspond to 
some grammar constituent, and the array $T$ can be very sparse
in practice.   It should also be observed that, in the natural 
language processing applications discussed in the introduction, $k$
can be quite small, say three or four.

To conclude this section, we compare the time complexity of CFG
parsing as traditionally defined for strings and the time complexity
of parsing for IDL-graphs.  
As reference for string parsing we take the Earley algorithm, which 
has already been presented in
Section~\ref{s:parser}.  
By a minor change proposed by~\citeA{GR80}, 
the Earley algorithm can be improved 
to have time complexity $\order{\size{G} \cdot n^3}$,
where $G$ is
the input CFG and $n$ is the length of the input string.  We observe
that, if we ignore the factor $d(k)$ in the time complexity of
IDL-graph parsing (Theorem~\ref{t:main}), 
the two upper bounds become very similar, with
function $(\frac{\size{V}}{k})^{k}$ in IDL-graph parsing 
replacing the input sentence length $n$ from the Earley algorithm.  

We observe that function $(\frac{\size{V}}{k})^{k}$ can be taken as a measure
of the complexity of the internal structure of the input
IDL-expression.  More specifically,  assume that no precedence
constraints at all are given for the words of the input
IDL-expression. 
We then obtain IDL-expressions with occurrences of the I operator
only, with a worst case of $k = \frac{\size{V}}{2} - 1$.
Then $\order{(\frac{\size{V}}{k})^{k}}$ can be written as 
$\order{c^{\size{V}}}$ for some constant $c > 1$, 
resulting in exponential running time for
our algorithm.  This comes at no surprise, since the
problem at hand then becomes the problem of recognition of a bag of words
with a CFG, which is known to be NP-complete~\cite{BR92}, as already
discussed in Section~\ref{s:bag}.  

Conversely, no I operator may be used in the IDL-expression $\pi$, and thus the
resulting representation matches a finite automaton or word
lattice. In this case we have $k = 1$ and function
$(\frac{\size{V}}{k})^{k}$ becomes $\size{V}$.  The resulting running
time is then a cubic function of the input length, as in the case of
the Earley algorithm.  
The fact that (cyclic or acyclic) finite automata can be parsed
in cubic time is also a well-known result~\cite{BA64,NO95}.

It is noteworthy to observe that in applications
where $k$ can be assumed to be bounded, our algorithm still runs in
polynomial time.  As already discussed, in practical applications
of natural language generation, only few subexpressions from $\pi$
will be processed simultaneously, 
with $k$ being typically, say, three or four.
In this case our algorithm behaves in a way that is
much closer to traditional string parsing than to bag
parsing.

We conclude that the
class of IDL-expressions provides a flexible representation for bags of
words with precedence constraints, with solutions in the range
between pure word bags without precedence constraints and word
lattices, depending on the value of 
$\mywidth(\pi)$.  We have also proved a fine-grained result on the
time complexity of the CFG parsing problem for IDL-expressions, again
depending on values of the parameter $\mywidth(\pi)$.



\section{Final Remarks}
\label{s:discussion}

Recent proposals view natural language surface generation
as a multi-phase process where finite but very large 
sets of candidate sentences are first 
generated on the basis of some input conceptual structure, 
and then filtered using statistical knowledge. 
In such architectures, it is crucial that the 
adopted representation for the set of candidate sentences 
is very compact, and at the same time 
that the representation can be parsed in polynomial time. 

We have proposed IDL-expressions as a solution to the above
problem.  IDL-expressions combine features that were considered
only in isolation before.
In contrast to existing formalisms, interaction of 
these features provides enough flexibility
to encode strings in cases where only partial knowledge is 
available about word order, whereas the parsing process 
remains polynomial in practical cases.

The recognition algorithm we have presented for IDL-expressions
can be easily extended to a parsing algorithm, using standard
representations of parse forests that can be extracted from 
the constructed parse table~\cite{LA92}.  Furthermore, if 
the productions of the CFG at hand are weighted, to express
preferences among derivations,
it is easy to extract a parse with
the highest weight, adapting standard 
Viterbi search techniques as used in traditional string
parsing~\cite{VI67,TE73}. 

Although we have only considered the parsing problem for
CFGs, one may also parse IDL-expressions
with language models based on finite automata, including 
$n$-gram models. 
Since finite automata can be represented as right-linear
context-free grammars, 
the algorithm in Figure~\ref{f:Earley} is still applicable.

Apart from natural language generation, IDL-expressions 
are useful wherever uncertainty on word or constituent
order is to be represented at the level of syntax
and has to be linearized for the purpose of parsing. 
As already discussed in the introduction, this 
is an active research topic both in generative 
linguistics and in natural language parsing, 
and has given rise to several paradigms, most importantly
immediate dominance and linear precedence parsing~\cite{Gazdar:85}, 
discontinuous parsing~\citeA{DA02,RA99a,SU99}
and grammar linearization~\cite{GO97a,GO95,MA95}. 
\citeA{NE03b} use IDL-expressions to define 
a new rewriting formalism, based on context-free grammars
with IDL-expressions in the right-hand sides of productions.
By means of this formalism, fine-grained results were proven on 
immediate dominance and linear precedence parsing.%
\footnote{In the cited work, the lock operator was ignored,
as it did not affect the weak generative capacity nor 
the compactness of grammars.}

IDL-expressions are similar in spirit to formalisms 
developed in the programming language literature for the 
representation of the semantics of concurrent programs.  
More specifically, so called
series-parallel partially ordered multisets, 
or series-parallel pomsets, have been proposed 
by~\citeA{GI88a} to represent choice and parallelism among processes.
However, the basic idea of a lock operator is absent from 
series-parallel pomsets.



\acks{A preliminary version of this paper 
has appeared in the {\em Proceedings of the 7th Conference 
on Formal Grammars} (FG2002), Trento, Italy.
The notions of IDL-graph and cut, central to the present study, 
are not found in the earlier paper.
We wish to thank Michael Daniels, Irene Langkilde, Owen Rambow and Stuart 
Shieber for very helpful discussions related to the topics in this paper. 
We are also grateful to the anonymous reviewers for helpful comments
and pointers to relevant literature.
The first author was supported by the PIONIER Project
{\it Algorithms for Linguistic Processing\/}, funded by
NWO (Dutch Organization for Scientific Research).
The second author was supported by MIUR under 
project PRIN No.\ 2003091149\_005.
}


\vskip 0.2in
\bibliography{/home/satta/bibl/mj}
%\bibliography{/home/markjan/bib/refs}
\bibliographystyle{theapa}

\end{document}
