Druckansicht der Internetadresse:

Faculty of Mathematics, Physics & Computer Science

Theoretical Computer Science (AI VII) – Prof. Dr. Wim Martens

Print page
Bookshelf

Publications

2019

Split-Correctness in Information Extraction
Johannes Doleschal, Benny Kimelfeld, Wim Martens, Yoav Nahshon, and Frank Neven.
ACM Symposium on Principles of Database Systems (PODS 2019). 
Preprint

2018

MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras
Matthias Niewerth.
ACM/IEEE Symposium on Logic in Computer Science (LICS 2018).
Paper

Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates.
Matthias Niewerth and Luc Segoufin.
ACM Symposium on Principles of Database Systems (PODS 2018). 

Paper

Chisel: Sculpting Tabular and Non-Tabular Data on the Web.
Johannes Doleschal, Nico Höllerich, Wim Martens, and Frank Neven.
Companion of the The Web Conference 2018 (WWW 2018). ​Demo paper.

Paper
DARQL: Deep Analysis of SPARQL Queries.

Angela BonifatiWim Martens, and Thomas Timm.
Companion of the The Web Conference 2018 (WWW 2018). ​Demo paper.

Paper

Evaluation and Enumeration Problems for Regular Path Queries. 
Tina Trautner and Wim Martens.
International Conference on Database Theory (ICDT 2018).
Best paper award

Paper
Talk

Satisfiability for SCULPT-schemas for CSV-like data.
Johannes Doleschal, Wim Martens, Frank Neven, and Adam Witkowski.
International Conference on Database Theory (ICDT 2018).

Paper
Talk

An Analytical Study of Large SPARQL Query Logs.
Angela Bonifati, Wim Martens, and Thomas Timm.
International Conference on Very Large Data Bases (VLDB 2018).

Paper 
Talk

Minimization of Tree Patterns.
Wojciech CzerwinskiWim MartensMatthias Niewerth, and Pawel Parys.
Journal of the ACM (J. ACM).

Paper

Conjunctive Query Containment over Trees using Schema Information.
Henrik Björklund, Wim Martens, and Thomas Schwentick.
Acta Informatica.

Preprint
Paper


2017

Optimizing Tree Pattern Queries: Why Cutting Is Not Enough.
Wim Martens.
ACM Symposium on Theory of Computing (STOC 2017).

Talk

A Logic for Document Spanners.
Dominik D. Freydenberger.
International Conference on Database Theory (ICDT 2017).

Paper

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).

Paper

Optimizing Tree Patterns for Querying Graph- and Tree-Structured Data.
Wojciech Czerwinski, Wim Martens, Matthias Niewerth, and Pawel Parys.
SIGMOD Record, 46(1).

Paper
Deciding Definability by Deterministic Regular Expressions.
Wojciech Czerwinski, Claire David, Katja Losemann, and Wim Martens.
Journal of Computer and System Sciences (JCSS).
Preprint
Paper
A Characterization for Decidable Separability by Piecewise Testable Languages.
Wojciech Czerwinski, Wim Martens, Lorijn van Rooijen, Marc Zeitoun, and Georg Zetzsche.
Discrete Mathematics & Theoretical Computer Science (DMTCS).
Paper

2016

Minimization of Tree Pattern Queries.
Wojciech Czerwinski, Wim Martens, Matthias Niewerth, and Pawel Parys.
ACM Symposium on Principles of Database Systems (PODS 2016).
SIGMOD Research Highlight Award

Paper
Talk

Document Spanners: From Expressive Power to Decision Problems.
Dominik D. Freydenberger and Mario Holldack.
International Conference on Database Theory (ICDT 2016).

Paper

Querying Graphs with Data.
Leonid Libkin, Wim Martens, and Domagoj Vrgoc.
Journal of the ACM (J. ACM).

Preprint
Paper

