Formal Languages and Automata Theory (cs.FL)

  • PDF
    Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts.
  • PDF
    We introduce and study cellular automata whose cell spaces are left-homogeneous spaces. Examples of left-homogeneous spaces are spheres, Euclidean spaces, as well as hyperbolic spaces acted on by isometries; uniform tilings acted on by symmetries; vertex-transitive graphs, in particular, Cayley graphs, acted on by automorphisms; groups acting on themselves by multiplication; and integer lattices acted on by translations. For such automata and spaces, we prove, in particular, generalisations of topological and uniform variants of the Curtis-Hedlund-Lyndon theorem, of the Tarski-Følner theorem, and of the Garden-of-Eden theorem on the full shift and certain subshifts. Moreover, we introduce signal machines that can handle accumulations of events and using such machines we present a time-optimal quasi-solution of the firing mob synchronisation problem on finite and connected graphs.
  • PDF
    We compare pushdown automata (PDAs for short) against other representations. First, we show that there is a family of PDAs over a unary alphabet with $n$ states and $p \geq 2n + 4$ stack symbols that accepts one single long word for which every equivalent context-free grammar needs $\Omega(n^2(p-2n-4))$ variables. This family shows that the classical algorithm for converting a PDA to an equivalent context-free grammar is optimal even when the alphabet is unary. Moreover, we observe that language equivalence and Parikh equivalence, which ignores the ordering between symbols, coincide for this family. We conclude that, when assuming this weaker equivalence, the conversion algorithm is also optimal. Second, Parikh's theorem motivates the comparison of PDAs against finite state automata. In particular, the same family of unary PDAs gives a lower bound on the number of states of every Parikh-equivalent finite state automaton. Finally, we look into the case of unary deterministic PDAs. We show a new construction converting a unary deterministic PDA into an equivalent context-free grammar that achieves best known bounds.
  • PDF
    Every rational number p/q defines a rational base numeration system in which every integer has a unique finite representation, up to leading zeroes. This work is a contribution to the study of the set of the representations of integers. This prefix-closed subset of the free monoid is naturally represented as a highly non-regular tree. Its nodes are the integers, its edges bear labels taken in 0,1,...,p-1, and its subtrees are all distinct. We associate with each subtree (or with its root n) three infinite words. The bottom word of n is the lexicographically smallest word that is the label of a branch of the subtree. The top word of n is defined similarly. The span-word of n is the digitwise difference between the latter and the former. First, we show that the set of all the span-words is accepted by an infinite automaton whose underlying graph is essentially the same as the tree itself. Second, we study the function that computes for all n the bottom word associated with n+1 from the one associated with n, and show that it is realised by an infinite sequential transducer whose underlying graph is once again essentially the same as the tree itself. An infinite word may be interpreted as an expansion in base p/q after the radix point, hence evaluated to a real number. If T is a subtree whose root is n, then the evaluations of the labels of the branches of T form an interval of $\mathbb{R}$. The length of this interval is called the span of n and is equal to the evaluation of the span-word of n. The set of all spans is then a subset of R and we use the preceding construction to study its topological closure. We show that it is an interval when p is greater than or equal to 2q-1, and a Cantor set of measure zero otherwise.