Search

International audience; This special issue contains eight articles which are based on extended abstracts that were presented at the 35th Symposium on Theoretical Aspects of Computer Science (STACS), which was held at the University of Caen from February 28th to March 3rd, 2018. These extended abstracts were chosen among the top papers of those that were selected for presentation at STACS 2018 in a highly competitive peer-review process (after which only 54 papers out of 186 submissions were accepted). Compared with the original extended abstracts, the articles have been extended with a description of the context, full proofs and additional results. They underwent a further rigorous reviewing process, following the TOCS Journal standards, completely independent from the selection process of STACS 2018. The topics of the chosen papers cover a rich set of areas within Theoretical Computer Science, that is, algorithmic game theory, automata theory, circuit complexity, efficient algorithms, logic and model checking, Markov chains, pa-rameterized complexity, and proof complexity. Kernelization (provably effective and efficient preprocessing) is a central theme in parameterized complexity. The article Computing Hitting Set Kernels by AC 0-Circuits by Max Bannach and Till Tantau presents for the first time kernels for the d-Hitting Set problem that can be computed in constant parallel time, thereby refuting a previous conjecture. To this end, the authors introduce a new, generalized notion of hypergraph sunflowers. Altogether, this gives an important contribution to parameterized circuit complexity.

We show how some problems in additive number theory can be attacked in a novel way, using techniques from the theory of finite automata. We start by recalling the relationship between first-order logic and finite automata, and use this relationship to solve several problems involving sums of numbers defined by their base-2 and Fibonacci representations. Next, we turn to harder results. Recently, Cilleruelo, Luca, & Baxter proved, for all bases b ≥ 5, that every natural number is the sum of at most 3 natural numbers whose base-b representation is a palindrome (Cilleruelo et al., Math. Comput. 87, 3023–3055, 2018). However, the cases b = 2, 3, 4 were left unresolved. We prove that every natural number is the sum of at most 4 natural numbers whose base-2 representation is a palindrome. Here the constant 4 is optimal. We obtain similar results for bases 3 and 4, thus completely resolving the problem of palindromes as an additive basis. We consider some other variations on this problem, and prove similar results. We argue that heavily case-based proofs are a good signal that a decision procedure may help to automate the proof.

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theories of typed monoids and of rational series are used to characterize the language classes that arise algebraically. Complexity bounds are derived, such as containment of the unambiguous Parikh automata languages in NC1. Affine Parikh automata, where each transition applies an affine transformation on the registers, are also considered. Relying on these characterizations, the landscape of relationships and closure properties of the classes at hand is completed, in particular over unary languages.

In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after which all of the predictor’s guesses are correct. In this paper we consider the case in which the predictor is an automaton and the emitted values are drawn from a finite set; i.e., the emitted sequence is an infinite word. We examine the predictive capabilities of finite automata, pushdown automata, stack automata (a generalization of pushdown automata), and multihead finite automata. We relate our predicting automata to purely periodic words, ultimately periodic words, and multilinear words, describing novel prediction algorithms for mastering these sequences.

We show that the problem of checking careful synchronizability of partial finite automata is PSPACE-complete. Also the problems of checking D 1-, D 2-, and D 3-directability of nondeterministic finite automata are PSPACE-complete; moreover, the restrictions of all these problems to automata with two input letters remain PSPACE-complete.

Various automata using certain kinds of tuples of storages are defined in the literature. In this paper we investigate some possibilities to define such storages independently of automata by a restricted type of product on storages, called concatenation. It is shown that there is a strong relation between automata with concatenated pushdowns and restricted classes of linear controlled grammars. Using this result, some relations between hierarchies of automata with an ascending number of concatenated pushdowns and some well-known hierarchies of controlled grammars follow naturally.

We prove that several problems associated with probabilistic finite automata are undecidable for automata whose number of input letters and number of states are fixed. As a corollary of one of our results we prove that the problem of determining if the set of all products of two 47 x 47 matrices with nonnegative rational entries is bounded is undecidable.

We present properties of multihead two-way probabilistic finite automata that parallel those of their deterministic and nondeterministic counterparts. We define multihead probabilistic finite automata withlogspace constructible transition probabilities, and we describe a technique to simulate these automata by standard logspace probabilistic Turing machines. Next, we represent logspace probabilistic complexity classes as proper hierarchies based on corresponding multihead two-way probabilistic finite automata, and we show their (deterministic logspace) reducibility to the second levels of these hierarchies. We obtain a simple formula for the maximum inherent bandwidth of the configuration transition matrices associated with thek-head probabilistic finite automata processing a length-n input string. (The inherent bandwidth of the configuration transition matrices associated with an automaton processing a length-n input string is the smallest bandwidth we can get by changing the enumeration order of the automaton’s configurations.) Partially based on this relation, we find an apparently easier logspace complete problem forPL (the class of languages recognized by logspace unbounded-error probabilistic Turing machines), and we discuss possibilities for a space-efficient deterministic simulation of probabilistic automata.

The time-honored Chomsky hierarchy has long shown its value as a structural tool in formal languages and automata theory, and gained followers in various areas. We show here how very similar hierarchies can be obtained for families of sets of piecewise continuous functions. We use systems of ordinary differential equations in the same way that automata are used in establishing the traditional Chomsky hierarchy. A functional memory is provided by state-dependent delays which are used in a novel way, paired with certain state components, giving memory structures similar to push-down stores and Turing machine tapes. The resulting machine model may be viewed as a “functional computing machine’’, with functional input, functional memory and, though this is not emphasized here, functional output.