Closure Properties and Descriptional Complexity of Deterministic Regular Expressions.
Katja Losemann, Wim Martens, and Matthias Niewerth.
Theoretical Computer Science (TCS).

Preprint
Paper

Research Directions for Principles of Data Management (Abridged). 
Serge Abiteboul, Marcelo Arenas, Pablo Barceló, Meghyn Bienvenu, Diego Calvanese, Claire David, Richard Hull, Eyke Hüllermeier, Benny Kimelfeld, Leonid Libkin, Wim Martens, Tova Milo, Filip Murlak, Frank Neven, Magdalena Ortiz, Thomas Schwentick, Julia Stoyanovich, Jianwen Su, Dan Suciu, Victor Vianu, and Ke Yi.
SIGMOD Record 45(4).

Paper 
Full Version

2015

Definability by Weakly Deterministic Regular Expressions with Counters is Decidable.
Markus Latte and Matthias Niewerth.
International Symposium on Mathematical Foundations of Computer Science (MFCS 2015).

Preprint
Paper

Efficient Incremental Evaluation of Succinct Regular Expressions.
Henrik Björklund, Wim Martens, and Thomas Timm.
International Conference on Information and Knowledge Management (CIKM 2015).

Preprint
Paper

A Note on Decidable Separability by Piecewise Testable Languages.
Wojciech Czerwinski, Wim Martens, Lorijn van Rooijen, and Marc Zeitoun.
International Symposium on Fundamentals of Computation Theory (FCT 2015).
Preprint
Paper
SCULPT: A Schema Language for Tabular Data on the Web.
Wim Martens, Frank Neven, and Stijn Vansummeren.
International World Wide Web Conference (WWW 2015).

Preprint
Paper
Talk

BonXai: Combining the Simplicity of DTDs with the Expressiveness of XML Schema.
Wim Martens, Frank Neven, Matthias Niewerth, and Thomas Schwentick.
ACM Symposium on Principles of Database Systems (PODS 2015).
Paper
The (Almost) Complete Guide to Tree Pattern Containment.
Wojciech Czerwiński, Wim Martens, Paweł Parys, and Marcin Przybyłko.
ACM Symposium on Principles of Database Systems (PODS 2015).
Preprint
Paper
Separability by Short Subsequences and Subwords.
Piotr Hofman and Wim Martens.
International Conference on Database Theory (ICDT 2015).

Paper  
Talk

Deciding Twig-Definability of Node-Selecting Tree Automata.
Timos Antonopoulos, Dag Hovland, Wim Martens, and Frank Neven.
Theory on Computing Systems (TOCS).
Preprint
Paper
3. Dagstuhl-Erklärung zur Informatischen Bildung in der Schule
Informatik Spektrum 38(3), 244-245.
Preprint
Paper


2014

Infinite-State Energy Games.
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).
Paper
MSO Queries on Trees: Enumerating Answers Under Updates.
Katja Losemann and Wim Martens.
Joint Meeting of Computer Science Logic and Logic in Computer Science (CSL/LICS 2014).
Preprint
Paper
Reasoning about XML Constraints based on XML-to-relational mappings.
Matthias Niewerth and Thomas Schwentick.
International Conference on Database Theory (ICDT 2014).
Best paper award

Paper

Trace Inclusion for One-Counter Nets Revisited.
Piotr Hofman and Patrick Totzke.
International Workshop on Reachability Problems (RP 2014).
Paper

2013

The Complexity of Regular Expressions and Property Paths in SPARQL.
Katja Losemann and Wim Martens.
ACM Transactions on Database Systems (TODS), 38(4).
Preprint
Paper

Efficient Separability of Regular Langagues by Subsequences and Suffixes.
Wojciech Czerwinski, Wim Martens, and Tomas Masopust.
International Colloquium on Automata, Languages, and Programming (ICALP 2013).

Preprint
Paper

