Publikationen

Publications of the Theoretical Computer Science Group, University of Bayreuth

2017

  • Optimizing Tree Pattern Queries: Why Cutting Is Not Enough (Invited Talk)
    Wim Martens
    ACM Symposium on Theory of Computing (STOC 2017)
  • A Logic for Document Spanners.
    Dominik D. Freydenberger
    International Conference on Database Theory (ICDT 2017)
  • BonXai: Combining the simplicity of DTD with the expressiveness of XML Schema.
    Wim Martens, Frank Neven, Matthias Niewerth, and Thomas Schwentick
    ACM Transactions on Database Systems (TODS). To appear
  • Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data.
    Wojciech Czerwinski, Wim Martens, Matthias Niewerth, and Pawel Parys
    SIGMOD Record, 46(1)
  • Deciding Definability by Deterministic Regular Expressions. (preprint)
    Wojciech Czerwinski, Claire David, Katja Losemann, and Wim Martens
    Journal of Computer and System Sciences (JCSS). To appear
  • A Characterization for Decidable Separability by Piecewise Testable Languages. (preprint)
    Wojciech Czerwinski, Wim Martens, Lorijn van Rooijen, Marc Zeitoun, and Georg Zetzsche
    Discrete Mathematics & Theoretical Computer Science (DMTCS). To appear

2016

  • Minimization of Tree Pattern Queries. (preprint, paper, talk)
    Wojciech Czerwinski, Wim Martens, Matthias Niewerth, and Pawel Parys
    ACM Symposium on Principles of Database Systems (PODS 2016)
    SIGMOD Research Highlight Award (link)
  • Document Spanners: From Expressive Power to Decision Problems. (paper)
    Dominik D. Freydenberger and Mario Holldack
    International Conference on Database Theory (ICDT 2016)
  • Querying Graphs with Data. (preprint, paper)
    Leonid Libkin, Wim Martens, and Domagoj Vrgoc
    Journal of the ACM (J. ACM)
  • Closure Properties and Descriptional Complexity of Deterministic Regular Expressions. (preprint, paper)
    Katja Losemann, Wim Martens, and Matthias Niewerth
    Theoretical Computer Science (TCS)
  • Conjunctive Query Containment over Trees using Schema Information
    Henrik Björklund, Wim Martens, and Thomas Schwentick
    Acta Informatica

2015

  • Definability by Weakly Deterministic Regular Expressions with Counters is Decidable. (preprint)
    Markus Latte and Matthias Niewerth
    International Symposium on Mathematical Foundations of Computer Science (MFCS 2015)
  • Efficient Incremental Evaluation of Succinct Regular Expressions. (preprint)
    Henrik Björklund, Wim Martens, and Thomas Timm
    International Conference on Information and Knowledge Management (CIKM 2015)
  • A Note on Decidable Separability by Piecewise Testable Languages. (preprint, paper)
    Wojciech Czerwinski, Wim Martens, Lorijn van Rooijen, and Marc Zeitoun
    International Symposium on Fundamentals of Computation Theory (FCT 2015)
  • SCULPT: A Schema Language for Tabular Data on the Web. (preprint, slides)
    Wim Martens, Frank Neven, and Stijn Vansummeren
    International World Wide Web Conference (WWW 2015)
  • BonXai: Combining the Simplicity of DTDs with the Expressiveness of XML Schema. (preprint, paper)
    Wim Martens, Frank Neven, Matthias Niewerth, and Thomas Schwentick
    ACM Symposium on Principles of Database Systems (PODS 2015) 
  • The (Almost) Complete Guide to Tree Pattern Containment. (preprint, paper)
    Wojciech Czerwiński, Wim Martens, Paweł Parys, and Marcin Przybyłko
    ACM Symposium on Principles of Database Systems (PODS 2015)
  • Separability by Short Subsequences and Subwords. (preprint, paper)
    Piotr Hofman and Wim Martens
    International Conference on Database Theory (ICDT 2015)
  • Deciding Twig-Definability of Node-Selecting Tree Automata. (paper)
    Timos Antonopoulos, Dag Hovland, Wim Martens, and Frank Neven
    Theory on Computing Systems (TOCS) 

