Seminár Ústavu informatiky


Automata with translucent letters

Dr. habil. Benedek Nagy, PhD
Eastern Mediterranean University, Famagusta, North Cyprus, Mersin-10, Turkey

2. februára 2017 (štvrtok) o 10:30
SJSP19 (P/19), PF UPJŠ


Finite-state acceptors with translucent letters are devices that do not read their input strictly from left to right as in the traditional setting, but for each internal state of such a device, certain letters are translucent, that is, in this state the acceptor cannot see them. We study the computational power of these acceptors, both in the deterministic and in the nondeterministic case. However, in contrast to the classical finite-state acceptor, the deterministic acceptors are less expressive than the nondeterministic ones. Closure properties and decidibility questions are also addressed. We show an alternative model of these systems (technically this alternative model was first, and then the above more simple interpretation has appeared). They are the cooperating distributed systems (CD-systems) of restarting automata that are very restricted: they are deterministic, they cannot rewrite, but only delete symbols, they restart immediately after performing a delete operation, they are stateless, and they have a read/write window of size 1 only, that is, these are stateless deterministic R(1)-automata. We relate the class of languages that are accepted by mode =1 computations of these CD-systems to other well-studied language classes, showing in particular that it only consists of semi-linear languages, and that it includes all rational trace languages. Extensions, e.g., pushdown automata with translucent letters will also be mentioned. These automata are able to characterize context-free trace languages. Automata with translucent stack symbols are capable to accept any RE languages.