Markus Holzer

I&C Journal 2026 Journal Article

On Jaffe's pumping lemma, revisited

• Markus Holzer
• Christian Rauch

We consider Jaffe's pumping lemma [J. Jaffe. A necessary and sufficient pumping lemma for regular languages. SIGACT News, Summer, 1978] from a descriptional complexity perspective. Jaffe's pumping lemma is a necessary and sufficient condition for a language for being regular. Building on this, we improve on a result of [A. Yehudai. A note on the pumping lemma for regular languages. Inform. Proc. Lett. , 9(3): 135–136, 1979] by proving the existence of a regular language over an alphabet Σ with at least two symbols whose deterministic state complexity lies strictly between p, the minimal pumping constant in Jaffe's lemma, and ∑ i = 0 p − 1 | Σ | i. This finding aligns with recent work on minimal pumping constants for various pumping lemmas, as studied in [J. Dassow and I. Jecker. Operational complexity and pumping lemmas. Acta Inform. , 59: 337–355, 2022]. We further compare the minimal pumping constant in Jaffe's lemma with those of other well-known pumping lemmata from the literature, demonstrating that, in most cases, these constants can be independently assigned across the different lemmata.

I&C Journal 2026 Journal Article

Optimal regular expressions for palindromes of given length

• Hermann Gruber
• Markus Holzer

We determine the optimal regular expression size for sets of palindromes of a given length. For n ≥ 1, let Pal n denote the set of binary palindromes of length n. We construct a regular expression that specifies Pal2n ( Pal 2 n − 1, respectively) of alphabetic width 4 · 2 n − 4 ( 3 · 2 n − 4, respectively) and show that this is optimal, that is, the expression has minimum alphabetic width among all expressions that describe this set of words. Also, we study the set of the lexicographically first k palindromes of length n, denoted by Lex n, k. Let Sq (n) denote the digit sum of the integer n in base q, with q ≥ 2. Here, the optimum regular expression size for Lex2n, k is given by 2 n + 3 ( k − 1 ) − 2 S 2 ( k − 1 ) − 1. A similar formula is derived for odd lengths. We generalize all results to larger alphabet sizes. In the course of our investigation, we derive a new equation on digit sums, which is of independent interest. Namely, max 0 ≤ i ≤ n { S q ( i ) + S q ( n − i ) } = ( q − 1 ) · ⌊ log q ( n + 1 ) ⌋ + S q ( n + 1 ) − 1. For each fixed q, the above equation naturally gives birth to an integer sequence. For q = 2, the right-hand side of the equation is famously known as the number of binary multiplications to compute the nth power by the ancient Indian Chandah-Sutra method.

I&C Journal 2022 Journal Article

Nondeterministic right one-way jumping finite automata

• Simon Beier
• Markus Holzer

Right-one way jumping finite automata are deterministic devices that process their input in a discontinuous fashion. We generalise these devices to nondeterministic machines. More precisely we study the impact on the computational power of these machines when allowing multiple initial states and/or a nondeterministic transition function including spontaneous or λ-transitions. We show inclusion relations and incomparability results of the induced language families. Since for right-one way jumping devices the use of spontaneous transitions is subject to different natural interpretations, we also study this subject in detail, showing that most interpretations are equivalent to each other and lead to the same language families. Finally we also study inclusion and incomparability results to classical language families and to the families of languages accepted by finite automata with translucent letters.

I&C Journal 2019 Journal Article

A mesh of automata

• Sabine Broda
• Markus Holzer
• Eva Maia
• Nelma Moreira
• Rogério Reis

We contribute new relations to the taxonomy of different conversions from regular expressions to equivalent finite automata. In particular, we are interested in transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton ( A POS ), and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version A POS ← of the position automaton which plays a similar role as A POS but now for the reverse expression. Moreover, it turns out that the prefix automaton A Pre is central to reverse expressions, because the determinisation of the double reversal of A Pre (first reverse the expression, construct the automaton A Pre, and then reverse the automaton) can be represented as a quotient of any of the considered deterministic automata that we consider in this investigation. This shows that although the conversion of regular expressions and reversal of regular expressions to finite automata seems quite similar, there are significant differences.

