[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
Originator: Deepak Kapur
Date: April 1991
Summary: What is the complexity of deciding ground-reducibility?
A term t is ground reducible with respect to a rewrite system R if all its ground (variable-free) instances contain a redex. Ground reducibility is decidable for ordinary rewriting (and finite R) [Com88, KNZ87, Pla85], but n^{nn} is the best known upper bound in general, 2^{d n logn} and 2^{c n/ logn} are the best upper and lower bounds, respectively, for left-linear systems, where n is the size of the system R and c,d are constants [KNZ87]. Can these bounds be improved?
Ground-reducibility is EXPTIME-complete [CJ97, CJ03].
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |