Welcome to my homepage! My name ist Stefan Hoffmann and I am a PhD student in Trier under the supervision of Prof. Dr. Henning Fernau.
My interests circle around the areas of finite automata theory, more specifically problems of synchronization and state complexity, and formal language theory, in particular commutative languages and the shuffle operation. Furthermore, I am interested in group theory and algebra and applications of it to above mentioned fields of study. Sometimes I dabble into omega languages and (general) topology. Recently, I got more involved into computational complexity, in particular parameterized complexity.
Research interest keywords: automata, formal language theory, synchronization, (finite) permutation group theory, permutation automata, group languages, parameterized complexity, computational complexity, shuffle product, partial commutativity, commutative languages, state complexity, omega languages.
My Erdös number is three (via Henning Fernau or Ludwig Staiger, both two).
Contact: hoffmanns (at) informatik (dot) uni (hyphen) trier (dot) de
For some papers, I have put up a link to an errata - unfortunately mistakes happen, but up to now they were all minor and I mostly fixed them in the latest arXiv version (indicated in the corresponding errata file). If you spot any mistakes or unclear formulations, please do not hesitate to tell me!
In preparation:
- New Characterizations of Primitive Permutation Groups with Applications to Synchronizing Automata (Journal Version)
- Automata Containing a Cyclic Permutation and Having Maximal State Complexity for the Set of Synchronizing Words (Journal Version)
- State Complexity Bounds for the Commutative Closure of Group Languages (Journal Version)
- Constrained Synchronization and Commutative Languages (Journal Version)
- Commutative Regular Languages - Properties and State Complexity (Journal Version)
Preprints:
- Henning Fernau, Stefan Hoffmann, Michael Wehar, Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited
arXiv version
Published:
2021
- Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, Petra Wolf,
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
arXiv version · conference version - Stefan Hoffmann, Sync-Maximal Permutation Groups Equal Primitive Permutation Groups
23rd International Conference on Descriptional Complexity of Formal Systems (DCFS) 2021 - Stefan Hoffmann, Commutative Regular Languages with Product-Form Minimal Automata
23rd International Conference on Descriptional Complexity of Formal Systems (DCFS) 2021 - Stefan Hoffmann, State Complexity Bounds for Upward and Downward Closures on Commutative Languages and Further Results for Two Subclasses
23rd International Conference on Descriptional Complexity of Formal Systems (DCFS) 2021 - Stefan Hoffmann, Ideal Separation and General Theorems for Constrained Synchronization and their Application to Small Constraint Automata
The 27th International Computing and Combinatorics Conference (COCOON) 2021 - Stefan Hoffmann, Computational Complexity of Synchronization under Sparse Regular Constraints
International Symposium on Fundamentals of Computation Theory (FCT) 2021
arXiv version · conference version · errata - Stefan Hoffmann, The n-ary Literal Shuffle and Variants
Prague Stringology Conference (PSC) 2021
arXiv version · conference version and slides - Stefan Hoffmann, State Complexity of Projection on Languages Recognized by Permutation Automata and Commuting Letters
Developments in Language Theory (DLT) 2021
arXiv version · conference version · slides · errata - Stefan Hoffmann, Constrained Synchronization and Subset Synchronization Problems for Weakly Acyclic Automata
Developments in Language Theory (DLT) 2021
arXiv version · conference version · slides - Stefan Hoffmann, Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
International Conference on Implementation and Application of Automata (CIAA) 2021
arXiv version · conference version · slides - Stefan Hoffmann, The Commutative Closure of Shuffle Languages over Group Languages is Regular
International Conference on Implementation and Application of Automata (CIAA) 2021
arXiv version · conference version · slides - Stefan Hoffmann, State Complexity of Permutation and Related Decision Problems on Alphabetical Pattern Constraints
International Conference on Implementation and Application of Automata (CIAA) 2021
arXiv version · conference version · slides · errata - Stefan Hoffmann, Completely Reachable Automata, Primitive Groups and the State Complexity of the Set of Synchronizing Words
Language and Automata Theory and Applications (LATA) 2021
arXiv version · conference version - Stefan Hoffmann, State Complexity of the Set of Synchronizing Words for Circular Automata and Automata over Binary Alphabets
Language and Automata Theory and Applications (LATA) 2021
arXiv version · conference version
2020
- Stefan Hoffmann, State Complexity Bounds for the Commutative Closure of Group Languages
Descriptional Complexity of Formal Systems (DCFS) 2020
arXiv version · conference version - Stefan Hoffmann, On a Class of Constrained Synchronization Problems in NP
Italian Conference on Theoretical Computer Science (ICTCS) 2020
arXiv version · conference version · errata - Stefan Hoffmann, Computational Complexity of Synchronization Under Regular Commutative Constraints
International Computing and Combinatorics Conference (COCOON) 2020
arXiv version · conference version · errata
2019
- Henning Fernau, Stefan Hoffmann, Extensions to Minimal Synchronizing Words
Journal of Automata, Languages and Combinatorics (JALC) Volume 24
published version - Stefan Hoffmann, Commutative Regular Languages - Properties and State Complexity
International Conference on Algebraic Informatics (CAI) 2019
conference version - Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, Petra Wolf Computational Complexity of Synchronization under Regular Constraints
Mathematical Foundations of Computer Science (MFCS) 2019
conference version
2017
- Stefan Hoffmann, Sibylle Schwarz, Ludwig Staiger Shift-invariant topologies for the Cantor space Xω
Theoretical Computer Science, Vol. 679
published version
2015
- Stefan Hoffmann, Ludwig Staiger Subword Metrics for Infinite Words
International Conference Implementation and Application of Automata (CIAA) 2015
conference version