Free Word-Order and Restarting Automata

• Autorzy: Mráz F. , Otto F. , Plátek M.

Identyfikatory

DOI

10.3233/FI-2014-1083

• Języki publikacji: EN

Abstrakty

EN

In natural languages with a high degree of word-order freedom, syntactic phenomena like dependencies (subordinations) or valences do not depend on the word-order (or on the individual positions of the individual words). This means that some permutations of sentences of these languages are in some (important) sense syntactically equivalent. Here we study this phenomenon in a formal way. Various types of j-monotonicity for restarting automata can serve as parameters for the degree of word-order freedom and for the complexity of word-order in sentences (languages). Here we combine two types of parameters on computations of restarting automata: the degree of j-monotonicity, and the number of rewrites per cycle. We study these notions formally in order to obtain an adequate tool for modelling and comparing formal descriptions of (natural) languages with different degrees of word-order freedom and word-order complexity.

Słowa kluczowe

EN

restarting automaton; word-order freedom; word-order complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 133, nr 4
• Strony: 399--419
• Opis fizyczny: Bibliogr. 26 poz.

Twórcy

autor

Mráz F.

• Department of Computer Science, Faculty of Mathematics and Physics Charles University, CZ-118 00 Praha 1, Czech Republik

autor

Otto F.

• Fachbereich Elektrotechnik/Informatik, Universität Kassel, D-34109 Kassel, Germany

autor

Plátek M.

• Department of Computer Science, Faculty of Mathematics and Physics Charles University, CZ-118 00 Praha 1, Czech Republik

Bibliografia

• [1] J. Baldridge and G.J. Kruijff. Multi-modal combinatory categorial grammar. 11th Conference of the European Chapter of the Association for Computational Linguistics, Budapest, 2003, 211–218.
• [2] M. Bodirsky, M. Kuhlmann, and M. Möhl. Well-nested drawings as models of syntactic structure. 10th Conference on Formal Grammar and Ninth Meeting on Mathematics of Language, Edinburgh, United Kingdom, 2005.
• [3] J. W. Bresnan, R. M. Kaplan, S. Peters, and A. Zaenen. Cross-serial dependencies in Dutch. Linguistic Inquiry 13 (1983) 613–635.
• [4] N. Chomsky. Syntactic Structures. Mouton & Co., 1957, reprinted 1978.
• [5] R. Debusmann, D. Duchier, and J. Niehren. The XDG grammar development kit. In: P. Van Roy (ed.), MOZ 2004, Proc., Lecture Notes in Computer Science 3389, Springer, Berlin, 2005, 188–199.
• [6] R. Gramatovici and C. Martin-Vide. Contextual grammars and dependency trees. In: B. Daille and E. Morin (eds.), Actes de TALN. 10e Conference sur le Traitement Automatique des Langues Naturelles, TALN 2003, Batz-sur-Mer, France, 2003, 135–144.
• [7] H. Haider. Argument Structure: Semantic Basis and Syntactic Effects. Class notes from the Third European Summer School in Language, Logic and Information, Saarbrücken, 1991.
• [8] T. Holan, V. Kuboň, K. Oliva, and M. Plátek. Two useful measures of word order complexity. In: A. Polguere and S. Kahane (eds.), Coling ’98, Workshop ‘Processing of Dependency-Based Grammars,’ Proc., University of Montreal, 1998, 21–28.
• [9] P. Jančar, F. Mráz, M. Plátek, and J. Vogel. On monotonic automata with a restart operation. J. Autom. Lang. Comb. 4 (1999) 283-292.
• [10] P. Jančar, F. Mráz, M. Plátek, and J. Vogel. Monotonicity of restarting automata. J. Autom. Lang. Comb. 12 (2007) 355–371.
• [11] A.K. Joshi and Y. Shabes. Tree-adjoining grammars. In: G. Rosenberg and A. Salomaa (eds.), Handbook of Formal Languages, Vol. 3, Springer, Berlin, 1997, 69–123.
• [12] T. Jurdziński, F. Mráz, F. Otto, and M. Plátek. Degrees of non-monotonicity for restarting automata. Theoretical Computer Science 369 (2006) 1–34.
• [13] T. Jurdziński and F. Otto. On left-monotone restarting automata. Mathematische Schriften Kassel 17/03, Universität Kassel, 2003.
• [14] T. Jurdziński and F. Otto. Shrinking restarting automata. International Journal of Foundations of Computer Science 18 (2007) 361–385. An extended abstract appeared in: J. Jędrzejowicz and A. Szepietowski (eds.), MFCS 2005, Proc., Lecture Notes in Computer Science 3618, Springer, Berlin, 2005, 532–543.
• [15] T. Jurdziński, F. Otto, F. Mráz, and M. Plátek. On the complexity of 2-monotone restarting automata. Theory of Computing Systems 42 (2008) 488–518.
• [16] V. Kuboň and M. Plátek. A grammar based approach to a grammar checking of free word order languages. In: COLING’94, Proc., Vol. II, Kyoto, Japan, 1994, 906–910.
• [17] M. Lopatková, M. Plátek, and P. Sgall. Towards a formal model for functional generative description, analysis by reduction and restarting automata. The Prague Bulletin of Mathematical Linguistics 87 (2007) 1–20.
• [18] F. Mráz, M. Plátek, and T. Jurdziński. Ambiguity by restarting automata. International Journal of Foundations of Computer Science 18 (2007) 1343–1352.
• [19] K. Oliva, P. Květoň, and R. Ondruška. The computational complexity of rule-based part-of-speech tagging. In: V. Matoušek and P. Mautner (eds.), TSD 2003, Proc., Lecture Notes in Computer Science 2807, Springer, Berlin, 2003, 82–89.
• [20] F. Otto. Restarting automata and their relations to the Chomsky hierarchy. In: Z. Ésik and Z. Fülöp (eds.), DLT’2003, Proc., Lecture Notes in Computer Science 2710, Springer, Berlin, 2003, 55–74.
• [21] F. Otto. Restarting automata. In: Z. Esik, C. Martin-Vide, and V. Mitrana (eds.), Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence, Vol. 25, Springer, Berlin, 2006, 269–303.
• [22] F. Otto and M. Plátek. Two-dimensional taxonomy of proper languages of lexicalized FRR-automata. In: C. Martin-Vide, F. Otto, and H. Fernau (eds.), LATA 2008, Proc., Lecture Notes in Computer Science 5196, Springer, Berlin, 2008, 409–420.
• [23] M. Plátek, M. Lopatková, and K. Oliva. Restarting automata: motivations and applications. In: M. Holzer (ed.), Workshop ‘Petrinetze’ and 13. Theorietag ‘Formale Sprachen und Automaten’, Proc., Institut für Informatik, Technische Universität München, 2003, 90–96.
• [24] M. Plátek, F. Otto, and F. Mráz. Two-dimensional hierarchies of proper languages of lexicalized FRR-automata. Information and Computation 207 (2009) 1300-1314. Extended and revised version of [22].
• [25] O. Rambow and A. Joshi. A processing model for free word order languages. In: J. C. Clifton, L. Frazier, and K. Rayner (eds.), Perspectives on Sentence Processing, Lawrence Erlbaum Associates, 1994, 267–301.
• [26] M. Steedman. Linguistic and Computational Theories of Grammar. Course at the University of Edinburgh, 2005, http://www.iccs.informatics.ed.ac.uk/˜steedman/tl/home.html.