Complexity of Checking Bisimilarity between Sequential and Parallel Processes.
Wojciech Czerwinski, Petr Jancar, Martin Kot, and Zdenek Sawa.
International Symposium on Mathematical Foundations of Computer Science (MFCS 2013).
Paper
Validity of Tree Pattern Queries with Respect to Schema Information.
Henrik Björklund, Wim Martens, and Thomas Schwentick.
International Symposium on Mathematical Foundations of Computer Science (MFCS 2013).
Preprint
Paper
Deciding Definability by Deterministic Regular Expressions.
Wojciech Czerwinski, Claire David, Katja Losemann, and Wim Martens.
International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2013).

Preprint
Paper

Querying Graph Databases with XPath.
Leonid Libkin, Wim Martens, and Domagoj Vrgoc.
International Conference on Database Theory (ICDT 2013).

Preprint
Paper

Containment of Pattern-Based Queries over Data Trees.
Claire David, Amélie Gheerbrant, Leonid Libkin, and Wim Martens.
International Conference on Database Theory (ICDT 2013).

Preprint
Paper

Counting in SPARQL Property Paths: Perspectives from Theory and Practice.
Wim Martens.
Invited Talk at the International Workshop on Logic, Language, Information, and Computation (WoLLIC 2013).
Preprint
Paper
Multilevel Coordination Control of Modular DES.
Jan Komenda, Tomas Masopust, and Jan H. Van Schuppen.
IEEE Conference on Decision and Control (CDC 2013).
Paper
On the State Complexity of the Reverse of R- and J-trivial Regular Languages.
Galina Jiraskova and Tomas Masopust.
International Workshop on Descriptional Complexity of Formal Systems (DCFS 2013).
Paper
Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages.
Wouter Gelade, Tomasz Idziaszek, Wim Martens, Frank Neven, and Jan Paredaens.
Journal of Computer and System Sciences (JCSS).

Preprint
Paper

Generating, Sampling, and Counting Subclasses of Regular Tree Languages.
Timos Antonopoulos, Floris Geerts, Wim Martens, and Frank Neven.
Theory of Computing Systems (TOCS).

Preprint
Article

2012

Descriptional Complexity of Deterministic Regular Expressions.
Katja Losemann, Wim Martens, and Matthias Niewerth.
International Conference on Mathematical Foundations of Computer Science (MFCS 2012).

Preprint
Paper

Developing and Analyzing XSDs through BonXai.
Wim Martens, Frank Neven, Matthias Niewerth, and Thomas Schwentick.
International Conference on Very Large Databases (VLDB 2012). Demo paper.

Paper

The Complexity of Evaluating Path Expressions in SPARQL.
Katja Losemann and Wim Martens.
ACM Symposium on Principles of Database Systems (PODS 2012).

Preprint
Paper

Deciding Twig-Definability of Node-Selecting Tree Automata.
Timos Antonopoulous, Dag Hovland, Wim Martens, and Frank Neven.
International Conference on Database Theory (ICDT 2012).

Preprint
Paper

The Tractability Frontier for NFA Minimization.
Henrik Björklund and Wim Martens.
Journal of Computer and System Sciences (JCSS), 78(1), pp. 198-210.

Preprint
Paper

Regular Expressions with Counting: Weak versus Strong Determinism.
Wouter Gelade, Marc Gyssens, and Wim Martens.
SIAM Journal on Computing (SICOMP).

Preprint
Paper


2011

The Complexity of Text-Preserving XML Transformations.
Timos Antonopoulous, Wim Martens, and Frank Neven.
ACM Symposium on Principles on Database Systems (PODS 2011).

Preprint
Paper

Generating, Sampling and Counting Subclasses of Regular Tree Languages.
Timos Antonopoulous, Floris Geerts, Wim Martens, and Frank Neven.
International Conference on Database Theory (ICDT 2011), pp. 30-41.

Preprint
Paper

