Reducing nondeterministic finite automata with SAT solvers

Simple item page
dc.contributor.authorGeldenhuys J.
dc.contributor.authorVan Der Merwe B.
dc.contributor.authorVan Zijl L.
dc.date.accessioned2011-05-15T16:02:05Z
dc.date.available2011-05-15T16:02:05Z
dc.date.issued2010
dc.description.abstractWe consider the problem of reducing the number of states of nondeterministic finite automata, and show how to encode the reduction as a Boolean satisfiability problem. This approach improves on previous work by reducing a more general class of automata. Experimental results show that it produces a minimal automaton in almost all cases and that the running time compares favourably to the Kameda-Weiner algorithm. © 2010 Springer-Verlag Berlin Heidelberg.
dc.description.versionConference Paper
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.identifier.citation6062 LNAI
dc.identifier.issn3029743
dc.identifier.other10.1007/978-3-642-14684-8_9
dc.identifier.urihttp://hdl.handle.net/10019.1/12299
dc.subjectBoolean satisfiability problems
dc.subjectGeneral class
dc.subjectMinimal automaton
dc.subjectNondeterministic finite automaton
dc.subjectNumber of state
dc.subjectRunning time
dc.subjectSAT solvers
dc.subjectBoolean functions
dc.subjectComputational linguistics
dc.subjectNatural language processing systems
dc.subjectPipeline processing systems
dc.subjectRobots
dc.subjectTranslation (languages)
dc.subjectFinite automata
dc.titleReducing nondeterministic finite automata with SAT solvers
dc.typeConference Paper
Files
Collections
Stellenbosch University - Scopus Publications