Markus L. Schmid

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

Linear Time Subsequence and Supersequence Regex Matching.

[BibT_eX]

[DOI]

Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science, 2025

A Framework for Extraction and Transformation of Documents.

[BibT_eX]

[DOI]

Cristian Riveros

Proceedings of the 28th International Conference on Database Theory, 2025

A General Information Extraction Framework Based on Formal Languages.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 29th International Conference, 2025

Embracing Change: Incremental Updates of Discovered Event Queries.

[BibT_eX]

[DOI]

Proceedings of the Datenbanksysteme für Business, 2025

2024

Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration.

[BibT_eX]

[DOI]

Pawel Gawrychowski

Proc. ACM Manag. Data, November, 2024

Shortest distances as enumeration problem.

[BibT_eX]

[DOI]

Discret. Appl. Math., January, 2024

Enumeration for MSO-Queries on Compressed Trees.

[BibT_eX]

[DOI]

Markus Lohrey

Proc. ACM Manag. Data, 2024

Refl-Spanners: A Purely Regular Approach to Non-Regular Core Spanners.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2024

Regular Expressions with Backreferences: Polynomial-Time Matching Techniques.

[BibT_eX]

[DOI]

J. Autom. Lang. Comb., 2024

A Short Note on the Mutually Beneficial Relationship Between Information Extraction in Database Theory and Classical Formal Language Theory.

[BibT_eX]

[DOI]

Bull. EATCS, 2024

The Information Extraction Framework of Document Spanners - A Very Informal Survey.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2024: Theory and Practice of Computer Science, 2024

Subsequences with Generalised Gap Constraints: Upper and Lower Complexity Bounds.

[BibT_eX]

[DOI]

Jonas Richardsen

Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching, 2024

2023

Discovering Multi-Dimensional Subsequence Queries from Traces - From Theory to Practice.

[BibT_eX]

[DOI]

Proceedings of the Datenbanksysteme für Business, 2023

2022

Conjunctive Regular Path Queries with Capture Groups.

[BibT_eX]

[DOI]

ACM Trans. Database Syst., 2022

Extending Shinohara's Algorithm for Computing Descriptive (Angluin-Style) Patterns to Subsequence Patterns.

[BibT_eX]

[DOI]

CoRR, 2022

Document Spanners - A Brief Overview of Concepts, Results, and Recent Developments.

[BibT_eX]

[DOI]

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Query Evaluation over SLP-Represented Document Databases with Complex Document Editing.

[BibT_eX]

[DOI]

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Subsequences with Gap Constraints: Complexity Bounds for Matching and Analysis Problems.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Algorithms and Computation, 2022

Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints.

[BibT_eX]

[DOI]

Proceedings of the 25th International Conference on Database Theory, 2022

2021

On the Complexity of the Smallest Grammar Problem over Fixed Alphabets.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2021

Spanner Evaluation over SLP-Compressed Documents.

[BibT_eX]

[DOI]

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

A Purely Regular Approach to Non-Regular Core Spanners.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Database Theory, 2021

Fine-Grained Complexity of Regular Path Queries.

[BibT_eX]

[DOI]

Katrin Casel

Fernando Sánchez Villaamil

Proceedings of the 24th International Conference on Database Theory, 2021

2020

Pattern Matching with Variables: Efficient Algorithms and Complexity Results.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2020

Complexity of independency and cliquy trees.

[BibT_eX]

[DOI]

Erik Jan van Leeuwen

Discret. Appl. Math., 2020

Conjunctive Regular Path Queries with String Variables.

[BibT_eX]

[DOI]

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

2019

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Matching Patterns with Variables.

[BibT_eX]

[DOI]

Proceedings of the Combinatorics on Words - 12th International Conference, 2019

2018

Revisiting Shinohara's algorithm for computing descriptive patterns.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Simple picture processing based on finite automata and regular grammars.

[BibT_eX]

[DOI]

D. Gnanaraj Thomas

J. Comput. Syst. Sci., 2018

On the Complexity of Solving Restricted Word Equations.

[BibT_eX]

[DOI]

Dirk Nowotka

Int. J. Found. Comput. Sci., 2018

Consensus Strings with Small Maximum Distance and Small Distance Sum.

[BibT_eX]

[DOI]

Laurent Bulteau

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

On Matching Generalised Repetitive Patterns.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 22nd International Conference, 2018

2017

Characterization and complexity results on jumping finite automata.

[BibT_eX]

[DOI]

Vojtech Vorel

Theor. Comput. Sci., 2017

Deterministic Regular Expressions with Back-References.

[BibT_eX]

[DOI]

Dominik D. Freydenberger

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Combinatorial Properties and Recognition of Unit Square Visibility Graphs.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

Computing equality-free and repetitive string factorisations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

On the Complexity of Grammar-Based Compression over Fixed Alphabets.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

On the Solvability Problem for Restricted Classes of Word Equations.

[BibT_eX]

[DOI]

Dirk Nowotka

Proceedings of the Developments in Language Theory - 20th International Conference, 2016

2015

Contextual array grammars and array P systems.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2015

Jumping Finite Automata: Characterizations and Complexity.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2015

Pattern Matching with Variables: Fast Algorithms and New Hardness Results.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Finding Consensus Strings with Small Length Difference Between Input and Solution Strings.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Scanning Pictures the Boustrophedon Way.

[BibT_eX]

[DOI]

D. Gnanaraj Thomas

Proceedings of the Combinatorial Image Analysis - 17th International Workshop, 2015

Computing Equality-Free String Factorisations.

[BibT_eX]

[DOI]

Proceedings of the Evolving Computability - 11th Conference on Computability in Europe, 2015

2014

Characterising REGEX Languages by Regular Languages Equipped with Factor-Referencing.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 18th International Conference, 2014

Closure Properties of Pattern Languages.

[BibT_eX]

[DOI]

Joel D. Day

Proceedings of the Developments in Language Theory - 18th International Conference, 2014

2013

A note on the complexity of matching patterns with variables.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2013

Array Insertion and Deletion P Systems.

[BibT_eX]

[DOI]

Proceedings of the Unconventional Computation and Natural Computation, 2013

Two-dimensional pattern languages.

[BibT_eX]

K. G. Subramanian

Proceedings of the Fifth Workshop on Non-Classical Models for Automata and Applications - NCMA 2013, Umeå, Sweden, August 13, 2013

On the Parameterised Complexity of String Morphism Problems.

[BibT_eX]

[DOI]

Yngve Villanger

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

Pattern Matching with Variables: A Multivariate Complexity Analysis.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012

On multi-head automata with restricted nondeterminism.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2012

Automata with Modulo Counters and Nondeterministic Counter Bounds.

[BibT_eX]

[DOI]

Proceedings of the Implementation and Application of Automata, 2012

Patterns with Bounded Treewidth.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2012

Inside the Class of REGEX Languages.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 16th International Conference, 2012

Regular and Context-Free Pattern Languages over Small Alphabets.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 16th International Conference, 2012

2011

Finding Shuffle Words That Represent Optimal Scheduling of Shared Memory Access.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2011

2010

A Polynomial Time Match Test for Large Classes of Extended Regular Expressions.

[BibT_eX]

[DOI]