International Journal of Foundations of Computer Science

We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.

We study a game for recognising formal languages, in which two players with imperfect information should coordinate on a common decision, given private input words correlated by a finite graph. The players have a common objective to avoid an inadmissible decision, in spite of the uncertainty induced by the input.

We show that the acceptor model based on consensus games characterises context-sensitive languages. Further, we describe the expressiveness of these games in terms of iterated synchronous transductions and identify a subclass that characterises context-free languages.

The existence of a substantial gap between deterministic and nondeterministic two-way automata is one of the most famous open problems in automata theory. This problem is also related to the fundamental DLOG vs. NLOG question. An exponential gap between the number of states of two-way nondeterministic automata (2NFAS) and their deterministic counterparts (2DFAS) has been proved only for some restrictions of 2DFAS up to now. It seems that the hardness of this problem lies in the fact that, when trying to prove lower bounds, we must consider every possible automaton, without imposing any particular structure or meaning to the states, while when designing a specific automaton, we always assign an unambiguous interpretation to the states. In an attempt to capture the concept of meaning of states, a new model of two-way automata, namely reasonable automaton (RA), was introduced in [6]. In a RA, each state is associated with a logical formula expressing some properties of the input word, and transitions are designed to maintain consistency within this setting. In this paper we extend the study, started in [6], of the descriptional complexity of RAS solving the liveness problem, showing several lower and upper bounds with respect to the logic used for describing the meaning of the individual states.

Two models of automata over infinite alphabets are presented, mainly with a focus on the alphabet $\mathbb{N}$. In the first model, transitions can refer to logic formulas that connect properties of successive letters. In the second, the letters are considered as columns of a labeled grid which an automaton traverses column by column. Thus, both models focus on the comparison of successive letters, i.e. “local changes”. We prove closure (and non-closure) properties, show the decidability of the respective non-emptiness problems, prove limits on decidability results for extended models, and discuss open issues in the development of a generalized theory.

A language $L$ is said to be dense if every word in the universe is an infix of some word in $L$. This notion has been generalized from the infix operation to arbitrary word operations $\varrho$ in place of the infix operation ($\varrho$-dense, with infix-dense being the standard notion of dense). It is shown here that it is decidable, for a language $L$ accepted by a one-way nondeterministic reversal-bounded pushdown automaton, whether $L$ is infix-dense. However, it becomes undecidable for both deterministic pushdown automata (with no reversal-bound), and for nondeterministic one-counter automata. When examining suffix-density, it is undecidable for more restricted families such as deterministic one-counter automata that make three reversals on the counter, but it is decidable with less reversals. Other decidability results are also presented on dense languages, and contrasted with a marked version called $\varrho$-marked-density. Also, new languages are demonstrated to be outside various deterministic language families after applying different deletion operations from smaller families. Lastly, bounded-dense languages are defined and examined.

We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characterization of regular languages that can be accepted by REV-DFAs. This characterization is based on the absence of a forbidden pattern in the (minimal) deterministic state graph. Again with a forbidden pattern approach, we also show that the minimality of REV-DFAs among all equivalent REV-DFAs can be decided. Both forbidden pattern characterizations give rise to $NL$-complete decision algorithms. In fact, our techniques allow us to construct the minimal REV-DFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REV-DFAs. Thus, almost all problems that concern uniqueness and the size of minimal REV-DFAs are solved.

Rational relations are binary relations of finite words that are realised by non-deterministic finite state transducers (NFT). A multi-sequential relation is a rational relation which is equal to a finite union of (graphs) of partial sequential functions, i.e. functions realised by input-deterministic transducers.

The particular case of multi-sequential functions was studied by Choffrut and Schützenberger who proved that given a rational function (as a transducer), it is decidable whether it is multi-sequential. Their procedure is based on an effective characterisation of unambiguous transducers that do not define multi-sequential functions, that we call the fork property.

In this paper, we show that the fork property also characterises the class of transducers that do not define multi-sequential relations. Moreover, we prove that the fork property can be decided in PTime. This leads to a PTime procedure which, given a transducer, decides whether it defines a multi-sequential relation.

The class of automaton groups is a rich source of the simplest examples of infinite Burnside groups. However, all such examples have been constructed as groups generated by non-reversible automata. Moreover, it was recently shown that 2-state reversible Mealy automata cannot generate infinite Burnside groups. Here we extend this result to connected 3-state reversible Mealy automata, using new original techniques. The results rely on a fine analysis of associated orbit trees and a new characterization of the existence of elements of infinite order.

The neighbourhood of a language $L$ with respect to an additive distance consists of all strings that have distance at most the given radius from some string of $L$. We show that the worst case deterministic state complexity of a radius $r$ neighbourhood of a language recognized by an $n$ state nondeterministic finite automaton $A$ is ${(r+2)}^n-1$. In the case where $A$ is deterministic we get the same lower bound for the state complexity of the neighbourhood if we use an additive quasi-distance. The lower bound constructions use an alphabet of size linear in $n$. We show that the worst case state complexity of the set of strings that contain a substring within distance $r$ from a string recognized by $A$ is ${(r+2)}^{n-2}+1$.