Druckansicht der Internetadresse:

Faculty of Mathematics, Physics & Computer Science

Data-Intensive Computing (AI VII) – Prof. Dr. Wim Martens

Print page
formal languages and automata theory header

Formal Language Theory

Research Description:

At the core of our research questions (e.g., on data management or internet standarization) we often find fundamental questions about formal language theory. We encounter questions about regular languages, finite automata, or tree automata. 

Selected topics:

  • Tree Languages and Tree Automata
  • Regular Expressions
  • Determinism versus Nondeterminism
  • Separability and Language Decomposition Problems
  • Enumeration Problems

Selected Papers on this topic:

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


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).
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).
Deciding Definability by Deterministic Regular Expressions.
Wojciech Czerwinski, Claire David, Katja Losemann, and Wim Martens.
Journal of Computer and System Sciences (JCSS).
The Tractability Frontier for NFA Minimization.
Henrik Björklund and Wim Martens.
Journal of Computer and System Sciences (JCSS).

Webmaster: Johannes Doleschal

Facebook Twitter Youtube-Kanal Instagram UBT-A Contact