International Journal of Foundations of Computer Science

The largest known reset thresholds for DFAs are equal to ${(n-1)}^2$, where $n$ is the number of states. This is conjectured to be the maximum possible. PFAs (with partial transition function) can have exponentially large reset thresholds. This is still true if we restrict to binary PFAs. However, asymptotics do not give conclusions for fixed $n$. We prove that the maximal reset threshold for binary PFAs is strictly greater than ${(n-1)}^2$ if and only if $n\ge 6$.

These results are mostly based on the analysis of synchronizing word lengths for a certain family of binary PFAs. This family has the following properties: it contains the well-known Černý automata; for $n\le 10$ it contains a binary PFA with maximal possible reset threshold; for all $n\ge 6$ it contains a PFA with reset threshold larger than the maximum known for DFAs.

Analysis of this family reveals remarkable patterns involving the Fibonacci numbers and related sequences such as the Padovan sequence. We derive explicit formulas for the reset thresholds in terms of these recurrent sequences.

Asymptotically the Černý family gives reset thresholds of polynomial order. We prove that PFAs in the family are not extremal for $n\ge 41$. For that purpose, we present an improvement of Martyugin’s prime number construction of binary PFAs.

Paren_n is the typical generalization of the Dyck language to multiple types of parentheses. We generalize its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and $\omega$-regular languages can be characterized by syntactic constraints on regular and $\omega$-regular expressions and, using the shuffle on trajectories operator, we define grammars for balanced-by-construction expressions with which one can express every balanced regular and $\omega$-regular language.

We consider two-tape automata where one tape contains the input word $w$ and the other an advice string $\alpha (|w|)$. Such an automaton recognizes a language $L$ if there is an advice function for which every word on the input tape is correctly classified. This model has been introduced by Küçük et al. with the aim of modeling non-uniform computations on finite automata. So far, most results concerned automata with 1-way tapes, both for the input and the advice. First, we show that making just one of the tapes 2-way already increases the model’s power. Then we consider the case where both tapes are 2-way, which can also be viewed as a restricted version of the non-uniform families of automata used by Ibarra and Ravikumar to define the class NUDSPACE. We show this restriction to be not too significant since, e.g., ${ℒ}({}_{2_{{𝒜}}}^{2_{{ℐ}}}$DFA/poly), i.e., the languages recognized by automata with 2-way input and advice tape with polynomial advice, equals $NUDSPACE(O(log(n)))$. Hence, we can show that many interesting problems concerning the state complexity of families of automata carry over to the problems concerning the advice size of non-uniform automata. In particular, the question whether there can be a more than polynomial gap in advice between determinism and nondeterminism is of great interest: The existence of a language that is recognized by a 2-way NFA with a constant number of advice heads and polynomial (resp. logarithmic) advice, while a corresponding 2-head DFA needs exponential (resp. polynomial) advice, would imply $L\ne NL$ (resp. $LL\ne NLL$). We show that for advice of size ${(logn)}^{o(1)}$ there is no gap between determinism and nondeterminism, and that the gap is at most exponential.

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 with fixed transitions. This automaton has an additional integer input that allows it to simulate any semi-Thue system.

We consider two-variable first-order logic FO² and its quantifier alternation hierarchies over both finite and infinite words. Our main results are forbidden patterns for deterministic automata (finite words) and for Carton-Michel automata (infinite words). In order to give concise patterns, we allow the use of subwords on paths in finite graphs. This concept is formalized as subword-patterns. For certain types of subword-patterns there exists a non-deterministic logspace algorithm to decide their presence or absence in a given automaton. In particular, this leads to NL algorithms for deciding the levels of the FO² quantifier alternation hierarchies. This applies to both full and half levels, each over finite and infinite words. Moreover, we show that these problems are NL-hard and, hence, NL-complete.

