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

• 2005 - 2009: University studies in computer science, Goethe University Frankfurt, Germany.
• 2009 - 2012: PhD in theoretical computer science, Loughborough University, United Kingdom, supervised by Daniel Reidenbach. Title of PhD thesis: "On the Membership Problem for Pattern Languages and Related Topics".
• 2012 - 2019: Researcher, Theoretical Computer Science research group, Trier University, Germany.
• 2019 - 2023: Principal Investigator, DFG-Project (Eigene Stelle), HU Berlin, Germany.
• Since 2023: Principal Investigator, DFG-Project (Eigene Stelle), HU Berlin, Germany.

Publications

Overview of published papers:

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)

41.	Revisiting Weighted Information Extraction: A Simpler and Faster Algorithm for Ranked Enumeration (Paweł Gawrychowski, Florin Manea, Markus L. Schmid) PODS 2025 (accepted for publication). [TR]
40.	Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds (Florin Manea, Jonas Richardsen, Markus L. Schmid) CPM 2024. [PV] [TR]
39.	Shortest distances as enumeration problem (Katrin Casel, Tobias Friedrich, Stefan Neubert, Markus L. Schmid) DAM. [PV]
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) PODS 2024. [PV] [TR] [ConfVid]
36.	Subsequences With Gap Constraints: Complexity Bounds for Matching and Analysis Problems (Joel D. Day, Maria Kosche, Florin Manea, Markus L. Schmid) ISAAC 2022. [PV] [TR]
35.	Query Evaluation over SLP-Represented Document Databases With Complex Document Editing (Markus L. Schmid, Nicole Schweikardt) PODS 2022. [PV] [Slides] [ConfVid]
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) ICDT 2022. [PV] [ConfVid]
33.	Spanner Evaluation over SLP-Compressed Documents (Markus L. Schmid, Nicole Schweikardt) PODS 2021. [PV] [TR] [Slides] [ConfVid]
32.	Fine-Grained Complexity of Regular Path Queries (Katrin Casel, Markus L. Schmid) ICDT 2021. [PV] [TR] [Slides] [ConfVid] LMCS (Logical Methods in Computer Science), 2023. [PV]
31.	A Purely Regular Approach to Non-Regular Core Spanners (Markus L. Schmid, Nicole Schweikardt) ICDT 2021. [PV] [TR] [Slides] [ConfVid] LMCS (Logical Methods in Computer Science), accepted for publication.
30.	Conjunctive Regular Path Queries with String Variables (Markus L. Schmid) PODS 2020. [PV] [TR] [ConfVid] ACM TODS (ACM Transactions on Database Systems), 2022. [PV]
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) ICALP 2019. [PV] [TR] [Slides]
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) MFCS 2018. [PV] [Slides] Algorithmica, 2019. [PV] [Pre]
26.	On Matching Generalised Repetitive Patterns (Joel D. Day, Pamela Fleischmann, Florin Manea, Dirk Nowotka, Markus L. Schmid) DLT 2018. [PV] [Pre]
25.	Combinatorial Properties and Recognition of Unit Square Visibility Graphs (Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, Sue Whitesides) MFCS 2017. [PV] [TR] [Slides] DCG (Discrete & Computational Geometry). [PV]
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)       ICALP 2016. [PV] [Pre] [Slides] ToCS (Theory of Computing Systems), 2021. [PV]
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)       MFCS 2015. [PV] [Pre] [Slides] ACM TOCT (ACM Transactions on Computation Theory), 2017. [PV] [Pre]
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)       CiE 2015. [PV] [Pre] [Slides] TCS (Theoretical Computer Science), 2016. [PV] [Pre]
16.	Pattern Matching with Variables: Fast Algorithms and New Hardness Results (Henning Fernau, Florin Manea, Robert Mercaş, Markus L. Schmid)       STACS 2015. [PV] [Pre] [Slides] ACM TOCT (ACM Transactions on Computation Theory), 2020. [PV] [Pre]
15.	Characterising REGEX Languages by Regular Languages Equipped with Factor-Referencing (Markus L. Schmid)       DLT 2014. [PV] [Pre] [Slides] I&C (Information and Computation), 2016. [PV] [Pre]
14.	Closure Properties of Pattern Languages (Joel Day, Daniel Reidenbach, Markus L. Schmid) DLT 2014. [PV] [Pre] [Slides] JCSS (Journal of Computer and System Sciences), 2017. [PV] [Pre]
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)       FSTTCS 2013. [PV] [Pre] [Slides] ToCS (Theory of Computing Systems), 2015. [PV] [Pre]
11.	Two-Dimensional Pattern Languages (Henning Fernau, Markus L. Schmid, K. G. Subramanian) NCMA 2013. [PV] [Pre] [TR]
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) UCNC 2013. [PV] [Pre]
8.	Pattern Matching with Variables: A Multivariate Complexity Analysis (Henning Fernau, Markus L. Schmid)       CPM 2013. [PV] [Pre] [Slides] I&C (Information and Computation), 2015. [PV] [Pre]
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) DLT 2012. [PV] [Pre] [Slides] TCS (Theoretical Computer Science), 2014. [PV] [Pre]
5.	Automata with Modulo Counters and Nondeterministic Counter Bounds (Daniel Reidenbach, Markus L. Schmid) CIAA 2012. [PV] [Pre] [Slides] Kybernetika, 2014. [PV] [Pre]
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) CIAA 2010. [PV] [Pre] [TR] [Slides] [additional content]