2014

  • Infinite-State Energy Games. (paper)
    Aziz Abdulla, Mohamed Faouzi Atig, Piotr Hofman, Richard Mayr, K. Narayan Kumar and Patrick Totzke
    Joint Meeting of Computer Science Logic and Logic in Computer Science (CSL/LICS 2014)
  • MSO Queries on Trees: Enumerating Answers Under Updates. (preprint, paper)
    Katja Losemann and Wim Martens
    Joint Meeting of Computer Science Logic and Logic in Computer Science (CSL/LICS 2014)
  • Reasoning about XML Constraints based on XML-to-relational mappings. (paper)
    Matthias Niewerth and Thomas Schwentick
    International Conference on Database Theory (ICDT 2014)
    Best paper award
  • Trace Inclusion for One-Counter Nets Revisited. (paper)
    Piotr Hofman and Patrick Totzke
    International Workshop on Reachability Problems (RP 2014)

2013

  • The Complexity of Regular Expressions and Property Paths in SPARQL. (preprint, paper)
    Katja Losemann and Wim Martens
    ACM Transactions on Database Systems (TODS), 38(4)
  • Efficient Separability of Regular Langagues by Subsequences and Suffixes. (preprint, paper)
    Wojciech Czerwinski, Wim Martens, and Tomas Masopust
    International Colloquium on Automata, Languages, and Programming (ICALP 2013)
    © Springer-Verlag
  • Complexity of Checking Bisimilarity between Sequential and Parallel Processes.  (paper)
    Wojciech Czerwinski, Petr Jancar, Martin Kot, and Zdenek Sawa
    International Symposium on Mathematical Foundations of Computer Science (MFCS 2013)
  • Validity of Tree Pattern Queries with Respect to Schema Information.  (preprint, paper)
    Henrik Björklund, Wim Martens, and Thomas Schwentick
    International Symposium on Mathematical Foundations of Computer Science (MFCS 2013)
    © Springer-Verlag
  • Deciding Definability by Deterministic Regular Expressions. (preprint)
    Wojciech Czerwinski, Claire David, Katja Losemann, and Wim Martens
    International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2013)
    © Springer-Verlag
  • Querying Graph Databases with XPath. (preprint)
    Leonid Libkin, Wim Martens, and Domagoj Vrgoc
    International Conference on Database Theory (ICDT 2013)
    © ACM
  • Containment of Pattern-Based Queries over Data Trees. (preprint)
    Claire David, Amélie Gheerbrant, Leonid Libkin, and Wim Martens
    International Conference on Database Theory (ICDT 2013).
    © ACM
  • Counting in SPARQL Property Paths: Perspectives from Theory and Practice. (paper)
    Wim Martens
    Invited Talk at the International Workshop on Logic, Language, Information, and Computation (WoLLIC 2013).
  • Multilevel Coordination Control of Modular DES. (paper)
    Jan Komenda, Tomas Masopust, and Jan H. Van Schuppen
    IEEE Conference on Decision and Control (CDC 2013).
  • On the State Complexity of the Reverse of R- and J-trivial Regular Languages. (paper)
    Galina Jiraskova and Tomas Masopust
    International Workshop on Descriptional Complexity of Formal Systems (DCFS 2013).
  • Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages. (preprint, article)
    Wouter Gelade, Tomasz Idziaszek, Wim Martens, Frank Neven, and Jan Paredaens
    Journal of Computer and System Sciences (JCSS).
    © Elsevier
  • Generating, Sampling, and Counting Subclasses of Regular Tree Languages. (preprint, article)
    Timos Antonopoulos, Floris Geerts, Wim Martens, and Frank Neven
    Theory of Computing Systems (TOCS).
    © Springer-Verlag

2012

  • Descriptional Complexity of Deterministic Regular Expressions. (preprint)
    Katja Losemann, Wim Martens, and Matthias Niewerth
    International Conference on Mathematical Foundations of Computer Science (MFCS 2012).
  • Developing and Analyzing XSDs through BonXai. (preprint)
    Wim Martens, Frank Neven, Matthias Niewerth, and Thomas Schwentick.
    International Conference on Very Large Databases (VLDB 2012). Demo paper.
  • The Complexity of Evaluating Path Expressions in SPARQL. (preprint)
    Katja Losemann and Wim Martens.
    ACM Symposium on Principles of Database Systems (PODS 2012).
    © ACM
  • Deciding Twig-Definability of Node-Selecting Tree Automata. (preprint)
    Timos Antonopoulous, Dag Hovland, Wim Martens, and Frank Neven.
    International Conference on Database Theory (ICDT 2012).
    © ACM
  • The Tractability Frontier for NFA Minimization. (preprint, article)
    Henrik Björklund and Wim Martens.
    Journal of Computer and System Sciences (JCSS), 78(1), pp. 198-210.
    © Elsevier.
  • Regular Expressions with Counting: Weak versus Strong Determinism. (preprint)
    Wouter Gelade, Marc Gyssens, and Wim Martens.
    SIAM Journal on Computing (SICOMP).
    © SIAM.

