In the seminar the subject of mathematical (computational) linguistics is defined, its foundations and relation to related fields such as: general linguistics, computer science, artificial intelligence, various special fields of mathematics (especially the theory of formal languages and automata theory, algebra and other). The main objective consists in how natural language (rather than a formal one, e.g. a programming language) can be processed by exact mathematical and computer science methods and formalisms, the stress being laid on morphology and syntax. The basic elements of the theory of

Je vymezen předmět matematické lingvistiky, její základy a vztah k obecné lingvistice, matematice a informatice. Studují se matematické a informatické metody a formalismy pro popis přirozených jazyků s důrazem na morfologii a syntax. Hlavní strukturní vlastnosti přirozených jazyků se vystihují formálními gramatikami a automaty s důrazem na jejich generativní a explikativní sílu. Rovněž se studují základní vlastnosti lexikální, morfologické a syntaktické analýzy přirozených jazyků.

F. Čermák (1994): Jazyk a jazykověda. Pražská imaginace. Praha.

V. Fromkin, R. Rodman (1978): An Introduction to Language. Holt, Rinehart and Winston, New York.

A. V. Gladkij, I. A. Mel'čuk (1969): Elementy matematičeskoj lingvistiki. Moskva.

A. V. Gladkij (1973): Formal'nyje grammatiki i jazyki. Moskva.

Hajič J. (in press): Disambiguation of Rich Inflection (Computational Morphology of Czech), Vol. 1. Karolinum Charles University Press, Prague.

Harrison, M.A. (1978): Introduction to Formal Language Theory. Addison-Wesley Publ. Comp, Inc., Reading (Mass.).

Hajičová E., J. Panevová, P. Sgall (2002): Úvod do teoretické a počítačové lingvistiky. I. svazek - Teoretická lingvistika. Nakladatelství Karolinum, Univerzita Karlova v Praze, Praha.

Roland Hausser (2001): Foundations of Computational Linguistics. Human-Computer Communication in Natural Language. Springer-Verlag, Berlin, Heidelberg, New York.

J. E. Hopcroft, J. D. Ullman (1978): Formálne jazyky a automaty. Alfa, Bratislava.

Chomsky N. (1957): Syntactic Structures. Mouton, The Hague.

M. Chytil (1978): Teorie automatů a formálních jazyků. [Lecture notes.] SPN, Praha.

M. Chytil (1984): Automaty a gramatiky. SNTL Praha.

Karlsson F., Voutilainen A., Heikkilä J., Antilla A. (eds.) (1995): Constraint Grammar. A Language-Independent System for Parsing Unrestricted Text. Mouton de Gruyter, Berlin New York.

G. K. Krulee (1991): Computer Processing of Natural Language. Prentice-Hall, Inc., New Jersey.

J. Lyons (1968): Introduction to General Linguistics. Cambridge University Press, Cambridge.

Marcus S. (1969): Algebraické modely v lingvistice. Academia, Praha.

Mel'čuk I. A. (1988): Dependency Syntax. State University of New York Press, Albany.

Nebeský L. (1987): Kombinatorické vlastnosti větných struktur. Acta Universitatis Carolinae, Philologica, Monographia XCV - 1987, Univerzita Karlova, Praha.

Novotný M. (1988): S algebrou od jazyka ke gramatice a zpět. Academia, Praha.

Oliva K., M. Hnátková, V. Petkevič, P. Květoň (2000): The Linguistic Basis of a Rule-Based Tagger of Czech. Text, Speech and Dialogue. Proceedings of the Third International Workshop, TSD 2000, LNAI 1902, Brno 2000, 3-8.

B.H. Partee, A. ter Meulen, R. E. Wall (1990): Mathematical Methods in Linguistics. Kluwer Academic Publishers. Dordrecht, Boston, London.

Roche E., Y. Schabes (eds.) (1997): Finite-State Language Processing. The Massachusetts Institute of Technology, Mass.

Rozenberg, G., A. Salomaa (eds.) (1997): Handbook of Formal Languages. Springer-Verlag Berlin Heidelberg.

Sgall P. et al. (1986): Úvod do syntaxe a sémantiky. Academia, Praha.

Tesniere L. (1959): Eléments de syntaxe structurale. Klincksieck, Paris.

A. What is mathematical linguistics (ML in the sequel)?

• definition of concepts: natural language processing (NLP); computational linguistics; formal linguistics; statistical linguistics; quantitative linguistics; algebraic linguistics; applied linguistics

• relation of ML to mathematics, especially to: the theory of formal languages and automata; algebra; mathematical logic; probability and statistics; relation of ML to logic and to computer science

• natural and artificial languages

• computational analysis and synthesis of language: an outline

• the tasks and objectives of ML

B. The foundations of the mathematical theory of languages: theory of formal languages and automata

• formal generative grammars - Chomsky hierarchy of grammars and automata and its linguistic motivation

• generative and recognizing procedures

• recursion, recursive and recursively-enumerable languages

• relation of formal grammars and languages (natural and artificial)

• linguistically motivated examples of formal languages generated by these grammars

• generative (weak) and explicative power of grammars

C. Immediate-constituent phrase-structure grammars

• motivation and definition of immediate-constituent grammars

• main features of immediate-constituent grammars

• word order and hierarchical constituent structure

• languages generated by immediate-constituent grammars and their properties

• immediate-constituent tree

D. Introduction to transformational grammars

• base component, phrase-structure, phrase-structure grammar, phrase-marker

• transformation (preserving and nonpreserving meaning), transformational grammar

• deep and surface structure of sentence

• pros and cons of transformational grammars

