Formal Language Theory
Research Description:
At the core of our research questions (e.g., on data management or internet
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 Czerwinski, Wim Martens, Matthias 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). | Paper |
| Efficient Separability of Regular Wojciech Czerwinski, Wim Martens, and Tomas Masopust. International Colloquium on Automata, Languages, and Programming (ICALP 2013). | Preprint Paper |
| Deciding Definability by Deterministic Regular Expressions. Wojciech Czerwinski, Claire David, Katja Losemann, and Wim Martens. Journal of Computer and System Sciences (JCSS). | Preprint Paper |
| The Tractability Frontier for NFA Minimization. Henrik Björklund and Wim Martens. Journal of Computer and System Sciences (JCSS). | Preprint Paper |