Two-variable logic and key constraints on data words.
Matthias Niewerth and Thomas Schwentick.
International Conference on Database Theory (ICDT 2011), pp. 138-149.

Paper

Learning Algorithms.
Henrik Björklund, Johanna Högberg, and Wim Martens.
Book Chapter.

Paper

Conjunctive Query Containment over Trees.
Henrik Björklund, Wim Martens, and Thomas Schwentick.
Journal of Computer and System Sciences (JCSS).
Selected papers from DBPL 2007.

Preprint
Paper

30 Years of PODS in Facts and Figures.
Tom Ameloot, Maarten Marx, Wim Martens, Frank Neven, and Justin Van Wees.
SIGMOD Record 40(3), p.54-60, 2011.

Preprint
Paper


2010

Schema Design for XML Repositories: Complexity and Tractability.
Wim Martens, Matthias Niewerth, and Thomas Schwentick. 
ACM Symposium on Principles on Database Systems (PODS 2010).

Paper

Simplifying XML Schema: Single-Type Approximations of Regular Tree Languages.
Wouter Gelade, Tomasz Idziaszek, Wim Martens, and Frank Neven.
ACM Symposium on Principles on Database Systems (PODS 2010).
Preprint
Paper

Incremental XPath Evaluation.
Henrik Björklund, Wouter Gelade, and Wim Martens.
ACM Transactions on Database Systems (ACM TODS).

Preprint
Paper

Logik und Automaten: ein echtes Dreamteam.
Henrik Björklund, Wim Martens, Nicole Schweikardt, and Thomas Schwentick.
Informatik Spektrum 33(5), pp. 452-461.

Preprint
Paper


2009

Incremental XPath Evaluation.
Henrik Björklund, Wouter Gelade, Marcel Marquardt, and Wim Martens.
International Conference on Database Theory (ICDT 2009), pp. 162-173.

Preprint
Paper
Talk

Simplifying XML Schema: Effortless Handling of Nondeterministic Regular Expressions.
Geert Jan Bex, Wouter Gelade, Wim Martens, and Frank Neven.
ACM International Conference on Management of Data (SIGMOD 2009), pp. 731-744.

Preprint
Paper
Talk by W. Gelade

Regular Expressions with Counting: Weak versus Strong Determinism.
Wouter Gelade, Marc Gyssens, and Wim Martens.
International Conference on Mathematical Foundations of Computer Science (MFCS 2009), pp. 369-381.

Preprint
Paper
Talk

Complexity of Decision Problems for XML Schemas and Chain Regular Expressions.
Wim Martens, Frank Neven, and Thomas Schwentick.
SIAM Journal on Computing (SICOMP), 39(4), pp.1486-1530, 2009.

Preprint
Paper

Optimizing Schema Languages for XML: Numerical Constraints and Interleaving.
Wouter Gelade, Wim Martens, and Frank Neven.
SIAM Journal on Computing (SICOMP), 38(5), pp. 2021-2043, 2009.

Preprint
Paper

Efficient Algorithms for Descendant-Only Tree Pattern Queries.
Christoph Koch, Michaela Götz, and Wim Martens.
Information Systems (IS), 34(7), pp. 602-623, 2009.
Selected papers from DBPL 2007.

Preprint
Paper


2008

The Tractability Frontier for NFA Minimization.
Henrik Björklund and Wim Martens.
International Conference on Automata, Logic, and Programming (ICALP 2008), pp. 27-38.

Preprint
Paper
Talk

Optimizing Conjunctive Queries over Trees using Schema Information.
Henrik Björklund, Wim Martens, and Thomas Schwentick.
International Conference on Mathematical Foundations of Computer Science (MFCS 2008), pp. 132-143.

Preprint
Paper

XML Research for Formal Language Theorists.
Wim Martens.
Weighted Automata: Theory and Applications (WATA 2008).
Invited paper.

