Integer sizes and DFAs

One of the posters mentioned that ignoring the size of integers used
in the DFAs was "not computer science". Actually, it is. It's called
the RAM model of computing. And, in it you assume each "integer"
occupies one location and is also sufficient to address any memory
location. Sa, accessing any integer any where in memory is an O(1)
operation.


Note how that even works for the DNA DFAs, assuming 32 bit integers
and a byte addressed machine. With that model, you can fit 10 million
(1E7) states in the 2 billion byte (2GB) address space (each state has
4, 4 byte entries or 16 bytes). You might even fit something over 100
million (1E8) states there. Thus, your memory access time is linear
in the worst case (assuming every request is a cache miss).


With 64 bit integers, one is essentially only limited by total memory
(including disk) and it is still linear although the worst case time
is every access is a page fault. Probably not particularly practical,
but CS is about theory and how you model it.


--
******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.