We discuss two dichotomic views on crossing dependencies. This kind of phenomena is relevant both for natural language and biology as has been extensively argued. On one hand, we discuss an approach that looks for formalisms more powerful than context free grammars to capture the phenomena as a word recognition problem. On the other hand, we present an approach that deals with the same kind of problem, using finite state technology, but instead of treating the problem as a word recognition problem, it is solved using an automata construction approach. Unrestricted crossing dependencies are exemplified using the well known problem of propositional satisfiability.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com