Xref: utzoo comp.theory:1528 sci.logic:1102
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!edcastle!cs.ed.ac.uk!cs.edinburgh.ac.uk!hans
From: hans@lfcs.edinburgh.ac.uk (Hans Huttel)
Newsgroups: comp.theory,sci.logic
Subject: (Un)decidability results for partial orderings/preorders ?
Message-ID: <5982@skye.cs.ed.ac.uk>
Date: 11 Feb 91 13:27:32 GMT
Sender: nnews@cs.ed.ac.uk
Reply-To: hans@lfcs.edinburgh.ac.uk (Hans Huttel)
Followup-To: comp.theory
Organization: Lab. for Foundations of Computer Science, University of Edinburgh
Lines: 23

There are several well-known problems concerning equivalences that are
known to be decidable: the word problem for Thue systems and the equivalence of
context-free grammars come to mind. How about results for partial orderings ?

One example that I can think of is the following:

Language inclusion is undecidable for simple grammars and thus for context-free
grammars in general; this was proved by Emily Friedman back in 1976.

My question is now:

Are there any similar (un)decidability results for language inclusion and other
partial orders/preorders for grammars, automata or similar structures (e.g.
Petri nets) ? 

Please reply by e-mail. If there is interest, I will post a summary of the
replies.

-- 
Hans H\"{u}ttel, Office 1603        JANET: hans@uk.ac.ed.lfcs
Lab. for Foundations of Comp. Sci.  UUCP:  ..!mcvax!ukc!lfcs!hans
JCMB, University of Edinburgh       ARPA: hans%lfcs.ed.ac.uk@nsfnet-relay.ac.uk
Edinburgh EH9 3JZ, SCOTLAND         Casualties ? Nothing casual about dying.