Computación a saltos: Actualización de autómatas y gramáticas para el procesamiento discontinuo de la información

Título original:

Jumping Computation: Updating Automata and Grammars for Discontinuous Information Processing

Contenido del libro:

Jumping Computation: Updating Automata and Grammars for Discontinuous Information Processing es ante todo un tratamiento teórico de los autómatas y gramáticas de salto, que abarca todos los temas teóricos esenciales relacionados con ellos, incluida su potencia, propiedades y transformaciones. Desde un punto de vista práctico, describe diversos conceptos, métodos, algoritmos, técnicas, estudios de casos y aplicaciones basados en estos autómatas y gramáticas.

En el mundo informatizado actual, el desarrollo científico y el estudio de la computación, denominados teoría de la computación, desempeñan un papel crucial. Una rama importante, la teoría del lenguaje, investiga cómo definir y estudiar los lenguajes y sus modelos, que formalizan algoritmos según los cuales se ejecuta su computación. Estos modelos de definición de lenguajes se clasifican en dos categorías básicas: los autómatas, que definen lenguajes mediante el reconocimiento de sus palabras, y las gramáticas, que los generan. Introducidas hace muchas décadas, estas reglas reflejan la computación secuencial clásica. Sin embargo, los métodos computacionales actuales suelen procesar la información de un modo fundamentalmente distinto, "saltando" con frecuencia sobre grandes porciones de la información en su conjunto. Este libro adapta los modelos clásicos para formalizar y estudiar adecuadamente este tipo de computación. En pocas palabras, durante su proceso de definición del lenguaje, estas versiones adaptadas, denominadas autómatas y gramáticas saltarinas, saltan a través de las palabras sobre las que trabajan.

El libro selecciona modelos importantes y resume los resultados clave sobre ellos de forma compacta y uniforme. Relaciona cada modelo con una forma particular de computación moderna, como la computación secuencial, semiparalela y totalmente paralela, y explica cómo el modelo en cuestión refleja y formaliza adecuadamente la forma de computación correspondiente, permitiéndonos así obtener un cuerpo sistematizado de conocimientos matemáticamente precisos sobre la computación saltatoria. El libro presta especial atención a la potencia, las propiedades de cierre y las transformaciones, y también describe muchos algoritmos que modifican las gramáticas y autómatas de salto para que satisfagan algunas propiedades prescritas sin cambiar el lenguaje definido. El libro será de gran interés para cualquiera que investigue la teoría de la computación en los campos de la informática, las matemáticas, la ingeniería, la lógica y la lingüística.