2011

  • The Complexity of Text-Preserving XML Transformations. (paper)
    Timos Antonopoulous, Wim Martens, and Frank Neven.
    ACM Symposium on Principles on Database Systems (PODS 2011).
    © ACM
  • Generating, Sampling, and Counting Subclasses of Regular Tree Languages. (paper)
    Timos Antonopoulous, Floris Geerts, Wim Martens, and Frank Neven.
    International Conference on Database Theory (ICDT 2011), pp. 30-41.
    © ACM
  • Learning Algorithms.
    Henrik Björklund, Johanna Högberg, and Wim Martens.
    Book Chapter, to appear.
  • Conjunctive Query Containment over Trees. (preprint, article)
    Henrik Björklund, Wim Martens, and Thomas Schwentick.
    Journal of Computer and System Sciences (JCSS).
    © Elsevier.
    Selected papers from DBPL 2007.
  • 30 Years of PODS in Facts and Figures. (article)
    Tom Ameloot, Maarten Marx, Wim Martens, Frank Neven, Justin Van Wees.
    SIGMOD Record 40(3), p.54-60, 2011.
    ©  ACM

2010

  • Schema Design for XML Repositories: Complexity and Tractability. (paper)
    Wim Martens, Matthias Niewerth, and Thomas Schwentick. 
    ACM Symposium on Principles on Database Systems (PODS 2010).
    © ACM
  • Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages. (paper)
    Wouter Gelade, Tomasz Idziaszek, Wim Martens and Frank Neven.
    ACM Symposium on Principles on Database Systems (PODS 2010).
    © ACM
  • Incremental XPath Evaluation. (preprint, article)
    Henrik Björklund, Wouter Gelade, and Wim Martens.
    ACM Transactions on Database Systems (ACM TODS).
    © ACM
    Selected papers from ICDT 2009.
  • Logik und Automaten: ein echtes Dreamteam. (preprint, article)
    Henrik Björklund, Wim Martens, Nicole Schweikardt, and Thomas Schwentick.
    Informatik Spektrum 33(5), pp. 452-461.
    © Springer-Verlag.

2009

  • Incremental XPath Evaluation. (paper, talk)
    Henrik Björklund, Wouter Gelade, Marcel Marquardt, and Wim Martens.
    International Conference on Database Theory (ICDT 2009), pp. 162-173.
    © ACM
  • Simplifying XML Schema: Effortless Handling of Nondeterministic Regular Expressions. (paper, talk by Wouter Gelade)
    Geert Jan Bex, Wouter Gelade, Wim Martens, and Frank Neven.
    ACM International Conference on Management of Data (SIGMOD 2009), pp. 731-744.
    © ACM
  • Regular Expressions with Counting: Weak versus Strong Determinism. (paper, talk)
    Wouter Gelade, Marc Gyssens, and Wim Martens.
    International Conference on Mathematical Foundations of Computer Science (MFCS 2009), pp. 369-381.
    © Springer-Verlag.
  • Complexity of Decision Problems for XML Schemas and Chain Regular Expressions. (paper)
    Wim Martens, Frank Neven, and Thomas Schwentick.
    SIAM Journal on Computing (SICOMP), 39(4), pp.1486-1530, 2009.
    © SIAM.
  • Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. (paper)
    Wouter Gelade, Wim Martens, and Frank Neven.
    SIAM Journal on Computing (SICOMP), 38(5), pp. 2021-2043, 2009.
    © SIAM.
  • Efficient Algorithms for Descendant-Only Tree Pattern Queries. (paper)
    Christoph Koch, Michaela Götz, and Wim Martens.
    Information Systems (IS), 34(7), pp. 602-623, 2009.
    © Elsevier.
    Selected papers from DBPL 2007.

