Author name cluster

Andreas Malcher

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.

24 papers

2 author rows

I&C Journal 2026 Journal Article

Deterministic pushdown automata with translucent input letters

Martin Kutrib
Andreas Malcher
Carlo Mereghetti
Beatrice Palano
Priscilla Raucci
Matthias Wendlandt

The use of translucent input letters represents a way of implementing a discontinuous input processing in automata. In detail, a translucent automaton performs several sweeps from left to right on the input: according to the current state, some symbols are visible and can be processed, whereas some other symbols are invisible and may be processed in another sweep. We also distinguish between the returning and non-returning mode, which differ in the way the automaton behaves after reading a symbol: in the returning mode, a new sweep starts immediately, while in the non-returning mode, the device processes the next visible symbol. Here, we investigate deterministic pushdown automata with translucent letters both in the returning and non-returning mode. We prove that the non-returning mode strictly outperforms the returning mode, and that the families of the languages accepted by these two types of devices can be ranked strictly between the deterministic context-free languages and the deterministic context-sensitive languages. Moreover, both families are shown to be incomparable to the families of context-free, growing context-sensitive, and Church-Rosser languages. The ability of accepting non-semilinear languages is also emphasized (addressing an open question in the literature). Finally, we study the closure properties of both language families under the Boolean operations, obtaining that they are both closed under complementation but not under union and intersection. Further non-closure results are pointed-out for returning devices.

TCS Journal 2026 Journal Article

On properties of languages accepted by deterministic pushdown automata with translucent input letters

Martin Kutrib
Andreas Malcher
Carlo Mereghetti
Beatrice Palano
Priscilla Raucci
Matthias Wendlandt

We study deterministic pushdown automata operating with translucent input letters. These devices can be obtained by equipping classical deterministic pushdown automata with a translucency function which, depending on the current state, establishes the set of invisible input symbols: such invisible symbols are skipped in the current move and dealt with in subsequent sweeps, while the first visible symbol from the current input head position rightward is processed and consumed. Deterministic pushdown automata with translucent input letters can be returning, meaning that a new input sweep starts from the leftmost input symbol left on the tape immediately after processing a visible symbol, or non-returning. We show some incomparability results between the acceptance capabilities of returning and non-returning deterministic pushdown automata with translucent input letters and those of non-returning deterministic and nondeterministic finite state automata with translucent input letters. Then, we prove the non-closure of the families of languages accepted by returning and non-returning deterministic pushdown automata with translucent input letters under: concatenation, Kleene star, length-preserving and inverse homomorphism, reversal, and intersection with regular languages. In particular, arguments used to prove the non-closure under intersection with regular languages enable us to answer a question left open in the literature, on the recognition power of non-returning deterministic finite state automata with translucent input letters.

I&C Journal 2025 Journal Article

Complexity of exclusive nondeterministic finite automata

Martin Kutrib
Andreas Malcher
Matthias Wendlandt

Exclusive nondeterministic finite automata (XNFA) are nondeterministic finite automata with an exclusive-or-like acceptance condition. An input is accepted if there is exactly one accepting path in its computation tree. If there are none or more than one accepting paths, the input is rejected. It turns out that, from a descriptional complexity point of view, XNFAs differ significantly from the known types of finite automata. In particular the state costs for the simulation of an XNFA by a DFA are 3 n − 2 n + 1 states, while the costs for simulating an XNFA by an NFA are n ⋅ 2 n − 1 states. Both bounds are also shown to be tight. On the other hand, NFAs may have advantages in comparison to XNFAs. For the simulation of an NFA by an XNFA, a tight bound of 2 n − 1 states is given. Finally, we investigate the computational complexity of different decision problems for XNFAs and it turns out that emptiness, universality, inclusion, and equivalence are PSPACE-complete.

TCS Journal 2024 Journal Article

On the power of pushing or stationary moves for input-driven pushdown automata

Martin Kutrib
Andreas Malcher
Matthias Wendlandt

Input-driven pushdown automata (IDPDAs) are pushdown automata where the next action on the pushdown store (push, pop, nothing) is solely governed by the input symbol. Nowadays such devices are usually defined such that every push operation pushes exactly one additional symbol on the pushdown store and, in addition, stationary moves are not allowed so that the devices work in real time. Here, we relax this strong definition and consider IDPDAs that may push more than one symbol in one step (push-IDPDA) or may perform stationary moves (stat-IDPDA). We study the computational power of the extended variants both in the deterministic and nondeterministic case, we investigate several decidability questions for the new automata classes, and we obtain interesting representations by inverse homomorphisms. Namely, every (1) deterministic, (2) real-time deterministic, and (3) nondeterministic context-free language can be characterized as the inverse homomorphic image of a language accepted by a (1) stat-IDPDA, (2) push-IDPDA, and (3) nondeterministic push-IDPDA.

