Systematic Verification of Safety Properties of Arbitrary Network Protocol Compositions Using CHAIN

Formal correctness of complex multi-party network protocols can be difficult to verify. While models of specific fixed compositions of agents can be checked against design constraints, protocols which lend themselves to arbitrarily many compositions of agents-such as the chaining of proxies or the peering of routers-are more difficult to verify because they represent potentially infinite state spaces and may exhibit emergent behaviors which may not materialize under particular fixed compositions. We address this challenge by developing an algebraic approach that enables us to reduce arbitrary compositions of network agents into a behaviorally-equivalent (with respect to some correctness property) compact, canonical representation, which is amenable to mechanical verification. Our approach consists of an algebra and a set of property-preserving rewrite rules for the Canonical Homomorphic Abstraction of Infinite Network protocol compositions (CHAIN). Using CHAIN, an expression over our algebra (i.e., a set of configurations of network protocol agents) can be reduced to another behaviorally-equivalent expression (i.e., a smaller set of configurations). Repeated applications of such rewrite rules produces a canonical expression which can be checked mechanically. We demonstrate our approach by characterizing deadlock-prone configurations of HTTP agents, as well as establishing useful properties of an overlay protocol for scheduling MPEG frames, and of a protocol for Web intra-cache consistency.

Type Inference for Variant Object Types

Existing type systems for object calculi are based on invariant subtyping. Subtyping invariance is required for soundness of static typing in the presence of method overrides, but it is often in the way of the expressive power of the type system. Flexibility of static typing can be recovered in different ways: in first-order systems, by the adoption of object types with variance annotations, in second-order systems by resorting to Self types. Type inference is known to be P-complete for first-order systems of finite and recursive object types, and NP-complete for a restricted version of Self types. The complexity of type inference for systems with variance annotations is yet unknown. This paper presents a new object type system based on the notion of Split types, a form of object types where every method is assigned two types, namely, an update type and a select type. The subtyping relation that arises for Split types is variant and, as a result, subtyping can be performed both in width and in depth. The new type system generalizes all the existing first-order type systems for objects, including systems based on variance annotations. Interestingly, the additional expressive power does not affect the complexity of the type inference problem, as we show by presenting an O(n^3) inference algorithm.

The abelianization of the Johnson kernel

We prove that the first complex homology of the Johnson subgroup of the Torelli group Tg is a non-trivial, unipotent Tg-module for all g ≥ 4 and give an explicit presentation of it as a Sym H 1(Tg,C)-module when g ≥ 6. We do this by proving that, for a finitely generated group G satisfying an assumption close to formality, the triviality of the restricted characteristic variety implies that the first homology of its Johnson kernel is a nilpotent module over the corresponding Laurent polynomial ring, isomorphic to the infinitesimal Alexander invariant of the associated graded Lie algebra of G. In this setup, we also obtain a precise nilpotence test. © European Mathematical Society 2014.

Consistent deformations of [p,p]-type gauge field theories

Using BRST-cohomological techniques, we analyze the consistent deformations of theories describing free tensor gauge fields whose symmetries are represented by Young tableaux made of two columns of equal length p, p > 1. Under the assumptions of locality and Poincaré invariance, we find that there is no consistent deformation of these theories that non-trivially modifies the gauge algebra and/or the gauge transformations. Adding the requirement that the deformation contains no more than two derivatives, the only possible deformation is a cosmological-constant-like term. © SISSA/ISAS 2004.

No self-interaction for two-column massless fields

We investigate the problem of introducing consistent self-couplings in free theories for mixed tensor gauge fields whose symmetry properties are characterized by Young diagrams made of two columns of arbitrary (but different) lengths. We prove that, in flat space, these theories admit no local, Poincaré-invariant, smooth, selfinteracting deformation with at most two derivatives in the Lagrangian. Relaxing the derivative and Lorentz-invariance assumptions, there still is no deformation that modifies the gauge algebra, and in most cases no deformation that alters the gauge transformations. Our approach is based on a Becchi-Rouet-Stora-iyutin (BRST) -cohomology deformation procedure. © 2005 American Institute of Physics.

Spin three gauge theory revisited

We study the problem of consistent interactions for spin-3 gauge fields in flat spacetime of arbitrary dimension 3$">n>3. Under the sole assumptions of Poincaré and parity invariance, local and perturbative deformation of the free theory, we determine all nontrivial consistent deformations of the abelian gauge algebra and classify the corresponding deformations of the quadratic action, at first order in the deformation parameter. We prove that all such vertices are cubic, contain a total of either three or five derivatives and are uniquely characterized by a rank-three constant tensor (an internal algebra structure constant). The covariant cubic vertex containing three derivatives is the vertex discovered by Berends, Burgers and van Dam, which however leads to inconsistencies at second order in the deformation parameter. In dimensions 4$">n>4 and for a completely antisymmetric structure constant tensor, another covariant cubic vertex exists, which contains five derivatives and passes the consistency test where the previous vertex failed. © SISSA 2006.

Parity-violating vertices for spin-3 gauge fields

The problem of constructing consistent parity-violating interactions for spin-3 gauge fields is considered in Minkowski space. Under the assumptions of locality, Poincaré invariance, and parity noninvariance, we classify all the nontrivial perturbative deformations of the Abelian gauge algebra. In space-time dimensions n=3 and n=5, deformations of the free theory are obtained which make the gauge algebra non-Abelian and give rise to nontrivial cubic vertices in the Lagrangian, at first order in the deformation parameter g. At second order in g, consistency conditions are obtained which the five-dimensional vertex obeys, but which rule out the n=3 candidate. Moreover, in the five-dimensional first-order deformation case, the gauge transformations are modified by a new term which involves the second de Wit-Freedman connection in a simple and suggestive way. © 2006 The American Physical Society.

Layers of generality and types of generalization in pattern activities

Pattern generalization is considered one of the prominent routes for in-troducing students to algebra. However, not all generalizations are al-gebraic. In the use of pattern generalization as a route to algebra, we —teachers and educators— thus have to remain vigilant in order not to confound algebraic generalizations with other forms of dealing with the general. But how to distinguish between algebraic and non-algebraic generalizations? On epistemological and semiotic grounds, in this arti-cle I suggest a characterization of algebraic generalizations. This char-acterization helps to bring about a typology of algebraic and arithmetic generalizations. The typology is illustrated with classroom examples.

Errores y dificultades en procesos de representación: el caos de la generalización y el razonamiento algebraico

Al respecto de las múltiples angustias surgidas por docentes de matemáticas en formación entorno a las dificultades y errores evidenciados por estudiantes de básica segundaria y media en la construcción de pensamiento algebraico, se expone a continuación para el caso de la generalización algebraica los hallazgos logrados desde la investigación que recupera en primera instancia a manera de reseña los referentes teórico conceptuales, las definiciones pertinentes y la clasificación de las dificultades y errores en la educación matemática especialmente en el caso de algebra; de igual manera se detallan características y acuerdos conceptuales entorno a razonamiento, razonamiento algebraico; esta ponencia evidencia los presupuestos e ideales para la educación matemática y la enseñanza del algebra para finalmente establecer la relación y justificación conceptual entre: sistemas de representación (errores); las dificultades (comprensión) y razonamiento algebraico. Con la exposición de ejemplos logrados en las experiencias de aula y analizados producto del trabajo de campo en este estudio, se presenta a manera de propuesta los comentarios, reflexiones y recomendaciones que permitirán al futuro docente de matemáticas diseñar un modelo de competencia formal y cognitivo para entender y actuar en situaciones de la enseñabilidad que se dan en el entorno educativo en especial en relación al razonamiento algebraico.

La derivada a la caratheodory, una nueva concepción en el aprendizaje y la enseñanza del calculo

A nivel educativo la noción de derivada se enseña en los cursos regulares de cálculo, pero por lo general, siempre en la forma en que fue definida por Cauchy, lo que implica un procedimiento se hace necesario hacer una factorización. Constantin Caratheodory establece una definición diferente. Esta definición presenta tres aspectos didácticos destacados: Nos muestra que el proceso de acercamiento de las pendientes de las secantes a la pendiente de la tangente es continuo y por tanto, la continuidad es esencial para la derivabilidad, la segunda parte se refiere a la facilidad de la derivación como un proceso de factorización repetitivo y no como cálculo de límites, así como simplicidad en la demostración de teoremas de linealidad, regla de la cadena, algebra de derivadas (suma, producto y cociente), aplicado a funciones polinómicas de valor real y la tercera es que a nivel escolar se generan alternativas en la enseñanza del cálculo a través de la implementación de conceptos nuevos, con el fin de evitar procedimientos tediosos que se tienen con las definiciones tradicionales como la de Cauchy.

Estrategias para accesar a la comprensión de tus estudiantes en ciertos conceptos matemáticos

En este taller (de una sesión) se proponen ciertas actividades que conectan el algebra con diversas situaciones del mundo real. La idea es hacer que los presentes desarrollen las tareas para que conozcan otras alternativas para construir conceptos como tasa de cambio o pendiente, modelamiento de datos, líneas de mejor ajuste, datos atípicos, errores en experimentos, bases de ingenierías civil, uso de modelos matemáticos para hacer predicciones y cuando los modelos matemáticos no describen la realidad de los experimentos. En el taller se realizaran tres actividades: A. FORTALEZA DE LAS VIGAS B. ATANDO NUDOS C. CONSTRUCCION DEL TRIACONTRAEDRO ROMBICO (LAMPARA DANESA) El realizar estas experiencias nos ayudaran a entender los estados de conflicto que entra el estudiante a la hora de procesar, adquirir y afianzar el conocimiento

Ecuaciones lineales con una incógnita

Este capítulo presenta el diseño, implementación y evaluación de una unidad didáctica sobre ecuaciones lineales con una incógnita. Diseñamos e implementamos la unidad didáctica objeto de este trabajo teniendo en cuenta las dificultades que presentan los estudiantes en la traducción al lenguaje algebraico, el planteamiento y solución de ecuaciones lineales de primer grado y la solución de problemas con ecuaciones lineales de primer grado. La interpretación de frases de la cotidianidad que deben ser traducidas a un lenguaje formal para construir expresiones algebraicas y con ellas generar ecuaciones crean una barrera para la utilización real del álgebra. Para alcanzar un aprendizaje significativo de los procesos algebraicos es necesario dotar las actividades de significado dentro del contexto del joven y así tener un aprendizaje concreto que posteriormente sirva de plataforma para el uso de la ecuación como herramienta fundamental en la aplicación del algebra en contextos reales.

Una caracterización del tratamiento y asimilación de contenidos en los cursos de álgebra superior

Las Instituciones de Educación Superior,en México, reportan bajos índices de Eficiencia Terminal, hecho relacionado con la reprobación, como es el caso de la Facultad de Matemáticas de la Universidad Autónoma de Yucatán, donde se presentan altos porcentajes de reprobación en la asignatura de Álgebra. Desarrollamos un estudio cualitativo empleando la etnografía, para caracterizar el tratamiento de los contenidos, otorgado por el profesor, y el nivel de asimilación de estos, por parte de los estudiantes. Identificamos las principales representaciones semióticas empleadas por el profesor, donde concluimos que el tratamiento otorgado a los contenidos es preferentemente algebraico y conjuntista. Además, la práctica de evaluación limita a los estudiantes a reproducir los conceptos enseñados.

Deducciones del teorema de Pitágoras a lo largo de la historia como recurso didáctico en el proceso de enseñanza-aprendizaje de la matemática

Las deducciones que a lo largo de la historia se han realizado en torno al teorema de Pitágoras pueden ayudar en el proceso de enseñanza-aprendizaje que realmente necesitan nuestros estudiantes, con el fin de que comprendan los conceptos a través de la reconstrucción de un método, de tal manera que no mecanicen reglas sino mas bien se logre aumentar y relacionar los conceptos adquiridos previamente de tal manera que se logre una mejor comprensión. Usaremos el enfoque histórico como una propuesta metodológica que actué como motivación para el alumno, ya que por medio de ella el estudiante descubrirá como generar los conceptos a través de métodos que aprenderá en clase. Discutiremos los conceptos y propiedades fundamentales de magnitudes, tales como la longitud y el área de figuras geométricas dadas en una y dos dimensiones, repasaremos los conceptos del producto notable del cuadrado de la suma de dos cantidades desde el punto de vista geométrico lo cual nos ayudara a inducir la demostración del teorema de Pitágoras a través de triángulos rectángulos notables e isósceles rectángulos, tomando en consideración el área de los cuadrados que se encuentra en los lados de dichos triángulos. Esto nos ayudara a recalcar la generalización del teorema de Pitágoras a través de figuras regulares. Las deducciones se harán pasando de la rama de la matemática llamada Algebra, conjugándola o dándole soporte con otra que muestra la forma estructural, como lo es la Geometría.