2008

  • The Tractability Frontier for NFA Minimization. (paper, talk
    Henrik Björklund and Wim Martens.
    International Conference on Automata, Logic, and Programming (ICALP 2008), pp. 27-38.
    © Springer-Verlag.
  • Optimizing Conjunctive Queries over Trees using Schema Information. (paper
    Henrik Björklund, Wim Martens, and Thomas Schwentick.
    International Conference on Mathematical Foundations of Computer Science (MFCS 2008), pp. 132-143.
    © Springer-Verlag.
  • XML Research for Formal Language Theorists. (abstract, talk)
    Wim Martens.
    Weighted Automata: Theory and Applications (WATA 2008). Invited paper.
  • Typechecking Top-Down XML Transformations: Fixed Input or Output Schemas. (paper)
    Wim Martens, Frank Neven, and Marc Gyssens.
    Information and Computation, 206(7), pp. 806–827, 2008.
    © Elsevier.
  • Deterministic Top-Down Tree Automata: Past, Present, and Future. (paper)
    Wim Martens, Frank Neven, and Thomas Schwentick.
    In "Logic and Automata." Texts in Logic and Games, Vol. 2, pp. 515-541, 2008.
    © Amsterdam University Press.

2007

  • Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. (paper, talk by Wouter Gelade)
    Wouter Gelade, Wim Martens, and Frank Neven.
    International Conference on Database Theory (ICDT 2007), pp. 269-283.
    © Springer-Verlag.
  • Conjunctive Query Containment over Trees. (paper, talk
    Henrik Björklund, Wim Martens, and Thomas Schwentick.
    International Symposium on Database Programming Languages (DBPL 2007), pp. 66-80. 
    © Springer-Verlag.
  • Efficient Algorithms for the Tree Homeomorphism Problem. (paper
    Michaela Götz, Christoph Koch, and Wim Martens.
    International Symposium on Database Programming Languages (DBPL 2007), pp.17-31. 
    © Springer-Verlag.
  • Simple off the Shelf Abstractions for XML Schema. (paper)
    Wim Martens, Frank Neven, and Thomas Schwentick.
    SIGMOD Record, 36(3), pp. 15-22, 2007.
    © ACM
  • On the Minimization of XML Schemas and Tree Automata for Unranked Trees. (paper)
    Wim Martens and Joachim Niehren.
    Journal of Computer and System Sciences (JCSS), 73(4), pp. 550-583, 2007.
    © Elsevier.
    Selected papers from DBPL 2005.
  • Frontiers of Tractability for Typechecking Simple XML Transformations. (paper)
    Wim Martens and Frank Neven.
    Journal of Computer and System Sciences (JCSS), 73(3), pp. 362-390, 2007.
    © Elsevier.
    Selected papers from PODS 2004.

2006

  • Static Analysis of XML Transformation and Schema Languages. (thesis)
    Wim Martens.
    Ph.D. Thesis, Hasselt University, 2006.
    Awarded the "FWO-IBM Belgium Prijs voor de Informatica"
    (FWO-IBM Belgium Award for Computer Science -- Best dissertation of the year in Computer Science / Belgium).
  • Expressiveness and Complexity of XML Schema. (paper)
    Wim Martens, Frank Neven, Thomas Schwentick, and Geert-Jan Bex.
    Combined full version of ICDT 2005 and WWW 2005 papers.
    ACM Transactions on Database Systems (ACM TODS), 31(3), pp. 770-813, 2006.
    © ACM
    Selected papers from ICDT 2005.

2005

  • Which XML Schemas Admit 1-Pass Preorder Typing? (paper, talk)
    Wim Martens, Frank Neven, and Thomas Schwentick.
    International Conference on Database Theory (ICDT 2005), pp. 68-82.
    © Springer-Verlag.
  • Expressiveness of XSDs: From Practice to Theory, There and Back Again. (paper)
    Geert-Jan Bex, Wim Martens, Frank Neven, and Thomas Schwentick.
    International World Wide Web Conference (WWW 2005), pp. 712-721.
    © ACM
  • Minimizing Tree Automata for Unranked Trees. (paper, talk)
    Wim Martens and Joachim Niehren.
    International Symposium on Database Programming Languages (DBPL 2005), pp. 232-246.
    © Springer-Verlag.
  • The Typechecking Problem for XML Transformations: Methods and Formal Models. (paper, talk)
    Wim Martens.
    Methods for Modalities (M4M 2005). Invited paper.
  • On the Complexity of Typechecking Top-Down XML Transformations. (paper)
    Wim Martens and Frank Neven.
    Theoretical Computer Science (TCS), 336(1), pp. 153-180, 2005.
    © Elsevier.
    Selected papers from ICDT 2003.

2004

  • Complexity of Decision Problems for Simple Regular Expressions. (paper, talk)
    Wim Martens, Frank Neven, and Thomas Schwentick.
    International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), pp. 889-900.
    © Springer-Verlag.
  • Frontiers of Tractability for Typechecking Simple XML Transformations. (paper, talk)
    Wim Martens and Frank Neven.
    ACM Symposium on Principles of Database Systems (PODS 2004), pp. 23-34.
    © ACM

2003

  • Typechecking Top-Down Uniform Unranked Tree Transducers. (paper, talk)
    Wim Martens and Frank Neven.
    International Conference on Database Theory (ICDT 2003), pp. 64-78.
    © Springer-Verlag

Universität Bayreuth -