Author name cluster

Stefan Hoffmann

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

8 papers

1 author row

I&C Journal 2024 Journal Article

State complexity bounds for projection, shuffle, up- and downward closure and interior on commutative regular languages

Stefan Hoffmann

We consider the state complexity of projection, shuffle, up- and downward closure and interior on commutative regular languages. We deduce the state complexity bound n | Σ | for upward closure and downward interior, and ( 2 n m ) | Σ |, ( n m ) | Σ |, ( n + m − 1 ) | Σ | and ( n + m − 2 ) | Σ | for the shuffle on commutative regular, group, aperiodic and finite languages, respectively, with state complexities n and m over the alphabet Σ. We do not know whether these bounds are sharp. For projection, downward closure and upward interior, we give the sharp bound n. Our results are obtained by using the index and period vectors of a regular language, which we introduce in the present work and investigate w. r. t. the above operations and also union and intersection. Furthermore, we characterize the commutative aperiodic and commutative group languages in terms of these parameters and prove that a commutative regular language equals a finite union of shuffle products of commutative finite and commutative group languages.

Details DOI

I&C Journal 2023 Journal Article

Binary and circular automata having maximal state complexity for the set of synchronizing words

Stefan Hoffmann

An automaton is synchronizing if there exists a word driving it into a definite state regardless of the starting state. For an n-state automaton the set of synchronizing words is a regular language that can be accepted by an automaton having 2 n − n states. Here, we study automata over two input letters and circular automata with n states having the property that the minimal automata for their sets of synchronizing words have 2 n − n states, i. e. , the minimal automata are maximal possible. We give a sufficient condition for this property that links it to completely reachable automata, non-trivial automaton congruences and the notion of uniform minimality. We apply our result to the family K n of automata that was previously only conjectured to have this property.

Details DOI

I&C Journal 2023 Journal Article

New characterizations of primitive permutation groups with applications to synchronizing automata

Stefan Hoffmann

For a finite permutation group on n elements we show the following (and variants thereof) equivalences: (1) the permutation group is primitive, (2) in the transformation monoid generated by the group and any rank n − 1 mapping there exists, for every non-empty subset, an element mapping the whole permutation domain onto this subset, (3) in the transformation monoid generated by the group and any rank n − 1 mapping there exists, for every two distinct subsets, an element mapping precisely one to a singleton set. We also investigate further properties related to the reachability of subsets. Lastly, we apply our results to automata and show that automata whose transformation monoids contain a primitive permutation group and a mapping that excludes precisely one state from its image are completely reachable and have the property that a minimal automaton for the set of synchronizing words has the maximal possible number of states.

Details DOI

Highlights Conference 2022 Conference Abstract

Directable and Synchronizable Parikh Automata

Stefan Hoffmann

A finite and deterministic complete automaton is \emph{synchronizing} if there exists a reset state and an input word that drives the automaton to the reset state when started from any state. The notion of synchronizability has been extended to various other models: non-deterministic and partial automata, weighted and timed automata, register automata, nested word automata, Markov decision processes, probabilistic automata and push-down automata. Parikh automata were introduced by Klaedtke & Rueß and enrich finite automata with counters that are checked against a semilinear condition at the end. Here, we will present various notions of synchronization for Parikh automata that yield decidable problems that are PSPACE-complete in general. We will also consider subclasses for which the problem is NP-complete or polynomial time computable. This is ongoing (yet unpublished) work.

Details

TCS Journal 2021 Journal Article

Constrained synchronization and commutativity

Stefan Hoffmann

In the constrained synchronization problem we want to know if a given input automaton admits a synchronizing word contained in a (fixed) regular constraint language. Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages and the computational complexity of the problem restricted to commutative input semi-automata. We give a full classification of the computational complexity of the constrained synchronization problem for commutative regular constraints. Depending on the constraint language, our problem becomes PSPACE-complete, NP-complete or polynomial time solvable. In addition, we derive a polynomial time decision procedure for the complexity of the constrained synchronization problem, given a constraint automaton accepting a commutative language as input. Furthermore, for commutative input semi-automata, the problem is decidable in polynomial time, regardless of the regular constraint language.

Details DOI

Highlights Conference 2021 Conference Abstract

Primitive Permutation Groups and Extremal Synchronizing Automata

Stefan Hoffmann

Primitive permutation groups play a prominent role in permutation group theory since they have been introduced by \’Evariste Galois in his famous solution of the unsolvability of polynomial equations of degree five or higher~\cite{Neumann2011}. An automaton is completely reachable, if every subset of states is reachable from the whole set of states. This notion was introduced by Volkov \& Bondar~\cite{BondarV16} as a strengthening of the notion of a synchronizing automaton, where an automaton is synchronizing if at least one singleton set is reachable from the whole state set. Synchronizing automata have a wide range of applications and the \v{C}ern\’y conjecture, stating that any -state synchronizing automaton has a synchronizing word of length at most, is among the most famous open problems from combinatorial automata theory~\cite{Vol2008}. Now, every automaton whose transition monoid contains a primitive permutation group on its state set and a letter of deficiany one is completely reachable, and this in fact characterizes primitivity, a result published recently~\cite{Hoffmann21}. The sync-maximal groups of degree have been introduced~\cite{Hoffmann21} by the demand that for any non-permutation of deficiency one the minimal automaton for the set of synchronizing words of an associated automaton has size, i. e. , is extremal in this respect. It has been recently discovered that this in fact gives another characterization of the primitive permutation groups, i. e. , sync-maximal permutation groups are precisely the primitive permutation groups~\cite{HoffmannA}. This extremal property on the set of synchronizing words is also shared by families of slowly synchronizing automata, i. e. , automata for which a shortest synchronizing word has quadratic length. It is conjectured that primitive permutation groups are also intimately connected to slowly synchronizing automata, a topic of on-going work~\cite{HoffmannB}.

Details

TCS Journal 2017 Journal Article

Shift-invariant topologies for the Cantor space X

Stefan Hoffmann
Sibylle Schwarz
Ludwig Staiger

The space of one-sided infinite words plays a crucial rôle in several parts of Theoretical Computer Science. Usually, it is convenient to regard this space as a metric space, the Cantor space. It turned out that for several purposes topologies other than the one of the Cantor space are useful, e. g. for studying fragments of first-order logic over infinite words or for a topological characterisation of random infinite words. It is shown that these topologies refine the topology of the Cantor space. Moreover, from common features of these topologies we extract properties which characterise a large class of topologies. It turns out that, for this general class of topologies, the corresponding closure and interior operators respect the shift operations and also, to some extent, the definability of sets of infinite words by finite automata.

Details DOI

TCS Journal 2016 Journal Article

A linear time algorithm for metric dimension of cactus block graphs

Stefan Hoffmann
Alina Elterman
Egon Wanke

An undirected graph G = ( V, E ) has metric dimension at most k if there is a vertex set U ⊆ V such that | U | ≤ k and ∀ u, v ∈ V, u ≠ v, there is a vertex w ∈ U such that d G ( w, u ) ≠ d G ( w, v ), where d G ( u, v ) is the distance (the length of a shortest path in an unweighted graph) between u and v. The metric dimension of G is the smallest integer k such that G has metric dimension at most k. A cactus block graph is an undirected graph whose biconnected components are either cycles or complete graphs. We present a linear time algorithm for computing the metric dimension of cactus block graphs.

Details DOI