Survey Papers

• The Information Extraction Framework of Document Spanners - A Very Informal Survey (Markus L. Schmid), SOFSEM 2024, [PV]
• Document Spanners - A Brief Overview of Concepts, Results, and Recent Developments (Markus L. Schmid, Nicole Schweikardt), Principles of Database Systems, "Gems of PODS", (PODS 2022), [PV]
• Matching Patterns with Variables (Florin Manea, Markus L. Schmid), International Conference on Combinatorics on Words (WORDS 2019), [PV] [TR]

Invited Talks

• "Regular Languages in Database Theory", 32. Theorietag der GI Fachgruppe "Automaten und Formale Sprachen"
• "On Structural Tractability Parameters for Hard String Problems", Joint Events' Invited Speaker of DLT & WORDS 2023
• "The Information Extraction Framework of Document Spanners - An Overview of Concepts, Results, and Recent Developments", SOFSEM 2024
• "Enumeration for MSO-Queries on Compressed Trees", DLT 2024 - Highlights of Language Theory Session

Other papers (workshops, national conferences, community meetings)

• Discovering Multi-Dimensional Subsequence Queries from Traces - From Theory to Practice (Sarah Kleest-Meißner, Rebecca Sattler, Markus L. Schmid, Nicole Schweikardt, Matthias Weidlich)
  20th Conference on "Database Systems for Business, Technology and Web" (BTW2023) [conference proceedings]

• Proc. 29. Theorietag der GI Fachgruppe Automaten und Formale Sprachen (AFS), 2019.
  • Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number (Katrin Casel, Joel D. Day, Pamela Fleischmann, Tomasz Kociumaka, Florin Manea, Markus L. Schmid)
  • Regular Expressions with Backreferences: Polynomial-Time Matching Techniques (Markus L. Schmid)
• Proc. 76. Workshop über Algorithmen und Komplexität der GI Fachgruppen Algorithmen (ALGO) und Komplexität (KP) und 28. Theorietag der GI Fachgruppe Automaten und Formale Sprachen (AFS), 2018.
  • Consensus Strings with Small Maximum Distance and Small Distance Sum (Laurent Bulteau, Markus L. Schmid)
  • Exact and Approximated Computation of the Locality Number of Words (Joel D. Day, Pamela Fleischmann, Florin Manea, Markus L. Schmid)
