ABSTRACT. Study on numerical properties of words based on scattered subwords of words was initiated around the year 2000, introducing certain upper triangular matrices, called Parikh matrices. On the other hand, linking the areas of combinatorics on words and graph theory, a class of graphs, called Parikh word representable graphs ($PWRG$) of words, was introduced based on certain scattered subwords of words. Several properties of $PWRG$ have been investigated, especially corresponding to binary words. Here, we derive several structural properties of $PWRG$ of images of ternary words under certain morphisms.

ABSTRACT. We propose a strong non-overlapping set of Dyck paths having variable length. First, we construct a set starting from an elevated Dyck path by cutting it in a specific point and inserting suitable Dyck paths (not too long...) in this cutting point. Then, we increase the cardinality of the set by replacing the first and the second factor of the original elevated Dyck path with suitable sets of prefixes and suffixes.

ABSTRACT. We prove that for a given deterministic top-down transducers with look-ahead it is decidable whether or not its translation is definable (1)~by a linear top-down tree transducer or (2)~by a tree homomorphism. We present algorithms that construct equivalent such transducers if they exist.

ABSTRACT. In this paper we combine two classical generalisations of finite automata (weighted automata and automata on infinite words) into a model of integer weighted automata on infinite words and study the universality and the emptiness problems under zero weight acceptance. We show that the universality problem is undecidable for three-state automata by a direct reduction from the infinite Post correspondence problem. We also consider other more general acceptance conditions as well as their complements with respect to the universality and the emptiness problems. Additionally, we build a universal integer weighted automaton where the automaton is fixed and the word problem is undecidable.

ABSTRACT. Second-order finite automata, introduced recently by Andrade de Melo and de Oliveira Oliveira, represent classes of languages. Since their semantics is defined by a synchronized rational relation, they can be studied using the theory of automatic structures. We exploit this connection to uniformly reprove and strengthen known and new results regarding closure and decidability properties concerning these automata. We then proceed to characterize their expressive power in terms of automatic classes of languages studied by Jain, Luo, and Stephan.

ABSTRACT. We continue our investigation on the descriptional complexity of the cascade product of finite state devices started in [\textsc{M.~Holzer}, \textsc{C.~Rauch}: The Range of State Complexities of Languages Resulting from the Cascade Product---The Unary Case (Extended Abstract). Accept for publication at CIAA, 2021]. Here we study the general case, that is, cascade products of reset, permutation-reset, permutation, and finite automata in general, where the left operand automaton has an alphabet of size at least two. In all cases, except for the cascade product of two permutation automata, it is shown that the whole range of state complexities, namely the interval $[1,nm]$, where~$n$ is the state complexity of the left operand and~$m$ that of the right one, is reachable. The cascade product of two permutation automata produces a bunch of non-reachable numbers---numbers of this kind are called magic in the relevant literature, even for arbitrary alphabet sizes. These results are in sharp contrast to the unary case.

ABSTRACT. Two classical families of infinite sequences with some regularity properties are the families of morphic and of automatic  sequences. After recalling their definitions, we survey some recent work trying to "separate" between them.

ABSTRACT. Given a regular language L over an ordered alphabet Σ, the set of lexicographically smallest (resp., largest) words of each length is itself regular. Moreover, there exists an unambiguous finite-state transducer that, on a given word w ∈ Σ^∗, outputs the length-lexicographically smallest word larger than w (henceforth called the L-successor of w). In both cases, naïve constructions result in an exponential blowup in the number of states. We prove that if L is recognized by a DFA with n then 2^\Theta(\sqrt(n log n)) states are sufficient for a DFA to recognize the subset S(L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S(L) is represented as an NFA. We then show that the same upper and lower bounds hold for an unambiguous finite-state transducer that computes L-successors.

ABSTRACT. We study the fine grained complexity of the DFA non-emptiness of intersection problem parameterized by the number k of input automata (k-DFA-NEI). More specifically, we are given a list ⟨A₁,...,A_k⟩ of DFA’s over a common alphabet Σ, and the goal is to determine whether ⋂{i=1}^k L(A_i)<> ∅. This problem can be solved in time O(n^k) by applying the classic Rabin-Scott product construction. In this work, we show that the existence of algorithms solving k-DFA-NEI in time slightly faster than O(n^k) would imply the existence of deterministic sub-exponential time algorithms for the simulation of nondeterministic linear space bounded computations. This consequence strengthens the existing conditional lower bounds for k-DFA-NEI and implies new non-uniform circuit lower bounds.

ABSTRACT. A word u = u₁...u_n is a scattered factor of a word w if u can be obtained from w by deleting some of its letters: there exist the (potentially empty) words v₀ ,v₁, ... , v_n such that w = v₀u₁v₁...u_nv_n. The set of all scattered factors up to length k of a word is called its full k-spectrum. Firstly, we show an algorithm deciding whether the k-spectra for given k of two words are equal or not, running in optimal time. Secondly, we consider a notion of scattered-factors universality: the word w, with alph(w) = Σ, is called k-universal if its k-spectrum includes all words of length k over the alphabet Σ; we extend this notion to k-circular universality. After a series of preliminary combinatorial results, we present an algorithm computing, for a given k′-universal word w the minimal i such that wi is k-universal for some k > k′. Several other connected problems are also considered.

ABSTRACT. The projected language of a general deterministic automaton with $n$ states is recognizable by a deterministic automaton with $2^{n-1} + 2^{n-m} - 1$ states, where $m$ denotes the number of states incident to unobservable non-loop transitions, and this bound is best possible. Here, we derive the sharp bound $2^{n - \lceil \frac{m}{2} \rceil} - 1$ for permutation automata. For a state-partition automaton with $n$ states, also called automata with the observer property, the projected language is recognizable with $n$ states. Up to now, these, and finite languages projected onto unary languages, were the only classes of automata known to possess this property. We will show that this is also true for commutative automata and we find commutative automata that are not state-partition automata.

ABSTRACT. We present a formalization of Lyndon words and basic relevant results in Isabelle/HOL. We give a short review of Isabelle/HOL and focus on challenges that arise in this formalization. The presented formalization is based on an ongoing larger project of formalization of Combinatorics on Words.