TCS Journal 2019 Journal Article

Properties of right one-way jumping finite automata

• Simon Beier
• Markus Holzer

Right one-way jumping finite automata (ROWJFAs), were recently introduced in H. Chigahara et al. (2016) [3] and are jumping automata that process the input in a discontinuous way with the restriction that the input head reads deterministically from left-to-right starting from the leftmost letter in the input and when it reaches the end of the input word, it returns to the beginning and continues the computation. We characterize the family of permutation closed languages accepted by ROWJFAs in terms of Myhill-Nerode equivalence classes. Using this, we investigate closure and non-closure properties as well as inclusion relations to families of the Chomsky-hierarchy and related families. We also give more characterizations of languages accepted by ROWJFAs in the case that the language is given as the concatenation of two languages.

I&C Journal 2018 Journal Article

On the computational complexity of problems related to distinguishability sets

• Markus Holzer
• Sebastian Jakobi

We study the computational complexity of problems related to distinguishability sets for regular languages. Roughly speaking, the distinguishability set D ( L ) for a (not necessarily regular) language L consists of all those words w for which there exists x and y such that word xw is in L if and only if word yx is not in L; hence the word w distinguishes the two prefixes x and y. One can view this mapping from L to its distinguishability set as an operator D: 2 Σ ⁎ → 2 Σ ⁎ with L ↦ D ( L ). In particular, we investigate the complexity of the representation problem, i. e. , deciding for two given automata A and B, whether B accepts the distinguishability set of L ( A ). It is shown that this problem and some of its variants are highly intractable, namely PSPACE -complete. In fact, determining the size of an automaton for D ( L ( A ) ) is already PSPACE -complete. On the other hand, questions related to the hierarchy induced by iterated application of the D -operator turn out to be much easier. For instance, the question whether for a given automaton A, the accepted language is equal to its own distinguishability set, i. e. , whether L ( A ) = D ( L ( A ) ) holds, is shown to be NL -complete. As a byproduct of our investigations, we found a nice characterization of synchronizing automata, namely that a (minimal) automaton A is synchronizing if and only if D ( L ( A ) ) = D 2 ( L ( A ) ).

TCS Journal 2017 Journal Article

More on deterministic and nondeterministic finite cover automata

• Hermann Gruber
• Markus Holzer
• Sebastian Jakobi

Finite languages are an important sub-regular language family, which were intensively studied during the last two decades in particular from a descriptional complexity perspective. An important contribution to the theory of finite languages are the deterministic and the recently introduced nondeterministic finite cover automata (DFCAs and NFCAs, respectively) as an alternative representation of finite languages by ordinary finite automata. We compare these two types of cover automata from a descriptional complexity point of view, showing that these devices have a lot in common with ordinary finite automata. In particular, we study how to adapt lower bound techniques for nondeterministic finite automata to NFCAs such as, e. g. , the biclique edge cover technique, solving an open problem from the literature. Moreover, the trade-off of conversions between DFCAs and NFCAs as well as between finite cover automata and ordinary finite automata are investigated. Finally, we present some results on the average size of finite cover automata.

TCS Journal 2017 Journal Article

The chop of languages

• Markus Holzer
• Sebastian Jakobi
• Martin Kutrib

We investigate chop operations, which can be seen as generalized concatenation. For several language families of the Chomsky hierarchy we prove (non)closure properties under chop operations and incomparability to the family of languages that are the chop of two regular languages. We also prove non-closure of that language family under Boolean operations and closure under reversal. Further, the representation of a regular language as the chop of two regular expressions can be exponentially more succinct than its regular expression. By considering the chop of two linear context-free languages we already obtain language families that have non-semi-decidable problems such as emptiness or finiteness.

TCS Journal 2016 Journal Article

Boundary sets of regular and context-free languages

• Markus Holzer
• Sebastian Jakobi

