[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[SIGMORPHON] Special issue on Finite State Methods and Models in Natural Language Processing

Journal of Natural Language Engineering
Special issue call for papers


Unabridged call available:

The languages described by regular expressions are exactly those recognized by
finite state automata (Kleene 1956).  This fundamental result has been extended
to string transductions, sets of trees, formal power series, grammars,
semigroups, and finite models.  Furthermore, the interest in finite
equivalence relations in these systems has led to the study of families of
recognizable languages.  The study was pioneered by Schützenberger, McNaughton,
Papert and Kamp, who established the equivalence of star-free generalized
regular expressions, counter-free automata, first-order logic and temporal logic.

Kleene's theorem, its extensions and its restrictions have tremendous
methodological relevance to NLP.  Finite state methods in NLP continue to be an
area of further research and growing area.

The current special issue has two goals.  The first is to summarize the state of
the art.  The second is to increase awareness about open issues and new

The call is open to everyone.


1.  New or updated work on the traditional topics of FSMNLP workshops

2. Study of new questions raised by fundamental results in finite state
phonology and morphology

One can construct finite state transducers aka lexical transducers from
phonological and morphological grammars (Beesley and Karttunen 2003).  This
fundamental result paves the way for further study:

- less rigid formalisms and descriptive approaches used in field linguistics
- correlation between computational morphology and language development
- approaches to language clusters
- dynamically changing linguistic descriptions
- model-checking and automatic verification of grammars
- language variation and diachronic description
- portability and long-term archiving
- constructing from updated extended regular expressions
- tonal languages
- learning and training from small samples
- grammar designs
- optimality-theoretic and multi-tiered phonology
- finite state re-implementation of competitively efficient ad hoc methods (see
NLE 14(4) 2007).

3. Study of new methods with connections between languages, trees and finite
state automata

The theory of classical string automata has a natural extension to tree
automata, which found applications in NLP.  In 1982, Joshi and Levy pointed out
in Computational Linguistics 8(1) that phrase structure grammars actually
generalize to tree automata that bring more descriptive power.

Furthermore, Chomsky and Schützenberger (1963) gave a morphic representation for
the context-free languages i.e. the yields of local tree automata.  The
representation gives rise to methods between tree automata and string automata.

Please refer to the unabridged call for more information.

4. Study of advantages of restrictions defined in algebraic theories of automata
and languages or in finite model theory

In NLP, there remain situations where straightforward and general finite state
methods fail to be applicable or efficient.  These situations motivate interest
in special families of regular relations, automata, semirings, and formal power

In addition, the topics of interest include tools that support related experiments.


Deadline for submissions: 23 May 2010


- Anssi Yli-Jyrä (University of Helsinki)
firstname (dot) last-name (at) helsinki (dot) fi

- András Kornai (Budapest Institute of Technology, and MetaCarta, USA)
- Jacques Sakarovitch (CNRS, and Ecole Nationale Supérieure des
Télécommunications, France)


- Julie Berndsen
- Francisco Casacuberta
- Jean-Marc Champarnaud
- Jan Daciuk
- Manfred Droste
- Dafydd Gibbon
- Colin de la Higuera
- Lauri Karttunen
- André Kempe
- Kevin Knight
- Hans-Ulrich Krieger
- Marco Kuhlmann
- Andreas Maletti
- Stoyan Mihov
- Mark-Jan Nederhof
- Kemal Oflazer
- Jakub Piskorski
- Michael Riley
- Strahil Ristov
- Max Silberztein
- Bruce Watson
- Menno van Zaanen