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.

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.

Hamburg was the place where he used to live from his childhood onwards.There, he also obtained his doctoral degree with his dissertation entitled "Kontextfrei kontrollierte ET0L-Systeme" (engl."Context-free Controlled ET0L-Systems") in 1983, and his habilitation with the thesis "Nichtdeterministische Reduktionen und logarithmische Hierarchien" (engl."Nondeterministic Reductions and Logarithmic Hierarchies") in 1986.During his Hamburg years he visited

In the Intersection Non-Emptiness problem, we are given a list of finite automata $A_1,A_2,\dots,A_m$ over a common alphabet $Σ$ as input, and the goal is to determine whether some string $w\in Σ^*$ lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-Emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels zero or one half and already PSPACE-hard when all automata accept a language from the level one. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC$^0$ when restricted to level zero; complete for LOGSPACE or NLOGSPACE, depending on the input representation, when restricted to languages in the level one half; NP-complete when the input is given as DFAs accepting a language in from level one or three half; and finally, PSPACE-complete when the input automata accept languages in level two or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in the Straubing-Thérien hierarchy levels one ore three half does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.

A two-sided extension of strictly locally testable languages is presented. In order to determine membership within a two-sided strictly locally testable language, the input must be scanned from both ends simultaneously, whereby it is synchronously checked that the factors read are correlated with respect to a given binary relation. The class of two-sided strictly locally testable languages is shown to be a proper subclass of the even linear languages that is incomparable to the regular languages with respect to inclusion. Furthermore, closure properties of the class of two-sided strictly locally testable languages and decision problems are studied. Finally, it is shown that two-sided strictly k-testable languages are learnable in the limit from positive data.

We investigate the state complexity of the cut and iterated cut operation for deterministic finite automata (DFAs), answering an open question stated in [M. BERGLUND, et al.: Cuts in regular expressions. In Proc. DLT, LNCS 7907, 2011]. These operations can be seen as an alternative to ordinary conc atenation and Kleene star modelling leftmost maximal string matching. We show that the cut operation has a matching upper and lower bound of n states, if m = 1, and (n–1)·m+n states, otherwise, on DFAs accepting the cut of two individual languages that are accepted by n- and m-state DFAs, respectively. In the unary case we obtain max(2n–1,m+n–2) states as a tight bound—notice that for m ≤ n the bound for unary DFAs only depends on the former automaton and not on the latter. For accepting the iterated cut of a language accepted by an n-state DFA we find a matching bound of 1+(n+1) · F(1,n+2,–n+2;n+1 | –1) states on DFAs, if n ≥ 4 and where F refers to the generalized hypergeometric function. This bound is in the order of magnitude Θ((n – 1)!). Finally, the bound drops to 2n – 1 for unary DFAs accepting the iterated cut of an n-state DFA, if n ≥ 3, and thus is similar to the bound for the cut operation on unary DFAs.

We consider the computational complexity of problems related to partial word automata. Roughly speaking, a partial word is a word in which some positions are unspecified and a partial word automaton is a finite automaton that accepts a partial word language—here the unspecified positions in the wor d are represented by a “hole” symbol ⋄. A partial word language L′ can be transformed into an ordinary language L by using a ⋄-substitution. In particular, we investigate the complexity of the compression or minimization problem for partial word automata, which is known to be NP-hard. We improve on the previously known complexity on this problem, by showing PSPACE-completeness. In fact, it turns out that almost all problems related to partial word automata, such as, e.g., equivalence and universality, are already PSPACE-complete. Moreover, we also study these problems under the further restriction that the involved automata accept only finite languages. In this case, the complexities of the studied problems drop from PSPACE-completeness down to coNP-hardness and containment in ∑2P depending on the problem investigated.

We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the

Many non-classical automata models are natural objects of theoretical computer science.They are studied from different points of view in various areas, both as theoretical concepts and as formal models for applications.A deeper and interdisciplinary coverage of this particular area may lead to new insights and substantial progress.The Second Workshop on Non-Classical Models of Automata and Applications (NCMA 2010) has been organized in order to bring together researchers working on different aspects of various variants of non-classical automata models to exchange and develop novel ideas.

We show that the popular pencil puzzle NURIKABE is intractable from the computational complexity point of view, that is, it is NP-complete, even when the involved numbers are 1 and 2 only. To this end, we show how to simulate Boolean gates by the puzzle under consideration. Moreover, we also study some NURIKABE variants, which remain NP-complete, too.

We study computational problems arising from the iterated removal of weakly dominated actions in anonymous games. Our main result shows that it is NP-complete to decide whether an anonymous game with three actions can be solved via iterated weak dominance. The two-action case can be reformulated as a natural elimination problem on a matrix, the complexity of which turns out to be surprisingly difficult to characterize and ultimately remains open. We however establish connections to a matching problem along paths in a directed graph, which is computationally hard in general but can also be used to identify tractable cases of matrix elimination. We finally identify different classes of anonymous games where iterated dominance is in P and NP-complete, respectively.

A not so well-known result in formal language theory is that the Higman-Haines sets for any language are regular [11, Theorem 4.4]. It is easily seen that these sets cannot be effectively computed in general. The Higman-Haines sets are the languages of all scattered subwords of a given language as well as the sets of all words that contain some word of a given language as a scattered subword. Recently, the exact level of unsolvability of Higman-Haines sets was studied in [8]. Here we focus on language families whose Higman-Haines sets are effectively constructible. In particular, we study the size of descriptions of Higman-Haines sets for the lower classes of the Chomsky hierarchy, namely for the family of regular, linear context-free, and context-free languages. We prove upper and lower bounds on the size of descriptions of these sets for general and unary languages.

Tensor calculus over semirings is shown relevant to complexity theory in unexpected ways. First, evaluating well-formed tensor formulas with explicit tensor entries is shown complete for $\bigoplusP$, for NP, and for #P as the semiring varies. Indeed the permanent of a matrix is shown expressible as the value of a tensor formula in much the same way that Berkowitz’s theorem expresses its determinant. Second, restricted tensor formulas are shown to capture the classes LOGCFL and NL, their parity counterparts $\bigoplusLOGCFL$ and $\bigoplusL$, and several other counting classes. Finally, the known inclusions $\NP/\poly \subseteq \bigoplusP/\poly$, $\LOGCFL/\poly \subseteq \bigoplusLOGCFL/\poly$, and $\NL/\poly \subseteq \bigoplusL/\poly$, which have scattered proofs in the literature (Valiant & Vazirani 1986; Gál & Wigderson 1996), are shown to follow from the new characterizations in a single blow. As an intermediate tool, we define and make use of the natural notion of an algebraic Turing machine over a semiring $ \mathcal{S}$.

We consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.