We investigate the descriptional and computational complexity of boundary sets of regular and context-free languages. For a letter a, the right (left, respectively) a-boundary set of a language L consists of the words in L whose a-predecessor or a-successor w. r. t. the prefix (suffix, respectively) relation is not in L. For regular languages described by deterministic finite automata (DFAs) we give tight bounds on the number of states for accepting boundary sets. Moreover, the question whether the boundary sets of a regular language is finite is shown to be NL -complete for DFAs, while it turns out to be PSPACE -complete for nondeterministic devices. Boundary sets for context-free languages are not necessarily context free anymore. Here we find a subtle difference of right and left a-boundary sets. While right a-boundary sets of deterministic context-free languages stay deterministic context free, we give an example of a deterministic context-free language whose a-boundary set is already non-context free. In fact, the finiteness problem for a-boundary sets of context-free languages becomes undecidable.

TCS Journal 2012 Journal Article

Nondeterministic state complexity of star-free languages

• Markus Holzer
• Martin Kutrib
• Katja Meckel

We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. This nicely complements the results recently obtained by Brzozowski and Liu (2011) [8] for the operation problem of star-free and unary star-free languages accepted by deterministic finite automata.

TCS Journal 2012 Journal Article

Preface

• Markus Holzer
• Martin Kutrib
• Giovanni Pighizzini

TCS Journal 2011 Journal Article

Complexity of multi-head finite automata: Origins and directions

• Markus Holzer
• Martin Kutrib
• Andreas Malcher

Multi-head finite automata were introduced and first investigated by Rabin and Scott in 1964 and Rosenberg in 1966. Since that time, a vast literature on computational and descriptional complexity issues on multi-head finite automata documenting the importance of these devices has been developed. Although multi-head finite automata are a simple concept, their computational behavior can be already very complex and leads to undecidable or even non-semi-decidable problems on these devices such as, for example, emptiness, finiteness, universality, equivalence, etc. Additionally the conversions between different types of multi-head finite automata induce in most cases size bounds that cannot be bounded by any recursive function, so-called non-recursive trade-offs. These strong negative results trigger the study of subclasses and alternative characterizations of multi-head finite automata for a better understanding of the nature of non-recursive trade-offs and, thus, the borderline between decidable and undecidable problems. In the present paper, we tour a fragment of this literature.

I&C Journal 2011 Journal Article

Decidability of operation problems for T0L languages and subclasses

• Henning Bordihn
• Markus Holzer
• Martin Kutrib

We investigate the decidability of the operation problem for T0L languages and subclasses. Fix an operation on formal languages. Given languages from the family considered (0L languages, T0L languages, or their propagating variants), is the application of this operation to the given languages still a language that belongs to the same language family? Observe, that all the Lindenmayer language families in question are anti-AFLs, that is, they are not closed under homomorphisms, inverse homomorphisms, intersection with regular languages, union, concatenation, and Kleene closure. Besides these classical operations we also consider intersection and substitution, since the language families under consideration are not closed under these operations, too. We show that for all of the above mentioned language operations, except for the Kleene closure, the corresponding operation problems of 0L and T0L languages and their propagating variants are not even semidecidable. The situation changes for unary 0L languages. In this case we prove that the operation problems with respect to Kleene star, complementation, and intersection with regular sets are decidable.

I&C Journal 2011 Journal Article

Descriptional and computational complexity of finite automata—A survey

• Markus Holzer
• Martin Kutrib

Finite automata are probably best known for being equivalent to right-linear context-free grammars and, thus, for capturing the lowest level of the Chomsky-hierarchy, the family of regular languages. Over the last half century, a vast literature documenting the importance of deterministic, nondeterministic, and alternating finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss developments relevant to finite automata related problems like, for example, (i) simulation of and by several types of finite automata, (ii) standard automata problems such as fixed and general membership, emptiness, universality, equivalence, and related problems, and (iii) minimization and approximation. We thus come across descriptional and computational complexity issues of finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.

TCS Journal 2011 Journal Article

Equilibria of graphical games with symmetries

• Felix Brandt
• Felix Fischer
• Markus Holzer

