BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Stefan Kiefer

Stefan Kiefer contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Formal Languages and Automata TheoryComputational ComplexityData Structures and Algorithmsmath.GRmath.RANumerical AnalysisLogic in Computer Sciencemath.COPerformance

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
13works
0followers
9topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2026arXiv

The asymptotic size of finite irreducible semigroups of rational matrices

We study finite semigroups of $n \times n$ matrices with rational entries. Such semigroups provide a rich generalization of transition monoids of unambiguous (and, in particular, deterministic) finite automata. In this paper we determine the maximum size of finite semigroups of rational $n \times n$ matrices, with the goal of shedding more light on the structure of such matrix semigroups. While in general such semigroups can be arbitrarily large in terms of $n$, a classical result of Schützenberger from 1962 implies an upper bound of $2^{O(n^2 \log n)}$ for irreducible semigroups, i.e., the only subspaces of $Q^n$ that are invariant for all matrices in the semigroup are $Q^n$ and the subspace consisting only of the zero vector. Irreducible matrix semigroups can be viewed as the building blocks of general matrix semigroups, and as such play an important role in mathematics and computer science. From the point of view of automata theory, they generalize strongly connected automata. Using a very different technique from that of Schützenberger, we improve the upper bound on the cardinality to $3^{n^2}$. This is the main result of the paper. The bound is in some sense tight, as we show that there exists, for every $n$, a finite irreducible semigroup with $3^{\lfloor n^2/4 \rfloor}$ rational matrices. Our main result also leads to an improvement of a bound, due to Almeida and Steinberg, on the mortality threshold. The mortality threshold is a number $\ell$ such that if the zero matrix is in the semigroup, then the zero matrix can be written as a product of at most $\ell$ matrices from any subset that generates the semigroup.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Image-Binary Automata

We introduce a certain restriction of weighted automata over the rationals, called image-binary automata. We show that such automata accept the regular languages, can be exponentially more succinct than corresponding NFAs, and allow for polynomial complementation, union, and intersection. This compares favourably with unambiguous automata whose complementation requires a superpolynomial state blowup. We also study an infinite-word version, image-binary Büchi automata. We show that such automata are amenable to probabilistic model checking, similarly to unambiguous Büchi automata. We provide algorithms to translate $k$-ambiguous Büchi automata to image-binary Büchi automata, leading to model-checking algorithms with optimal computational complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Lower Bounds for Unambiguous Automata via Communication Complexity

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. $\textit{Complement:}$ There is a language $L$ recognised by an $n$-state UFA such that the complement language $\overline{L}$ requires NFAs with $n^{\tildeΩ(\log n)}$ states. This improves on a lower bound by Raskin. $\textit{Union:}$ There are languages $L_1$, $L_2$ recognised by $n$-state UFAs such that the union $L_1\cup L_2$ requires UFAs with $n^{\tildeΩ(\log n)}$ states. $\textit{Separation:}$ There is a language $L$ such that both $L$ and $\overline{L}$ are recognised by $n$-state NFAs but such that $L$ requires UFAs with $n^{Ω(\log n)}$ states. This refutes a conjecture by Colcombet.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Complementing Unambiguous Automata and Graphs With Many Cliques and Cocliques

We show that for any unambiguous finite automaton with $n$ states there exists an unambiguous finite automaton with $\sqrt{n+1} \cdot 2^{n/2}$ states that recognizes the complement language. This builds and improves upon a similar result by Jirásek et al. [Int. J. Found. Comput. Sci. 29 (5) (2018)]. Our improvement is based on a reduction to and an analysis of a problem from extremal graph theory: we show that for any graph with $n$ vertices, the product of the number of its cliques with the number of its cocliques (independent sets) is bounded by $(n+1) 2^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On Nonnegative Integer Matrices and Short Killing Words

Let $n$ be a natural number and $\mathcal{M}$ a set of $n \times n$-matrices over the nonnegative integers such that the joint spectral radius of $\mathcal{M}$ is at most one. We show that if the zero matrix $0$ is a product of matrices in $\mathcal{M}$, then there are $M_1, \ldots, M_{n^5} \in \mathcal{M}$ with $M_1 \cdots M_{n^5} = 0$. This result has applications in automata theory and the theory of codes. Specifically, if $X \subset Σ^*$ is a finite incomplete code, then there exists a word $w \in Σ^*$ of length polynomial in $\sum_{x \in X} |x|$ such that $w$ is not a factor of any word in $X^*$. This proves a weak version of Restivo's conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Notes on Equivalence and Minimization of Weighted Automata

This set of notes re-proves known results on weighted automata (over a field, also known as multiplicity automata). The text offers a unified view on theorems and proofs that have appeared in the literature over decades and were written in different styles and contexts. None of the results reported here are claimed to be new. The content centres around fundamentals of equivalence and minimization, with an emphasis on algorithmic aspects. The presentation is minimalistic. No attempt has been made to motivate the material. Weighted automata are viewed from a linear-algebra angle. As a consequence, the proofs, which are meant to be succinct, but complete and almost self-contained, rely mainly on elementary linear algebra.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Affine Reachability Problems

