<html dir="ltr"><head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style title="owaParaStyle">P {
MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px
}
</style>
</head>
<body ocsi="x">
<div dir="ltr">CALL FOR PAPERS</div>
<div dir="ltr"> </div>
<div dir="ltr">Natural Language Engineering</div>
<div dir="ltr">SPECIAL ISSUE ON</div>
<div dir="ltr">Finite State Methods and Models in Natural Language Processing</div>
<div dir="ltr"><br>
Special Issue Description<br>
--------------------------------</div>
<div dir="ltr"><font face="times new roman"></font> </div>
<div dir="ltr">The languages described by regular expressions are exactly those<br>
recognized by automata that have a finite number of states (Kleene<br>
1956). This fundamental result has been extended to string<br>
transductions, sets of trees, formal power series, grammars,<br>
semigroups, and finite models. Furthermore, the interest in finite<br>
equivalence relations in these systems has led to the study of further<br>
formal properties of recognizable languages. The study was pioneered<br>
by Schützenberger, McNaughton, Papert and Kamp, who established the<br>
equivalence of star-free generalized regular expressions, counter-free<br>
automata, first-order logic and temporal logic.</div>
<div dir="ltr">Kleene's theorem, its extensions and its restrictions have tremendous<br>
methodological relevance to speech and natural language processing<br>
(NLP). In 1972, C. Douglas Johnson pioneered the study of formal<br>
aspects of phonological descriptions by reducing phonological grammars<br>
to finite state systems. This was the dawn for the currently existing<br>
finite state approached to phonology and morphology with wide-spread<br>
applications to written languages. In addition, many other NLP areas<br>
admit that they employ finite state systems or their extensions. In<br>
particular, we mention decision trees, deterministic parsing, chunk<br>
parsing, edit distance, rational kernels, hidden Markov models,<br>
Viterbi algorithms, semiring parsing, and weighted tree automata. In<br>
sum, finite state methods, both statistical and knowledge-based, are<br>
now being used in various areas of linguistic computation, ranging<br>
from speech and character recognition to message understanding and<br>
statistical machine translation. Finite state methods in NLP continue<br>
to be an area of further research and growing area.</div>
<div dir="ltr">The current special issue has two goals. The first is to summarize<br>
the state of the art in the finite state methods and models of the NLP<br>
community. The second is to increase awareness of the community about<br>
open issues and new perspectives: the study of the adequacy of<br>
finite-state methods and models extends from the traditional richness<br>
and use to new generalizations and ambitious tasks.</div>
<div dir="ltr">The call for papers is open to everyone: New contributions are warmly<br>
encouraged; in addition, the issue is ideal *also* for extended and<br>
updated versions of the papers presented in workshops on Finite State<br>
Methods and Natural Language Processing (FSMNLP Helsinki 2005, Potsdam<br>
2007, Ispra 2008, and Pretoria 2009). Submissions of completely new<br>
papers under the special theme are welcomed as equally appropriate as<br>
extended and updated papers.</div>
<div dir="ltr"><br>
Topics of Interest<br>
------------------</div>
<div dir="ltr">1. New or updated work on the traditional topics of FSMNLP workshops</div>
<div dir="ltr">The traditional topics in the series of FSMNLP workshops are<br>
appropriate. The submitted paper must clearly deal with finite<br>
states. An extended version of a meeting paper can be submitted,<br>
provided that the contribution has been updated as appropriate given<br>
the progress in the field. The forums for any preliminary versions of<br>
the paper must be indicated.</div>
<div dir="ltr"><br>
2. Study of new questions raised by fundamental results in finite<br>
state phonology and morphology</div>
<div dir="ltr">In linguistics, morphological grammars describe the structure of word<br>
forms in a language, and phonological grammars describe the systematic<br>
use of sounds as units that encode the word forms. Finite state<br>
phonology and morphology consider grammars and rules whose formal<br>
semantics can be defined using finite state transducers. The<br>
fundamental result in these fields states that one can construct<br>
finite state transducers aka lexical transducers from phonological<br>
(Johnson 1972, Kaplan and Kay 1994) and morphological grammars<br>
(Koskenniemi 1983, Karttunen 1994, Beesley and Karttunen 2003). This<br>
result is not the end of inquiries but it paves the way for the study<br>
of many interesting problems, including the following:</div>
<div dir="ltr">- adaptations of the fundamental result to less rigid formalisms and<br>
descriptive approaches used in field linguistics<br>
- correlation between availability of computational morphology and<br>
language development of under-resourced languages<br>
- approaches to the adaptation of lexical transducers to a cluster of<br>
languages<br>
- seamless construction of computational lexicons from dynamically<br>
changing linguistic descriptions<br>
- model-checking and automatic verification of phonological grammars<br>
- finite state approaches to language variation and diachronic<br>
description<br>
- portability and long-term archiving of resources in computational<br>
morphology and morpho-syntax<br>
- constructing refreshed lexical transducers quickly from updated<br>
extended regular expressions<br>
- lexical transducers for tonal languages from auto-segmental accounts<br>
of spreading and alignment of articulatory features<br>
- learning and training finite state grammars from small samples<br>
- designs of weighted phonological and morphological grammars<br>
- feasible finite state restrictions of optimality-theoretic and<br>
multi-tiered phonology<br>
- efficient finite state re-implementation of competitively efficient<br>
ad hoc methods (see the article by S. Wintner in NLE 14(4) 2007).</div>
<div dir="ltr"><br>
3. Study of new methods with connections between languages, trees and<br>
finite state automata</div>
<div dir="ltr">The theory of classical string automata has a natural extension to<br>
tree automata, which found applications in NLP. In 1982, Joshi and<br>
Levy pointed out in Computational Linguistics 8(1) that phrase<br>
structure grammars actually generalize to tree automata that bring<br>
more descriptive power. The link between phrase-structure grammars,<br>
tree grammars and tree automata has enriched the study of enumerative<br>
grammars that generate trees and has given birth to model-theoretic<br>
grammars that instead describe trees. The study includes but is not<br>
restricted to:</div>
<div dir="ltr">- representations of languages by tree automata and tree grammars<br>
- non-projectivity and partial commutativity of yields of tree<br>
automata and grammars<br>
- hierarchies of tree automata and tree grammars<br>
- weighted extensions of representations of languages and<br>
transductions<br>
- tree logics and model-theoretic syntax<br>
- language generation through tree logics<br>
- efficient and dynamic construction of automata from updated rules or<br>
logical formulas<br>
- representations of trees and automata-based query languages for tree<br>
banks<br>
- learning, training and minimization of representations of languages<br>
and transductions<br>
- semiring parsing and other generalizations of classical parsing<br>
algorithms<br>
- applications and case studies of methods based on the theory of tree<br>
automata.</div>
<div dir="ltr">In 1963, Chomsky and Schützenberger gave a morphic representation for<br>
the context-free languages i.e. the yields of local tree automata.<br>
The representation involves bracketed strings that encode the<br>
structure of the parse trees. Such use of bracketed strings and local<br>
trees gives rise to methods that decompose tree automata into simpler<br>
components many of which have regular yields. The relevant topics<br>
include:</div>
<div dir="ltr">- representation of tree grammars and tree automata through<br>
decompositions into constraints<br>
- Chomsky-Schützenberger representations for tree grammars and<br>
weighted tree grammars<br>
- feasible constituent, dependency and alignment bracketing schemes<br>
for grammars, tree banks and parallel corpora<br>
- intersection grammars and conjunctive grammars with recognizable<br>
sets of string or trees<br>
- chart parsing, restarting automata, nested word automata and visibly<br>
pushdown languages<br>
- regular bracketed string languages that approximate sets of trees.</div>
<div dir="ltr"><br>
4. Study of advantages of restrictions defined in algebraic theories<br>
of automata and languages or in finite model theory</div>
<div dir="ltr">Feasible finite state methods in natural language processing are an<br>
application of a vast body of basic research in mathematics and<br>
computer science. There remain, however, situations where<br>
straightforward and general methods fail to be applicable or<br>
efficient. It is in these situations where NLP applications motivate<br>
interest in special families of regular relations, automata,<br>
semirings, and formal power series. Connections between such families<br>
and NLP tasks have not yet been fully elaborated. If we are lucky,<br>
the study of the connections will lead to new fundamental results that<br>
give rise to freshly identified subfamilies of finite state<br>
methodologies in NLP. The linguistically relevant restrictions on the<br>
power of general-purpose finite state methods might include:</div>
<div dir="ltr">- finite ambiguity<br>
- sequential functions<br>
- step functions<br>
- idempotent semirings<br>
- locally finite semirings<br>
- descriptive complexity<br>
- deterministic transition closure<br>
- first-order definability<br>
- aperiodic, counter-free and star-free sets<br>
- unambiguous concatenation<br>
- partial commutativity<br>
- discounted weights<br>
- finite synchronization delay<br>
- limited center-embedding<br>
- local testability<br>
- finite bandwidth.</div>
<div dir="ltr">In addition, the topics of interest include tools that support<br>
experiments with these restrictions and their specialized algorithms:</div>
<div dir="ltr">- new kinds of implementations of finite state compilers, libraries<br>
and on-demand operations<br>
- optimized algorithms for manipulation of automata or related<br>
formalisms<br>
- benchmarks suitable for evaluation of performance of algorithms<br>
- methods that construct, minimize or decompose automata or<br>
transducers.</div>
<div dir="ltr"><br>
Important Dates<br>
---------------</div>
<div dir="ltr">- Deadline for submissions: 23 May 2010<br>
- First decision: 10 July 2010<br>
- Submission of revised version: 15 August 2010<br>
- Final decision: 22 September 2010<br>
- Submission of camera-ready versions: 23 October 2010</div>
<div dir="ltr">Submission<br>
----------</div>
<div dir="ltr">Articles submitted to this special issue must adhere to the NLE<br>
instructions for contributors. We encourage authors to keep their<br>
submissions below 30 pages.</div>
<div dir="ltr">Up to date information will be available at<br>
<a href="http://www.ling.helsinki.fi/projects/jnle/.">http://www.ling.helsinki.fi/projects/jnle/.</a></div>
<div dir="ltr"> </div>
<div dir="ltr">Editorial Board<br>
-------------------</div>
<div dir="ltr"> </div>
<div dir="ltr">Guest Editors</div>
<div dir="ltr">- Anssi Yli-Jyrä (Department of Modern Languages, University of<br>
Helsinki, Finland)<br>
<a href="mailto:firstname.yli-jyra@helsinki.fi">firstname.yli-jyra@helsinki.fi</a></div>
<div dir="ltr">- András Kornai (Budapest Institute of Technology, Hungary and<br>
MetaCarta, Cambridge, USA)</div>
<div dir="ltr">- Jacques Sakarovitch (CNRS and Ecole Nationale Supérieure des<br>
Télécommunications, Paris, France)</div>
<div dir="ltr"><br>
Guest Editorial Board</div>
<div dir="ltr"><font face="times new roman">---------------------------</font></div>
<div dir="ltr"><font face="times new roman"></font> </div>
<div dir="ltr">- Julie Berndsen (School of Computer Science & Informatics, University<br>
College Dublin, Ireland)<br>
- Francisco Casacuberta (Instituto Tecnologico De Informática,<br>
Valencia, Spain)<br>
- Jean-Marc Champarnaud (Université de Rouen, France)<br>
- Jan Daciuk (Gdansk University of Technology, Poland)<br>
- Manfred Droste (Institut für Informatik, Universität Leipzig,<br>
Germany)<br>
- Dafydd Gibbon (Fakultät für Linguistik und Literaturwissenschaft,<br>
University of Bielefeld, Germany)<br>
- Colin de la Higuera (University of Nantes, France)<br>
- Lauri Karttunen (Palo Alto Research Center and Department of<br>
Linguistics, Stanford University, USA)<br>
- André Kempe (CADEGE Technologies & Consulting, France)<br>
- Kevin Knight (Computer Science Department, University of Southern<br>
California)<br>
- Hans-Ulrich Krieger (DFKI GmbH, Saarbrücken, Germany)<br>
- Marco Kuhlmann (Department of Linguistics and Philology, Uppsala<br>
University, Sweden)<br>
- Andreas Maletti (Universitat Rovira i Virgili, Spain)<br>
- Stoyan Mihov (Bulgarian Academy of Sciences, Sofia, Bulgaria)<br>
- Mark-Jan Nederhof (School of Computer Science, University of St<br>
Andrews, Scotland)<br>
- Kemal Oflazer (Sabanci University, Turkey)<br>
- Jakub Piskorski (Polish Academy of Sciences, Warsaw, Poland)<br>
- Michael Riley (Google Research, New York, USA)<br>
- Strahil Ristov (Ruder Boskovic Institute, Zagreb, Croatia)<br>
- Max Silberztein (Université de Franche-Comté, France)<br>
- Bruce Watson (Dept. of Computer Science, University of Pretoria,<br>
South Africa)<br>
- Menno van Zaanen (Department of Communication and Information<br>
Sciences, Tilburg University, the Netherlands)</div>
<div dir="ltr"><br>
Contact<br>
-------</div>
<div dir="ltr">Anssi Yli-Jyrä<br>
Department of Modern Languages<br>
University of Helsinki<br>
firstname (dot) lastname-with-dash (at) helsinki (dot) fi</div>
<div dir="ltr"><font face="times new roman"></font> </div>
<div dir="ltr"><font face="times new roman"></font> </div>
</body>
</html>