We study graphical games where the payoff function of each player satisfies one of four types of symmetry in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in general for all four types. Using a characterization of games with pure equilibria in terms of even cycles in the neighborhood graph, as well as a connection to a generalized satisfiability problem, we identify tractable subclasses of the games satisfying the most restrictive type of symmetry. Hardness for a different subclass leads us to identify a satisfiability problem that remains NP-hard in the presence of a matching, a result that may be of independent interest. Finally, games with symmetries of two of the four types are shown to possess a symmetric mixed equilibrium which can be computed in polynomial time. We thus obtain a natural class of games where the pure equilibrium problem is computationally harder than the mixed equilibrium problem, unless P=NP.

TCS Journal 2011 Journal Article

On the size of inverse semigroups given by generators

• Martin Beaudry
• Markus Holzer

The size of the transformation semigroup of a reversible deterministic finite automaton with n states, or equivalently, of a semigroup given by generators of injective partial functions on n objects, had remained unexplored in the case where the set of generators is a pair. We show that in this case, the maximal size is attained by a semigroup generated by a permutation that satisfies a property depending on n and a partial injective mapping whose domain and image both have size n − 1. Moreover, we give precise formulas in terms of n for this maximal size.

TCS Journal 2010 Journal Article

An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton

• Markus Holzer
• Andreas Maletti

We improve a recent result [A. Badr, Hyper-minimization in O ( n 2 ), Internat. J. Found. Comput. Sci. 20 (4) (2009) 735–746] for hyper-minimized finite automata. Namely, we present an O ( n log n ) algorithm that computes for a given deterministic finite automaton (dfa) an almost-equivalent dfa that is as small as possible—such an automaton is called hyper-minimal. Here two finite automata are almost-equivalent if and only if the symmetric difference of their languages is finite. In other words, two almost-equivalent automata disagree on acceptance on finitely many inputs. In this way, we solve an open problem stated in [A. Badr, V. Geffert, I. Shipman, Hyper-minimizing minimized deterministic finite state automata, RAIRO Theor. Inf. Appl. 43 (1) (2009) 69–94] and by Badr. Moreover, we show that minimization linearly reduces to hyper-minimization, which shows that the time-bound O ( n log n ) is optimal for hyper-minimization. Independently, similar results were obtained in [P. Gawrychowski, A. Jeż, Hyper-minimisation made efficient, in: Proc. 34th Int. Symp. Mathematical Foundations of Computer Science, in: LNCS, vol. 5734, Springer, 2009, pp. 356–368].

TCS Journal 2009 Journal Article

Determination of finite automata accepting subregular languages

• Henning Bordihn
• Markus Holzer
• Martin Kutrib

We investigate the descriptional complexity of the nondeterministic finite automaton (NFA) to the deterministic finite automaton (DFA) conversion problem, for automata accepting subregular languages such as combinational languages, definite languages and variants thereof, (strictly) locally testable languages, star-free languages, ordered languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages. Most of the bounds for the conversion problem are shown to be tight in the exact number of states, that is, the number is sufficient and necessary in the worst case. Otherwise tight bounds in order of magnitude are shown.

TCS Journal 2009 Journal Article

Language operations with regular expressions of polynomial size

• Hermann Gruber
• Markus Holzer

This work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. Some language operations are identified which are feasible for regular expressions in the sense that the result of the operation can be represented as a regular expression of size polynomial in that of the operands. We prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a quadratic blow-up on the required expression size. The circular shift operation can cause only a cubic increase in size and at least a quadratic bloat can be necessary in the worst case.

I&C Journal 2009 Journal Article

On input-revolving deterministic and nondeterministic finite automata

• Suna Bensch
• Henning Bordihn
• Markus Holzer
• Martin Kutrib

We introduce and investigate input-revolving finite automata, which are (nondeterministic) finite state automata with the additional ability to shift the remaining part of the input. Three different modes of shifting are considered, namely revolving to the left, revolving to the right, and circular interchanging. We investigate the computational capacities of these three types of automata and their deterministic variants, comparing any of the six classes of automata with each other and with further classes of well-known automata. In particular, it is shown that nondeterminism is better than determinism, that is, for all three modes of shifting there is a language accepted by the nondeterministic model but not accepted by any deterministic automaton of the same type. Concerning the closure properties most of the deterministic language families studied are not closed under standard operations. For example, we show that the family of languages accepted by deterministic right-revolving finite automata is an anti-AFL which is not closed under reversal and intersection.

