The concept of LL( k ) context-free grammars is extended to cooperating distributed (CD) grammar systems working in the = m -mode of derivation in a consistent way. Namely, every LL( k ) context-free language can be generated by an LL( k ) CD grammar system. Further fundamental properties of languages generated by LL( k ) CD grammar systems are proved, for instance their unambiguity and the capability of LL( k ) CD grammar systems to describe typical non-context-free languages, including even a non-semilinear language. Most importantly, a parsing algorithm with strictly sub-quadratic time complexity is presented for LL( k ) CD grammar systems.

Abstract We study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.

A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages.

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 consider pure Lindenmayer systems, more precisely, 0L and T0L systems as language accepting devices and compare them to their generating counterparts. Accepting Lindenmayer systems can be seen as systems of inverse finite substitutions which are iteratively applied over a free monoid. Hereby, we investigate the deterministic case in detail, comparing several different concepts of determinism in such systems. Whereas in the usual generating case these concepts trivially are equally powerful, the structure of families of accepted languages is much richer. In passing, the case of unary Lindenmayer systems is investigated.