TCS Journal 2023 Journal Article

Iterated uniform finite-state transducers on unary languages

Martin Kutrib
Andreas Malcher
Carlo Mereghetti
Beatrice Palano

An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep works on the output of the previous one. All sweeps always start from the sole initial state. The device accepts upon halting in an accepting state at the end of a sweep. We consider devices with one-way sweep motion and two-way sweep motion, i. e. , sweeps are either from left to right only, or strictly alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. We focus on iterated uniform finite-state transducers accepting unary languages, i. e. , languages built over single-letter alphabets. We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max ⁡ { 2 ⋅ ϱ, p } + 1 states, where ϱ and p are the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. Such a state cost cannot be improved by using two-way motion, and it turns out to greatly outperform in the worst case the state costs of equivalent classical models of finite-state automata. Next, we give a characterization of classes of unary languages accepted by non-constant sweep-bounded iterated uniform finite-state transducers in terms of time-bounded one-way cellular automata. This characterization enables both to exhibit interesting families of unary nonregular languages accepted by iterated uniform finite-state transducers, and to prove the undecidability of several questions related to iterated uniform finite-state transducers accepting unary languages with an amount of sweeps that is at least logarithmic.

I&C Journal 2022 Journal Article

Descriptional complexity of iterated uniform finite-state transducers

Martin Kutrib
Andreas Malcher
Carlo Mereghetti
Beatrice Palano

We introduce the deterministic computational model of an iterated uniform finite-state transducer (iufst). An iufst performs the same length-preserving transduction on several left-to-right sweeps. The first sweep acts on the input string, any other sweep processes the output of the previous one. The iufst accepts by halting in an accepting state at the end of a sweep. First, we study constant sweep bounded iufsts. We prove their computational power coincides with the class of regular languages. We show their descriptional power vs. deterministic finite automata, and the state cost of implementing language operations. We prove the NL-completeness of typical decision problems. Next, we analyze non-constant sweep bounded iufsts. We show they can accept non-regular languages provided an at least logarithmic amount of sweeps is allowed. We exhibit a proper non-regular language hierarchy depending on sweep complexity. The non-semidecidability of typical decision problems is also addressed.

TCS Journal 2021 Journal Article

Input-driven multi-counter automata

Martin Kutrib
Andreas Malcher
Matthias Wendlandt

The model of deterministic input-driven multi-counter automata is introduced and studied. On such devices, the input letters uniquely determine the operations on the underlying data structure that is consisting of multiple counters. We study the computational power of the resulting language families and compare them with known language families inside the Chomsky hierarchy. In addition, it is possible to prove a proper counter hierarchy depending on the alphabet size. This means that any input alphabet induces an upper bound which depends on the alphabet size only, such that k + 1 counters are more powerful than k counters as long as k is less than this bound. The hierarchy interestingly collapses at the level of the bound. Furthermore, we investigate the closure properties of the language families. For input-driven multi-counter automata with 0 or 1 counter, we discuss the computational complexity of their decidable problems. For k ≥ 2 counters, the decidability problems of emptiness, finiteness, universality, inclusion, equivalence, regularity, and context-freeness are shown to be non-semidecidable. Finally, we study descriptional complexity aspects of input-driven multi-counter automata. It is shown that a nondeterministic device can be determinized and that 2 n − 1 is a necessary and sufficient blow-up in the number of states for the determinization. For the operational state complexity of deterministic input-driven multi-counter automata under Boolean operations, tight bounds on the number of states are established. Finally, it turns out that the size trade-offs between deterministic input-driven multi-counter automata with k + 1 and k counters are non-recursive, that is, they are not bounded by any recursive function.

I&C Journal 2021 Journal Article

Reversible pushdown transducers

Bruno Guillon
Martin Kutrib
Andreas Malcher
Luca Prigioniero

Deterministic pushdown transducers are studied with respect to their ability to compute reversible transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are also backward deterministic and thus are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to four types of length-preserving transductions as well as to the property of working reversibly. It turns out that accurate to one case separating witness transductions can be provided. For the remaining case it is possible to establish the equivalence of both families by proving that stationary moves can always be removed in length-preserving reversible pushdown transductions.

TCS Journal 2019 Journal Article

Transducing reversibly with finite state machines

Martin Kutrib
Andreas Malcher
Matthias Wendlandt

