Stretching and jamming of finite automata

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic

81 Downloads (Pure)

Abstract

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 processing time. Given a 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 inverse 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 and we will calculate theoretical bounds, when stretching/jamming is effective in terms of memory consumption.
Original languageEnglish
Title of host publicationProceedings of the Eindhoven FASTAR Days 2004 (Eindhoven, The Netherlands, September 3-4, 2004)
EditorsL.G.W.A. Cleophas, B.W. Watson
Place of PublicationEindhoven
PublisherTechnische Universiteit Eindhoven
Publication statusPublished - 2004

Publication series

NameComputer Science Reports
Volume04-40
ISSN (Print)0926-4515

Fingerprint

Dive into the research topics of 'Stretching and jamming of finite automata'. Together they form a unique fingerprint.

Cite this