TCS Journal 2009 Journal Article

On the uniqueness of shuffle on words and finite languages

• Franziska Biegler
• Mark Daley
• Markus Holzer
• Ian McQuillan

We investigate a special variant of the shuffle decomposition problem for regular languages; namely, when the given regular language is the shuffle of finite languages. The shuffle decomposition into finite languages is, in general, not unique. That is, there are L 1, L 2, L 3, L 4 with but { L 1, L 2 } ≠ { L 3, L 4 }. However, if all four languages are singletons (with at least two combined letters), it follows by a result of Berstel and Boasson [J. Berstel, L. Boasson, Shuffle factorization is unique, Theoretical Computer Science 273 (2002) 47–67] that the solution is unique; that is, { L 1, L 2 } = { L 3, L 4 }. We further show that if L 1 and L 2 are arbitrary finite sets and L 3 and L 4 are singletons (with at least two letters in each), the solution is unique. Therefore, shuffle decomposition of words is unique not only over words, but over arbitrary sets. This is strong as we cannot let all four be arbitrary finite sets. Hopefully, the obtained results will help to better understand the very nature of the shuffle operation.

TCS Journal 2007 Journal Article

On the average state and transition complexity of finite languages

• Hermann Gruber
• Markus Holzer

We investigate the average-case state and transition complexity of deterministic and nondeterministic finite automata, when choosing a finite language of a certain “size” n uniformly at random from all finite languages of that particular size. Here size means that all words of the language are either of length n, or of length at most n. It is shown that almost all deterministic finite automata accepting finite languages over a binary input alphabet have state complexity Θ ( 2 n n ), while nondeterministic finite automata are shown to perform better, namely the nondeterministic state complexity is in Θ ( 2 n ). Interestingly, in both cases the aforementioned bounds are asymptotically like in the worst case. However, the nondeterministic transition complexity is shown to be again Θ ( 2 n n ). The case of unary finite languages is also considered. Moreover, we develop a framework that allows us to investigate the average-case complexity of operations like, e. g. , union, intersection, complementation, and reversal, on finite languages in this setup.

TCS Journal 2007 Journal Article

The size of Higman–Haines sets

• Hermann Gruber
• Markus Holzer
• Martin Kutrib

We show that for the family of Church–Rosser languages the Higman–Haines sets, which are the sets of all scattered subwords of a given language and the sets of all words that contain some word of a given language as a scattered subword, cannot be effectively constructed, although both these sets are regular for any language. This nicely contrasts the result on the effectiveness of the Higman–Haines sets for the family of context-free languages. The non-effectiveness is based on a non-recursive trade-off result between the language description mechanism of Church–Rosser languages and the corresponding Higman–Haines sets, which in turn is also valid for all supersets of the language family under consideration, and in particular for the family of recursively enumerable languages. Finally for the family of regular languages we prove an upper and a matching lower bound on the size of the Higman–Haines sets in terms of nondeterministic finite automata.

TCS Journal 2006 Journal Article

Iterated sequential transducers as language generating devices

• Henning Bordihn
• Henning Fernau
• Markus Holzer
• Vincenzo Manca
• Carlos Martín-Vide

Iterated finite state sequential transducers are considered as language generating devices. The hierarchy induced by the size of the state alphabet is proved to collapse to the fourth level. The corresponding language families are related to the families of languages generated by Lindenmayer systems and Chomsky grammars. Finally, some results on deterministic and extended iterated finite state transducers are established.

TCS Journal 2005 Journal Article

A common algebraic description for probabilistic and quantum computations

