Dr. Markus L. Schmid

I am currently working as the principal investigator of a DFG-funded project within the group "Logik in der Informatik" led by Prof. Dr. Nicole Schweikardt at Humboldt-Universität in Berlin. A project description can be found here (german, english).

My research interests are automata theory, formal language theory, (parameterised) complexity theory and database theory.

On this page, you can find information about my research and my academic activities. For contact details, please visit my university page.

The best way to reach me is by email. My email address is "x@x.de" with x = mlschmid.

Short CV


Overview of published papers:

General TCS Conferences #Papers
ICALP International Colloquium on Automata, Languages, and Programming 2
STACS International Symposium on Theoretical Aspects of Computer Science 2
MFCS International Symposium on Mathematical Foundations of Computer Science 3
FSTTCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science 1
CiE Computability in Europe 1
Database Theory Conferences
PODS Principles of Database Systems 4
ICDT International Conference on Database Theory 3
Algorithms Conferences
ISAAC International Symposium on Algorithms and Computation 1
CPM Annual Symposium on Combinatorial Pattern Matching 2
Automata and Formal Languages Conferences
DLT International Conference on Developments in Language Theory 6
LATA International Conference on Language and Automata Theory and Applications 2
CIAA International Conference Implementation and Application of Automata 3
NCMA Workshop on Non-Classical Models of Automata and Applications 1
UCNC International Conference on Unconventional Computation and Natural Computation 1
Other Specialised Conferences
IWCIA International Workshop on Combinatorial Image Analysis 1
TCS Journals
ACM TODS ACM Transactions on Database Systems 1
JCSS Journal of Computer and System Sciences 3
ToCS Theory of Computing Systems 2
Algorithmica Algorithmica 1
I&C Information and Computation 3
ACM TOCT ACM Transactions on Computation Theory 2
DCG Discrete & Computational Geometry 1
DAM Discrete Applied Mathematics 2
TCS Theoretical Computer Science 4
LMCS Logical Methods in Computer Science 1
IJFCS International Journal of Foundations of Computer Science 2
IPL Information Processing Letters 2
IJCM International Journal of Computer Mathematics 1
AMAI Annals of Mathematics and Artificial Intelligence 1
Kybernetika Kybernetika 1
JALC Journal of Automata, Languages, and Combinatorics 1

Peer reviewed publications (conferences and journals):

[PV] = Publisher's Version
[Pre] = Preprint Version
[TR] = Full Version as Technical Report
[Slides] = Conference slides
[ConfVid] = Conference video
= Video abstract   (information about video abstracts)

40.   Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds (Florin Manea, Jonas Richardsen, Markus L. Schmid)
  • CPM (accepted for publication). [TR]
39.   Shortest distances as enumeration problem (Katrin Casel, Tobias Friedrich, Stefan Neubert, Markus L. Schmid)
38.   Regular Expressions with Backreferences: Polynomial-Time Matching Techniques (Markus L. Schmid)
  • JALC (accepted for publication). [TR]
37.   Enumeration for MSO-queries on compressed trees (Markus Lohrey, Markus L. Schmid)
36.   Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems (Joel D. Day, Maria Kosche, Florin Manea, Markus L. Schmid)
35.   Query Evaluation over SLP-Represented Document Databases With Complex Document Editing (Markus L. Schmid, Nicole Schweikardt)
34.   Discovering Event Queries from Traces: Laying Foundations for Subsequence-Queries with Wildcards and Gap-Size Constraints (Sarah Kleest-Meißner, Rebecca Sattler, Markus L. Schmid, Nicole Schweikardt and Matthias Weidlich)
33.   Spanner Evaluation over SLP-Compressed Documents (Markus L. Schmid, Nicole Schweikardt)
32.   Fine-Grained Complexity of Regular Path Queries (Katrin Casel, Markus L. Schmid)
31.   A Purely Regular Approach to Non-Regular Core Spanners (Markus L. Schmid, Nicole Schweikardt)
30.   Conjunctive Regular Path Queries with String Variables (Markus L. Schmid)
29.   Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number (Katrin Casel, Joel Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea and Markus L. Schmid)
28.   Complexity of Independency and Cliquy Trees (Katrin Casel, Jan Dreier, Henning Fernau, Moritz Gobbert, Philipp Kuinke, Fernando Sánchez Villaamil, Markus L. Schmid, Erik Jan van Leeuwen)
  • DAM (Discrete Applied Mathematics), 2018. [PV]
27.   Consensus Strings with Small Maximum Distance and Small Distance Sum (Laurent Bulteau, Markus L. Schmid)
26.   On Matching Generalised Repetitive Patterns (Joel D. Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka, Markus L. Schmid)
25.   Combinatorial Properties and Recognition of Unit Square Visibility Graphs (Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, Sue Whitesides)
24.   Deterministic Regular Expressions With Back-References (Dominik D. Freydenberger and Markus L. Schmid)      
  • STACS 2017. [PV] [TR]
  • JCSS (Journal of Computer and System Sciences), 2019. [PV]
