Artículos relacionados a Match-Bounded String Rewriting Systems

Match-Bounded String Rewriting Systems - Tapa blanda

Geser, Alfons

 
9781289263676: Match-Bounded String Rewriting Systems
Tapa blanda
ISBN 10: 1289263671 ISBN 13: 9781289263676
Editorial: BiblioGov, 2013

Sinopsis

We introduce a new class of automated proof methods for the termination of rewriting systems on strings. The basis of all these methods is to show that rewriting preserves regular languages. To this end, letters are annotated with natural numbers, called match heights. If the minimal height of all positions in a redex is h+1 then every position in the reduct will get height h+1. In a match-bounded system, match heights are globally bounded. Using recent results on deleting systems, we prove that rewriting by a match-bounded system preserves regular languages. Hence it is decidable whether a given rewriting system has a given match bound. We also provide a sufficient criterion for the abence of a match-bound. The problem of existence of a match-bound is still open. Match-boundedness for all strings can be used as an automated criterion for termination, for match-bounded systems are terminating. This criterion can be strengthened by requiring match-boundedness only for a restricted set of strings, for instance the set of right hand sides of forward closures.

"Sinopsis" puede pertenecer a otra edición de este libro.

Reseña del editor

We introduce a new class of automated proof methods for the termination of rewriting systems on strings. The basis of all these methods is to show that rewriting preserves regular languages. To this end, letters are annotated with natural numbers, called match heights. If the minimal height of all positions in a redex is h+1 then every position in the reduct will get height h+1. In a match-bounded system, match heights are globally bounded. Using recent results on deleting systems, we prove that rewriting by a match-bounded system preserves regular languages. Hence it is decidable whether a given rewriting system has a given match bound. We also provide a sufficient criterion for the abence of a match-bound. The problem of existence of a match-bound is still open. Match-boundedness for all strings can be used as an automated criterion for termination, for match-bounded systems are terminating. This criterion can be strengthened by requiring match-boundedness only for a restricted set of strings, for instance the set of right hand sides of forward closures.

"Sobre este título" puede pertenecer a otra edición de este libro.

Editorial
BiblioGov
Año de publicación
2013
Idioma
Inglés
ISBN 10 
1289263671
ISBN 13 
9781289263676
Encuadernación
Tapa blanda
Número de páginas
26
Contacto del fabricante
no disponible
Persona responsable
no disponible