Title: Reactive automata

Dov M. Gabbay1
 King’s College and Bar Ilan University



Abstract.
A reactive automaton has extra links whose role is to change
the behaviour of the automaton. These links do not increase the expres-
sive power of finite automata but are used to reduce the size of their
representation. Typical examples of regular expressions associated with
deterministic automata of exponential size according to the length of the
expression show that reactive links provide an alternative representation
of total linear size.

The reactive idea was introduced in [2] and [3], the notion of reactive automata is part of a general re-
active methodology. The basic idea is that of a system that changes its behaviour
when used, which means that it dynamically changes during its execution as a
reaction to feedback or anticipation. A reactive system is not a time-dependent
system because it depends only on the states or transition is goes through and
is independent of an objective clock.
 
The notion of reactive automata opens the way to various questions on the
representation of languages and on the algorithms for the management of au-
tomata. For example, it would be interesting to know if any language admits a
deterministic reactive automaton of sub-exponential size according to the size
of a regular expression representing it. Or, equivalently, if determinising a non-
deterministic automaton into a deterministic reactive one can be done in sub-
exponential time.

References
1. M.-P. B´eal, M. Crochemore, F. Mignosi, A. Restivo, and M. Sciortino. Forbidden
words of regular languages. Fundamenta Informaticae, 56(1,2):121–135, 2003.
2. D. M. Gabbay. Reactive Kripke semantics and arc accessibility. In W. Carnielli,
F. M. Dionesio, and P. Mateus, editors, Combinatorial Logic, pages 7–20. Centre of
Logic and Computation, University of Lisbon, 2004.
3. D. M. Gabbay. Reactive Kripke semantics and arc accessibility. In A. Avron,
N. Dershowitz, and A. Rabinovitch, editors, Pillars of Computer Science: Essays
dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday, volume
4800 of LNCS, pages 292–341. Springer-Verlag, Berlin, 2008.
4. J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory,
Languages, and Computation. Addison-Wesley, third edition edition, 2006.



(work together with Maxime Crochemore)