Author name cluster

Markus Holzer 0001

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.

9 papers

1 author row

MFCS Conference 2021 Conference Paper

Optimal Regular Expressions for Palindromes of Given Length

Hermann Gruber
Markus Holzer 0001

The language P_n (P̃_n, respectively) consists of all words that are palindromes of length 2n (2n-1, respectively) over a fixed binary alphabet. We construct a regular expression that specifies P_n (P̃_n, respectively) of alphabetic width 4⋅ 2ⁿ-4 (3⋅ 2ⁿ-4, respectively) and show that this is optimal, that is, the expression has minimum alphabetic width among all expressions that describe P_n (P̃_n, respectively). To this end we give optimal expressions for the first k palindromes in lexicographic order of odd and even length, proving that the optimal bound is 2n+4(k-1)-2 S₂(k-1) in case of odd length and 2n+3(k-1)-2 S₂(k-1)-1 for even length, respectively. Here S₂(n) refers to the Hamming weight function, which denotes the number of ones in the binary expansion of the number n.

Details

MFCS Conference 2019 Conference Paper

Computational Complexity of Synchronization under Regular Constraints

Henning Fernau
Vladimir V. Gusev
Stefan Hoffmann 0001
Markus Holzer 0001
Mikhail V. Volkov 0001
Petra Wolf 0002

Many variations of synchronization of finite automata have been studied in the previous decades. Here, we suggest studying the question if synchronizing words exist that belong to some fixed constraint language, given by some partial finite automaton called constraint automaton. We show that this synchronization problem becomes PSPACE-complete even for some constraint automata with two states and a ternary alphabet. In addition, we characterize constraint automata with arbitrarily many states for which the constrained synchronization problem is polynomial-time solvable. We classify the complexity of the constrained synchronization problem for constraint automata with two states and two or three letters completely and lift those results to larger classes of finite automata.

Details

MFCS Conference 2004 Conference Paper

A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract)

Martin Beaudry
José M. Fernandez 0001
Markus Holzer 0001

Abstract Through the study of gate arrays we develop a unified framework to deal with probabilistic and quantum computations, where the former is shown to be a natural special case of the latter. On this basis we show how to encode a probabilistic or quantum gate array into a sum-free tensor formula which satisfies the conditions of the partial trace problem, and vice-versa. In this way complete problems for the classes pr-BPP (promise BPP) and pr-BQP (promise BQP) are given when changing the semiring from (ℚ +, +, ·) to the field (ℚ, +, ·). Moreover, by variants of the problem under consideration, classes like ⊕P, NP, C = P, its complement co-C = P, the promise version of Valiant’s class UP, its generalization promise SPP, and unique polytime US are captured as problem property and the semiring varies.

Details

MFCS Conference 2001 Conference Paper

The Complexity of Tensor Circuit Evaluation

Martin Beaudry
Markus Holzer 0001

Abstract The study of tensor calculus over semirings in terms of complexity theory was initiated by Damm et al. in [ 8 ]. Here we first look at tensor circuits, a natural generalization of tensor formulas; we show that the problem of asking whether the output of such circuits is non-zero is complete for the class NE = NTIME(2 o ( n ) ) for circuits over the boolean semiring, ⊕E for the field \( \mathbb{F}_2 \), and analogous results for other semirings. Common sense restrictions such as imposing a logarithmic upper bound on circuit depth are also discussed. Second, we analyze other natural problems concerning tensor formulas and circuits over various semirings, such as asking whether the output matrix is diagonal or a null matrix.

Details

MFCS Conference 2000 Conference Paper

Alternating and Empty Alternating Auxiliary Stack Automata

Markus Holzer 0001
Pierre McKenzie

Abstract We consider variants of alternating auxiliary stack automata and characterize their computational power when the number of alternations is bounded by a constant or unlimited. In this way we get new characterizations of NP, the polynomial hierarchy, PSpace, and bounded query classes like NL 〈 NP [1]〉 and Θ 2 P = P NP [O(logn)], in a uniform framework.

Details

MFCS Conference 1997 Conference Paper

Multi-Head Finite Automata: Data-Independent Versus Data-Dependent Computations

Markus Holzer 0001

Abstract We develop a framework on multi-head finite automata that allows us to study the relation of parallel logarithmic time and sequential logarithmic space in a uniform and nonuniform setting in more detail. In both settings it turns out that NC 1 requires data-independent computations—the movement of the input-heads only depends on the length of the input—whereas logarithmic space is caught with data dependent computations on multi-head finite state machines. This shed new light on the question whether these two classes coincide or not.

Details

MFCS Conference 1995 Conference Paper

Automata That Take Advice

Carsten Damm
Markus Holzer 0001

Abstract Karp and Lipton introduced advice-taking Turing machines to capture nonuniform complexity classes. We study this concept for automata-like models and compare it to other nonuniform models studied in connection with formal languages in the literature. Based on this we obtain complete separations of the classes of the Chomsky hierarchy relative to advices.

Details

MFCS Conference 1994 Conference Paper

Inductive Counting Below LOGSPACE

Carsten Damm
Markus Holzer 0001

Abstract We apply the inductive counting technique to nondeterministic branching programs and prove that complementation on this model can be done without increasing the width of the branching programs too much. This shows that for an arbitrary space bound s(n), the class of languages accepted by nonuniform nondeterministic O(s(n)) space bounded Turing machines is closed under complementation. As a consequence we obtain for arbitrary space bounds s(n) that the alternation hierarchy of nonuniform O(s(n)) space bounded Turing machines collapses to its first level. This improves the previously known result of Immerman [6] and Szelepcsényi [12] to space bounds of order o (log n ) in the nonuniform setting. This reveals a strong difference to the relations between the corresponding uniform complexity classes, since very recently it has been proved that in the uniform case the alternating space hierarchy does not collapse for sublogarithmic space bounds [3, 5, 9].

Details

MFCS Conference 1992 Conference Paper

Parallel Complexity of Iterated Morphisms and the Arithmetic of Small Numbers

Carsten Damm
Markus Holzer 0001
Klaus-Jörn Lange

Abstract We improve several upper bounds to the complexity of the membership problem for languages defined by iterated morphisms (D0L systems). The complexity bounds are expressed in terms of DLOGTIME -uniform circuit families. We prove: 1) For polynomially growing DOL systems the membership problem is contained in AC 0. 2) For arbitrary DOL systems the membership problem is contained in NC 1. 3) The latter can be improved to TC 0 if and only if upper bounds to a number of natural arithmetic problems can be improved to TC 0. 4) The general D0L membership problem (the D0L system is part of the input) is contained in Cook's class DET.

Details