Hardcoding and dynamic implementation of finite automata

E.K. Ngassam, B.W. Watson, D.G. Kourie

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

43 Downloads (Pure)

Abstract

The theoretical complexity of a string recognizer is linear to the length of the string being tested for acceptance. However, for some kind of strings the processing time largely depends on the number of states visited by the recognizer at run-time. Various experiments are conducted in order to compare the time efficiency of both hardcoded and table-driven algorithms when using such strings patterns. The results of the experiments are cross-compared in order to show the efficiency of the hardcoded algorithm over its table-driven counterpart. This help further the investigations on the problem of the dynamic implementation of finite automata. It is shown that we can rely on the history of the states previously visited in the dynamic framework in order to predict the suitable algorithm for acceptance testing.
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 'Hardcoding and dynamic implementation of finite automata'. Together they form a unique fingerprint.

Cite this