Abstract
Talk
Typechecking Top-Down XML Transformations: Fixed Input or Output Schemas.
Wim Martens, Frank Neven, and Marc Gyssens.
Information and Computation, 206(7), pp. 806–827, 2008.

Preprint
Paper

Deterministic Top-Down Tree Automata: Past, Present, and Future.
Wim Martens, Frank Neven, and Thomas Schwentick.
In "Logic and Automata." Texts in Logic and Games, Vol. 2, pp. 515-541, 2008.

Preprint
Paper


2007

Optimizing Schema Languages for XML: Numerical Constraints and Interleaving.
Wouter Gelade, Wim Martens, and Frank Neven.
International Conference on Database Theory (ICDT 2007), pp. 269-283.

Preprint
Paper
Talk by W. Gelade

Conjunctive Query Containment over Trees.
Henrik Björklund, Wim Martens, and Thomas Schwentick.
International Symposium on Database Programming Languages (DBPL 2007), pp. 66-80. 

Preprint
Paper
Talk

Efficient Algorithms for the Tree Homeomorphism Problem.
Michaela Götz, Christoph Koch, and Wim Martens.
International Symposium on Database Programming Languages (DBPL 2007), pp.17-31.

Preprint
Paper

Simple off the Shelf Abstractions for XML Schema.
Wim Martens, Frank Neven, and Thomas Schwentick.
SIGMOD Record, 36(3), pp. 15-22, 2007.

Preprint
Paper

On the Minimization of XML Schemas and Tree Automata for Unranked Trees.
Wim Martens and Joachim Niehren.
Journal of Computer and System Sciences (JCSS), 73(4), pp. 550-583, 2007.
Selected papers from DBPL 2005.

Preprint
Paper

Frontiers of Tractability for Typechecking Simple XML Transformations.
Wim Martens and Frank Neven.
Journal of Computer and System Sciences (JCSS), 73(3), pp. 362-390, 2007.
Selected papers from PODS 2004.

Preprint
Paper


2006

Static Analysis of XML Transformation and Schema Languages.
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).

Thesis

Expressiveness and Complexity of XML Schema.
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.
Selected papers from ICDT 2005.

Preprint
Paper


2005

Which XML Schemas Admit 1-Pass Preorder Typing?
Wim Martens, Frank Neven, and Thomas Schwentick.
International Conference on Database Theory (ICDT 2005), pp. 68-82.

Preprint
Paper
Talk

Expressiveness of XSDs: From Practice to Theory, There and Back Again.
Geert-Jan Bex, Wim Martens, Frank Neven, and Thomas Schwentick.
International World Wide Web Conference (WWW 2005), pp. 712-721.

Preprint
Paper

Minimizing Tree Automata for Unranked Trees.
Wim Martens and Joachim Niehren.
International Symposium on Database Programming Languages (DBPL 2005), pp. 232-246.

Preprint
Paper
Talk

The Typechecking Problem for XML Transformations: Methods and Formal Models.
Wim Martens.
Methods for Modalities (M4M 2005).
Invited paper.

Paper
Talk

On the Complexity of Typechecking Top-Down XML Transformations.
Wim Martens and Frank Neven.
Theoretical Computer Science (TCS), 336(1), pp. 153-180, 2005.
Selected papers from ICDT 2003.

Preprint
Paper


2004

Complexity of Decision Problems for Simple Regular Expressions.
Wim Martens, Frank Neven, and Thomas Schwentick.
International Symposium on Mathematical Foundations of Computer Science (MFCS 2004), pp. 889-900.

Preprint
Paper
Talk

Frontiers of Tractability for Typechecking Simple XML Transformations.
Wim Martens and Frank Neven.
ACM Symposium on Principles of Database Systems (PODS 2004), pp. 23-34.

Preprint
Paper
Talk


2003

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

Preprint
Paper
Talk


Webmaster: Johannes Doleschal

Facebook Twitter Youtube-Kanal Instagram Blog Contact