Publications by Project A2

In Print

Stephan Kepser. On the Complexity of RSRL. To appear in Journal of Language and Computation, Geert-Jan Kruijf, Larry Moss, and Richard Oehrle (eds.), in print.

Stephan Kepser, Uwe Mönnich, and Frank Morawietz. Regular Query Techniques for XML-Documents. In Linguistic modeling of information and Markup Languages, Dieter Metzing and Andreas Witt (eds), in press.

Uwe Mönnich. Grammar Morphisms. In Thinking Logically: a Memorial Volume for Jon Barwise, Larry Moss (ed.), in print.

2009

Hans-Jörg Tiede and Stephan Kepser. Monadic Second-Order Logic and Transitive Closure Logics over Trees. In Research on Language and Computation.
Paper

Hendrik Maryns and Stephan Kepser. MonaSearch - A Tool for Querying Linguistic Treebanks. In Treebanks and Linguistic Theories 2009, Frank Van Eynde, Anette Frank, Koenraad De Smedt (eds).

2008

Firtz Hamm and Stephan Kepser (eds.). Logics for Linguistic Structures. Trends in Linguistics 201, Mouton de Gruyter.
Book

Stephan Kepser. A Landscape of Logics for Finite Unordered Unranked Trees. In Formal Grammar 2008, Philippe de Groote, Laura Kallmeyer, Gerald Penn, and Giorgio Satta (eds.), 2008.
Paper

2007

Gerhard Jäger and Stephan Kepser. Automata, Complexity, and Optimality Theory. In Proceedings of the Colloquium "Cognitive Foundations of Interpretation", Gerlof Bouma, Irene Krämer, Joost Zwarts (eds.), pp. 95-110, 2007.
Book

Stephan Kepser and Jim Rogers. The Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars. In Mathematics of Language 10, Marcus Kracht, Gerald Penn, and Ed Stabler (eds.), 2007.
Extended abstract

Uwe Mönnich. Minimalist Syntax, Multiple Regular Tree Grammars and Direction Preserving Tree Transductions. In Proceedings Model Theoretic Syntax at 10, Jim Rogers and Stephan Kepser (eds.), workshop at ESSLLI 2007.
Paper

Jim Rogers and Stephan Kepser (eds.). Model Theoretic Syntax at 10. Proceedings, workshop at ESSLLI 2007.
Proceedings

2006

Stephan Kepser. Properties of Binary Transitive Closure Logic over Trees. In Formal Grammar 2006, Paola Monachesi, Gerald Penn, Giorgio Satta, and Shuly Wintner (eds.), pp. 77-89, 2006.
Paper

Stephan Kepser and Uwe Mönnich. Closure Properties of Linear Context-Free Tree Languages with an Application to Optimality Theory. In Theoretical Computer Science, 354(1), 82-97, 2006.
Paper
Corrigendum: Corollary 5 is true only if the CFTG is linear and non-deleting.

Hendrik Maryns. On the Implementation of Tree Automata: Limitations of the Naive Approach. In Treebanks and Linguistic Theories TLT 2006, Jan Hajic and Joakim Nivre (eds.), pp. 235-246, 2006.

Anton Nijholt, Giuseppe Scollo, and Uwe Mönnich (eds.). Algebraic Methods in Language Processing. Special issue of Theoretical Computer Science, 354 (1), 1-168, 2006.
Special issue

Hans-Jörg Tiede and Stephan Kepser. Monadic Second-Order Logic over Trees and Deterministic Transitive Closure Logics. In 13th Workshop on Logic, Language, Information and Computation, Grigori Mints (ed.), Electronic Notes in Theoretical Computer Science, Volume 165, pages 189-199, 2006.
Paper

2005

Stephan Kepser. Using MONA for Querying Linguistic Treebanks. In Proceedings HLT/EMNLP 2005, Chris Brew, Lee-Feng Chien, Katrin Kirchhoff (eds.), pp. 555-563, 2005.
Paper

Stephan Kepser and Marga Reis (eds). Linguistic Evidence - Empirical, Theoretical, and Computational Perspectives. Mouton de Gruyter, 2005
Book

2004

Stefanie Herrman, Hartmut Keck, and Stephan Kepser. A Multi-Modal Documentation System for Warao. In Proceedings LREC 2004, Maria Teresa Lino et al. (eds.), vol. IV, pp. 1377-1380, 2004.
Paper

Hartmut Keck. Dokumentationssystem ethno-linguistischer Feldforschungsdaten. M.a. thesis at the SfS, University of Tübingen. 2004.

Stephan Kepser. Querying Linguistic Treebanks with Monadic Second-Order Logic in Linear Time. In Journal of Logic, Language, and Information, 13: 457-470, 2004.

Stephan Kepser. Bidirectional Optimality for Regular Tree Languages. In Formal Grammar 2004, Gerhard Jäger, Paola Monachesi, Gerald Penn and Shuly Wintner (eds.), pp. 63-76, 2004.
Proceedings: PDF PS

Stephan Kepser. A Simple Proof of the Turing-Completeness of XSLT and XQuery. In Extreme Markup Languages 2004, Tommie Usdin et al. (eds.), 2004.
Paper

Stephan Kepser and Marga Reis (eds.). Linguistic Evidence - Empirical, Theoretical, and Computational Perspectives. Preproceedings, 2004.

