Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Classes of term rewrite systems with polynomial confluence problems

Autor
Godoy, G.; Nieuwenhuis, R.
Tipus d'activitat
Document cientificotècnic
Data
2002-06-06
Codi
LSI-02-45-R
Repositori
http://hdl.handle.net/2117/97487 Obrir en finestra nova
Resum
The confluence property of ground (i.e., variable-free) term rewrite systems (GTRS) is well-known to be decidable. This was proved independently in [DTHL87,DHLT90] and in [Oya87] using tree automata techniques and ground tree transducer techniques (originated from this problem), yielding EXPTIME decision procedures (PSPACE for strings). Since then, it has been a well-known longstanding open question whether this bound is optimal (see, e.g., [RTA01]). In [CGN01] we gave the first polynomial-t...
Citació
Godoy, G., Nieuwenhuis, R. "Classes of term rewrite systems with polynomial confluence problems". 2002.
Paraules clau
Confluence property of ground, GTRS, Polynomial confluence, Term rewrite systems
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals
LOGPROG - Lògica i Programació

Participants

Arxius