Finite state machines are investigated towards their ability to reversibly compute transductions, that is, to transform inputs into outputs in a reversible way. This means that the transducers are backward deterministic and hence are able to uniquely step the computation back and forth. The families of transductions computed are classified with regard to three types of length-preserving transductions as well as to the property of working reversibly. It is possible to settle all inclusion relations between these families of transductions even with injective witness transductions. Furthermore, the standard closure properties and decidability questions are investigated. It turns out that the non-closure under almost all operations can be shown, whereas all decidability questions can be answered in polynomial time. Finally, the concept of reversibility is extended to a broader view of reversibility and an infinite and dense hierarchy with respect to the grade of reversibility is obtained.

TCS Journal 2017 Journal Article

One-way reversible multi-head finite automata

Martin Kutrib
Andreas Malcher

One-way multi-head finite automata are considered towards their ability to perform reversible computations. It is shown that, for every number k ≥ 1 of heads, there are problems which can be solved by one-way k-head finite automata, but not by any one-way reversible k-head finite automaton. Additionally, a proper head hierarchy is obtained for one-way reversible multi-head finite automata. Closure properties and decidability problems are investigated as well. It turns out that one-way reversible finite automata with two heads are still a powerful model, since almost all commonly studied problems are not even semidecidable. Finally, descriptional complexity aspects are studied and non-recursive trade-offs are shown.

TCS Journal 2015 Journal Article

Deterministic input-driven queue automata: Finite turns, decidability, and closure properties

Martin Kutrib
Andreas Malcher
Carlo Mereghetti
Beatrice Palano
Matthias Wendlandt

We introduce and study the model of deterministic input-driven queue automata. On such devices, the input letters uniquely determine the operations on the memory store which is organized as a queue. In particular, we consider the case where only a finite number of turns on the queue is allowed. The resulting language families share with regular languages many desirable properties. We show that emptiness and several other problems are decidable. Furthermore, we investigate closure under Boolean operations. The existence of an infinite and tight hierarchy depending on the number of turns is also proved.

I&C Journal 2014 Journal Article

Oblivious two-way finite automata: Decidability and complexity

Martin Kutrib
Andreas Malcher
Giovanni Pighizzini

We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata. In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs by sweeping 2DFAs and one-way nondeterministic finite automata (1NFAs) as well as the simulation of sweeping 2DFAs by 1NFAs. In all cases exponential lower bounds on the number of states are obtained for languages over an alphabet with at most four letters. Finally, a procedure for deciding obliviousness of an arbitrary 2DFA is given and, moreover, the problem is shown to be PSPACE-complete.

I&C Journal 2013 Journal Article

Descriptional complexity of bounded context-free languages

Andreas Malcher
Giovanni Pighizzini

We investigate finite-turn pushdown automata (PDAs) from the point of view of descriptional complexity. It is known that such automata accept exactly the class of ultralinear context-free languages. Furthermore, the increase in size when converting arbitrary PDAs accepting ultralinear languages to finite-turn PDAs cannot be bounded by any recursive function. The latter phenomenon is known as non-recursive trade-off. In this paper, we consider finite-turn PDAs that can accept bounded languages. First, we study letter-bounded languages and prove that, in this case, the non-recursive trade-off is reduced to a recursive trade-off, more precisely, to an exponential trade-off. We present a conversion algorithm and show the optimality of the construction by proving tight lower bounds. Furthermore, we study the question of reducing the number of turns of a given finite-turn PDA. Again, we provide a conversion algorithm which shows that, in this case, the trade-off is at most polynomial. Finally, we investigate the more general case of word-bounded languages and show how the results obtained for letter-bounded languages can be extended to word-bounded languages.

TCS Journal 2012 Journal Article

Descriptional complexity of two-way pushdown automata with restricted head reversals

Andreas Malcher
Carlo Mereghetti
Beatrice Palano

Two-way nondeterministic pushdown automata ( 2PDA ) are classical nondeterministic pushdown automata ( PDA ) enhanced with two-way motion of the input head. In this paper, the subclass of 2PDA accepting bounded languages and making at most a constant number of input head turns is studied with respect to descriptional complexity aspects. In particular, the effect of reducing the number of pushdown reversals to a constant number is of interest. It turns out that this reduction leads to an exponential blow-up in case of nondeterministic devices, and to a doubly-exponential blow-up in case of deterministic devices. If the restriction on boundedness of the languages considered and on the finiteness of the number of head and pushdown turns is dropped, the resulting trade-offs are no longer bounded by recursive functions, and so-called non-recursive trade-offs are shown.

