Path: utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!mcsun!sunic!dkuug!daimi!mis
From: mis@daimi.dk (Michael I. Schwartzbach)
Newsgroups: comp.theory
Subject: lower bound for FSA language inclusion...
Message-ID: <5423@daimi.dk>
Date: 28 Feb 90 10:07:12 GMT
Sender: news@daimi.dk
Reply-To: mis@daimi.dk (Michael I. Schwartzbach)
Organization: DAIMI: Computer Science Department, Aarhus University, Denmark
Lines: 13

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