• Proc. 70. Workshop über Algorithmen und Komplexität der GI Fachgruppen Algorithmen (ALGO) und Komplexität (KP) und 25. Theorietag der GI Fachgruppe Automaten und Formale Sprachen (AFS), 2015.
  • A New Parameterisation for Consensus String Problems (Markus L. Schmid)
  • Revisiting Shinohara’s Algorithm for Computing Descriptive Patterns (Henning Fernau, Florin Manea, Robert Mercas and Markus L. Schmid)
• Proc. 24. Theorietag der GI Fachgruppe Automaten und Formale Sprachen (AFS), 2014.
  • Remarks on Jumping Finite Automata (Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid)
  • Characterising REGEX Languages by Regular Languages with Factor-Referencing (Markus L. Schmid)
• Proc. 23. Theorietag der GI Fachgruppe Automaten und Formale Sprachen (AFS), 2013.
  • Array insertion and deletion P systems (Henning Fernau, Rudolf Freund, Sergiu Ivanov, Marion Oswald, Markus L. Schmid, K.G. Subramanian) [abstract]
  • Eine natürliche Membranhierarchie (Henning Fernau, Rudolf Freund, Markus L. Schmid, K.G. Subramanian, Petra Wiederhold) [abstract]
• Inside the Class of REGEX Languages (Markus L. Schmid)
  Proc. 22. Theorietag der GI Fachgruppe AFS, Automata and Formal Languages, 2012. [conference proceedings]
• Automata for Languages Defined by Backreferencing (Daniel Reidenbach, Markus L. Schmid)
  Proc. 21. Theorietag der GI Fachgruppe AFS, Automaten und Formale Sprachen, 2011. [conference proceedings]
• Common Supersequences with Minimum Scope Coincidence Degree (Daniel Reidenbach, Markus L. Schmid)
  Proc. 20. Theorietag der GI Fachgruppe AFS, Automaten und Formale Sprachen, 2010. [conference proceedings]

Academic activities

• Reviewing:

  • Conferences: NCMA 2010, LATA 2010, SOFSEM 2012, CIAA 2013, MFCS 2013, NCMA 2013, COCOON 2014, SWAT 2014, IPEC 2014, STACS 2015, DCFS 2015, MFCS 2015, DCFS 2016, ICGI 2016, SPIRE 2016, STACS 2017, CiE 2017, NCMA 2017, FSTTCS 2017, DLT 2018, SYNASC 2018, STACS 2019, CIAC 2019, DLT 2019, MFCS 2019, SPIRE 2019, PODS 2020, DCFS 2020, STACS 2021, CiE 2021, FSTTCS 2021, IWOCA 2022, PODS 2022, CPM 2022, FSTTCS 2022, CPM 2023, CiE 2023, FCT 2023, ICDT 2024, ICALP 2024, DLT 2024, ISAAC 2024
    (total number of reviews: ~ 59)
  • Journals: Algorithmica, Journal of Computer and System Sciences, Mathematical Structures in Computer Science, Theoretical Computer Science, Information and Computation, Algorithms, International Journal of Artificial Intelligence and Soft Computing, International Journal of Foundations of Computer Science, Journal of Membrane Computing, Fundamenta Informaticae, Acta Informatica, Logical Methods in Computer Science, ACM Transactions on Database Systems, Theory of Computing Systems, Discrete Applied Mathematics, Journal of Automata, Languages and Combinatorics
    (total number of reviews: ~ 23)

• Program Committee Work:

  • 9th Workshop on Non-Classical Models of Automata and Applications - NCMA 2017
  • 22nd International Conference on Developments in Language Theory - DLT 2018
  • 20th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing - SYNASC 2018, Track: Advances in the Theory of Computing
  • 16th Computability in Europe - CiE 2020
  • 15th International Computer Science Symposium in Russia - CSR 2020
  • 38th International Symposium on Theoretical Aspects of Computer Science - STACS 2021
  • 19th Computability in Europe - CiE 2023
  • 24th International Symposium on Fundamentals in Computation Theory - FCT 2023
  • 27th International Conference on Database Theory - ICDT 2024
  • 21st Conference on Database Systems for Business, Technology and Web - BTW 2025

