ABSTRACT. Edit distance (or Levenshtein distance) is a measure of similarity of strings. The edit distance of two strings x, y is the minimum number of character insertions, deletions, and substitutions needed to convert x into y. It has numerous applications in various fields from text processing to bioinformatics so algorithms for edit distance computation attract lot of attention. In this talk I will survey recent progress on computational aspects of edit distance in several contexts: computing edit distance approximately, computing edit distance in streaming model, and exchanging similar strings in communication complexity model. I will point out many problems that are still open in those areas.

ABSTRACT. A language \(L\) is said to be regular measurable if there exists an infinite sequence of regular languages that ``converges'' to \(L\). In [1], the author showed that, while many complex context-free languages are regular measurable, the set of all primitive words and certain deterministic context-free languages are regular immeasurable. This paper investigates a general property of measurability, including closure properties, decidability and different characterisation. Further, for a suitable subclass \(\CC\) of regular languages, we show that the class of all \(\CC\)-measurable regular languages has a good algebraic structure.

ABSTRACT. We consider two-variable first-order logic FO2 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. Deciding the presence or absence of such a pattern in a given automaton is in NL. In particular, this leads to NL algorithms for deciding the levels of the FO2 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.

ABSTRACT. In this paper we introduce a new notion of symmetry group of an infinite word. Given a subgroup $G_n$ of the symmetric group $S_n$, it acts on the set of finite words of length $n$ by permutation. For each $n$, a symmetry group of an infinite word $w$ is a subgroup $G_n$ of the symmetric group $S_n$ such that for each permutation $g \in G_n$ and each factor $v$ of $w$ of length $n$, $g(v)$ is also a factor of $w$. We study general properties of symmetry groups of infinite words and characterize symmetry groups of several families of infinite words. We show that symmetry groups of Sturmian words and more generally Arnoux-Rauzy words are of order two for large enough $n$; on the other hand, symmetry groups of certain Toeplitz words have exponential growth.

ABSTRACT. This is a personal survey about pointlike sets since their inception to roughly the present.  Personal means  that I make no attempt to be exhaustive, but rather to highlight things that have affected my research in the area or that I consider fundamental to the area. Pointlike sets, in the language of separation and covering problems, have become very popular now in Computer Science because of the truly amazing work of Place and Zeitoun on dot-depth and related hierarchies.  I believe revisiting some of the older results will revive interest and provide perspective.

ABSTRACT. We define a new quantitative measure for an arbitrary factorial language: the entropy of a random walk in the prefix tree associated with the language; we call it Markov entropy. We relate Markov entropy to the growth rate of the language and to the parameters of branching of its prefix tree. We show how to compute Markov entropy for a regular language. Finally, we develop a framework for experimental study of Markov entropy by modelling random walks and present the results of experiments with power-free and Abelian-power-free languages.

ABSTRACT. Top-down syntax analysis can be based on $LL(k)$ grammars. The canonical acceptors for $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. Finally, 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.

ABSTRACT. This paper examines several measures of space complexity on variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept any word in a language (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves (up to small technicalities explained in the paper) like a linear function, or it grows arbitrarily larger than the length of the input word. However, this result does not hold for non-erasing stack automata; we provide an example when the space complexity grows with the square root of the input length. Furthermore, an investigation is done regarding the best complexity of any machine accepting a given language, and on decidability of space complexity properties.

ABSTRACT. Paren_n is the typical generalisation of the Dyck language to multiple types of parentheses. We generalise its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and omega-regular languages can be characterised 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.

ABSTRACT. Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property~$P$. What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question if is there exists one graph satisfying~$P$? We approach this question by using formal languages for specifying families of graphs. In particular, we show that certain graph properties can be decided by studying the syntactic monoid of the specification language.