Jumping automata are finite automata that read their input in a non-sequential manner, by allowing a reading head to ``jump'' between positions on the input, consuming a permutation of the input word. We argue that allowing the head to jump should incur some cost. To this end, we propose four quantitative semantics for jumping automata, whereby the jumps of the head in an accepting run define the cost of the run. The four semantics correspond to different interpretations of jumps: the \emph{absolute distance} semantics counts the distance the head jumps, the \emph{reversal} semantics counts the number of times the head changes direction, the \emph{Hamming distance} measures the number of letter-swaps the run makes, and the \emph{maximum jump} semantics counts the maximal distance the head jumps in a single step, We study these measures, with the main focus being the \emph{boundedness problem}: given a jumping automaton, decide whether its (quantitative) language is bounded by some given number $k$. We establish the decidability and complexity for this problem under several variants.

Abstract Nondeterministic Discounted-Sum Automata (NDAs) are nondeterministic finite automata equipped with a discounting factor $$\lambda >1$$ λ > 1 , and whose transitions are labelled by weights. The value of a run of an NDA is the discounted sum of the edge weights, where the i -th weight is divided by $$\lambda ^{i}$$ λ i . NDAs are a useful tool for modelling systems where the values of future events are less influential than immediate ones. While several problems are undecidable or open for NDA, their deterministic fragment (DDA) admits more tractable algorithms. Therefore, determinization of NDAs (i.e., deciding if an NDA has a functionally-equivalent DDA) is desirable. Previous works establish that when $$\lambda \in \mathbb {N}$$ λ ∈ N , then every complete NDA, namely an NDA whose states are all accepting and its transition function is complete, is determinizable. This, however, no longer holds when the completeness assumption is dropped. We show that the problem of whether an NDA has an equivalent DDA is decidable when $$\lambda \in \mathbb {N}$$ λ ∈ N (in particular, it is in $$\textsf{EXPSPACE}$$ EXPSPACE and is $$\mathsf {PSPACE-hard}$$ PSPACE - hard ).

We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decision tree complexity, sensitivity, block sensitivity, and a few others. We show that these complexity measures are polynomially related for the symmetric group and for many other domains. To show that all measures but sensitivity are polynomially related, we generalize classical arguments of Nisan and others. To add sensitivity to the mix, we reduce to Huang’s sensitivity theorem using "pseudo-characters", which witness the degree of a function. Using similar ideas, we extend the characterization of Boolean degree 1 functions on the symmetric group due to Ellis, Friedgut and Pilpel to the perfect matching scheme. As another application of our ideas, we simplify the characterization of maximum-size t-intersecting families in the symmetric group and the perfect matching scheme.

This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which *arbitrarily many* edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an $O(1)$ amortized time complexity, (2) using only $O(\log{n})$-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, $(degree+1)$-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.