ABSTRACT. This paper establishes an analogue of Greibach's hardest language theorem ("The hardest context-free language", 1973) for the subfamily of LL 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 \in L$ if and only if $h(w) \in L_0$. Then it is shown that this statement does not hold for LL($k$) languages. The second 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, there exists a homomorphism $h$, for which $w \in L$ if and only if $h(w \$) \in L_0$, where \$ is a new symbol.

ABSTRACT. Aprefixnormalwordisabinarywordwhoseprefixescontain at least as many 1s as any of its factors of the same length. Introduced by Fici and Lipták in 2011 the notion of prefix normality is so far only defined for words over the binary alphabet. In this work we investigate a generalisation for finite words over arbitrary finite alphabets, namely weighted prefix normality. We prove that weighted prefix normality is more expressive than binary prefix normality. Furthermore, we investigate the existence of a weighted prefix normal form since weighted prefix normality comes with several new peculiarities that did not already occur in the binary case. We characterise these issues and finally present a standard technique to obtain a generalised prefix normal form for all words over arbitrary, finite alphabets.

ABSTRACT. A d-limited automaton is a Turing machine that uses only the cells with the input word (and end-markers) and rewrites symbols only in the first d visits. This model was introduced by T.~Hibbard in 1967 and he showed that d-limited automata recognize context-free languages for each d starting with 2. He also proved that languages recognizable by deterministic d-limited automata form a hierarchy and it was shown later by Pighizzini and Pisoni that it begins with deterministic context-free languages (DCFLs) (for d=2).

As well-known, DCFLs are widely used in practice, especially in compilers since they are linear-time recognizable and have the corresponding CF-grammars subclass (LR(1)-grammars). In this paper we present a linear time recognition algorithm for d-limited automata (in the RAM model) which opens an opportunity for their possible practical applications.

ABSTRACT. GF(2)-grammars are a recently introduced grammar family that has some unusual algebraic properties and is closely connected to the family of unambiguous grammars. By using the method of formal power series, we establish strong conditions that are necessary for subsets of a_1* a_2* ... a_k* to be described by some GF(2)-grammar.

By further applying the established results, we settle the long-standing open question of proving the inherent ambiguity of the language {a^n b^m c^k}{n != m OR m != k}$, as well as give a new, purely algebraic, proof of the inherent ambiguity of the language {a^n b^m c^k}{n = m OR m = k}.

ABSTRACT. The Post Correspondence Problem is a classical decision problem about equalisers of free monoid homomorphisms. We prove connections between several variations of this classical problem, but in the setting of free groups and free group homomorphisms. Among other results, and working under certain injectivity assumptions, we prove that computing the rank of the equaliser of a pair of free group homomorphisms can be applied to computing a basis of this equaliser, and also to solve the “generalised” Post Correspondence Problem for free groups.

ABSTRACT. Guarded Kleene Algebra with Tests (GKAT) is an efficient fragment of KAT, as it allows for almost linear decidability of equivalence.  In this talk, we will review the basics of GKAT and describe its (co)algebraic properties. We will describe two completeness results and an automaton model that plays a key role in their proof. We will show examples of different models of GKAT that can be used in program verification and discuss future directions of research.

The material in this talk is based on the following two publications.

Todd Schmid, Tobias Kappé, Dexter Kozen, Alexandra Silva:

Guarded Kleene Algebra with Tests: Coequations, Coinduction, and Completeness. ICALP (2021)

Steffen Smolka, Nate Foster, Justin Hsu, Tobias Kappé, Dexter Kozen, Alexandra Silva:

Guarded Kleene algebra with tests: verification of uninterpreted programs in nearly linear time. Proc. ACM Program. Lang. 4(POPL): 61:1-61:28 (2020)

ABSTRACT. Maximal delta-repetitions (delta-subrepetitions) are fractional powers with exponent of at least 2+delta (and 1+delta, respectively) which are non-extendable with respect to their minimal period length.

In this paper, we prove that the number of distinct (unpositioned) maximal delta-repetitions in a string S with z LZ77-factors is bounded from above by (z+1)\lfloor 3 + \frac{6}{delta}\rfloor \cdot \lfloor log_{1+\frac{delta}{4}}(|S|) \rfloor.

Also, the number of distinct (unpositioned) maximal q-th power-free delta-subrepetitions in a string S with z LZ77-factors is bounded from above by (z+1)\lfloor 3 + \frac{4}{delta}\rfloor \cdot t\lfloor log_{1+\frac{delta}{2q}}(|S|)\rfloor.

We further prove that for fixed delta and q, both upper bounds are asymptotically tight.

ABSTRACT. 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 sharp. PFAs 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 is greater than or equal to 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 Cerny automata; for n less than or equal to 10 it contains a binary PFA with maximal possible reset threshold; for all n greater than or equal to 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 prove that the family asymptotically still gives reset thresholds of polynomial order. For a few sequences in the family, we derive explicit formulas for the reset tresholds, which turn out to be no pure polynomials.

ABSTRACT. A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word w ∈ {a, b}∗ can be reconstructed from the number of occurrences of at most min(|w|_a,|w|_b) + 1 scattered factors of the form a^i b, where |w|_a is the number of occurrences of the letter a in w. Moreover, we generalize the result to alphabets of the form {1,...,q} by showing that at most \sum{i=1}{q-1} |w|_i (q − i + 1) scattered factors suffices to reconstruct w. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here.

ABSTRACT. We consider two-tape automata where one tape contains the input word, and the other contains an advice string that depends only on the length of the input. 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 with the aim to model non-uniform computation on finite automata. So far, most of the results concerned automata whose tapes are both 1-way. First, we show that making even one of the tapes 2-way increases the power of the model. Then we turn our attention to the case of both tapes being 2-way, which can also viewed as a restricted version of non-uniform families of automata used by Ibarra and Ravikumar to define the class NUDSPACE. We show this restriction to be not very significant since, e.g., the languages recognized by automata with 2-way input and advice tape with polynomial advice equal 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 advice size of non-uniform automata. In particular, the question whether there can be a more than polynomial gap in advice between determinism and non-determinism is of great interest: e. g., the existence of a language that can be recognized by some 2-way NFA with some k heads on the advice tape and with polynomial (resp. logarithmic) advice, while a corresponding 2-head DFA would need exponential (resp. polynomial) advice, would imply L != NL (resp. LL != NLL). We show that for advice of size (log n)^o(1) there is no gap between determinism and non-determinism. In general, we can show that the gap is not more than exponential.

ABSTRACT. We investigate the constrained synchronization problem for weakly acyclic, or partially ordered, input automata. We show that, for input automata of this type, the problem is always in $\NP$. Furthermore, we give a full classification of the realizable complexities for constraint automata with at most two states and over a ternary alphabet. For certain constraint languages, for which the general problem is $\PSPACE$-complete, for weakly acyclic automata we get $\NP$-complete problems, whereas there are also problems that are $\PSPACE$-complete in general, but for which it is polynomial time solvable in our setting. We also investigate two problems related to subset synchronization, namely if there exists a word mapping all states into a given target subset of states, and if there exists a word mapping one subset into another. Both problems are $\PSPACE$-complete in general, but in our setting the former is polynomial time solvable and the latter is $\NP$-complete.