23.   On the Solvability Problem for Restricted Classes of Word Equations (Florin Manea, Dirk Nowotka, Markus L. Schmid)
  • DLT 2016. [PV] [Pre]
  • IJFCS (International Journal of Foundations of Computer Science, Special Issue of 20th International Conference on Developments in Language Theory, DLT 2016), 2018, under the title "On the Complexity of Solving Restricted Word Equations". [PV] [Pre]
22.   On the Complexity of Grammar-Based Compression over Fixed Alphabets (Katrin Casel, Henning Fernau, Serge Gaspers, Benjamin Gras, Markus L. Schmid)      
21.   Revisiting Shinohara's Algorithm for Computing Descriptive Patterns (Henning Fernau, Florin Manea, Robert Mercaş, Markus L. Schmid)      
  • TCS (Theoretical Computer Science), 2018, Special Issue on Learning Theory and Complexity. [PV] [Pre]
20.   Scanning Pictures the Boustrophedon Way (Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid, D. Gnanaraj Thomas)
  • IWCIA 2015. [PV] [Pre]
  • JCSS (Journal of Computer and System Sciences), 2018, under the title "Simple Picture Processing Based on Finite Automata and Regular Grammars". [PV]
19.   Finding Consensus Strings With Small Length Difference Between Input and Solution Strings (Markus L. Schmid)      
18.   Jumping Finite Automata: Characterizations and Complexity (Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid)
  • CIAA 2015. [PV] [Pre]
  • TCS (Theoretical Computer Science), 2016 (under the title "Characterization and complexity results on jumping finite automata" and with additional author "Vojtěch Vorel"). [PV] [Pre]
17.   Computing Equality-Free and Repetitive String Factorisations (Markus L. Schmid)      
16.   Pattern Matching with Variables: Fast Algorithms and New Hardness Results (Henning Fernau, Florin Manea, Robert Mercaş, Markus L. Schmid)      
15.   Characterising REGEX Languages by Regular Languages Equipped with Factor-Referencing (Markus L. Schmid)      
14.   Closure Properties of Pattern Languages (Joel Day, Daniel Reidenbach, Markus L. Schmid)
13.   Contextual Array Grammars and Array P Systems (Henning Fernau, Rudolf Freund, Markus L. Schmid, K. G. Subramanian, Petra Wiederhold)
  • AMAI (Annals of Mathematics and Artificial Intelligence, special journal issue on “Combinatorial and discrete geometric problems in image analysis”), 2013. [PV] [Pre]
12.   On the Parameterised Complexity of String Morphism Problems (Henning Fernau, Markus L. Schmid, Yngve Villanger)      
11.   Two-Dimensional Pattern Languages (Henning Fernau, Markus L. Schmid, K. G. Subramanian)
10.   A Note on the Complexity of Matching Patterns with Variables (Markus L. Schmid)
  • IPL (Information Processing Letters), 2013. [PV] [Pre]
9.   Array Insertion and Deletion P Systems (Henning Fernau, Rudolf Freund, Sergiu Ivanov, Markus L. Schmid, K.G. Subramanian)
8.   Pattern Matching with Variables: A Multivariate Complexity Analysis (Henning Fernau, Markus L. Schmid)      
7.   Inside the Class of REGEX Languages (Markus L. Schmid)
  • DLT 2012. [PV] [Pre] [Slides]
  • IJFCS (International Journal of Foundations of Computer Science, Special Issue of 16th International Conference on Developments in Language Theory, DLT 2012), 2013. [PV] [Pre]
6.   Regular and Context-Free Pattern Languages Over Small Alphabets (Daniel Reidenbach, Markus L. Schmid)
5.   Automata with Modulo Counters and Nondeterministic Counter Bounds (Daniel Reidenbach, Markus L. Schmid)
4.   On Multi-head Automata with Restricted Nondeterminism (Daniel Reidenbach, Markus L. Schmid)
  • IPL (Information Processing Letters), 2012. [PV] [Pre]
3.   Patterns with Bounded Treewidth (Daniel Reidenbach, Markus L. Schmid)      
  • LATA 2012. [PV] [Pre] [Slides]
  • I&C (Information and Computation, Special Issue of 6th International Conference on Language and Automata Theory and Applications, LATA 2012), 2014. [PV] [Pre]
2.   Finding Shuffle Words that Represent Optimal Scheduling of Shared Memory Access (Daniel Reidenbach, Markus L. Schmid)
  • LATA 2011. [PV] [Pre] [Slides]
  • IJCM (International Journal of Computer Mathematics, Special Issue of 5th International Conference on Language and Automata Theory and Applications, LATA 2011), 2013. [PV] [Pre]
1.   A Polynomial Time Match Test for Large Classes of Extended Regular Expressions (Daniel Reidenbach, Markus L. Schmid)

Survey Papers

Invited Talks

Other papers (workshops, national conferences, community meetings)

Academic activities


By Markus L. Schmid, last update 17 April 2024