mis@daimi.dk (Michael I. Schwartzbach) (02/28/90)
What is the lower bound for language inclusion of deterministic finite automata with n states? Language equality can be tested in time O(n a(n)) (where a() is the inverse Ackermann's) but algorithms for inclusion seem to be O(n^2). Is this in fact a lower bound? -- Michael I. Schwartzbach / mis@daimi.dk (..uunet!mcvax!diku!daimi!mis) Computer Science Department, Aarhus University Ny Munkegade 116, DK-8000 Aarhus C, DENMARK phone: +45 6 12 71 88 / telefax: +45 6 13 57 25 / telex: 64767 aausci dk