• Martin Beaudry
• José M. Fernandez
• Markus Holzer

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; that is, given a tensor formula F of order n × 1 over a semiring S plus a positive integer k, deciding whether the kth partial trace of the matrix val S n, n ( F · F T ) fulfills a certain property. We use this to show that a certain promise version of the sum-free partial trace problem is complete for the class pr- BPP (promise BPP) for formulas over the semiring ( Q +, +, · ) of the positive rational numbers, for pr-BQP (promise BQP) in the case of formulas defined over the field ( Q +, +, · ), and if the promise is given up, then completeness for PP is shown, regardless whether tensor formulas over positive rationals or rationals in general are used. This suggests that the difference between probabilistic and quantum polytime computers may ultimately lie in the possibility, in the latter case, of having destructive interference between computations occurring in parallel. Moreover, by considering variants of this problem, 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 can be characterized by carrying the problem properties and the underlying semiring.

TCS Journal 2005 Journal Article

On the descriptional complexity of finite automata with modified acceptance conditions

• Markus Holzer
• Martin Kutrib

We consider deterministic and nondeterministic finite automata with acceptance conditions that rely on the whole history of a computation on a given word and not only on the last state of the computation under consideration. Formally, these conditions can be seen as the natural analogies of the Büchi and Muller acceptance for finite automata on infinite words. We study the computational power of these new acceptance mechanisms and prove some results on the descriptional complexity of conversions between automata with these new acceptance criteria and finite automata with ordinary acceptance.

TCS Journal 2004 Journal Article

Assembling molecules in ATOMIX is hard

• Markus Holzer
• Stefan Schwoon

It is shown that assembling molecules in the ATOMIX game can be used to simulate finite automata. In particular, an instance of ATOMIX is constructed that has a solution if and only if the non-emptiness intersection problem for finite automata is solvable. This shows that the game under consideration is PSPACE-complete, improving a recent result of Hüffner et al. (Lecture Notes in Computer Science, Vol. 2174, Springer, Vienna, Austria, 2001, pp. 229–243). Moreover, the given reduction shows that there are ATOMIX games which have exponentially long optimal solutions. We also give an easy construction of ATOMIX game levels whose optimal solutions meet the worst case.

TCS Journal 2004 Journal Article

On deterministic finite automata and syntactic monoid size

• Markus Holzer
• Barbara König

We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of n-state (minimal) deterministic finite automata. We show tight upper and lower bounds on the syntactic monoid size depending on the number of generators (input alphabet size) used. It turns out, that the two generator case is the most involved one. There we show a lower bound of n n 1 - 2 n for the size of the syntactic monoid of a language accepted by an n-state deterministic finite automaton with binary input alphabet. Moreover, we prove that for every prime n ⩾ 7, the maximal size semigroup w. r. t. its size among all (transformation) semigroups which can be generated with two generators, is generated by a permutation with two cycles (of appropriate lengths) and a non-bijective mapping merging elements from these two cycles. As a by-product of our investigations we determine the maximal size among all semigroups generated by two transformations, where one is a permutation with a single cycle and the other is a non-bijective mapping.

TCS Journal 2003 Journal Article

Alternating and empty alternating auxiliary stack automata

• Markus Holzer
• Pierre McKenzie

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 co-DP = NL 〈 NP [1]〉 and Θ 2 P = P NP [O(log n)], in a uniform framework.

TCS Journal 2002 Journal Article

Multi-head finite automata: data-independent versus data-dependent computations

• Markus Holzer

We develop a multi-head finite automata framework suitable for a more detailed study of the relationship between parallel logarithmic time and sequential logarithmic space, in the uniform and nonuniform settings. In both settings it turns out that NC 1 requires data-independent or oblivious computations, i. e. , the movement of the input-heads only depends on the length of the input, whereas logarithmic space is captured with data-dependent computations on multi-head finite state machines. This sheds new light on the question whether NC 1 and logarithmic space coincide.

I&C Journal 1996 Journal Article

Inductive Counting for Width-Restricted Branching Programs

• Carsten Damm
• Markus Holzer

As an application of the inductive counting technique to a circuit-like model, we prove that complementation on nondeterministic branching programs can be done without increasing the width excessively. A consequence of this result is that the class of languages recognized by a generalization of nonuniform finite automata to nonconstant space is closed under complement.