A two-sided extension of strictly locally testable languages is presented. In order to determine membership within a two-sided strictly locally testable language, the input must be scanned from both ends simultaneously, whereby it is synchronously checked that the factors read are correlated with respect to a given binary relation. The class of two-sided strictly locally testable languages is shown to be a proper subclass of the even linear languages that is incomparable to the regular languages with respect to inclusion. Furthermore, closure properties of the class of two-sided strictly locally testable languages and decision problems are studied. Finally, it is shown that two-sided strictly k-testable languages are learnable in the limit from positive data.

A complete taxonomy is presented for restarting automata without auxiliary symbols. In this taxonomy, the language classes that are accepted by deterministic and nondeterministic, monotone, weakly monotone, and non-monotone, shrinking and length-reducing restarting automata are compared to each other with respect to inclusion. As it turns out, the 45 types of restarting automata considered yield 29 different classes of languages. By presenting a collection of rather simple example languages, it is shown that, for any two of these language classes ℒ1 and ℒ2, the class ℒ1 is a subclass of ℒ2 if and only if ℒ1 is defined by a type of restarting automaton that is a restriction of a type of restarting automaton that defines the class ℒ2.

Abstract Stateless ordered restart-delete automata (stl-ORD-automata) are studied. These are obtained from the stateless ordered restarting automata (stl-ORWW-automata) by introducing an additional restart-delete operation, which, based on the surrounding context, deletes a single letter. While the stl-ORWW-automata accept the regular languages, we show that the swift stl-ORD-automata yield a characterization for the class of context-free languages. Here a stl-ORD-automaton is called swift if it can move its window to any position after performing a restart. We also study the descriptional complexity of swift stl-ORD-automata and relate them to limited context restarting automata.

Many non-classical models of automata are natural objects of theoretical computer science. They are studied from different points of view in various areas, both as theoretical concepts and as formal models for applications. The Fifth Workshop on Non-Classical Models of Automata and Applications (NCMA 2013) was organized in order to provide an opportunity for researchers who work on different aspects of non-classical models of automata and related subjects to exchange and discuss new ideas and recent developments.

In natural languages with a high degree of word-order freedom, syntactic phenomena like dependencies (subordinations) or valences do not depend on the word-order (or on the individual positions of the individual words). This means that some permutations of sentences of these languages are in some (important) sense syntactically equivalent. Here we study this phenomenon in a formal way. Various types of j-monotonicity for restarting automata can serve as parameters for the degree of word-order freedom and for the complexity of word-order in sentences (languages). Here we combine two types of parameters on computations of restarting automata: the degree of j-monotonicity, and the number of rewrites per cycle. We study these notions formally in order to obtain an adequate tool for modelling and comparing formal descriptions of (natural) languages with different degrees of word-order freedom and word-order complexity.

Many non-classical automata models are natural objects of theoretical computer science.They are studied from different points of view in various areas, both as theoretical concepts and as formal models for applications.A deeper and interdisciplinary coverage of this particular area may lead to new insights and substantial progress.The Second Workshop on Non-Classical Models of Automata and Applications (NCMA 2010) has been organized in order to bring together researchers working on different aspects of various variants of non-classical automata models to exchange and develop novel ideas.

We study the McNaughton families of languages that are specified by four different variants of monadic string-rewriting systems: strictly monadic systems, monadic systems, inverse context-free systems, and generalized monadic systems. In the general case these four variants yield the same McNaughton family of languages, which coincides with the class of context-free languages. In the case of confluent systems, however, we obtain two McNaughton families by showing that special rules, that is, rules with empty right-hand side, are not needed. This implies that in this situation strictly monadic systems are as expressive as monadic systems, and inverse context-free systems are as expressive as generalized monadic systems. The McNaughton family defined by the former systems is contained in the McNaughton family that is defined by the latter systems, and this inclusion is proper if and only if the former family is not closed under inverse alphabetic morphisms. Finally, we show that the latter family is a proper subclass of the class of deterministic context-free languages.

Following the course set by A. Markov (1951), S. Adjan (1958), and M. Rabin (1958), C. Ó'Dúnlaing (1983) has shown that certain properties of finitely generated Thue congruences are undecidable in general. Here we prove that many of these undecidability results remain valid even when only finitely generated Thue congruences on a fixed two-letter alphabet Σ 2 are considered. In contrast to a construction given by P. Schupp (1976) which applies to groups only, we use a modified version of a technical lemma from A. Markov's original paper. Based on this technical result we can carry the result of A. Sattler-Klein (1996), which says that certain Markov properties remain undecidable even when they are restricted to finitely generated Thue congruences that are decidable, over to the alphabet Σ 2 .

Canonical presentations of groups are of interest, since they provide structurally simple algorithms for computing normal forms. A class of groups that has received much attention is the class of context-free groups. This class of groups can be characterized algebraically as well as through some language-theoretical properties as well as through certain combinatorial properties of presentations. Here we use the fact that a finitely generated group is context-free if and only if it admits a finite canonical presentation of a certain form that we call a virtually free presentation. Since finitely generated subgroups of context-free groups are again context-free, they admit presentations of the same form. We present a polynomial-time algorithm that, given a finite virtually free presentation of a context-free group G and a finite subset U of G as input, computes a virtually free presentation for the subgroup U of G that is generated by U.

We apply rewriting techniques to the generalized word problem for groups. Let R be a finite string-rewriting system on an alphabet Σ such that the monoid MR presented by (Σ:R) is a group, and let U ⊆ Σ→ be a finite set. The generalized word problem GWP is defined by GWP(w.U) if w ∈ , where is the subgroup of MR generated by U. With U we associate a prefix rewriting relation ⇒P on Σ* such that w P λ if GWP(w.U) holds. If ⇒P is λ-confluent then w ⇒ P λ if w ∈ . Then ⇒P yields a decision procedure for GWP. For groups given through confluent string-rewriting systems R, we develop a necessary and sufficient condition for ⇒P being λ-confluent and show that this condition becomes decidable in case of R being length-reducing, in addition.

Since about 1971, much research has been done on Thue systems that have properties that ensure viable and efficient computation. The strongest of these is the Church-Rosser property, which states that two equivalent strings can each be brought to a unique canonical form by a sequence of length-reducing rules. In this paper three ways in which formal languages can be defined by Thue systems with this property are studied, and some general results about the three families of languages so determined are studied.

It is undecidable in general whether the monoid presented by a given Thue system is a free monoid. Here it is shown that this question is decidable for Church–Rosser Thue systems.