Top-down syntax analysis can be based on $\mathrm{\text{LL}}(k)$ grammars. The canonical acceptors for $\mathrm{\text{LL}}(k)$ languages are deterministic stateless pushdown automata with input lookahead of size $k$. We investigate the computational capacity of reversible computations of such automata. A pushdown automaton with lookahead $k$ is said to be reversible if its predecessor configurations can uniquely be computed by a pushdown automaton with backward input lookahead (lookback) of size $k$. It is shown that we cannot trade a lookahead for states or vice versa. The impact of having states or a lookahead depends on the language. While reversible pushdown automata with states accept all regular languages, we are going to prove that there are regular languages that cannot be accepted reversibly without states, even in case of an arbitrarily large lookahead. This completes the comparison of reversible with ordinary pushdown automata in our setting. Moreover, it turns out that there are problems which can be solved by reversible deterministic stateless pushdown automata with lookahead of size $k+1$, but not by any reversible deterministic stateless pushdown automaton with lookahead of size $k$. So, an infinite and tight hierarchy of language families dependent on the size of the lookahead is shown. Finally, we prove that the language families accepted by reversible deterministic stateless pushdown automata with lookahead of size $k$ are not closed under standard operations. For example, we show that the families are anti-AFLs which are not closed under intersection.

Top-down tree transducers are well established formalism for describing tree translations. Such transducers can be further enhanced with look-ahead allowing them to inspect input subtrees before processing them. Oftentimes it is advantageous to know when the look-ahead can be eliminated and the translation be implemented by a simpler transducer. We show that for a given top-down transducer with look-ahead it is decidable whether or not its translation is definable (1) by a linear deterministic top-down tree transducer or (2) by a tree homomorphism. We present algorithms that construct equivalent such transducers if they exist. Our results also apply to bottom-up transducers as well as compositions of transducers.

This paper establishes an analogue of Greibach’s hardest language theorem (“The hardest context-free language”, SIAM J. Comp., 1973, http://dx.doi.org/10.1137/0202025) for the classical family of LL($k$) languages. The first result is that there is a language $L_0$ defined by an LL(1) grammar in the Greibach normal form, to which every language $L$ defined by an LL(1) grammar in the Greibach normal form can be reduced by a homomorphism, that is, $w\mathrm{ \in }L$ if and only if $h(w)\mathrm{ \in }{L}_0$. Then it is shown that this statement does not hold for the full class of LL($k$) languages. The other hardest language theorem is then established in the following form: there is a language $L_0$ defined by an LL(1) grammar in the Greibach normal form, such that, for every language $L$ defined by an LL($k$) grammar, with $k\ge 1$, there exists a homomorphism $h$, for which $w\mathrm{ \in }L$ if and only if $h(w\$)$ $\mathrm{ \in }$ $L_0$, where $\$$ is a new symbol. The results lead to two robust language families: the closures of the languages defined by LL(1) grammars in the Greibach normal form under inverse homomorphisms and under inverse finite transductions.

For $\delta \mathrm{ \in }{ℝ}^{+}$, maximal $\delta$-repetitions ($\delta$-subrepetitions) are fractional powers in strings with exponent of at least $2+\delta$ (and $1+\delta$, respectively) which are non-extendable with respect to their minimum period.

In this paper, we show that in a string $S$ with string attractor $\mathrm{\Gamma }$ there are at most $(|\mathrm{\Gamma }|+2)(\lfloor 3+\frac{6}{\delta }\rfloor \cdot \lfloor {log}_{1+\frac{\delta }{4}}(\left|S\right|)\rfloor +2)$ distinct (unpositioned) extended maximal $\delta$-repetitions. Also for any natural number $q\ge 2$ the string contains at most $(|\mathrm{\Gamma }|+2)(\lfloor 3+\frac{4}{\delta }\rfloor \cdot \lfloor {log}_{1+\frac{\delta }{2q}}(\left|S\right|)\rfloor +2)$ distinct extended maximal $\delta$-subrepetitions without $q$th powers.

We further prove that for fixed $\delta$ and $q\ge \lceil \delta +4\rceil$, both upper bounds are tight up to a constant factor.