TCS Journal 2011 Journal Article

Cellular automata with limited inter-cell bandwidth

Martin Kutrib
Andreas Malcher

A d -dimensional cellular automaton is a d -dimensional grid of interconnected interacting finite automata. There are models with parallel and sequential input modes. In the latter case, the distinguished automaton at the origin, the communication cell, is connected to the outside world and fetches the input sequentially. Often in the literature this model is referred to as an iterative array. In this paper, d -dimensional iterative arrays and one-dimensional cellular automata are investigated which operate in real and linear time and whose inter-cell communication bandwidth is restricted to some constant number of different messages independent of the number of states. It is known that even one-dimensional two-message iterative arrays accept rather complicated languages such as { a p ∣ p prime } or { a 2 n ∣ n ∈ N } (H. Umeo, N. Kamikawa, Real-time generation of primes by a 1-bit-communication cellular automaton, Fund. Inform. 58 (2003) 421–435). Here, the computational capacity of d -dimensional iterative arrays with restricted communication is investigated and an infinite two-dimensional hierarchy with respect to dimensions and messages is shown. Furthermore, the computational capacity of the one-dimensional devices in question is compared with the power of two-way and one-way cellular automata with restricted communication. It turns out that the relations between iterative arrays and cellular automata are quite different from the relations in the unrestricted case. Additionally, an infinite strict message hierarchy for real-time two-way cellular automata is obtained as well as a very dense time hierarchy for k -message two-way cellular automata. Finally, the closure properties of one-dimensional iterative arrays with restricted communication are investigated and differences to the unrestricted case are shown as well.

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.

TCS Journal 2010 Journal Article

Cellular automata with sparse communication

Martin Kutrib
Andreas Malcher

We investigate cellular automata whose internal inter-cell communication is bounded. The communication is quantitatively measured by the number of uses of the links between cells. Bounds on the sum of all communications of a computation as well as bounds on the maximal number of communications that may appear between each two cells are considered. It is shown that even the weakest non-trivial device in question, that is, one-way cellular automata where each two neighboring cells may communicate constantly often only, accept rather complicated languages. We investigate the computational capacity of the devices in question and prove an infinite strict hierarchy depending on the bound on the total number of communications during a computation. Despite their sparse communication even for the weakest devices, by reduction of Hilbert’s tenth problem the undecidability of several problems is derived. Finally, the question of whether a given real-time one-way cellular automaton belongs to the weakest class is shown to be undecidable. This result can be used to answer an open question.

TCS Journal 2010 Journal Article

Real-time reversible iterative arrays

Martin Kutrib
Andreas Malcher

Iterative arrays are one-dimensional arrays of interconnected interacting finite automata. The cell at the origin is equipped with a one-way read-only input tape. We investigate iterative arrays as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i. e. , from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. It is shown that real-time reversible iterative arrays can simulate restricted variants of stacks and queues. It turns out that real-time reversible iterative arrays are strictly weaker than real-time reversible cellular automata. On the other hand, a non-semilinear language is accepted. We show that real-time reversibility itself is not even semidecidable, which extends the undecidability for cellular automata and contrasts with the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the non-semidecidability of several other properties. Several closure properties are also derived.

TCS Journal 2009 Journal Article

Regulated nondeterminism in pushdown automata

Martin Kutrib
Andreas Malcher
Larissa Werlein

A generalization of pushdown automata towards regulated nondeterminism is studied. The nondeterminism is governed in such a way that the decision, whether or not a nondeterministic rule is applied, depends on the whole content of the stack. More precisely, the content of the stack is considered as a word over the stack alphabet, and the pushdown automaton is allowed to act nondeterministically, if this word belongs to some given set R of control words. Otherwise its behavior is deterministic. It turns out that non-context-free languages can be accepted if R is a context-free and non-regular language. On the other hand, if the control sets R are regular languages, then the resulting devices are not more powerful than nondeterministic pushdown automata. This raises the natural question of the relations between the structure and complexity of regular sets R on one hand and the computational capacity of the corresponding R - PDA on the other hand. The main result of the paper shows that an infinite proper hierarchy of regular control sets leads to an infinite proper hierarchy of the corresponding language classes. Additionally, closure properties and decision problems of these language classes are investigated.

I&C Journal 2008 Journal Article

Fast reversible language recognition using cellular automata

Martin Kutrib
Andreas Malcher