• Workshop Participation:

  • Lorentz Center - Fixed-Parameter Computational Geometry (2016)
  • Schloss Dagstuhl - Computation over Compressed Structured Data (2016)
  • Schloss Dagstuhl - Regular Expressions: Matching and Indexing (2024)

• Teaching

  • Assistance/exercises (bachelor and master course):
  • Goethe Universitaet Frankfurt:
  • 2007: Datenstrukturen (Data Structures), Algorithmentheorie (Algorithm Theory)
  • 2008: Formale Sprachen und Berechenbarkeit (Formal Languages and Decidability)
  • 2009: Formale Sprachen und Berechenbarkeit (Formal Languages and Decidability)
  • Loughborough University
  • 2010: Computer Systems, Formal Languages and Theory of Computation
  • 2011: Computer Systems, Formal Languages and Theory of Computation
  • 2012: Computer Systems
  • Trier University
  • 2012/2013:
    • Grundlagen der Informatik II (Foundations of Computer Science II)
  • 2013:
    • Automatentheorie und Formale Sprachen (Automata Theory and Formal Languages)
    • Formale Sprachen A: Regulierte Ersetzung (Formal Languages A: Regulated Rewriting)
  • 2013/2014:
    • Diskrete Strukturen (Discrete Structures)
  • 2014:
    • Automatentheorie und Formale Sprachen (Automata Theory and Formal Languages)
    • Formale Sprachen B: Baumsprachen (Formal Languages B: Tree Languages)
  • 2014/2015:
    • Diskrete Strukturen (Discrete Structures)
  • 2015:
    • Formale Sprachen (Formal Languages)
    • Formale Sprachen A: Formale Potenzreihen (Formal Languages A: Formal Power Series)
  • 2015/2016:
    • Diskrete Strukturen (Discrete Structures)
  • 2018:
    • Formale Sprachen B: Beschreibungskomplexität (Formal Languages B: Descriptional Complexity)
    • Lernalgorithmen (Computational Learning Theory)
  • Humboldt University Berlin
  • 2020:
    • Einführung in die formale Logik (Introduction to formal logics)
  • Lectures (own responsibility):
  • Master courses:
  • Stringalgorithmen (Algorithms on Strings), 2014/2015
  • Komplexitätstheorie A (Complexity Theory A), 2016/2017
  • Formale Sprachen A - Theoretische Grundlagen des Compilerbaus (Formal Languages A - Theory of Compiling), 2017
  • Bachelor courses:
  • Diskrete Strukturen (Discrete Structures), 2018/2019
  • Klassische Stringalgorithmik (String Algorithms), 2023

• Prizes

  • Bachelor Abschluss mit Auszeichnung (Bachelor degree with distinction)
  • Ondrej Sykora Prize 2010 (Department of Computer Science, Loughborough University)
  • Graduate School Research Student Prize (Loughborough University)

• Scholarships

  • October 2008 - September 2009: Stipendium der Studienstiftung des deutschen Volkes (Scholarship of the German National Academic Foundation)
  • October 2009 - October 2012: Scholarship from the Department of Computer Science, Loughborough University
  • November 2012 - April 2013: Rückkehrstipendium des Deutschen Akademischen Austausch Dienst (DAAD) (scholarship of the German Academic Exchange Service for returning scientists)

• Universities

  • 2005 - 2009: Goethe Universitaet Frankfurt, Germany, undergraduate studies
  • 2009 - 2012: Loughborough University, United Kingdom, PhD programme
  • 2012 - 2019: Trier University, Germany, researcher
  • Since 2019: Humboldt-Universität, Germany, researcher

• Degrees

  • Bachelor of Science in Computer Science (2009)
  • Master of Philosophy in Theoretical Computer Science (2010)
  • PhD in Theoretical Computer Science (2012)

Miscellaneous

• The membership problem for pattern languages in a nutshell
• My DBLP page
• My PhD thesis