Invited lectures

 

 

NON-CLASSICAL TURING MACHINES: EXTENDING THE NOTION OF COMPUTATION

 

Jiří Wiedermann, Academy of Sciences of the Czech Republic, Prague, Czech Republic and Jan van Leeuwen, Department of Information and Computing Science, Utrecht University, the Netherlands

 

The goal of this paper is to broaden our understanding of computations based on the classical paradigm of Turing machines. To this end we will point to models of non-classical Turing machines that capture computational behavior of contemporary or emerging computing technologies and that have been designed and studied by the authors. The  guiding design principles of such machines have been the currently existing or foreseeable technologies such as interactivity, non-uniform evolution, unbounded time behavior, process cooperation, and relativistic time-space effects. The computational behavior of these models and the fact that they mirror key aspects of present or envisaged technologies jointly offer compelling reasons for modifying the traditional and persisting view of computation. This change is quite a profound one: computations should no longer be seen as finite processes whose parameters are fixed before the start of processing. Rather, computations are potentially infinite evolutionary processes whose parameters can change during the processing in an unpredictable way in interaction with their environment.

 

HIERARCHIES OF LANGUAGE FAMILIES OF CONTEXTUAL GRAMMARS

 

Bianca Truthe, Institute of Computer Science, Justus-Liebig-Universität Giessen, Germany

 

We give an overview about the generative capacity of contextual grammars where contexts are adjoined around whole words (externally) or around subwords (internally) which belong to regular selection languages. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We compare such families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages, or based on languages defined by restrictions regarding the descriptional complexity.

 

NCMA 2017 - 9^th Workshop on Non-Classical Models of Automata and Applications

                         August 17-18, 2017, Prague, Czech Republic