lower bound for FSA language inclusion...

Article View: comp.theory

Article #2115

#2115

From: Michael I. Schwartzbach
Date: Wed, 28 Feb 1990 10:07

13 lines
959 bytes

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

Technical Details

Message-ID: <5423@daimi.dk>

Path: arc1-ca.pugleaf.net!utzoo!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!mcsun!sunic!dkuug!daimi!mis

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!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