We investigate cellular automata as acceptors for formal languages. In particular, we consider real-time devices which are reversible on the core of computation, i. e. , from initial configuration to the configuration given by the time complexity. This property is called real-time reversibility. We study whether for a given real-time CA working on finite configurations with fixed boundary conditions there exists a reverse real-time CA with the same neighborhood. It is shown that real-time reversibility is undecidable, which contrasts the general case, where reversibility is decidable for one-dimensional devices. Moreover, we prove the undecidability of emptiness, finiteness, infiniteness, inclusion, equivalence, regularity, and context-freedom. First steps towards the exploration of the computational capacity are done and closure under Boolean operations is shown.

TCS Journal 2007 Journal Article

Context-dependent nondeterminism for pushdown automata

Martin Kutrib
Andreas Malcher

Pushdown automata using a limited and unlimited amount of nondeterminism are investigated. Moreover, nondeterministic steps are allowed only within certain contexts, i. e. , in configurations that meet particular conditions. The relationships of the accepted language families with closures of the deterministic context-free languages (DCFL) under regular operations are studied. For example, automata with unbounded nondeterminism that have to empty their pushdown store up to the initial symbol in order to make a guess are characterized by the regular closure of DCFL. Automata that additionally have to reenter the initial state are (almost) characterized by the Kleene star closure of the union closure of the prefix-free deterministic context-free languages. Pushdown automata with bounded nondeterminism are characterized by the union closure of DCFL in any of the considered contexts. Proper inclusions between all language classes discussed are shown. Finally, closure properties of these families under AFL operations are investigated.

MFCS Conference 2006 Conference Paper

Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability

Martin Kutrib
Andreas Malcher

Abstract Iterative arrays (IAs) are one-dimensional arrays of interconnected interacting finite automata with sequential input mode. We investigate IAs which work in real time and whose inter-cell communication is bounded by some constant number of bits not depending on the number of states. It is known [13] that such IAs can recognize rather complicated unary languages with a minimum amount of communication, namely one-bit communication, in real time. Some examples are the languages \(\{a^{2^n} \mid n \ge 1\}\), \(\{a^{n^2} \mid n \ge 1\}\), and { a p | p is prime}. Here, we consider non-unary languages and it turns out that the non-unary case is quite different. We present several real-time constructions for certain non-unary languages. For example, the languages { a n b n | n ≥1}, { a n ( b n ) m | n, m ≥1}, and { a n ba m b ( ba ) n. m | n, m ≥1} are recognized in real time by 1-bit IAs. Moreover, it is shown that real-time 1-bit IAs can, in some sense, add and multiply integer numbers. Furthermore, closure properties and decidability questions of communication restricted IAs are investigated. Due to the constructions provided, non-closure results as well as undecidability results can be shown. It turns out that emptiness is still undecidable for 1-bit IAs despite their restricted communication. Thus, also the questions of finiteness, infiniteness, inclusion, and equivalence are undecidable.

TCS Journal 2005 Journal Article

On two-way communication in cellular automata with a fixed number of cells

Andreas Malcher

The effect of adding two-way communication to k cells one-way cellular automata (kC-OCAs) on their size of description is studied. kC-OCAs are a parallel model for the regular languages that consists of an array of k identical deterministic finite automata (DFAs), called cells, operating in parallel. Each cell gets information from its right neighbor only. In this paper, two models with different amounts of two-way communication are investigated. Both models always achieve quadratic savings when compared to DFAs. When compared to a one-way cellular model, the result is that minimum two-way communication can achieve at most quadratic savings whereas maximum two-way communication may provide savings bounded by a polynomial of degree k.

TCS Journal 2004 Journal Article

Minimizing finite automata is computationally hard

Andreas Malcher

It is known that deterministic finite automata (DFAs) can be algorithmically minimized, i. e. , a DFA M can be converted to an equivalent DFA M ′ which has a minimal number of states. The minimization can be done efficiently (in: Z. Kohavi (Ed.), Theory of Machines and Computations, Academic Press, New York, 1971, pp. 189–196). On the other hand, it is known that unambiguous finite automata and nondeterministic finite automata can be algorithmically minimized too, but their minimization problems turn out to be NP -complete and PSPACE -complete, respectively (SIAM J. Comput. 22(6) (1993) 1117–1141). In this paper, the time complexity of the minimization problem for two restricted types of finite automata is investigated. These automata are nearly deterministic, since they only allow a small amount of nondeterminism to be used. The main result is that the minimization problems for these models are computationally hard, namely NP -complete. Hence, even the slightest extension of the deterministic model towards a nondeterministic one, e. g. , allowing at most one nondeterministic move in every accepting computation or allowing two initial states instead of one, results in computationally intractable minimization problems.