On h-lexicalized restarting list automata. (English) Zbl 1462.68110
Summary: Following some previous studies on restarting list automata (RLA), we concentrate on a generalized and refined model – the h-lexicalized restarting list automaton(hLxRLA), which is useful for expressing properties of lexicalized syntax in computational linguistics. We present several subclasses of hLxRLA and provide some variants and extensions of the Chomsky hierarchy – the h-lexicalized variants of the Chomsky hierarchy. We compare the input languages of RLA, which are the languages traditionally considered in automata theory, to the so-calledbasicandh-proper languages of hLxRLA, which are used to defineh-lexicalized syntactic analysis. The h-lexicalized syntactic analysis allows us to stress several nice syntactic properties of h-lexicalized restarting automata (hRLWW). We present a transformation from monotone RLWWautomata that recognize the context-free languages (CFL) as their input languages to deterministic monotone hRLWW-automata that compute h-lexicalized syntactic analysis for the whole class CFL through their basic and h-proper languages. Through this transformation, we obtain several types of deterministic hRLWW-automata and hLxRLA-automata that cover h-lexicalized syntactic analyses of CFL and that satisfy the Complete Strong Correctness Preserving Property.
MSC:
| 68Q45 | Formal languages and automata |
Keywords:
restarting list automaton; h-lexicalized language; h-lexicalized syntactic analysis; complete strong correctness preserving property; extended Chomsky hierarchyReferences:
| [1] | A. V. Aho,J. E. Hopcroft,J. D. Ullman, A general theory of translation.Mathematical Systems Theory3(1969), 193-221. · Zbl 0175.00803 |
| [2] | N. Chomsky, Three models for the description of language.IRE Transactions on Information Theory2(1956), 113-124. · Zbl 0156.25401 |
| [3] | N. Chomsky, Formal properties of grammars. In:D. Luce,R. R. Bush,E. Galanter (eds.),Handbook of Mathematical Psychology. Vol. II, John Wiley and Sons, Inc., 1963, 323-418. · Zbl 0156.25303 |
| [4] | N. Chomsky,Syntactic Structures. Second edition, Mouton de Gruyter, Berlin, New York, 2002. · Zbl 0052.24706 |
| [5] | M. P. Chytil,M. Plátek,J. Vogel, A note on the Chomsky hierarchy.Bulletin of the EATCS27(1985), 23-30. |
| [6] | J. Hajič,J. Panevová,E. Hajičová,P. Sgall,P. Pajas,J. Štěpánek, J. Havelka,M. Mikulová,Z. Žabokrtský,M. Ševčíková-Razímová,Prague Dependency Treebank 2.0. Linguistic Data Consortium, Philadelphia, 2006. |
| [7] | J. E. Hopcroft,J. D. Ullman,Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, M.A., 1979. · Zbl 0426.68001 |
| [8] | P. Jančar,F. Mráz,M. Plátek,J. Vogel, Restarting automata. In:H. Reichel(ed.),Fundamentals of Computation Theory, 10th International Symposium, FCT ’95, Dresden, Germany, August 22-25, 1995, Proceedings. LNCS 965, Springer, Berlin, 1995, 283-292. · Zbl 1149.68052 |
| [9] | P. Jančar,F. Mráz,M. Plátek,J. Vogel, On monotonic automata with a restart operation.Journal of Automata, Languages and Combinatorics4(1999), 287-311. · Zbl 0942.68064 |
| [10] | P. Jančar,M. Plátek,J. Vogel, Generalized linear list automata. In:P. Vojtáš (ed.),ITAT 2004, Information Technologies - Applications and Theory, Workshop on Theory and Practice of Information Technologies, Proceedings, Department of Computer Science, Faculty of Science, Pavol Jozef Šafárik University, Slovakia, September 2004. Univerzita P. J. Šafárika v Košiciach, 2005, 97-105. |
| [11] | A. K. Joshi,Y. Schabes, Tree-adjoining grammars. In:G. Rozenberg,A. Salomaa(eds.),Handbook of Formal Languages. Vol. 3, Springer, Berlin, New York, 1997, 69-123. · Zbl 0798.68089 |
| [12] | A. K. Joshi,K. Vijay-Shanker,D. Weir, The convergence of mildly contextsensitive grammatical formalisms. In:P. Sells,S. Shieber,T. Wasow(eds.),Foundational Issues in Natural Language Processing. MIT Press, Cambridge, MA, 1991, 31-82. |
| [13] | T. Jurdziński,F. Otto, Shrinking restarting automata.International Journal of Foundations of Computer Science18(2007), 361-385. · Zbl 1112.68087 |
| [14] | T. Jurdziński,F. Otto,F. Mráz,M. Plátek, Deterministic two-way restarting automata and Marcus contextual grammars.Fundamenta Informaticae64(2005), 217-228. · Zbl 1102.68043 |
| [15] | M. Lopatková,M. Plátek,V. Kuboň, Modeling syntax of free word-order languages:Dependency analysis by reduction. In:V. Matoušek,P. Mautner,T. Pavelka(eds.),Text, Speech and Dialogue, 8th International Conference, TSD 2005, Karlovy Vary, Czech Republic, September 12-15, 2005, Proceedings. LNCS 3658, Springer, Berlin, 2005, 140-147. |
| [16] | M. Lopatková,M. Plátek,P. Sgall, Towards a formal model for functional generative description: Analysis by reduction and restarting automata.Prague Bulletin of Mathematical Linguistics87(2007), 7-26. |
| [17] | S. Marcus, Contextual grammars.Revue Roumaine de Mathématique Pures et Appliquées14(1969), 1473-1482. |
| [18] | F. Mráz,F. Otto,M. Plátek, The degree of word-expansion of lexicalized RRWWautomata - A new measure for the degree of nondeterminism of (context-free) languages.Theoretical Computer Science410(2009), 3530-3538. · Zbl 1191.68399 |
| [19] | F.Mráz,F.Otto,M.Plátek,CharacterizationsofLRR-languagesby correctness-preserving computations. In:R. Freund,M. Hospodár,G. Jirásková, G. Pighizzini(eds.),Tenth Workshop on Non-Classical Models of Automata and Applications (NCMA), Košice, Slovakia, August 21-22, 2018, Proceedings. books@ocg.at 332, Österreichische Computer Gesellschaft, 2018, 149-164. |
| [20] | F. Mráz,M. Plátek,M. Procházka, On special forms of restarting automata. Grammars2(1999) 3, 223-233. · Zbl 0967.68098 |
| [21] | F. Otto, Restarting automata. In:Z. Ésik,C. Martín-Vide,V. Mitrana(eds.), Recent Advances in Formal Languages and Applications. Studies in Computational Intelligence 25, Springer, Berlin, 2006, 269-303. · Zbl 1116.68044 |
| [22] | F. Otto, Left-to-right regular languages and two-way restarting automata.RAIRO - Theoretical Informatics and Applications43(2009), 653-665. · Zbl 1176.68107 |
| [23] | M. Plátek, Two-way restarting automata and j-monotonicity. In:L. Pacholski, P. Ružička(eds.),SOFSEM 2001: Theory and Practice of Informatics, 28th Conference on Current Trends in Theory and Practice of Informatics, Piešťany, Slovak Republic, November 24 - December 1, 2001, Proceedings. LNCS 2234, Springer, Berlin, 2001, 316-325. · Zbl 1052.68628 |
| [24] | M. Plátek,F. Otto, On h-lexicalized restarting automata. In:E. Csuhaj-Varjú, P. Dömösi,G. Vaszil(eds.),Proceedings of the 15th International Conference on Automata and Formal Languages, AFL 2017. EPTCS 252, Open Publishing Association, 2017, 219-233. · Zbl 1483.68180 |
| [25] | M. Plátek,F. Otto,F. Mráz, On h-lexicalized automata and h-syntactic analysis. In:J. Hlaváčová(ed.),Proceedings of the 17th Conference on Information Tech · Zbl 1250.68173 |
| [26] | M. Plátek,F. Otto,F. Mráz,On h-Lexicalized Restarting List Automata. Technical report, Fachbereich Elektrotechnik/Informatik, Universität Kassel, 2017. · Zbl 1250.68173 |
| [27] | M. Plátek,J. Vogel, Deterministic list automata and erasing graphs.Prague Bulletin of Mathematical Linguistics45(1986), 27-50. · Zbl 0589.68057 |
| [28] | D. J. Rosenkrantz, Matrix equations and normal forms for context-free grammars. Journal of the ACM14(1967), 501-507. · Zbl 0148.25102 |
| [29] | K. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
