Dr. Markus L. Schmid

I am currently working as a researcher in the Theoretical Computer Science research group, Trier University, led by Henning Fernau.

My general research interest lies in automata theory, formal language theory, and (parameterised) complexity theory.

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

Short CV


Overview of published papers:

General TCS Conferences #Papers
ICALP International Colloquium on Automata, Languages, and Programming 1
STACS International Symposium on Theoretical Aspects of Computer Science 2
MFCS International Symposium on Mathematical Foundations of Computer Science 2
FSTTCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science 1
CiE Computability in Europe 1
Automata and Formal Languages Conferences
DLT International Conference on Developments in Language Theory 5
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
CPM Annual Symposium on Combinatorial Pattern Matching 1
IWCIA International Workshop on Combinatorial Image Analysis 1
TCS Journals
JCSS Journal of Computer and System Sciences 2
ToCS Theory of Computing Systems 1
I&C Information and Computation 3
TOCT ACM Transactions on Computation Theory 1
TCS Theoretical Computer Science 4
IJFCS International Journal of Foundations of Computer Science 1
IPL Information Processing Letters 2
IJCM International Journal of Computer Mathematics 1
AMAI Annals of Mathematics and Artificial Intelligence 1
Kybernetika Kybernetika 1

Peer reviewed publications (conferences and journals):

[PV] = Publisher's Version
[Pre] = Preprint Version
[TR] = Full Version as Technical Report

25.   Combinatorial Properties and Recognition of Unit Square Visibility Graphs (Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, Sue Whitesides)
  • MFCS 2017, to appear.
24.   Deterministic Regular Expressions With Back-References (Dominik D. Freydenberger and Markus L. Schmid)
23.   On the Solvability Problem for Restricted Classes of Word Equations (Florin Manea, Dirk Nowotka, Markus L. Schmid)
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), to appear. [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), to appear (under the title "Simple Picture Processing Based on Finite Automata and Regular Grammars").
19.   Finding Consensus Strings With Small Length Difference Between Input and Solution Strings (Markus L. Schmid)
  • MFCS 2015. [PV] [Pre]
  • TOCT (ACM Transactions on Computation Theory), to appear. [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)
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]
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]
  • 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]
  • 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]
  • 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)

Other papers

Academic activities


Last update 13 July 2017