Reference : Reactive automata
Scientific journals : Article
Engineering, computing & technology : Computer science
http://hdl.handle.net/10993/15858
Reactive automata
English
Crochemore, Maxime [> >]
Gabbay, Dov M. [King’s College London, Department of Computer Science, London, UK > > > ; Bar-Ilan University, Ramat-Gan, Israel]
2011
Information & Computation
Academic Press
209
4
692–704
Yes (verified by ORBilu)
0890-5401
San Diego
CA
[en] Automaton ; Language representation ; Reactivity
[en] A reactive automaton has extra links whose role is to change the behaviour of the automaton.
We show that these links do not increase the expressiveness of finite automata but that they
can be used to reduce dramatically their state number both in the deterministic case and
the non-deterministic case.
Typical examples of regular expressions associated with deterministic automata of ex-
ponential size according to the length of the expression show that reactive links provide an
alternative representation of total linear size for the language
http://hdl.handle.net/10993/15858
10.1016/j.ic.2011.01.002

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
1-s2.0-S0890540111000137-main.pdfPublisher postprint819.14 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.