Thomas Schwentick Papers on DiSC'02 String Operations in Query Languages Publications Note: Links lead to the DBLP on the Web. Thomas Schwentick 35 Frank Neven , Thomas Schwentick: Query automata over finite trees. TCS 275 (1-2): 633-674 (2002) 34 Thomas Schwentick, Denis Thérien , Heribert Vollmer : Partially-Ordered Two-Way Automata: A New Characterization of DA. Developments in Language Theory 2001 : 239-250 33 Thomas Eiter , Georg Gottlob , Thomas Schwentick: Second-Order Logic over Strings: Regular and Non-regular Fragments. Developments in Language Theory 2001 : 37-56 32 Michael Benedikt , Leonid Libkin , Thomas Schwentick, Luc Segoufin : A Model-Theoretic Approach to Regular String Relations. LICS 2001 : 431- 31 Frank Neven , Thomas Schwentick, Victor Vianu : Towards Regular Languages over Infinite Alphabets. MFCS 2001 : 560-572 30 Michael Benedikt , Leonid Libkin , Thomas Schwentick, Luc Segoufin : String Operations in Query Languages. PODS 2001 29 Martin Grohe , Thomas Schwentick, Luc Segoufin : When is the evaluation of conjunctive queries tractable? STOC 2001 : 657-666 28 Clemens Lautemann , Pierre McKenzie , Thomas Schwentick, Heribert Vollmer : The Descriptive Complexity Approach to LOGCFL. JCSS 62 (4): 629-652 (2001) 27 Georg Gottlob , Phokion G. Kolaitis , Thomas Schwentick: Existential Second-Order Logic over Graphs: Charting the Tractability Frontier. FOCS 2000 : 664-674 26 Thomas Schwentick: Logically defined queries on trees. Grundlagen von Datenbanken 2000 : 96-100 25 Frank Neven , Thomas Schwentick: On the Power of Tree-Walking Automata. ICALP 2000 : 547-560 24 Pierre McKenzie , Thomas Schwentick, Denis Thérien , Heribert Vollmer : The Many Faces of a Translation. ICALP 2000 : 890-901 23 Thomas Schwentick: On Diving in Trees. MFCS 2000 : 660-669 22 Frank Neven , Thomas Schwentick: Expressive and Efficient Pattern Languages for Tree-Structured Data. PODS 2000 : 145-156 21 Martin Grohe , Thomas Schwentick: Locality of order-invariant first-order formulas. TOCL 1 (1): 112-130 (2000) 20 Frank Neven , Thomas Schwentick: Automata for Unary Queries on Trees. Grundlagen von Datenbanken 1999 : 102-106 19 Frank Neven , Thomas Schwentick: Query Automata. PODS 1999 : 205-214 18 Clemens Lautemann , Nicole Schweikardt , Thomas Schwentick: A Logical Characterisation of Linear Time on Nondeterministic Turing Machines. STACS 1999 : 143-152 17 Clemens Lautemann , Pierre McKenzie , Thomas Schwentick, Heribert Vollmer : The Descriptive Complexity Approach to LOGCFL. STACS 1999 : 444-454 16 Thomas Schwentick: Descriptive Complexity, Lower Bounds and Linear Time. CSL 1998 : 9-28 15 Martin Grohe , Thomas Schwentick: Locality of Order-Invariant First-Order Formulas. MFCS 1998 : 437-445 14 Thomas Schwentick, Klaus Barthelmann : Local Normal Forms for First-Order Logic with Applications to Games and Automata. STACS 1998 : 444-454 13 Clemens Lautemann , Pierre McKenzie , Thomas Schwentick, Heribert Vollmer : The Descriptive Complexity Approach to LOGCFL. Electronic Colloquium on Computational Complexity (ECCC) 5 (59): (1998) 12 Clemens Lautemann , Thomas Schwentick, Iain A. Stewart : Positive Versions of Polynomial Time. Information and Computation 147 (2): 145-170 (1998) 11 Arnaud Durand , Clemens Lautemann , Thomas Schwentick: Subclasses of Binary NP. Journal of Logic and Computation 8 (2): 189-207 (1998) 10 Thomas Schwentick: Padding and the Expressive Power of Existential Second-Order Logics. CSL 1997 : 461-477 9 Thomas Schwentick: Algebraic and Logical Characterizations of Deterministic Linear Time Classes. STACS 1997 : 463-474 8 Clemens Lautemann , Thomas Schwentick, Iain A. Stewart : On Positive P. IEEE Conference on Computational Complexity 1996 : 162-170 7 Thomas Schwentick: On Bijections vs. Unary Functions. STACS 1996 : 415-426 6 Thomas Schwentick: On Winning Ehrenfeucht Games and Monadic NP. Annals of Pure and Applied Logic 79 (1): 61-92 (1996) 5 Thomas Schwentick: Graph Connectivity, Monadic NP and Built-in Relations of Moderate Degree. ICALP 1995 : 405-416 4 Frederic Green , Johannes Köbler , Kenneth W. Regan , Thomas Schwentick, Jacobo Torán : The Power of the Middle Bit of a #P Function. JCSS 50 (3): 456-467 (1995) 3 Clemens Lautemann , Thomas Schwentick, Denis Thérien : Logics For Context-Free Languages. CSL 1994 : 205-216 2 Thomas Schwentick: Graph Connectivity and Monadic NP. FOCS 1994 : 614-622 1 Ulrich Hertrampf , Clemens Lautemann , Thomas Schwentick, Heribert Vollmer , Klaus W. Wagner : On the Power of Polynomial Time Bit-Reductions (Extended Abstract). Structure in Complexity Theory Conference 1993 : 200-207 DiSC'02 © 2003 Association for Computing Machinery