Name: Match-Bounded String Rewriting Systems (en Inglés)
Price: 27.69 USD
Availability: InStock
Author: Geser, Alfons ; Nasa Technical Reports Server (Ntrs) ; Et Al
ISBN: 9781289263676

portada Match-Bounded String Rewriting Systems (en Inglés)

Match-Bounded String Rewriting Systems (en Inglés)

Formato

Libro Físico

Autor

Nasa Technical Reports Server (Ntrs)

Alfons Geser

Editorial

Bibliogov

Idioma

Inglés

N° páginas

Encuadernación

Tapa Blanda

Dimensiones

24.6 x 18.9 x 0.1 cm

Peso

0.07 kg.

ISBN13

9781289263676

Categorías

Política y gobierno

Match-Bounded String Rewriting Systems (en Inglés)

Nasa Technical Reports Server (Ntrs) (Autor) · Alfons Geser (Autor) · Bibliogov · Tapa Blanda

Libro Nuevo Importado

Envío: 21 a 28 días háb.

$ 55.39$ 27.69

-50%

Costos de importación incluídos en el precio ✅

Libro Nuevo

Quedan 100 unidades

$ 27.69

Llega entre el 10 Sep y el 23 Sep a Quito, Pichincha. Seleccionar ubicación

Agregar a lista de deseos

Reseña del libro "Match-Bounded String Rewriting Systems (en Inglés)"

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.