Received: from fitis.ims.uni-stuttgart.de by moose.cs.indiana.edu (8.7.1/IUCS.1.39) id MAA14414; Fri, 1 Dec 1995 12:11:28 -0500 (EST) Received: by fitis.ims.uni-stuttgart.de (8.6.10/IMSsub-1.0) id SAA06740; Fri, 1 Dec 1995 18:10:30 +0100 Date: Fri, 1 Dec 1995 18:10:30 +0100 From: Tsutomu Fujinami Message-Id: <199512011710.SAA06740@fitis.ims.uni-stuttgart.de> To: ITALLC96@cs.indiana.edu Subject: ITALLC96 Submission (1/2) Reply-to: tsutomu@ims.uni-stuttgart.de Status: RO Dear Dr. Robert Koons, Here is my submission to ITALLC96. Name: Tsutomu FUJINAMI Title: A dynamic syntax-semantics interface Email: tsutomu@ims.uni-stuttgart.de Address: Institut fuer Maschinelle Sprachverarbeitung, Universitaet Stuttgart Azenbergstrasse 12, D-70174 Stuttgart, Germany Phone: +49 711 121 1388 Fax: +49 711 121 1366 The message contains the LaTeX file of my abstract, which needs to include a postscript file. The postscript file, fchannel.ps, will be sent separately in next message. Please uudecode and gunzip the file to recover it. The file must also be compiled with LaTeX2e. I assume amstex is installed at your site as well as the graphics package. To compile the file, there might be one minor problem; AmsTeX does not like the @ symbol appearing in my Email address and may display an error message. But is harmless. You can also get the postscript file of the abstract from our ftp site: at ftp.ims.uni-stuttgart.de under /pub/papers/tsutomu/sta.ps.gz Alternatively through my home page: http://www.ims.uni-stuttgart.de/users/tsutomu/ Please follow the link, 'research' and 'A dynamic syntax-semantics interface' It would be grateful if you could check the file is compiled properly by visiting these sites in case that there seems to be a problem. Yours sincerely, Tsutomu FUJINAMI ---------- cut here ---------- cut here ---------- % Title: sta.tex % % Doc: /home/tsutomu/docs/sta/sta.tex % Original Author: Tsutomu Fujinami tsutomu@burns % Created: Wed Nov 22 1995 % \documentclass[a4paper,11pt]{article} \usepackage{a4wide} \usepackage{graphics} \usepackage{amstex} %% %% the following is part of ekn.sty %% %% %% File: ekn.sty %% %% LaTeX macros for Extended Kamp Notation (EKN) %% Jon Barwise and Robin Cooper %% barwise@edu.indiana.phil, cooper@cogsci.ed.ac.uk %% %% (with some additions by Alan Black) %% %% Aug, 28th 1991 %% \newcommand{\conjbox}[1]{ \begin{tabular}{|l|}\hline \eknlist{#1}\\ \hline \end{tabular} } \newcommand{\relnbox}[2]{ \begin{tabular}{|l|}\hline \ \ \ #1 \\ \hline \eknlist{#2}\\ \hline \end{tabular} } \newcommand{\assign}[2]{ #1 $\rightarrow$ #2} \newcommand{\eknlist}[1]{\begin{tabular}{l} \\ #1 \\ \\ \end{tabular}} %% %% the end of citation (ekn.sty) %% % % newcommands % \newcommand{\term}[1]{\emph{#1}} \newcommand{\trans}[1]{\ensuremath{@>{\, #1 \,}>>}} % \newcommand{\trans}[1]{{\ensuremath{\stackrel{#1}{\longrightarrow}}}} \newcommand{\seq}[1]{\ensuremath{\langle #1 \rangle}} \newcommand{\nilout}[1]{\ensuremath{\overline{#1}}} \newcommand{\inp}[2]{\ensuremath{#1(#2)}} \newcommand{\out}[2]{\ensuremath{\overline{#1}\langle #2 \rangle}} \newcommand{\subst}[2]{\ensuremath{^{#1}\!/\!_{#2}}} \newcommand{\env}[1]{\ensuremath{\{#1\}}} \newcommand{\new}[1]{\ensuremath{\nu\,#1}} % \newcommand{\nspace}{\renewcommand{\baselinestretch}{1}\large\normalsize} \newcommand{\sent}[1]{\textit{``#1''}} \newcommand{\val}[1]{\texttt{#1}} \newcommand{\fet}[1]{\textit{#1}} %%%% AVM \newcommand{\avm}[1]{{ \setlength{\arraycolsep}{1mm} \renewcommand{\arraystretch}{1} %{0.8} \hspace*{-0.15em} \left[ \begin{array}{@{}l@{~~}l@{}} \\[-2.8mm] #1 \\[-2.8mm] %[-1.4mm] \end{array} \right] \hspace*{-0.15em} }} \newcommand{\typedavm}[2]{{\begin{array}{@{}l@{}} {\mbox{\scriptsize \it #1 }}^{\avm{#2}} \end{array}}} \newcommand{\emptytypedavm}[1]{\raisebox{-0.9ex}{$\mbox{\scriptsize \it #1} ^{\mbox{\normalsize [~]}}$}} \newcommand{\attval}[2]{\mbox{\attribute{#1}} & \fvalue{#2} \\} \newcommand{\ind}[1]{{\raisebox{.15ex}{\fbox{{\tiny #1}}}}} \newcommand{\attribute}[1]{{\it #1\/}} \newcommand{\nelist}[1]{\left\langle #1 \right\rangle} \newcommand{\fvalue}[1]{{\it #1\/}} %%% end of AVM \def\pical{$\pi$-calculus} \def\nul{{\bf 0}} \def\defed{\ensuremath{=_{{\rm def}}}} \def\para{\:\ensuremath{|}\,} \def\rep{!\,} \title{A Dynamic Syntax-Semantics Interface} \author{Tsutomu Fujinami\thanks{\texttt{tsutomu@ims.uni-stuttgart.de} Institut f\"{u}r Maschinelle Sprachverarbeitung, Universit\"{a}t Stuttgart, Azenbergstra{\ss}e 12, D-70174 Stuttgart, Germany. The work presented here was done while the author was at the Centre for Cognitive Science, University of Edinburgh. His sincere thanks to Robin Cooper and Jonathan Ginzburg for their supervision. He is working for and financially supported by \term{Verbmobil} project at IMS.}} \date{} \begin{document} \maketitle \abstract{The relation between syntax and semantics of natural language can be regarded as a constraint. With the ideas from Channel Theory, the way the content of a sentence is conveyed by an utterance can be captured as a linguistic channel. To study the operational aspects of such a channel, we construct it as a system of communicating processes by turning to the $\pi$-calculus. We show how a concurrent bottom-up chart parser can be encoded in the calculus and how a semantic object similar to those employed in Situation Theoretic Discourse Representation Theory can be created as the result of the interactions between processes, which are also encoded as a process. We conclude the paper with the discussion on how the system can be studied and its implication.} \section{Introduction} %\subsection{Linguistic channel} %\label{sec:lingchannel} In the study of natural language semantics, we are interested in how information can be conveyed from one to another by utterances. With the ideas from Channel Theory~\cite{Barwise:93,Barwise+Seligman:92,Seligman:93}, we regard a particular utterance \term{signals} a particular situation, the situation that the utterance conveys to another. We call the relation between the utterance and the situation \term{connection}. To recognise the relation, dialogue participants must classify it as an instance of a certain \term{constraint}. The figure \ref{fig:fchannel} depicts our view on how a participant may recognise a signal. He first parses the sentence to classify it as an instance of a certain sentence type, interprets it by relating it to a certain situation type, and finally anchors it to a particular situation through evaluating it against environments. \begin{figure}[htbp] \begin{center} \leavevmode \scalebox{.8}{\includegraphics{fchannel.ps}} \caption{Linguistic channel} \label{fig:fchannel} \end{center} \end{figure} % interpretation? Of these three steps, parsing and evaluation steps have been studied well by syntacticians and semanticists, respectively, but the interpretation step. Only semanticists have been interested in the relation, but so far the study has been almost nothing else than listing up pairs of a syntactic category and its corresponding semantic type, where the relation between them is assumed to be fixed. The problem inherit in such a \term{static} view may be apparent when one consider the effect of context on interpretation; a syntactic type can be related to several semantic types as is often observed as lexical ambiguity, for example. Context, though the notion must be clarified, determins which interpretation to be adopted in a particular case. The role that context can play in determining the content of utterances has been paid much attention in semantics, and there have been many proposals as to how to represent semantic types with the care to context. Situation Theoretic Discourse Representation Theory (ST-DRT)~\cite{Cooper:93, Cooper:93d} is one of such proposals, where the meaning is regarded as an abstract object and context-dependency is expressed by means of assignment function. The author previously proposed to encode the semantic objects employed in ST-DRT as a system of communicating processes and to study them by relating it to linear logic~\cite{Fujinami:95a}. Here we are extending the approach to study the interpretation step as well as the parsing step to show the linguistic channel can be constructed as a system of communicating processes. In the paper, we show how the steps of parsing and interpretation can be performed by a system of communicating processes. The ultimate goal of the project is to study the interaction between context and these steps including evaluation, where context is modelled as communicating processes, too. But such investigation is still far away, and we therefore confine ourselves to implementing the idea of parsing and interpretation as \term{reaction}. Although the project might appear to be cumbersome, it is a develpment of DRT~\cite{Kamp:84} and dynamic semantics. Recall in DRT the meaning of sentences is captured in terms of the update of Discourse Representation Structures (DRSs); the meaning of text consisting of sentences $s_{1}$ to $s_{n}$ is captured as the changes such as: \[ drs_{0} \trans{s_{1}} drs_{1} \trans{s_{2}} drs_{2} \cdots \trans{s_{n}} drs_{n} \] where $drs_{i}$ is a DRS obtained upon the input of $s_{i}$. This is very simple form of \term{process}, which we extend in the following by allowing for message passing, parallel composition, and non-determinism. The work presented here can therefore be seen as a refinment of DRT in operational aspects and as an extension of the approach towards parsing and interpretation. The paper is organised as follows: the section \ref{sec:scp} explains how we express systems of communicating processes, the \pical~\cite{MPW:92}. The section \ref{sec:parser} presents a concurrent bottom-up chart parser encoded into the calculus. The section \ref{sec:interface} shows how a semantic representation can be created as the result of interactions between processes. We conclude the paper with the discussion on how the system can be studied in linear logic and its implication (\S\ref{sec:conclusion}). The work presented here consists of part of the author's dissertation~\cite{Fujinami:95b}. The reader is invited to examine the thesis for more detail. \section{A system of communicating processes} \label{sec:scp} We turn to the \pical\ to express systems of communicating processes. The explanation given here is informal and not complete. The reader is referred to the original papers~\cite{MPW:92,Milner:93} for full explanation. We start with a simple automaton, $\alpha$. Suppose it accepts a sequence of signals, \seq{a, b}. We define the initial state $P_{0}$ of the automaton by writing \( P_{0} \defed a.b.\nul \), where \nul\ means termination. After accepting the first signal, $a$, the state of the automaton turns into another where it can only accept $b$. Let $P_{1}$ be the state, defined as \( b.\nul \). To describe the change caused to $\alpha$ by accepting $a$, we write \( P_{0} \trans{a} P_{1} \). We could think of the dual of $\alpha$. Let $\beta$ be a dual automaton such that it \term{emits} the sequence of signals, \seq{a, b}. In analogous to the definition of $\alpha$, we define the initial state $Q_{0}$ of $\beta$ as \( \nilout{a}.\nilout{b}.\nul \), where the upper bar indicates the action is output. Now think what would happen if these two automata, $\alpha$ and $\beta$, are concurrently active; $\alpha$ may pick up the signal when $\beta$ emits it. This is the most primitive form of a system of communicating processes. We write \( P_{0} \para Q_{0} \) to express the initial state of the system. If the communication occurs, the state of the system turns into another state, which we express as \( ( P_{0} \para Q_{0}) \trans{\tau} ( P_{1} \para Q_{1}) \). The symbol, $\tau$, means silent action unobservable from outside and could be suppressed for simplicity. The termination symbol, \nul, can be omitted, too. In the simple system, automata could only be kept in touch with each other when signals are emitted. If a communication is established between them, however, it is natural for them to exchange data as well. In this guise, the signaling action can be thought of as an action to establish a channel between automata. We allow them to do so by adding arguments to signals. Suppose $\beta$ sends a datum $c$ through $a$, which is expressed as \( Q_{0} \defed \out{a}{c}.Q_{1} \). Suppose $\alpha$ also receives it through $a$ replacing it for a parameter, $x$, which is expressed as \( P_{0} \defed \inp{a}{x}.P_{1} \). Upon the interaction, the datum $c$ is passed to $\alpha$, i.e., \( (P_{0} \para Q_{0}) \trans{\tau} (P_{1}\env{\subst{c}{x}} \para Q_{1}) \). We assume finitely many data can be sent and received upon a single interaction, that is, the number of arguments can be more than one.\footnote{In the notation, the use of different parenthesis for output actions, \out{}{c}, may be confusing. The sign indicates the datum is \term{free}, while \inp{}{x} indicates it is \term{bound}. } >From a different point of view, the above alphabets, $a$ and $b$, can be regarded as tokens to get access to a particular automaton. Once we discard the distincition between data to be exchanged and tokens for access, automata should also be able to exchange the tokens between them. The development brings about more flexibility to the system. Suppose $\alpha$ does not know which automaton may send it a datum but can emit a token to a channel from which some other automaton picks it up and sends back the datum with the token. The behaviour of $\alpha$ can be defined as \( P_{0}' \defed \out{d}{a}.\inp{a}{x}.P_{1} \) while that of $\beta$ as \( Q_{0}' \defed \inp{d}{y}.\out{y}{c}.Q_{1} \), where $d$ is such a channel. Upon the interaction, the state of $\beta$ is turned into \( \out{a}{c} \) because $y$ of \out{y}{c} will be replaced by $a$. Consequently, it can emit $c$ through $a$. In addition to these basic operators, the calculus is provided with other useful ones. One of them is \term{restriction}, $\nu$. If we add \new{a} to $P_{0}'$, i.e., \( (\new{a})(\out{d}{a}.\inp{a}{x}.P_{1}) \), then no other automata can get access to $a$ unless they receive it through other channels.\footnote{We say $a$ is bound by the operator.} The mechanism is useful to restrict communication to a particular group of automata, whose example can be seen in next section when we encode \term{adjunction}. Another operator is \term{replication}, !. The operator allows to make finitely many copies of an automaton. For example, \( \rep R \) can create a number of copies of $R$, i.e., \( \rep R \equiv\ R \para \cdots \para \rep R \). This is useful to provide a number of automata with the same data. The other operators are \term{choice}(+) and \term{match}. A non-deterministic automaton that behaves either as defined as $P$ or $Q$ can be expressed as $P + Q$. This itself is not so useful, but effective when combined with match. An automaton defined as \( [a=b]P \) with match formula behaves like $P$ if the condition, [a=b], is satisfied with respect to the substitution environment. When combined with the choice operator, this allows to define a case sentence. We will see the example in next section when we encode feature structures. \section{A concurrent bottom-up chart parser} \label{sec:parser} \subsection{Parsing as reaction} \label{sec:parreac} The parser is consisted of two parts: one of which is to create or update the system upon the input of words and the other is to turn the state into another through interactions between processes comprising the system. Hereinafter, we may call automata \term{process} to emphasise their dynamic aspects. The first part is not of our interest because it is not so problematic. We therefore only skectch it. Consider the case where a sequence of words, \seq{a, man}, is entered. To each lexical entry, we assume there is a process created upon the input. The mechanism can be realised by implementing the entry as a replicable process such as \( \rep a.C2 \), which is equivalent to \( (a.C2 \para \rep a.C2) \), thus turns into \( (C2 \para \rep a.C2) \) upon the interaction with \nilout{a}, the utterance of \sent{a} modelled as a signal, i.e., \( (\nilout{a} \para a.C2 \para \rep a.C2) \trans{} (C2 \para \rep a.C2) \). The change caused by the interaction to the system is the spin off of $C2$. The encoding of adjunction is more interesting. Suppose the system is given a sequence of words, \seq{a, man, walks}, to spin off three processes, $C2$, $C3$, and $C4$, respectively. We assume through intrinstic interactions a connection is established between neighbours, i.e., between $C2$ and $C3$, and $C3$ and $C4$. Through these channels, they exchange information. The process $C3$ corresponding to \sent{man} asks its left neighbour $C2$ corresponding to \sent{a} if its category is determiner. If it is the case, $C3$ creates a new process $C6$ corresponding to noun phrase and configures its connections with $C4$ so that they can exchange information. The process $C4$ then asks its new left neighbour $C6$ if its category is noun phrase, and so on. Such communications can occur in parallel between different group of processes, and the system ends up with a state where the process generated at last represents the information contained in the sentence. In the following, we explain how feature information is encoded (\S\ref{sec:fs}) and how it is retrieved for processes to interact with each other (\S\ref{sec:sysevo}). \subsection{Feature structures} \label{sec:fs} To begin with, we conceive of features and values to be tagged with a particular index, which works as a channel. The below is an eample of feature structure encoding the information available with the word, \sent{man}, where the whole structure is indexed with $r_{0}$, for example: % \begin{gather} {\small \fbox{$r_{0}$} \avm{ \attval{cat:}{\fbox{$s_{1}$} verb} \attval{phon:}{\fbox{$s_{2}$} walks} \attval{agr:}{\fbox{$r_{3}$} \avm{\attval{per:}{ \fbox{$s_{4}$} 3rd} \attval{num:}{ \fbox{$s_{5}$} sing} } } }} \label{fs:lexwalk} \end{gather} % To encode the feature structure, we first ensure these values, \val{verb}, \val{walks}, \val{3rd}, and \val{sing}, should be available through certain channles, $s_{1}$, $s_{2}$, $s_{4}$, and $s_{5}$, respectively. That is, they are encoded as a system of processes such as \( ( \out{s_{1}}{\val{verb}} \para \out{s_{2}}{\val{walks}} \para \out{s_{4}}{\val{3rd}} \para \out{s_{5}}{\val{sing}} ) \). Since many other processes may get access to these items of information, we make them replicable. We also restrict the access to these channles so that they are not mixed up with values of other entries. Thus, the encoding is modified to \[ (\new{s_{1}, s_{2}, s_{4}, s_{5}})( \rep\out{s_{1}}{\val{verb}} \para \rep\out{s_{2}}{\val{walks}} \para \rep\out{s_{4}}{\val{3rd}} \para \rep\out{s_{5}}{\val{sing}} ) \] We consider then how other processes may get access to these data. Since they cannot retrieve them directly, they have to send the system a channel through which it will retrive the data. They should also send it a message to tell it which item of information is needed. We suppose such communication is done through $r_{0}$ and $r_{3}$, the channels to features. From $r_{0}$ for example the system receives two data, the message and the channel for retrieval, to replace them for parameters, e.g., \inp{r_{0}}{x, ret}. If the messsage matches to \fet{cat}, it will return $s_{1}$ through $ret$ so that the interrogator can retrieve the value, \val{verb}, with it. Similary it will return $s_{2}$ if the message matches to \fet{phon} and $r_{3}$ if it matches to \fet{agr}, through which the interogator can repeat the same procedures to retrieve the other values. This can be encoded as a process $R_{0}$ such as: \[ R_{0} \defed\ \inp{r_{0}}{x,ret}.([x=cat]\out{ret}{s_{1}} + [x=phon]\out{ret}{s_{2}} + [x=agr]\out{ret}{r_{3}}) \] In the same manner, the agreement feature is encoded as:\footnote{The parameters $x$ appearing in both $R_{0}$ and $R_{3}$ are not identical because in the calculus each input action has its own binding power to the succeeding actions. Thus, the access to the parameter is restricted already to the process in which it appears. The same goes for $ret$.} \[ R_{3} \defed\ \inp{r_{3}}{x, ret}.([x=per]\out{ret}{s_{4}} + [x=num]\out{ret}{s_{5}}) \] By adding these two processes to the above and restricting the access to $r_{0}$ and $r_{3}$ as well, we get the following system:\footnote{The idea to encode feature structures as processes was proposed by Smolka~\cite{Smolka:94}, too.} \[ F3 \defed\ (\new{r_{0}, r_{3}, s_{1}, s_{2}, s_{4}, s_{5}})( \rep R_{0} \para \rep R_{3} \para \rep\out{s_{1}}{\val{verb}} \para \rep\out{s_{2}}{\val{walks}} \para \rep\out{s_{4}}{\val{3rd}} \para \rep\out{s_{5}}{\val{sing}} ) \] Now every item of information has been enclosed within the system. On top of these encodings, we have finally to provide it with a channel through which the index of top position, $r_{0}$, can be retrieved. Let $c_{3}$ be such a channel. All we need to do is to add to the sytem a process such as \( \rep \inp{c_{3}}{ret}.\out{ret}{r_{0}} \). In what follows, we assume such a process exists to each system encoding a lexical entry and write $F3(c_{3})$ to indicate which channel the system is provided with, for simplicity.\footnote{Another issue not discussed here is about channel \term{type}. In the definition of $R_{0}$, the channel, $ret$, is used to return both $s_{1}$ and $r_{3}$, which, strictly speaking, belong to different types in the sense the former is used to return values while the latter to return features. If we followed the strict typing discipline, these must have been returned through different channels, say $v$ and $f$. Then, the first action, \inp{r_{0}}{x, ret}, should have also been defined as \inp{r_{0}}{x,v,f}. There is an ongoing research on that topic. Interested readers are referred to ~\cite{Milner:93}.} \subsection{Adjunction} \label{sec:sysevo} \paragraph{Agents} We introduce a new terminology, \term{agent}, to mean a system that subsumes another system encoding a lexical entry explained in the above with the abilities to communicate with and create other agents. We reserve the terminology of \term{system} for the system consisted of agents. As is suggested in the begining of the section, agents are assigned to each word and phrase structure, e.g., $C2$ or $C3$. Each agent is provided with a distinctive channel, through which it communicates with other agents. The access to the lexical information is also initially restricted to the agent only. For example, only $C3$ can get the access to $c_{3}$ shown in the above, i.e., \( C3 \defed\ (\new{c_{3}})(F3(c_{3}) \para M3(c_{3})) \). In the following, we elaborate the process $M3$ to encode the abilities.\footnote{$M$ is meant to be a \term{method}, a terminology adopted in the research of object oriented programming.} \paragraph{Agents to trigger actions of other agents} To start the computation, each agent triggers its neighbours by emitting to them its channel, $e_{i}$, to inform that it exists at their left or right position. To inform them of its existence, the agent must know who are its left and right neighbours, which we assume each agent knows. We suppose $C2$ is assigned $e_{2}$ and $C3$ $e_{3}$. What $C2$ has to do is to get a write permission from $C3$ through $e_{3}$ to add the information that $C2$ is situated at the left position of $C3$. The process $M2$ should include an action such as \( \inp{e_{3}}{c_{3}', l_{3}', r_{3}'}.\out{l_{3}'}{e_{2}} \), where $l_{3}'$ and $r_{3}'$ will be replaced by distinctive channels to send back $C3$ the access to its left or right agent. The other agent $C3$ should also include the corresponding action such as \( (\new{c_{3}, l_{3}, r_{3}})( \rep \out{e_{3}}{c_{3}, l_{3}, r_{3}}) \). Upon the interaction, the channels, $c_{3}$, $l_{3}$, and $r_{3}$, are passed to $C2$ so that it can add to the system a new item of information, \out{l_{3}}{e_{2}}. The agent $C3$ is eager to pick up the item, provided with a process such as \( \rep\inp{l_{3}}{x}.C3l(x) \) as a composite of $M3$. $C3l(x)$ defines its succeeding actions parameterised over $x$. Given that process, $C3$ will spin off $C3l(e_{2})$ when it picks up $e_{2}$ through $l_{3}$ and replaces it for $x$. In this way, $C3$ can be triggered to perform actions to look into its left neighbour, $C2$. \paragraph{Recording and retrieving the access to neighbours} By $C3l(e_{2})$, the agent $C3$ first records $e_{2}$, the access to its left neighbour, $C2$. Agents record the information on their left and right neighbours by emitting them to particular channels, $pln_{i}$ and $prn_{i}$, abbreviation for Private record of Left Neighbour and Private record of Right Neighbour, respectively. The process, $C3l(e_{2})$, for instance, includes a replicable process, \( \rep \out{pln_{3}}{e_{2}} \). To allow other agents to get access to the neighbours, the output action, \out{e_{3}}{c_{3},l_{3},r_{3}}, is extended to \( (\new{c_{3}, l_{3}, r_{3}, ln_{3}, rn_{3}})(\out{e_{3}}{c_{3},l_{3},r_{3},ln_{3},rn_{3}}) \) by adding to it $ln_{3}$ and $rn_{3}$, through which the access to the neighbours can be retrieved. For example, a process such as \( \rep \inp{ln_{3}}{x}. \inp{pln_{3}}{y}. \out{x}{y} \) does the job. \paragraph{Retrieving feature information} When trigerred, the agent looks into the feature information through the given channel and may create a new agent depending on the items of information it extracts of. Suppose that $C3$, by means of \( C3l(e_{2}) \), interacts with $C2$ through $e_{2}$ and generates a new agent $C6$ corresponding to noun phrase if the extracted items of information indicate that the category of its left neighbour is determiner. To extract the items of information, \( C3l(e_{2}) \) must perform the following actions: % \[ (\new{d, ret})(\inp{e_{2}}{c_{2}',l_{2}',r_{2}',ln_{2}', rn_{2}'}.\out{c_{2}'}{d}.\inp{d}{r_{0}'}. \out{r_{0}'}{\fet{cat}, ret}.\inp{ret}{s_{1}'}.\inp{s_{1}'}{x}. [x=\val{det}]C3lg) \] % The explanation follows: \begin{enumerate} \item \inp{e_{2}}{c_{2}',l_{2}',r_{2}',ln_{2}', rn_{2}'}: The agent receives \(c_{2},l_{2},r_{2},ln_{2} \) and \( rn_{2} \) through $e_{2}$ and replaces them for \(c_{2}',l_{2}',r_{2}',ln_{2}' \) and \( rn_{2}' \). \item \out{c_{2}'}{d}: It emits its private channel $d$ through $c_{2}$. \item \inp{d}{r_{0}'}: Then it waits for the reply at the channel, which will replace the channel to the top level of the feature structure for $r_{0}'$. \item \out{r_{0}'}{\fet{cat},ret}: Once it gets the channel, it emits a request, \fet{cat}, along with the channel for retrieval, $ret$. \item \inp{ret}{s_{1}'}: The reply is received through $ret$ to substitute $s_{1}'$. \item \inp{s_{1}'}{x}: Then it can retrieve the information on category through $s_{1}$. \item \( [x=\val{det}]C3lg \): It will proceed to next actions, the creation of a new agent corresponding to noun phrase, if the category matches to \val{det}. It does nothing otherwise. \end{enumerate} \paragraph{Creating new agents} We now look into how the new agent, $C6$, can be created. First, it must be given the access to its left and right neighbours, $C1$ and $C4$, respectively, in addition to the access to its own. Let $left$, $self$, and $right$ be the access to these agents. The channel, $self$, can be instantiated with an arbitrary channel created freshly, say $e_{6}$ with restriction, but $left$ and $right$ have to be instantiated with $e_{1}$ and $e_{4}$, which must be extracted of other agents. It is not hard for $C3$, the creator of $C6$, to retrieve $e_{4}$ as it is its own right neighbour. It needs only to perform once the input action, \inp{prn_{3}}{right}. It is however more difficult to retrieve $e_{1}$, the access to $C1$, because $C3$ does not have direct access to it and has to consult $C2$ to retrieve it. The job can be defined as: \[(\new{w})(\inp{pln_{3}}{v}.\inp{v}{c_{2}',l_{2}',ln_{2}',rn_{2}}. \out{ln_{2}'}{w}.\inp{w}{left} ) \] The first action, \inp{pln_{3}}{v}, substitutes $e_{2}$ for $v$, as there is a replicable process, !\,\out{pln_{3}}{e_{2}}, recording the access to the left neighbour of $C3$. Then, by executing \inp{e_{2}}{c_{2}',l_{2}',ln_{2}',rn_{2}'}, it can retrieve $ln_{2}$, to which it can send the request to return $C2$'s left neighbour. Through the channel, it emits a private channel, $w$, to retrieve the access, $e_{1}$, replacing it for $left$. At last, $C3$ needs to inform $C1$ and $C4$ that $C6$ has been newly created, which is done by the following two actions: \inp{e_{1}}{c_{1}',l_{1}',r_{1}',ln_{1}',rn_{1}'}.\out{r_{1}'}{e_{6}} and \inp{e_{4}}{c_{4}',l_{4}',r_{4}',ln_{4}',rn_{4}'}.\out{l_{4}'}{e_{6}}. It also needs to inform $C6$ that $C1$ and $C4$ are its neighbours, which is done by the following action: \inp{e_{6}}{c_{6}',l_{6}',r_{6}',ln_{6}',rn_{6}'}.(\out{r_{6}'}{e_{4}} \para \out{l_{6}'}{e_{1}}). Without saying, $C6$ is provided with other processes as well similar to those provided for $C2$ and $C3$, such as the one encoding the feature information of the noun phrase, \sent{a man}. \paragraph{Further development} The parser sketched in the above is a simplified version based on the one presented in the dissertation~\cite{Fujinami:95b}. We have assumed for example that an agent can get only one agent at its left and right position, which does not obviously hold in practice when one applies for chart parsing. To record and manage more than one agents as neighbours, we have to introduce list data structure, which makes the configuration procedure more complex. Also, the simplified parser is not completely parallel. Some agents must become active earlier than the other. To remove the restriction, the communication procedure between agents must be more sophisticated. Interested readers are referred to the thesis.\footnote{It should also be mentioned that the approach to capture parsing as message passing is not new. See for example the work done by Norbert Br\"{o}eker, Michael Strube, Susanne Schacht and Udo Hahn~\cite{Hahn:92a, Hahn:92b, Hahn:94}. The construction presented in the paper can be seen as an algebraic refinment of such a program.} \section{Syntax-semantics interface} \label{sec:interface} \paragraph{Semantic representation} For the sake of simplicity, we adopt here a simplified version of encoding in representing semantic objects. More elaborated constructions can be found in elsewhere~\cite{Fujinami:95b, Fujinami:95a}. Let us consider the sentence, \sent{a man walks}. We encode its meaning as a process such as \inp{r}{x}.\out{man}{x}.\out{walk}{x}. The process receives a particular name through $r$ to replace it for $x$, then emits it through the channels, $man$ and $walk$, consecutively. What is intended to represent by the process is a semantic object (\ref{ex:manwalks}), similar to that employed in Discourse Representation Theory~\cite{Kamp+Reyle:93} or Situation Theoretic Discourse Representation Theory~\cite{Cooper:93, Cooper:93d}. We mean by the object that there is a constraint such that if there is a man, then he walks, where the person is parameterised as $x$.\footnote{The idea behind this view is to capture generalised quantifiers as constraint, whose development can be found in the thesis~\cite{Fujinami:95b}.} The alphabet, $r$ pointing $x$, is called \term{role} or \term{index} to the parameter. % \begin{gather} {\small \relnbox{\assign{$r$}{$x$}}{ \conjbox{man($x$)}$\stackrel{\exists}{\Longrightarrow}$ \conjbox{walk($x$)} } } \label{ex:manwalks} \end{gather} % \paragraph{Constructing semantic representation} How each word of \sent{a man walks.} can contribute to constructing the semantic object? One way to think about this is that the utterance of \sent{a} contributes to \inp{r}{x}, that of \sent{man} to \out{man}{x}, and that of \sent{walks} to \out{walk}{x}. The determiner, \sent{a}, is then conceived of as playing a role of abstractor, abstracting the succeeding actions over $x$ with the index $r$. Since the indefinite description is thought of as generating a new discourse marker, we assume $x$ is created as a bound name by the agent for \sent{a}. As for the marker, it is strange to assume that the other agents for \sent{man} and \sent{walks} know which discourse marker they will be assigned before the syntactic structure is build. We think therefore they should be parameterised over different names from $x$ in the initial state, i.e., \out{man}{y} and \out{walk}{z}. The question to be asked is then how these names $y$ and $z$ can be substituted by $x$. We think this is done when phrase structures, [a man] and [[a man] walks], are constructed. That is, when the agent for \sent{man} creates a new agent for {\sc np}, [a man], it looks into the agent for \sent{a} to retrieve the discourse marker, $x$, and replace it for $y$. Similary, when the agent for \sent{walks} creates a new agent for {\sc s}, [[a man] walks], it looks into the agent for the phrase, [a man], to get the discourse marker and replace it for $x$. We regard in this sense that discourse markers are conveyed along with syntactic structures. We sketch in the following how the idea can be implemented. Let $C2, C3$, and $C4$, the agents for \sent{a}, \sent{man}, and \sent{walks}, respectively. $C2$ holds of the action, \inp{r}{x}, $C3$ \out{man}{y}, and $C4$ \out{walk}{z}. Let $C6$ be the agent for the {\sc np}, [a man]. When $C3$ creates $C6$, it needs to read out the marker, $x$. We treat the discourse marker in the same way as $r_{0}$, the channel to the top level of feature descriptions. Other agents can retrieve it by emitting a channel, $y$, through $m$, and waiting for the marker to be returned through it from $C2$ provided with the process such as (\new{x})( \rep\inp{m}{y'}.\out{y'}{x}) After retrieving the marker, $C3$ substitutes it for $y$ in \out{man}{y}. This can be done in similar way that the access to the left and right neighbours of $C6$ are initialised with $e1$ and $e4$ explained in the previous section. The marker is also recorded by $C6$ in the same way so that $C4$ can read it out when creating $C7$, the agent for {\sc s}, [[a man] walk]. $C2$ itself needs to read out the marker from its feature description to instantiate \inp{r}{x}. Remember that $x$ in \inp{r}{x} is already a bound name and equivalent to \inp{r}{x_{1}}. To make it identical with the marker $x$ passed around, the action has to be prefixed by some substituting process, e.g., \inp{sub}{x_{1}} in \inp{sub}{x_{1}}.\inp{r}{x_{1}}, which reads out the marker $x$ to substitute it for $x_{1}$. Since the agents, $C2$, $C6$, and $C7$ are created in that order, the actions, \inp{r}{x}.\out{man}{x}.\out{walk}{x}, encoding the meaning, come out in the order. Thus, we can say the process is generated through parsing the sentence, dynamically. \section{Conclusion} \label{sec:conclusion} The parser and the syntax-semantics interface presented in the above two sections are simplified and not sophisticated enough to deal with utterances in practice. The approach may however be extended to cover broader ranges of sentences. You can construct whatever you need as a process no matter how the encoding becomes complex because the calculus is so powerful. What is important, though, is to examine what new insights we can obtain from the project. One way to get an insight is to relate the \pical\ to linear logic~\cite{Girard:87} as is proposed by the author in elsewhere~\cite{Fujinami:95b, Fujinami:95a}. In the proposal, the transition, \( P_{0} \trans{a} P_{1} \), is regarded as a sequent, \( a: \Gamma \Longrightarrow \Delta \), of combinatory intuitionistic linear logic~\cite{Lafont:88}, where $\Gamma$ and $\Delta$ represent the resources available at the states of $P_{0}$ and $P_{1}$, respectively. The choice operator, +, is mapped to the additive conjunction, \&, in the logic. The mobility and substitutions are realised by introducing the equal relation, =, to the logic. We have to include the exponential, !, to represent substitution environments. A benefit we can expect of the correspondence is that we can relate the work to Channel Theory by relating the logic to the theory, which has been already discussed in \cite{Fujinami:95b,Fujinami:95a}. We claim therefore the work presented in the paper is grounded to the theory of information flow. The trouble from our point of view as computational linguist is however the logic is \term{undecidable}~\cite{Lincoln:92}. No wonder, because the \pical\ is seemingly powerful. But its implication must be considered carefully. The claim that we have made inevitably when we adopted the calculus as our model is that the cognitive states involved in linguistic actions can be modelled as a system of communnicating processes. Given the possibility that the class of the computation provided by the calculus is undecidable, does it also mean that our intelligence suffers from similar problem? The question may be inappropriate to ask, but is inevitably rased when we work on the operational aspects of DRT and stick to the view that DRSs as a definition of cognitive states. Although the inquiry may be philosophically interesting, the author suggests that we had better look for other calculi that are computationally cheaper. He believes the work presented here could indicate a line to start the investigations. % \bibliographystyle{acm} \bibliographystyle{alpha} \begin{thebibliography}{LMSS92} \bibitem[Bar93]{Barwise:93} Jon Barwise. \newblock Constraints, channels, and the flow of information. \newblock In Peter Aczel, David Israel, Yasuhiro Katagiri, and Stanly Peters, editors, {\em Situation Theory and its Applications}, volume~3, pages 3--27. Stanford, California, 1993. \bibitem[BHS94]{Hahn:92b} Norbert Br\"{o}eker, Udo Hahn, and Susanne Schacht. \newblock Concurrent lexicalized dependency parsing: The \textit{ParseTalk} model. \newblock In {\em 15th International Conference on Computational Linguistics}, volume~2, pages 379--385. 1994. \bibitem[BS92]{Barwise+Seligman:92} Jon Barwise and Jerry Seligman. \newblock The rights and wrongs of natural regularity. \newblock In James Tomberlin, editor, {\em Philosophical Perspectives}. 1992. \newblock in preses. \bibitem[BSSH94]{Hahn:94} Norbert Br\"{o}eker, Michael Strube, Susanne Schacht, and Udo Hahn. \newblock Coarse-grained parallelism in natural language understanding: parsing as message passing. \newblock In {\em The International Conference on New Methods in Language Processing {(NeMLaP)}}, pages 182--189. September 1994. \newblock Manchester, U.K. \bibitem[Coo93a]{Cooper:93} Robin Cooper. \newblock Integrating different information sources in linguistic interpretation. \newblock In {\em First International Conference on Linguistics at Chosun University}, pages 79--109, Kwangju, Korea, November 1993. Foreign Culture Research Institute, Chosun University. \bibitem[Coo93b]{Cooper:93d} Robin Cooper. \newblock Towards a general semantic framework. \newblock In Robin Cooper, editor, {\em Integrating Semantic Theories}. ILLC/Department of Philosophy, University of Amsterdam, 1993. \newblock Deliverable R2.1.A, Dyana-2. \bibitem[Fuj95a]{Fujinami:95b} Tsutomu Fujinami. \newblock {\em A process algebraic approach to computational linguistic}. \newblock PhD thesis, Centre for Cognitive Science, University of Edinburgh, Edinburgh, 1995. \newblock avaibable in /pub/papers/tsutomu through ftp.ims.uni-stuttgart.de. \bibitem[Fuj95b]{Fujinami:95a} Tsutomu Fujinami. \newblock A process algebraic approach to situation semantics. \newblock In {\em 10th Amsterdam Colloquium}, Amsterdam, The Netherlands, December 1995. University of Amsterdam. \newblock in preparation. \bibitem[Gir87]{Girard:87} Jean-Yves Girard. \newblock Linear logic. \newblock {\em Theoretical Computer Science}, 50(1):1--102, 1987. \bibitem[Kam84]{Kamp:84} Hans Kamp. \newblock A theory of truth and semantic representation. \newblock In J.~A.~G. Groenendijk, T.~M.~V. Janseen, and M.~Stokhof, editors, {\em Truth, Interpretation and Information: Selected Papers from the Third Amsterdam Colloquium}, pages 1--41. Dordrecht: Foris Publication, 1984. \bibitem[KR93]{Kamp+Reyle:93} Hans Kamp and Uwe Reyle. \newblock {\em From Discourse to Logic: Introduction to Modeltheoretic Semantics of Natural Language, Formal Logic and Discourse Representation Theory}. \newblock Dordrecht: Kluwer, 1993. \bibitem[Laf88]{Lafont:88} Yves Lafont. \newblock The linear abstract machine. \newblock {\em Theoretical Computer Science}, 59:157--180, 1988. \bibitem[LMSS92]{Lincoln:92} Patrick Lincoln, Jhon Mitchell, Andre Scedrov, and Natarajan Shankar. \newblock Decision problems for propositional linear logic. \newblock {\em Annuals of Pure and Applied Logic}, 56:239--311, 1992. \bibitem[Mil93]{Milner:93} Robin Milner. \newblock The polyadic $\pi$-calculus: a tutorial. \newblock In F.~L. Bauer, W.~Brauer, and H.~Schwichtenberg, editors, {\em Logic and Algebra of Specification}, pages 203--246. Springer Verlag, 1993. \bibitem[MPW92]{MPW:92} Robin Milner, Joachim Parrow, and David Walker. \newblock A calculus of mobile processes, parts {I} and {II}. \newblock {\em Information and Computation}, 100:1--40 and 41--77, 1992. \bibitem[SB93]{Seligman:93} Jerry Seligman and Jon Barwise. \newblock Channel theory: toward a mathematics of imperfect information flow. \newblock Unpublished ms., May 1993. \bibitem[SHB94]{Hahn:92a} Susanne Schacht, Udo Hahn, and Norbert Br\"{o}eker. \newblock Concurrent lexicalized dependency parsing: A behavioral view on \textit{ParseTalk} events. \newblock In {\em 15th International Conference on Computational Linguistics}, volume~2, pages 489--493. 1994. \bibitem[Smo94]{Smolka:94} Gert Smolka. \newblock A foundation for concurrent constraint programming. \newblock In {\em Constraints in Computational Logics}, volume 845 of {\em LNCS}, pages 50--72. Springer Verlag, September 1994. \end{thebibliography} \end{document} % Local Variables: % End: