Abstract:
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. © 2011 The authors and IOS Press. All rights reserved.
Registro:
Documento: |
Artículo
|
Título: | Two views on crossing dependencies, language, biology and satisfiability |
Autor: | Castaño, J.M. |
Filiación: | Depto. de Computación, FCEyN, Pabellón I, Ciudad Universitaria, 1428 Buenos Aires, Argentina
|
Palabras clave: | Crossing dependencies; finite state automata; mildly context-sensitive; satisfiability; Automata theory; Biology; Computational grammars; Context free grammars; Finite automata; Palmprint recognition; Vocabulary control; Construction approaches; Context sensitive; Finite state technology; Natural languages; Propositional satisfiability; Satisfiability; Two views; Word recognition; Formal logic |
Año: | 2011
|
Volumen: | 228
|
Página de inicio: | 128
|
Página de fin: | 141
|
DOI: |
http://dx.doi.org/10.3233/978-1-60750-762-8-128 |
Título revista: | Frontiers in Artificial Intelligence and Applications
|
Título revista abreviado: | Front. Artif. Intell. Appl.
|
ISSN: | 09226389
|
Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09226389_v228_n_p128_Castano |
Referencias:
- Abney, S., Partial parsing via finite-state cascades (1995) Workshop on Robust Parsing; Eight European Summer School in Logic, Language and Information, pp. 8-15. , J. Carroll, editor
- Aloul, F.A., Markov, I.L., Sakallah, K.A., Force: A fast and easy-to-implement variable-ordering heuristic (2003) ACM Great Lakes Symposium on VLSI, pp. 116-119
- Barton, G.E., Computational complexity in two-level morphology (1986) Proc. of the 24th ACL, pp. 53-59. , New York
- Becker, T., Joshi, A., Rambow, O., Long-distance scrambling and tree adjoining grammars (1991) Proceedings of the 5th Conference of the European Chapter of the ACL, pp. 21-26. , Berlin
- Beesley, K.R., Karttunen, L., Finite state morphology (2003) CSLI Publications
- Bonfante, G., Le Roux, J., Intersection optimization is NP-Complete (2007) Sixth International Workshop on Finite-State Methods and Natural Language Processing - FSMNLP 2007, , Postdam Germany
- Castaño, J.M., (2004) Global Index Languages, , PhD thesis Brandeis University, Dept of Computer Science, Waltham, MA
- Castaño, J.M., Global index grammars and descriptive power (2004) Journal of Logic, Language and Information, 13, pp. 403-419
- Castaño, J.M., Castaño, R., Variable and Clause Ordering in An FSA Approach to Propositional Satisfiability, , Forthcoming
- Cherubini, A., Breveglieri, L., Citrini, C., Reghizzi, S., Multipushdown languages and grammars (1996) International Journal of Foundations of Computer Science, 7 (3), pp. 253-292
- Dassow, J., Paun, G., Salomaa, A., Grammars with controlled derivations (1997) Handbook of Formal Languages, 2. , G. Rozenberg and A. Salomaa, Editors Springer, Berlin
- Garey, M.R., Johnson, D.S., (1979) Computers and Intractability: A Guide to the Theory of NPCompleteness, , W. H. Freeman & Co., New York, NY, USA
- Gómez-Rodríguez, C., Weir, D., Carroll, J., Parsing mildly non-projective dependency structures (2009) Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics, EACL '09, pp. 291-299. , Stroudsburg, PA, USA Association for Computational Linguistics
- Guingne, F., Nicart, F., Finite state lazy operations in NLP (2002) Jean-Marc Champarnaud and Denis Maurel, 2608, pp. 138-147. , editors, CIAA of Lecture Notes in Computer Science Springer
- Head, T., Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors (1987) Bulletin of Mathematical Biology, pp. 737-759
- Joshi, A., Tree adjoining grammars: How much context-sensitivity is required to provide reasonable structural description? (1985) Natural Language Processing: Psycholinguistic, Computational and Theoretical Perspectives, pp. 206-250. , D Dowty L. Karttunen, and A. Zwicky, editors Chicago University Press, New York
- Jurafsky, D., Martin, J.H., (2000) Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition, , Prentice Hall Series in Artificial Intelligence. Prentice Hall, 1 edition
- Kallmeyer, L., Satta, G., A polynomial-time parsing algorithm for TT-MCTAG (2009) Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP: Volume 2 - Volume 2, pp. 994-1002. , ACL '09 Stroudsburg, PA, USA Association for Computational Linguistics
- Khabbaz, N.A., A geometric hierarchy of languages (1974) Journal of Computer and System Sciences, 8 (2), pp. 142-157
- García Menchaca, L., Rodríguez Flores, F., (2008) El Problema de la Satisfacibilidad Booleana Completo. un Algoritmo Polinomial, , Depto. de Matemática Aplicada Universidad de la Habana
- Rajasekaran, S., Tree-adjoining language parsing in O(n6) time (1996) SIAM J. of Computation, 25
- Reeder, J., Giegerich, R., Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics (2004) BMC Bioinformatics, 5, p. 104
- Rivas, E., Eddy, S.R., A dynamic programming algorithm for RNA structure prediction including pseudoknots (1999) Journal of Molecular Biology, 285 (5), pp. 2053-2068. , DOI 10.1006/jmbi.1998.2436
- Rivas, E., Eddy, S.R., The language of RNA: A formal grammar that includes pseudoknots (2000) Bioinformatics, 16 (4), pp. 334-340
- Satta, G., Recognition of linear context-free rewriting systems (1992) ACL, pp. 89-95
- Satta, G., Tree-adjoining grammar parsing and boolean matrix multiplication (1994) Computational Linguistics, 20 (2)
- Searls, D.B., String variable grammar: A logic grammar formalism for the biological language of DNA (1995) Journal of Logic Programming, 24 (1-2), pp. 73-102
- Searls, D.B., The language of genes (2002) Nature, 420 (6912), pp. 211-217. , DOI 10.1038/nature01255
- Searls, D.B., The computational linguistics of biological sequences (1993) Artificial Intelligence and Molecular Biology, pp. 47-120. , L. Hunter, editor AAAI Press
- Searls, D.B., Formal language theory and biological macromolecules (1999) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, , 117ff
- Seki Hiroyuki, Matsumura Takashi, Fujii Mamoru, Kasami Tadao, On multiple context-free grammars (1991) Theoretical Computer Science, 88 (2), pp. 191-229. , DOI 10.1016/0304-3975(91)90374-B
- Sproat, R., Morphology and computation (1992) Bradford Books, , MIT Press Cambridge, Massachusetts, USA
- Tapanainen, P., Applying a finite-state intersection grammar (1997) Emmanuel Roche and Yves Schabes, pp. 311-327. , editors, Finite-State Language Processing MIT Press, Cambridge
- Vempaty, N.R., Solving constraint satisfaction problems using finite state automata (1992) AAAI, pp. 453-458
- Weir, D., (1988) Characterizing Mildly Context-sensitive Grammar Formalisms., , PhD thesis University of Pennsylvania
- Weir, D., A geometric hierarchy beyond context-free languages (1992) Theoretical Computer Science, 104 (2), pp. 235-261
- Yu, S., Zhuang, Q., Salomaa, K., The state complexities of some basic operations on regular languages (1994) Theoretical Computer Science, 125 (2), pp. 315-328
Citas:
---------- APA ----------
(2011)
. Two views on crossing dependencies, language, biology and satisfiability. Frontiers in Artificial Intelligence and Applications, 228, 128-141.
http://dx.doi.org/10.3233/978-1-60750-762-8-128---------- CHICAGO ----------
Castaño, J.M.
"Two views on crossing dependencies, language, biology and satisfiability"
. Frontiers in Artificial Intelligence and Applications 228
(2011) : 128-141.
http://dx.doi.org/10.3233/978-1-60750-762-8-128---------- MLA ----------
Castaño, J.M.
"Two views on crossing dependencies, language, biology and satisfiability"
. Frontiers in Artificial Intelligence and Applications, vol. 228, 2011, pp. 128-141.
http://dx.doi.org/10.3233/978-1-60750-762-8-128---------- VANCOUVER ----------
Castaño, J.M. Two views on crossing dependencies, language, biology and satisfiability. Front. Artif. Intell. Appl. 2011;228:128-141.
http://dx.doi.org/10.3233/978-1-60750-762-8-128