Article View: comp.theory
Article #1751Re: Undecidable problems about CFL's.
From: Dr Sheila Greibach
Date: Mon, 27 May 1991 22:13
Date: Mon, 27 May 1991 22:13
19 lines
1247 bytes
1247 bytes
In article <1991May17.211050.3096@csun.edu> lorentz@ms.secs.csun.edu () writes: >just when is the question L=L'? decidable >for arbitrary CFL L and fixed L'. This is known, but I wouldn't dare use it for an exam even in a graduate course in cfl! The answer can be found (I think; I don't have it in front of me) in: Hunt & Rosenkrantz, "On equivalence and containment problems for formal languages" JACM (1977) Vol 24, 387-396 In a nutshell -- decidable if L' is bounded cfl (reduction to Presburger arithmetic); undecidable if L' is unbounded regular (in essence, reduction from the case L' = (0+1)* ). [A language L is called bounded if the are words w(1),...,w(n) such that L is included in w(1)* ... w(n)* ]
Technical Details
Message-ID:
<1991May27.221353.3595@cs.ucla.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ucla-cs!maui.cs.ucla.edu!greibachReferences:
<1991May17.211050.3096@csun.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!usc!elroy.jpl.nasa.gov!ucla-cs!maui.cs.ucla.edu!greibach From: greibach@maui.cs.ucla.edu (Dr Sheila Greibach) Newsgroups: comp.theory Subject: Re: Undecidable problems about CFL's. Message-ID: <1991May27.221353.3595@cs.ucla.edu> Date: 27 May 91 22:13:53 GMT References: <1991May17.211050.3096@csun.edu> Sender: usenet@cs.ucla.edu (Mr. News Himself) Organization: UCLA Computer Science Department Lines: 19 Nntp-Posting-Host: maui.cs.ucla.edu