EDP Sciences Journals List
Home Document
Subscriber Authentication Point
Issue RAIRO-Theor. Inf. Appl.
Volume 43, Number 1, January-March 2009
Page(s) 69 - 94
DOI 10.1051/ita:2007061
Published online 20 December 2007

RAIRO-Theor. Inf. Appl. 43, 69-94 (2009)
DOI: 10.1051/ita:2007061

Hyper-minimizing minimized deterministic finite state automata

Andrew Badr1, Viliam Geffert2 and Ian Shipman3

1  3210 Acklen Ave., Nashville, TN 37212, USA; badr@uiuc.edu
2  Department of Computer Science, P. J. Šafárik University, Jesenná 5, 04001 Košice, Slovakia; viliam.geffert@upjs.sk
3  Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, IL 60637, USA; ics@math.uchicago.edu


Received July 12, 2007. Accepted November 21, 2007. Published online 20 December 2007

Abstract
We present the first (polynomial-time) algorithm for reducing a given deterministic finite state automaton (DFA) into a hyper-minimized DFA, which may have fewer states than the classically minimized DFA. The price we pay is that the language recognized by the new machine can differ from the original on a finite number of inputs. These hyper-minimized automata are optimal, in the sense that every DFA with fewer states must disagree on infinitely many inputs. With small modifications, the construction works also for finite state transducers producing outputs. Within a class of finitely differing languages, the hyper-minimized automaton is not necessarily unique. There may exist several non-isomorphic machines using the minimum number of states, each accepting a separate language finitely-different from the original one. We will show that there are large structural similarities among all these smallest automata.


Mathematics Subject Classification. 68Q70

Key words: Finite state automata -- regular languages.


© EDP Sciences 2007


What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.