Stretching and jamming of automata

N. Beijer, de, B.W. Watson, D.G. Kourie

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

In this paper we present two transformations on automata, called stretching and jamming. These transformations will, under certain conditions, reduce the size of the transition table, and under other conditions reduce the string recognition time. Given a deterministic finite automaton, we can stretch it by transforming each single transition into two or more sequential transitions, thereby introducing additional intermediate states. Jamming is the opposite transformation, in which two or more successive transitions are transformed into a single transition, thereby removing redundant intermediate states.We will present formal definitions of stretching and jamming. We will give algorithms for stretching and jamming and we will calculate theoretical bounds, when stretching/jamming is effective in terms of memory consumption and string recognition time.
Originele taal-2Engels
TitelProceedings of the 2003 annual research conference of the South African Institute of computer scientists and information technologists on enablement through technology : SAICSIT, Fourways, South Africa, September 17-19, 2003
RedacteurenJ. Eloff, xx et al.
Plaats van productieNew York
UitgeverijAssociation for Computing Machinery, Inc
Pagina's198-207
ISBN van geprinte versie1-58113-774-5
StatusGepubliceerd - 2003

Publicatie series

NaamACM International Conference Proceeding Series
Volume47

Vingerafdruk

Duik in de onderzoeksthema's van 'Stretching and jamming of automata'. Samen vormen ze een unieke vingerafdruk.

Citeer dit