We analyze affine reachability problems in dimensions 1 and 2. We show that the reachability problem for 1-register machines over the integers with affine updates is PSPACE-hard, hence PSPACE-complete, strengthening a result by Finkel et al. that required polynomial updates. Building on recent results on two-dimensional integer matrices, we prove NP-completeness of the mortality problem for 2-dimensional integer matrices with determinants +1 and 0. Motivated by tight connections with 1-dimensional affine reachability problems without control states, we also study the complexity of a number of reachability problems in finitely generated semigroups of 2-dimensional upper-triangular integer matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Size of Finite Rational Matrix Semigroups

Let $n$ be a positive integer and $\mathcal M$ a set of rational $n \times n$-matrices such that $\mathcal M$ generates a finite multiplicative semigroup. We show that any matrix in the semigroup is a product of matrices in $\mathcal M$ whose length is at most $2^{n (2 n + 3)} g(n)^{n+1} \in 2^{O(n^2 \log n)}$, where $g(n)$ is the maximum order of finite groups over rational $n \times n$-matrices. This result implies algorithms with an elementary running time for deciding finiteness of weighted automata over the rationals and for deciding reachability in affine integer vector addition systems with states with the finite monoid property.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Online Monitoring $ω$-Regular Properties in Unknown Markov Chains

We study runtime monitoring of $ω$-regular properties. We consider a simple setting in which a run of an unknown finite-state Markov chain $\mathcal M$ is monitored against a fixed but arbitrary $ω$-regular specification $φ$. The purpose of monitoring is to keep aborting runs that are "unlikely" to satisfy the specification until $\mathcal M$ executes a correct run. We design controllers for the reset action that (assuming that $φ$ has positive probability) satisfy the following property w.p.1: the number of resets is finite, and the run executed by $\mathcal M$ after the last reset satisfies $φ$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Strategy Complexity of Parity Objectives in Countable MDPs

We study countably infinite MDPs with parity objectives. Unlike in finite MDPs, optimal strategies need not exist, and may require infinite memory if they do. We provide a complete picture of the exact strategy complexity of $\varepsilon$-optimal strategies (and optimal strategies, where they exist) for all subclasses of parity objectives in the Mostowski hierarchy. Either MD-strategies, Markov strategies, or 1-bit Markov strategies are necessary and sufficient, depending on the number of colors, the branching degree of the MDP, and whether one considers $\varepsilon$-optimal or optimal strategies. In particular, 1-bit Markov strategies are necessary and sufficient for $\varepsilon$-optimal (resp. optimal) strategies for general parity objectives.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Computing Least Fixed Points of Probabilistic Systems of Polynomials

We study systems of equations of the form X1 = f1(X1, ..., Xn), ..., Xn = fn(X1, ..., Xn), where each fi is a polynomial with nonnegative coefficients that add up to 1. The least nonnegative solution, say mu, of such equation systems is central to problems from various areas, like physics, biology, computational linguistics and probabilistic program verification. We give a simple and strongly polynomial algorithm to decide whether mu=(1, ..., 1) holds. Furthermore, we present an algorithm that computes reliable sequences of lower and upper bounds on mu, converging linearly to mu. Our algorithm has these features despite using inexact arithmetic for efficiency. We report on experiments that show the performance of our algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Computing the Least Fixed Point of Positive Polynomial Systems

We consider equation systems of the form X_1 = f_1(X_1, ..., X_n), ..., X_n = f_n(X_1, ..., X_n) where f_1, ..., f_n are polynomials with positive real coefficients. In vector form we denote such an equation system by X = f(X) and call f a system of positive polynomials, short SPP. Equation systems of this kind appear naturally in the analysis of stochastic models like stochastic context-free grammars (with numerous applications to natural language processing and computational biology), probabilistic programs with procedures, web-surfing models with back buttons, and branching processes. The least nonnegative solution mu f of an SPP equation X = f(X) is of central interest for these models. Etessami and Yannakakis have suggested a particular version of Newton's method to approximate mu f. We extend a result of Etessami and Yannakakis and show that Newton's method starting at 0 always converges to mu f. We obtain lower bounds on the convergence speed of the method. For so-called strongly connected SPPs we prove the existence of a threshold k_f such that for every i >= 0 the (k_f+i)-th iteration of Newton's method has at least i valid bits of mu f. The proof yields an explicit bound for k_f depending only on syntactic parameters of f. We further show that for arbitrary SPP equations Newton's method still converges linearly: there are k_f>=0 and alpha_f>0 such that for every i>=0 the (k_f+alpha_f i)-th iteration of Newton's method has at least i valid bits of mu f. The proof yields an explicit bound for alpha_f; the bound is exponential in the number of equations, but we also show that it is essentially optimal. Constructing a bound for k_f is still an open problem. Finally, we also provide a geometric interpretation of Newton's method for SPPs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Space-efficient scheduling of stochastically generated tasks

We study the problem of scheduling tasks for execution by a processor when the tasks can stochastically generate new tasks. Tasks can be of different types, and each type has a fixed, known probability of generating other tasks. We present results on the random variable S^sigma modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler sigma. We obtain tail bounds for the distribution of S^sigma for both offline and online schedulers, and investigate the expected value of S^sigma.

0 citations0 reviewsNo code linkedOpen access