Reactive automata

Maxime Crochemore; Dov M. Gabbay

doi:10.1016/j.ic.2011.01.002

Reactive automata

Maxime Crochemore, Dov M. Gabbay

Informatics

Research output: Contribution to journal › Article › peer-review

20 Citations (Scopus)

Abstract

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 exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size for the language. (C) 2011 Elsevier Inc. All rights reserved.

Original language	English
Pages (from-to)	692 - 704
Number of pages	13
Journal	INFORMATION AND COMPUTATION
Volume	209
Issue number	4
DOIs	https://doi.org/10.1016/j.ic.2011.01.002
Publication status	Published - Apr 2011

Access to Document

10.1016/j.ic.2011.01.002

Cite this

@article{4d82439610c04af29c74b2d89ea5ec1c,

title = "Reactive automata",

abstract = "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 exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size for the language. (C) 2011 Elsevier Inc. All rights reserved.",

author = "Maxime Crochemore and Gabbay, {Dov M.}",

year = "2011",

month = apr,

doi = "10.1016/j.ic.2011.01.002",

language = "English",

volume = "209",

pages = "692 -- 704",

journal = "INFORMATION AND COMPUTATION",

publisher = "Elsevier Inc.",

number = "4",

}

TY - JOUR

T1 - Reactive automata

AU - Crochemore, Maxime

AU - Gabbay, Dov M.

PY - 2011/4

Y1 - 2011/4

N2 - 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 exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size for the language. (C) 2011 Elsevier Inc. All rights reserved.

AB - 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 exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size for the language. (C) 2011 Elsevier Inc. All rights reserved.

U2 - 10.1016/j.ic.2011.01.002

DO - 10.1016/j.ic.2011.01.002

M3 - Article

VL - 209

SP - 692

EP - 704

JO - INFORMATION AND COMPUTATION

JF - INFORMATION AND COMPUTATION

IS - 4

ER -

Reactive automata

Abstract

Access to Document

Fingerprint

Cite this