Stephan Kepser, Ilona Steiner, and Wolfgang Sternefeld. Annotating and Querying a Treebank of Suboptimal Structures. In Treebanks and Linguistic Theories 2004, Sandra Kübler and Joakim Nivre (eds.), pp. 63-74, 2004.
Paper

Frank Morawietz and Uwe Mönnich. Formale Grundlagen. In Texttechnologie, Lothar Lemnitzer and Henning Lobin (eds.), pp. 109-142, Stauffenburg, 2004.

2003

Stephan Kepser. Querying Linguistic Treebanks with Monadic Second-Order Logic in Linear Time. In Proceedings Mathematics of Language (MoL8), Dick Oehrle and Jim Rogers (eds.), pp. 93-104, 2003.
Paper

Stephan Kepser. Finite Structure Query - A Tool for Querying Syntactically Annotated Corpora. In EACL 2003, Ann Copestake and Jan Hajic (eds.), pp. 179-186, 2003.
Paper

Stephan Kepser and Uwe Mönnich. Graph Properties of HPSG Feature Structures. In Formal Grammar 2003, Gerhard Jäger, Paola Monachesi, Gerald Penn, and Shuly Wintner (eds.), pp. 115-124, 2003.
Paper

Stephan Kepser and Uwe Mönnich. (Un-)Decidability Results for Head-Driven Phrase Structure Grammar. In Proceedings Algebraic Methods in Language Processing (AMiLP-3), Giuseppe Scollo and Anton Nijholt (eds.), pp. 141-152, 2003.
Paper

Stephan Kepser and Uwe Mönnich. A Note on the Complexity of Optimality Theory. In Proceedings Algebraic Methods in Language Processing (AMiLP-3), Giuseppe Scollo and Anton Nijholt (eds.), pp. 153-166, 2003.
Paper

An Operational and Denotational Approach to Non-Context-Freeness
Hans-Peter Kolb, Jens Michaelis, Uwe Mönnich, and Frank Morawietz
Theoretical Computer Science, 293(2), pp. 261-289, 2003.
(In cooperation with SFB 340 A8.)

Frank Morawietz. Two-Step Approaches to Natural Language Formalisms. Dissertation at the SfS, University of Tübingen; Mouton de Gruyter, SGG 64. 2003.

2002

Stefanie Herrmann. Warao. Erscheint in Encyclopedia of Linguistics, Chicago: Fitzroy Dearborn Publishers, 2002.
Paper: [PDF] [PS]

Stephan Kepser, Uwe Mönnich, and Frank Morawietz. Model Checking Secondary Relations. In Formal Grammar 2002, Gerhard Jäger, Paola Monachesi, Gerald Penn, and Shuly Wintner (eds.), pp. 65 - 75, 2002.
Paper

2001

Stephan Kepser. On the Complexity of RSRL. In Proceedings FG-MOL 2001, Geert-Jan Kruijf, Larry Moss, and Richard Oehrle (eds.). Electronic Notes in Theoretical Computer Science 53, Kluwer, 2001.
Paper

Uwe Mönnich, Frank Morawietz and Stephan Kepser. A Regular Query for Context-Sensitive Relations. In IRCS Workshop Linguistic Databases 2001, Steven Bird, Peter Buneman, Mark Liberman (eds.), pp. 187-195, 2001.
Abstract   Paper

Frank Morawietz and Uwe Mönnich. Model-Theoretic Description of TAGs. In Proceedings FG-MOL 2001, Geert-Jan Kruijf, Larry Moss, and Richard Oehrle (eds.). Electronic Notes in Theoretical Computer Science 53, Kluwer, 2001.
Paper

On Minimalist Attribute Grammars and Macro Tree Transducers
Jens Michaelis, Uwe Mönnnich, and Frank Morawietz
Linguistic Form and its Computation, Ch. Rohrer, A. Rossdeutscher, H. Kamp (eds), CSLI, pp. 287-326, 2001.
(In cooperation with SFB 340 A8.)

2000

Stephan Kepser. A Coalgebraic Modelling of Head-Driven Phrase Structure Grammar. In Proceedings AMiLP2000, Dirk Heylen, Anton Nijholt, G. Scollo (eds.), pp. 81-95, 2000.
Abstract Paper: [PDF] [PS]

Jens Michaelis, Uwe Mönnich and Frank Morawietz. Algebraic Description of Derivational Minimalism. In Proceedings AMiLP2000, Dirk Heylen, Anton Nijholt, G. Scollo (eds.), pp. 125-141, 2000.
(In cooperation with SFB 340 A8.)
Abstract Paper

Jens Michaelis, Uwe Mönnich and Frank Morawietz. Derivational Minimalism in Two Regular and Logical Steps. In Proceedings TAG+5 Workshop, 2000.
(In cooperation with SFB 340 A8.)
Abstract Paper

Manuscripts

Stefanie Herrmann. Abschließender Arbeitsbericht des dokumentarischen Teiles in Projekt A2.

Uwe Mönnich, Stephan Kepser and Stefanie Herrmann. Ergebnisbericht der ersten Phase (in German).

Stefanie Herrmann and Karin Krüger. Context-Based Image Indexing.

Stefanie Herrmann. Warao Demonstratives [PDF] [PS].

Stefanie Herrmann. XML-annotated fieldworker's diary, the dtd, and a style sheet.

Stephan Kepser. Computability and Complexity of RSRL.

Stephan Kepser. A Coalgebraic Modelling of Head-Driven Phrase Structure Grammar.