E. Introduction to automata theory

• automata as mathematical structures (devices)

• types of automata from the viewpoint of their weak (generative) power and their relation to formal grammars: finite-state automata, pushdown store automata, linear-bounded automata, Turing machines

• automata as acceptors and generators

• examples of natural (sub)languages processed by various kinds of automata

• the exploitation of finite-state automata for the processing of morphology and syntax of natural languages; two-level morphology

F. Dependency grammars

• basic characteristics of dependency grammars

• generative and explicative power of dependency grammars, their comparison with the Chomsky hierarchy and their status within the theory of formal languages

• algebraic sentence representation in the dependency framework: directed graph

• word order

• projectivity and nonprojectivity of syntactic structures, unbounded dependencies

• coordination and its description in dependency grammar

• comparison of immediate-constituent and dependency grammars from the aspect of explicative power

• convergence of immediate-constituent and dependency grammars: attempt at reconciliation

G. Categorial grammars

• basic characteristics of categorial grammars

• reasons for introducing categorial grammars and their adequacy for various types of languages

• relation of categorial grammars to immediate-constituent and dependency grammars

F. Structural complexity of natural languages from the Chomsky hierarchy perspective

• Capabilities and limitations of regular and context-free grammars for the description of various morphological and syntactic phenomena in natural languages

• Context-sensitive languages. Typically context-sensitive structures in natural languages

• Grammars on the boundary between context-free and context-sensitive languages: indexed grammars, tree-adjoining (TAG) grammars, head grammars

H. Automatic morphological analysis and disambiguation of natural languages

• main objective and problems of morphological analysis

• lemmatization of word forms and multi-word expressions

• morphological disambiguation, its problems and methods

• ambiguity in natural languages, its types and methods of discrimination

A. Co je MATEMATICKÁ LINGVISTIKA (dále ML)?

• vymezení pojmů: počítačové zpracování přirozeného jazyka; počítačová (komputační) lingvistika; formální lingvistika; statistická lingvistika; kvantitativní lingvistika; algebraická lingvistika; aplikovaná lingvistika

• vztah ML k matematice, zejména k: matematické teorii (formálních) jazyků a automatů; algebře; matematické logice; pravděpodobnosti a statistice; vztah ML k logice; vztah ML k informatice

• přirozené a umělé jazyky

• počítačová analýza a syntéza jazyka - nástin

• úkoly počítačové lingvistiky

B. Základy matematické teorie jazyků: teorie formálních jazyků

• formální generativní gramatiky - Chomského hierarchie gramatik a jazyků a její motivace

• generativní a rekognoskativní procedury

• rekurzivita, rekurzívní a rekurzívně-spočetné jazyky

• vztah formálních gramatik a jazyků (přirozených a umělých)

• lingvisticky motivované příklady formálních gramatik a jazyků generovaných těmito gramatikami

• generativní (slabá) a explikativní síla gramatik

C. Bezprostředněsložkové gramatiky

• motivace a definice bezprostředněsložkových gramatik

• hlavní vlastnosti bezprostředněsložkových gramatik

• slovosled a hierarchická složková struktura

• jazyk vymezený bezprostředněsložkovou gramatikou a jeho vlastnosti

• bezprostředněsložkový strom

D. Úvod do transformačních gramatik

• báze, frázová gramatika, transformační gramatika, frázový ukazatel

• transformace (zachovávající a nezachovávající význam), transformační gramatiky

• hloubková a povrchová struktura věty

• výhody a nevýhody transformačních gramatik

E. Úvod do teorie automatů

• automaty jako matematické struktury (zařízení)

• typy automatů z hlediska slabé (generativní) síly a jejich vztah k formálním gramatikám: konečné automaty, zásobníkové automaty, lineárně omezené automaty, Turingovy stroje

• automaty jakožto akceptory a generátory

• říklady přirozených (pod)jazyků zpracovávaných určitými typy automatů

• využití konečných automatů pro zpracování morfologie a syntaxe přirozených jazyků; dvoustupňová morfologie

F. Závislostní gramatiky

• základní charakteristika závislostních gramatik

• generativní a explikativní síla závislostních gramatik, jejich porovnání s Chomského hierarchií a jejich postavení v rámci teorie formálních jazyků

• algebraická reprezentace věty v závislostním pojetí - orientovaný strom

• slovosled

• projektiva a neprojektivita syntaktických struktur

• koordinace a její zachycení v závislostní gramatice

• srovnání bezprostředně-složkových a závislostních gramatik z hlediska explicitní síly

• přibližování bezprostředně-složkových a závislostních gramatik - pokus o smíření

G. Kategoriální gramatiky

• základní charakteristika kategoriálních gramatik

• smysl kategoriálních gramatik a jejich vhodnost pro různé typy jazyků

• vztah kategoriálních gramatik k bezprostředněsložkovým a závislostním gramatikám

F. Strukturní složitost přirozených jazyků z hlediska Chomského hierarchie

• Možnosti a meze regulárních a bezkontextových gramatik pro zachycení různých morfologických a syntaktických jevů v přirozených jazycích

• Kontextové jazyky. Typicky kontextové struktury přirozených jazyků

• Jazyky a formalismy na pomezí bezkontextových a kontextových jazyků: indexové gramatiky, tree-adjoining gramatiky (TAG), head gramatiky

H. Automatická morfologická analýza a disambiguace přirozených jazyků

• hlavní úkol a problémy morfologické analýzy

• lemmatizace slovních tvarů i víceslovných výrazů

• morfologická disambiguace, její problémy a metody

• homonymie v přirozených jazycích, její typy a odstraňování