bluuebunny/crossref_metadata_2025 huggingface dataset:
A rare complication of follicular hair unit extraction: Kaposi’s varicelliform eruption
Authors: Mansur A. Tulin , Demirci Gulsen T. , Uzunismail M. Adnan , Yıldız Semsi
Published: February 2016

Follicular hair unit extraction (FUE) is becoming a popular type of hair transplantation recently. Kaposi’s varicelliform eruption (KVE) is an uncommon skin emergency due to cutaneous dissemination of several types of viruses, most notably herpes virus, over the lesions of preexisting skin disorders.

A 34-year-old man visited our plastic surgery outpatient clinic with a blistering, itchy and tender eruption on his head and body. He had undergone follicular FUE for androgenic alopecia 12 days previously, and 5 days after the procedure, umbilicated and/or hemorrhagic vesiculopustules appeared firstly on the occipital scalp skin where the hair units were taken. The lesions had rapidly spread over the upper chest and back. After the operation, he had taken oral methylprednisolone, amoxicillin clavulanate and had used fusidic acid ointment without any benefit. Bacterial culture of the pustules yielded no microorganism, while Tzanck smear from the vesicles revealed multinuclear giant cell groups. Based on a diagnosis of KVE, we treated the patient with oral valacyclovir hydrochloride 1000 mg 3 times a day for 14 days. Symptoms cleared rapidly, pustules and vesicles dried in a few days, and re-epithelialization of the eroded areas started at the end of the first week.

The reported complications of FUE include necrosis of the donor site, postoperative hyperesthesia, recipient area folliculitis, keloids, bleeding, infection and pyogenic granuloma. Up to this date there are only three reports of KVE developing just after dermatological surgery, including dermabrasion, laser resurfacing, and skin grafting. According to our knowledge, this is the first case of KVE occurring after the FUE procedure. We think that the traumatic effects and skin barrier disruption due to operation and immune alteration due to postsurgical steroid treatment might have precipitated the activation and dissemination of latent herpesvirus infection.
Vasculitis with panniculitis following botulinum toxin A injection for cosmetic use
Authors: Namazi Nastaran , Robati Reza M. , Dadkhahfar Sahar , Shafiee Anoush , Bidari-Zerehpoush Farahnaz
Published: February 2016

Botulinum toxin A injection is performed most frequently for facial rejuvenation all over the world. Some bizarre and severe side effects have been reported after botulinum toxin A injection. Herein, we present a case of vasculitis with panniculitis after a patient underwent a cosmetic procedure that included injection of purported botulinum toxin A.
Therapeutic management of users with oral anticoagulant therapy
Authors: Cascalho Serra Isaura da Conceição , Ribeiro Lurdes da Conceição Afonso Nobre , Gemito Maria Laurência Grou Parreirinha , Mendes Felismina Rosa Parreira
Published: February 2016

Objetivo: Caracterizar a los usuarios con terapia anticoagulante oral; conocer el régimen de tratamiento y estimar los costes de evaluación de la International Normalized Ratio (INR).

Metodologia: Estudio descriptivo, transversal, exploratorio, con 83 usuarios con terapia anticoagulante oral de un Centro de Salud de Alentejo. Los datos fueron recolectados con la aplicación de cuestionario construido para este fin.

Resultados: Se concluyó que 50,6% informaron no saber qué es la coagulación; 49,4% lo que son anticoagulantes orales; 63,9% las complicaciones de la terapia anticoagulante oral. 27,7% conoce los alimentos que interfieren con esta terapia y 51,8% declara saber qué hacer en caso de lesión, cirugía o de la extracción de un diente. El costo de la evaluación de RNI (Razón Normalizada Internacional)  en laboratorio es mayor que en los centros de salud.

Conclusiones: Existen lagunas en el conocimiento sobre el proceso de coagulación, la interferencia de alimentación y el régimen. La descentralización de la consulta de enfermería puede reducir los costos, mejorar la accesibilidad y la gestión del régimen terapéutico.
Estudio piloto. Memoria implícita, memoria explícita y deterioro cognitivo: evolución en el trastorno psicótico
Authors: Pérez Moreno Juan José , Romero García Manuel , Salazar Gámez Almudena , Moreno Beatriz Ortega
Published: February 2016

En relación a los sistemas de memoria de nuestra investigación, clasificamos la memoria explícita, voluntaria, consciente; mientras que la memoria implícita no requiere la recuperación intencional o consciente.

Además del envejecimiento, las enfermedades psiquiátricas constituyen otras causas frecuentes de deterioro cognitivo; más específicamente, en el Trastorno psicótico están afectadas la memoria declarativa verbal (explícita), la memoria de trabajo y existen otros déficits cognitivos.

Metodología: El objetivo de este estudio consiste en analizar la evolución del Trastorno psicótico (en años) en relación a la memoria y al deterioro cognitivo, así como describir posibles asociaciones entre ambos tipos de memoria (implícita/explícita) y el deterioro cognitivo.

Se trata de un estudio descriptivo, observacional, transversal, formado por tres muestras de pacientes con Trastorno psicótico.

Resultados: Se obtienen proporciones medias mayores en los dos primeros grupos (0-5 años de evolución del Trastorno psicótico/ 10-15 años de evolución) que en el tercer grupo (25-35 años de evolución) para los resultados de memoria explícita. Respecto a la memoria implícita se observa la existencia de Priming en los tres grupos. Mientras que la puntuación positiva en el cribado de deterioro cognitivo es progresivamente mayor al aumentar los años de evolución de la enfermedad.

Conclusiones: Las personas con más años de evolución del trastorno psicótico presentan mayor deterioro cognitivo y puntuaciones medias menores en memoria explícita; mientras que la memoria implícita se mantiene estable independientemente de los años de evolución de la enfermedad.
Cultura de segurança: a percepção dos profissionais de enfermagem intensivistas
Authors: Barcelos Schwonke Camila Rose Guadalupe , Lunardi Filho Wilson Danilo , Lunardi Guilherme Lerch , Da Silveira Rosemary Silva , Soares Rodrigues Maria Cristina , Guerreiro. Márcio Osório
Published: February 2016

Se trata de un estudio que tuvo por objetivo caracterizar la cultura de seguridad de las instituciones hospitalarias, en la percepción de los profesionales de enfermería intensivista. Para ello, se adaptó el instrumento de percepción de cultura de seguridad, propuesto por Singer et al (2003), para el contexto brasileño.

La muestra se constituyó de 173 profesionales de enfermería, trabajadores en siete unidades de terapia intensiva localizadas en Río Grande del Sur. A partir de la validación del instrumento, fueron propuestos cuatro construtos conteniendo diferentes actitudes en relación a la seguridad del paciente: promoción de la seguridad del paciente a nivel organizacional, seguridad en el cuidado al paciente, prevención de errores como prioridad organizacional y percepción de riesgos y errores que ocurren en la organización.

Los resultados apuntan la necesidad de conducir mejor por parte de los servicios de salud las cuestiones que involucran la seguridad del paciente.
Cuidados de enfermería basados en evidencia y modelo de Betty Neuman, para controlar estresores del entorno que pueden ocasionar delirium en unidad de cuidados intensivos
Authors: Gómez Tovar Luz Omaira , Díaz Suárez Leticia , Cortés Muñoz Fabián
Published: February 2016

Antecedentes: El Delirium es una alteración del estado de conciencia, frecuente en las unidades de cuidado intensivo. En la UCI adultos del Hospital Universitario de Neiva se tiene una incidencia del 28%, esto aumenta la morbimortalidad; sin embargo es prevenible y requiere intervención.

Objetivo: Determinar la efectividad de los cuidados aplicados, según la Guía de enfermería elaborada con evidencia y en base al Modelo de Betty Neuman, para controlar estresores del entorno que pueden ocasionar Delirium, en pacientes hospitalizados en la unidad de cuidados intensivos adulto.

Metodología: Se realizó un estudio cuantitativo, transversal, pre-experimental, donde se aplicó la Guía de cuidados de enfermería a 49 pacientes. Se utilizó el diseño de preprueba y postprueba para conocer la percepción que tenían los pacientes de los estresores del entorno.

Resultados: Los cuidados aplicados según la Guía propuesta, fueron efectivos, ya que previnieron el delirium en el 94% de los pacientes, sólo tres presentaron el evento, representando una incidencia acumulada de 6.12 casos X 100 pacientes intervenidos (IC 95%: 1.67 – 16.1), evidenciado en la curva de Kaplan–Meier. La prueba de hipótesis de proporciones (Z0.05= -1.65) indica que la presencia de delirium es significativamente menor a la de 2011 (28%).

Conclusiones: Los cuidados aplicados según la Guía propuesta, lograron prevenir la aparición de delirium en 94% de los pacientes a pesar de sus antecedentes de factores de riesgo desencadenantes de delirium. De tal forma que, al minimizar la presencia de estresores del entorno, se  favorece un ambiente creado agradable y familiar, y se constituye en un cuidado de enfermería fundamental para la prevención de delirium en UCI.
Síndrome de Burnout en el personal de enfermería de un hospital de referencia Ibagué, Colombia, 2014
Authors: Grisales Romero Hugo , Muñoz Yudi , Osorio Diana , Robles Elena
Published: February 2016

Objetivo: Determinar la prevalencia del Síndrome de Burnout (SB) en el personal de enfermería de un hospital de referencia de una ciudad colombiana y su relación con variables demográficas.

Materiales y métodos: Se llevó a cabo un estudio de corte transversal en una muestra aleatoria y representativa de 174 enfermeras(os), estratificada según si la enfermera era profesional o auxiliar, en un hospital de referencia de la ciudad de Ibagué, Colombia. Se utilizó la escala validada en Colombia del MBI (Maslach Burnout Inventory). Se utilizaron pruebas de independencia, t para diferencia de promedios y análisis de la varianza de una vía. En el análisis multivariado, se construyó un modelo de regresión logística binaria explicativo, con medida de la asociación el OR acompañado de su respectivo intervalo de confianza del 95%.

Resultados: La prevalencia de Burnout fue del 20.1% (IC 95%: 13,9 26,4) y además el 52,3% están a riesgo de padecerlo. Los profesionales de enfermería que tenían una vinculación temporal o de supernumerario, aquellos que laboraban en servicios administrativos/oncología/camillero/esterilización, los hombres y quienes afirmaron tener más de un contrato, fueron quienes presentaron indicadores de la proporción de Burnout mayores del 20,1%. En el análisis multivariado, los factores conjuntos que probablemente tienen mayor incidencia en la presencia del Burnout son el número de hijos y ser hombre.

Conclusiones: Con respecto a otros estudios, este revela que la prevalencia del síndrome de Burnout en el hospital de referencia es mayor.
O olhar da Enfermagem diante do Processo de Morte e Morrer de pacientes críticos: Uma Revisão Integrativa
Authors: De Freitas Tiago Luan Labres , Banazeski Ana Claudia , Eisele Adriane , De Souza Elaine Natália , Vargas Bitencourt Júlia Valéria de Oliveira , De Souza Silvia Silva
Published: February 2016

Encarar la muerte y el miedo a enfrentarse a ella a cada instante se ha convertido en esencial para los trabajadores del área de la salud, en especial para el profesional de enfermería, que a su vez es quien presta los cuidados integrales al paciente y a la familia, ya que este debe luchar con el sufrimiento y con los miedos que pueden existir en los diversos momentos que acompañan el cuidar. Por tanto, es necesario profundizar em la visión del profesional de enfermería sobre el tema, de modo que pueda ver más allá de las circunstancias del contexto, y conocer los procesos de la muerte y del morir, para que su asistencia sea de calidad.

Partiendo de esto, el presente estudio tiene como objetivo: Analizar la producción científica nacional sobre la experiencia del equipo de enfermería ante la muerte de los pacientes críticos. Se empleó el método de revisión integral de la literatura. Se analizaron 14 artículos que cumplían la pregunta principal de la investigación y a partir del enfoque de estos estudios, fueron listadas dos categorías: 1-El proceso de muerte y morir: praxis y significados; 2- La cualificación del enfermero en su proceso de formación ante la temática muerte y el morir. El estudio identificó que existe una deficiencia en el aprendizaje de los profesionales para el proceso de la muerte y el morir, causando sufrimiento del equipo de enfermería, lo que influye en la calidad de la atención prestada a los pacientes y a sus familias. En este sentido, es importante realizar investigaciones acerca de esta temática para la ampliación del conocimiento y (re)deconstrucción de los paradigmas existentes.
Vantagens da presença da família numa reanimação pediátrica ou em procedimentos dolorosos
Authors: Vaz Judite , Alves Rita , Gomes Ramos Vera Lúcia
Published: February 2016

Introducción: La presencia de los padres o de otros familiares ante la prestación de procedimientos dolorosos para el niño, así como en la reanimación pediátrica, ha provocado discusión entre profesionales de la salud, por las ventajas y desventajas que presenta.

Objetivo: Teniendo en cuenta este problema, el objetivo de esta investigación consiste en identificar estudios científicos orientados a las ventajas de la presencia de los familiares en la sala de reanimación y/o en procedimientos dolorosos.  

Método: Fue realizada una revisión sistemática de la literatura con la siguiente pregunta de investigación: ¿Cuáles son las ventajas de la presencia de la familia en la sala de reanimación y/o procedimientos dolorosos?

Resultados: Todos los artículos identifican ventajas de la presencia de la familia en la sala de reanimación y/o procedimientos dolorosos.  

Conclusiones: La investigación favorece el debate y la reflexión entre el equipo multidisciplinar sobre la presencia de los familiares de los niños frente a procedimientos dolorosos o reanimación. Sin embargo, a fin de que este proceso sea factible, es necesaria la formación y capacitación de todo el equipo de salud, para que puedan estar disponibles para explicar los procedimientos a los familiares y acompañarlos en todo el proceso.
Prevalencia y factores asociados a osteoporosis en pacientes de Santa Marta (Colombia)
Authors: González-Ruiz Gisela Esther , Álvarez-Miño Lidice , Borré-Ortiz Yeis Miguel , Rivas Oduber Elimiled , Serrano Angarita Nini Sorell , Tavera Galeano Nivalysay
Published: February 2016

Objetivo: Identificar la prevalencia y los factores asociados a osteoporosis en un grupo de pacientes Samarios.

Materiales y Método: Estudio descriptivo, retrospectivo y correlacional, realizado en una población de 406 pacientes de un total de 1486 consultantes.

Resultados: La prevalencia encontrada fue de 27,32; los factores asociados fueron: edad mayor de 50 años (p=0,3405); género femenino (p= 0,3405), no realización de ejercicio físico (p= 0,011); paridad (p= 0,0001). Se halló asociación estadística entre la osteoporosis y las enfermedades del ojo y sus anexos (p= 0,0415), según la clasificación del Consejo Internacional de Enfermedades.

Conclusiones: La prevalencia de osteoporosis fue de 27,32%. La edad, el sedentarismo, la multiparidad, las enfermedades de los ojos y sus anexos, los antecedentes de cirugías ginecobstétricas y de vesícula fueron factores de riesgo estadísticamente significativos para el desarrollo de la osteoporosis.
Wireless Authentication in chi-Spaces
Authors: Crazzolara Federico , Milicia Giuseppe
Published: February 2016

The chi-Spaces framework provides a set of tools to support every step of the security protocol's life-cycle. The framework includes a simple, yet powerful programming language which is an implementation of the Security Protocol Language (SPL). SPL is a formal calculus designed to model security protocols and prove interesting properties about them. In this paper we take an authentication protocol suited for low-power wireless devices and derive a chi-Spaces implementation from its SPL model. We study the correctness of the resulting implementation using the underlying SPL semantics of chi-Spaces.
A Complexity Analysis of Functional Interpretations
Authors: Hernest Mircea-Dan , Kohlenbach Ulrich
Published: February 2016

We give a quantitative analysis of Gödel's functional interpretation and its monotone variant. The two have been used for the extraction of programs and numerical bounds as well as for conservation results. They apply both to (semi-)intuitionistic as well as (combined with negative translation) classical proofs. The proofs may be formalized in systems ranging from weak base systems to arithmetic and analysis (and numerous fragments of these). We give upper bounds in basic proof data on the depth, size, maximal type degree and maximal type arity of the extracted terms as well as on the depth of the verifying proof. In all cases terms of size linear in the size of the proof at input can be extracted and the corresponding extraction algorithms have cubic worst-time complexity. The verifying proofs have depth linear in the depth of the proof at input and the maximal size of a formula of this proof.
Some Logical Metatheorems with Applications in Functional Analysis
Authors: Kohlenbach Ulrich
Published: February 2016

In previous papers we have developed proof-theoretic techniques for extracting effective uniform bounds from large classes of ineffective existence proofs in functional analysis. `Uniform' here means independence from parameters in compact spaces. A recent case study in fixed point theory systematically yielded uniformity even w.r.t. parameters in metrically bounded (but noncompact) subsets which had been known before only in special cases. In the present paper we prove general logical metatheorems which cover these applications to fixed point theory as special cases but are not restricted to this area at all. Our theorems guarantee under general logical conditions such strong uniform versions of non-uniform existence statements. Moreover, they provide algorithms for actually extracting effective uniform bounds and transforming the original proof into one for the stronger uniformity result. Our metatheorems deal with general classes of spaces like metric spaces, hyperbolic spaces, normed linear spaces, uniformly convex spaces as well as inner product spaces.
Recent Advances in Σ-definability over Continuous Data Types
Authors: Korovina Margarita
Published: February 2016

The purpose of this paper is to survey our recent research in computability and definability over continuous data types such as the real numbers, real-valued functions and functionals. We investigate the expressive power and algorithmic properties of the language of Sigma-formulas intended to represent computability over the real numbers. In order to adequately represent computability we extend the reals by the structure of hereditarily finite sets. In this setting it is crucial to consider the real numbers without equality since the equality test is undecidable over the reals. We prove Engeler's Lemma for Sigma-definability over the reals without the equality test which relates Sigma-definability with definability in the constructive infinitary language L_{omega_1 omega}. Thus, a relation over the real numbers is Sigma-definable if and only if it is definable by a disjunction of a recursively enumerable set of quantifier free formulas. This result reveals computational aspects of Sigma-definability and also gives topological characterisation of Sigma-definable relations over the reals without the equality test. We also illustrate how computability over the real numbers can be expressed in the language of Sigma-formulas.
A Functional Correspondence between Call-by-Need Evaluators and Lazy Abstract Machines
Authors: Ager Mads Sig , Danvy Olivier , Midtgaard Jan
Published: February 2016

We bridge the gap between compositional evaluators and abstract machines for the lambda-calculus, using closure conversion, transformation into continuation-passing style, and defunctionalization of continuations. This article is a spin-off of our article at PPDP 2003, where we consider call by name and call by value. Here, however, we consider call by need.

We derive a lazy abstract machine from an ordinary call-by-need evaluator that threads a heap of updatable cells. In this resulting abstract machine, the continuation fragment for updating a heap cell naturally appears as an `update marker', an implementation technique that was invented for the Three Instruction Machine and subsequently used to construct lazy variants of Krivine's abstract machine. Tuning the evaluator leads to other implementation techniques such as unboxed values and the push-enter model. The correctness of the resulting abstract machines is a corollary of the correctness of the original evaluators and of the program transformations used in the derivation.

Superseded by BRICS-RS-04-3.
Regular Languages Definable by Lindström Quantifiers
Authors: Ésik Zoltán , Larsen Kim G.
Published: February 2016

In our main result, we establish a formal connection between Lindström quantifiers with respect to regular languages and the double semidirect product of finite monoids with a distinguished set of generators. We use this correspondence to characterize the expressive power of Lindström quantifiers associated with a class of regular languages.
Extracting Herbrand Disjunctions by Functional Interpretation
Authors: Gerhardy Philipp , Kohlenbach Ulrich
Published: February 2016

Carrying out a suggestion by Kreisel, we adapt Gödel's functional interpretation to ordinary first-order predicate logic(PL) and thus devise an algorithm to extract Herbrand terms from PL-proofs. The extraction is carried out in an extension of PL to higher types. The algorithm consists of two main steps: first we extract a functional realizer, next we compute the beta-normal-form of the realizer from which the Herbrand terms can be read off. Even though the extraction is carried out in the extended language, the terms are ordinary PL-terms. In contrast to approaches to Herbrand's theorem based on cut elimination or epsilon-elimination this extraction technique is, except for the normalization step, of low polynomial complexity, fully modular and furthermore allows an analysis of the structure of the Herbrand terms, in the spirit of Kreisel, already prior to the normalization step. It is expected that the implementation of functional interpretation in Schwichtenberg's MINLOG system can be adapted to yield an efficient Herbrand-term extraction tool.
A Functional Correspondence between Monadic Evaluators and Abstract Machines for Languages with Computational Effects
Authors: Ager Mads Sig , Danvy Olivier , Midtgaard Jan
Published: February 2016

We extend our correspondence between evaluators and abstract machines from the pure setting of the lambda-calculus to the impure setting of the computational lambda-calculus. Specifically, we show how to derive new abstract machines from monadic evaluators for the computational lambda-calculus. Starting from a monadic evaluator and a given monad, we inline the components of the monad in the evaluator and we derive the corresponding abstract machine by closure-converting, CPS-transforming, and defunctionalizing this inlined interpreter. We illustrate the construction first with the identity monad, obtaining yet again the CEK machine, and then with a state monad, an exception monad, and a combination of both.

In addition, we characterize the tail-recursive stack inspection presented by Clements and Felleisen at ESOP 2003 as a canonical state monad. Combining this state monad with an exception monad, we construct an abstract machine for a language with exceptions and properly tail-recursive stack inspection. The construction scales to other monads--including one more properly dedicated to stack inspection than the state monad--and other monadic evaluators.
Unfair Noisy Channels and Oblivious Transfer
Authors: Damgård Ivan B. , Fehr Serge , Morozov Kirill , Salvail Louis
Published: February 2016

In a paper from EuroCrypt'99, Damgård, Kilian and Salvail show various positive and negative results on constructing Bit Commitment (BC) and Oblivious Transfer (OT) from Unfair Noisy Channels (UNC), i.e., binary symmetric channels where the error rate is only known to be in a certain interval [gamma ..delta] and can be chosen adversarily. They also introduce a related primitive called PassiveUNC. We prove in this paper that any OT protocol that can be constructed based on a PassiveUNC and is secure against a passive adversary can be transformed using a generic "compiler'' into an OT protocol based on a UNC which is secure against an active adversary. Apart from making positive results easier to prove in general, this also allows correcting a problem in the EuroCrypt'99 paper: There, a positive result was claimed on constructing from UNC an OT that is secure against active cheating. We point out that the proof sketch given for this was incomplete, and we show that a correct proof of a much stronger result follows from our general compilation result and a new technique for transforming between weaker versions of OT with different parameters.
Full Abstraction for HOPLA
Authors: Nygaard Mikkel , Winskel Glynn
Published: February 2016

A fully abstract denotational semantics for the higher-order process language HOPLA is presented. It characterises contextual and logical equivalence, the latter linking up with simulation. The semantics is a clean, domain-theoretic description of processes as downwards-closed sets of computation paths: the operations of HOPLA arise as syntactic encodings of canonical constructions on such sets; full abstraction is a direct consequence of expressiveness with respect to computation paths; and simple proofs of soundness and adequacy shows correspondence between the denotational and operational semantics.
On converting CNF to DNF
Authors: Miltersen Peter Bro , Radhakrishnan Jaikumar , Wegener Ingo
Published: February 2016

We study how big the blow-up in size can be when one switches between the CNF and DNF representations of boolean functions. For a function f : {0,1}^n -> {0,1}, cnfsize(f) denotes the minimum number of clauses in a CNF for f; similarly, dnfsize(f) denotes the minimum number of terms in a DNF for f. For 0 <= m <= 2^{n-1} , let dnfsize(m,n) be the maximum dnfsize(f) for a function f : {0,1}^n -> {0,1} with cnfsize(f) <= m. We show that there are constants c_1, c_2 >= 1 and epsilon > 0 , such that for all large n and all m in [ 1/epsilon n , 2^{epsilon n}], we have
2^{(n - c_1) n / log(m/n)}  <= dnfsize(m,n) <=  2^{(n - c_2) n / log(m/n)}.
 In particular, when m is the polynomial n^c, we get dnfsize(n^c,n) = 2^{(n - theta) (c^{-1} n / log n)}.
Precise Analysis of String Expressions
Authors: Christensen Aske Simon , Møller Anders , Schwartzbach Michael I.
Published: February 2016

We perform static analysis of Java programs to answer a simple question: which values may occur as results of string expressions? The answers are summarized for each expression by a regular language that is guaranteed to contain all possible values. We present several applications of this analysis, including statically checking the syntax of dynamically generated expressions, such as SQL queries. Our analysis constructs flow graphs from class files and generates a context-free grammar with a nonterminal for each string expression. The language of this grammar is then widened into a regular language through a variant of an algorithm previously used for speech recognition. The collection of resulting regular languages is compactly represented as a special kind of multi-level automaton from which individual answers may be extracted. If a program error is detected, examples of invalid strings are automatically produced. We present extensive benchmarks demonstrating that the analysis is efficient and produces results of useful precision.
Jeeg: Temporal Constraints for the Synchronization of Concurrent Objects
Authors: Milicia Giuseppe , Sassone Vladimiro
Published: February 2016

We introduce Jeeg, a dialect of Java based on a declarative replacement of the synchronization mechanisms of Java that results in a complete decoupling of the `business' and the `synchronization' code of classes. Synchronization constraints in Jeeg are expressed in a linear temporal logic which allows to effectively limit the occurrence of the inheritance anomaly that commonly affects concurrent object oriented languages. Jeeg is inspired by the current trend in aspect oriented languages. In a Jeeg program the sequential and concurrent aspects of object behaviors are decoupled: specified separately by the programmer these are then weaved together by the Jeeg compiler.
The METAFRONT System: Extensible Parsing and Transformation
Authors: Brabrand Claus , Schwartzbach Michael I. , Vanggaard Mads
Published: February 2016

We present the metafront tool for specifying flexible, safe, and efficient syntactic transformations between languages defined by context-free grammars. The transformations are guaranteed to terminate and to map grammatically legal input to grammatically legal output.

We rely on a novel parser algorithm that is designed to support gradual extensions of a grammar by allowing productions to remain in a natural style and by statically reporting ambiguities and errors in terms of individual productions as they are being added.

Our tool may be used as a parser generator in which the resulting parser automatically supports a flexible, safe, and efficient macro processor, or as an extensible lightweight compiler generator for domain-specific languages. We show substantial examples of both kinds.
Efficient Algorithms for gcd and Cubic Residuosity in the Ring of Eisenstein Integers
Authors: Damgård Ivan B. , Frandsen Gudmund Skovbjerg
Published: February 2016

We present simple and efficient algorithms for computing gcd and cubic residuosity in the ring of Eisenstein integers, Z[zeta] , i.e. the integers extended with zeta , a complex primitive third root of unity. The algorithms are similar and may be seen as generalisations of the binary integer gcd and derived Jacobi symbol algorithms. Our algorithms take time O(n^2) for n bit input. This is an improvement from the known results based on the Euclidian algorithm, and taking time O(n· M(n)), where M(n) denotes the complexity of multiplying n bit integers. The new algorithms have applications in practical primality tests and the implementation of cryptographic protocols. The technique underlying our algorithms can be used to obtain equally fast algorithms for gcd and quartic residuosity in the ring of Gaussian integers, Z[i].
Probabilistic Event Structures and Domains
Authors: Varacca Daniele , Völzer Hagen , Winskel Glynn
Published: February 2016

This paper studies how to adjoin probability to event structures, leading to the model of probabilistic event structures. In their simplest form probabilistic choice is localised to cells, where conflict arises; in which case probabilistic independence coincides with causal independence. An application to the semantics of a probabilistic CCS is sketched. An event structure is associated with a domain--that of its configurations ordered by inclusion. In domain theory probabilistic processes are denoted by continuous valuations on a domain. A key result of this paper is a representation theorem showing how continuous valuations on the domain of a confusion-free event structure correspond to the probabilistic event structures it supports. We explore how to extend probability to event structures which are not confusion-free via two notions of probabilistic runs of a general event structure. Finally, we show how probabilistic correlation and probabilistic event structures with confusion can arise from event structures which are originally confusion-free by using morphisms to rename and hide events.
Maximum Exact Satisfiability: NP-completeness Proofs and Exact Algorithms
Authors: Madsen Bolette Ammitzbøll , Rossmanith Peter
Published: February 2016

Inspired by the Maximum Satisfiability and Exact Satisfiability problems we present two Maximum Exact Satisfiability problems. The first problem called Maximum Exact Satisfiability is: given a formula in conjunctive normal form and an integer k, is there an assignment to all variables in the formula such that at least k clauses have exactly one true literal. The second problem called Restricted Maximum Exact Satisfiability has the further restriction that no clause is allowed to have more than one true literal. Both problems are proved NP-complete restricted to the versions where each clause contains at most two literals. In fact Maximum Exact Satisfiability is a generalisation of the well-known NP-complete problem MaxCut. We present an exact algorithm for Maximum Exact Satisfiability where each clause contains at most two literals with time complexity O(poly(L) . 2^{m/4}), where m is the number of clauses and L is the length of the formula. For the second version we give an algorithm with time complexity O(poly(L) . 1.324718^n) , where n is the number of variables. We note that when restricted to the versions where each clause contains exactly two literals and there are no negations both problems are fixed parameter tractable. It is an open question if this is also the case for the general problems.
From Natural Semantics to Abstract Machines
Authors: Ager Mads Sig
Published: February 2016

We describe how to construct correct abstract machines from the class of L-attributed natural semantics introduced by Ibraheem and Schmidt at HOOTS 1997. The construction produces stack-based abstract machines where the stack contains evaluation contexts. It is defined directly on the natural semantics rules. We formalize it as an extraction algorithm and we prove that the algorithm produces abstract machines that are equivalent to the original natural semantics. We illustrate the algorithm by extracting abstract machines from natural semantics for call-by-value, call-by-name, and call-by-need evaluation of lambda terms.
Recursion vs. Replication in Simple Cryptographic Protocols
Authors: Hüttel Hans , Srba Jirí
Published: February 2016

We use some recent techniques from process algebra to draw several conclusions about the well studied class of ping-pong protocols introduced by Dolev and Yao. In particular we show that all nontrivial properties, including reachability and equivalence checking wrt. the whole van Glabbeek's spectrum, become undecidable for a very simple recursive extension of the protocol. The result holds even if no nondeterministic choice operator is allowed. We also show that the extended calculus is capable of an implicit description of the active intruder, including full analysis and synthesis of messages in the sense of Amadio, Lugiez and Vanackere. We conclude by showing that reachability analysis for a replicative variant of the protocol becomes decidable.
On the Adaptiveness of Quicksort
Authors: Brodal Gerth Stølting , Fagerberg Rolf , Moruz Gabriel
Published: February 2016

Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the best of which are among the fastest generic sorting algorithms available, as testified by the choice of Quicksort as the default sorting algorithm in most programming libraries. Some sorting algorithms are adaptive, i.e. they have a complexity analysis which is better for inputs which are nearly sorted, according to some specified measure of presortedness. Quicksort is not among these, as it uses Omega(n log n) comparisons even when the input is already sorted. However, in this paper we demonstrate empirically that the actual running time of Quicksort is adaptive with respect to the presortedness measure Inv. Differences close to a factor of two are observed between instances with low and high Inv value. We then show that for the randomized version of Quicksort, the number of element swaps performed is provably adaptive with respect to the measure Inv. More precisely, we prove that randomized Quicksort performs expected O(n (1 + log (1 + Inv/n))) element swaps, where Inv denotes the number of inversions in the input sequence. This result provides a theoretical explanation for the observed behavior, and gives new insights on the behavior of the Quicksort algorithm. We also give some empirical results on the adaptive behavior of Heapsort and Mergesort.
From Reduction-Based to Reduction-Free Normalization
Authors: Danvy Olivier
Published: February 2016

We present a systematic construction of a reduction-free normalization function. Starting from a reduction-based normalization function, i.e., the transitive closure of a one-step reduction function, we successively subject it to refocusing (i.e., deforestation of the intermediate reduced terms), simplification (i.e., fusing auxiliary functions), refunctionalization (i.e., Church encoding), and direct-style transformation (i.e., the converse of the CPS transformation). We consider two simple examples and treat them in detail: for the first one, arithmetic expressions, we construct an evaluation function; for the second one, terms in the free monoid, we construct an accumulator-based flatten function. The resulting two functions are traditional reduction-free normalization functions.

The construction builds on previous work on refocusing and on a functional correspondence between evaluators and abstract machines. It is also reversible.
Strongly Uniform Bounds from Semi-Constructive Proofs
Authors: Gerhardy Philipp , Kohlenbach Ulrich
Published: February 2016

In 2003, the second author obtained metatheorems for the extraction of effective (uniform) bounds from classical, prima facie non-constructive proofs in functional analysis. These metatheorems for the first time cover general classes of structures like arbitrary metric, hyperbolic, CAT(0) and normed linear spaces and guarantee the independence of the bounds from parameters raging over metrically bounded (not necessarily compact!) spaces. The use of classical logic imposes some severe restrictions on the formulas and proofs for which the extraction can be carried out. In this paper we consider similar metatheorems for semi-intuitionistic proofs, i.e. proofs in an intuitionistic setting enriched with certain non-constructive principles. Contrary to the classical case, there are practically no restrictions on the logical complexity of theorems for which bounds can be extracted. Again, our metatheorems guarantee very general uniformities, even in cases where the existence of uniform bounds is not obtainable by (ineffective) straightforward functional analytic means. Already in the purely intuitionistic case, where the existence of effective bounds is implicit, the metatheorems allow one to derive uniformities that may not be obvious at all from a given constructive proofs. Finally, we illustrate our main metatheorem by an example from metric fixed point theory.
The Design Space of Type Checkers for XML Transformation Languages
Authors: Møller Anders , Schwartzbach Michael I.
Published: February 2016

We survey work on statically type checking XML transformations, covering a wide range of notations and ambitions. The concept of type may vary from idealizations of DTD to full-blown XML Schema or even more expressive formalisms. The notion of transformation may vary from clean and simple transductions to domain-specific languages or integration of XML in general-purpose programming languages. Type annotations can be either explicit or implicit, and type checking ranges from exact decidability to pragmatic approximations.

We characterize and evaluate existing tools in this design space, including a recent result of the authors providing practical type checking of full unannotated XSLT 1.0 stylesheets given general DTDs that describe the input and output languages.
Fast Partial Evaluation of Pattern Matching in Strings
Authors: Ager Mads Sig , Danvy Olivier , Rohde Henning Korsholm
Published: February 2016

We show how to obtain all of Knuth, Morris, and Pratt's linear-time string matcher by specializing a quadratic-time string matcher with respect to a pattern string. Although it has been known for 15 years how to obtain this linear matcher by partial evaluation of a quadratic one, how to obtain it in linear time has remained an open problem.

 Obtaining a linear matcher by partial evaluation of a quadratic one is achieved by performing its backtracking at specialization time and memoizing its results. We show (1) how to rewrite the source matcher such that its static intermediate computations can be shared at specialization time and (2) how to extend the memoization capabilities of a partial evaluator to static functions. Such an extended partial evaluator, if its memoization is implemented efficiently, specializes the rewritten source matcher in linear time.

Finally, we show that the method also applies to a variant of Boyer and Moore's string matcher.

Supersedes BRICS-RS-03-11 and BRICS-RS-03-20.
On Reducing a System of Equations to a Single Equation
Authors: Frandsen Gudmund Skovbjerg , Shparlinski Igor E.
Published: February 2016

For a system of polynomial equations over Q_p we present an efficient construction of a single polynomial of quite small degree whose zero set over Q_p coincides with the zero set over Q_p of the original system. We also show that the polynomial has some other attractive features such as low additive and straight-line complexity.

 The proof is based on a link established here between the above problem and some recent number theoretic result about zeros of p-adic forms.
Program Extraction from Proofs of Weak Head Normalization
Authors: Biernacka Malgorzata , Danvy Olivier , Støvring Kristian
Published: February 2016

We formalize two proofs of weak head normalization for the simply typed lambda-calculus in first-order minimal logic: one for normal-order reduction, and one for applicative-order reduction in the object language. Subsequently we use Kreisel's modified realizability to extract evaluation algorithms from the proofs, following Berger; the proofs are based on Tait-style reducibility predicates, and hence the extracted algorithms are instances of (weak head) normalization by evaluation, as already identified by Coquand and Dybjer.
A Dynamic Continuation-Passing Style for Dynamic Delimited Continuations
Authors: Biernacki Dariusz , Danvy Olivier , Millikin Kevin
Published: February 2016

We present a new abstract machine that accounts for dynamic delimited continuations. We prove the correctness of this new abstract machine with respect to a pre-existing, definitional abstract machine. Unlike this definitional abstract machine, the new abstract machine is in defunctionalized form, which makes it possible to state the corresponding higher-order evaluator. This evaluator is in continuation+state passing style and threads a trail of delimited continuations and a meta-continuation. Since this style accounts for dynamic delimited continuations, we refer to it as `dynamic continuation-passing style.'

 We show that the new machine operates more efficiently than the definitional one and that the notion of computation induced by the corresponding evaluator takes the form of a monad. We also present new examples and a new simulation of dynamic delimited continuations in terms of static ones.
A Quantum Cipher with Near Optimal Key-Recycling
Authors: Damgård Ivan B. , Pedersen Thomas B. , Salvail Louis
Published: February 2016

Assuming an insecure quantum channel and an authenticated classical channel, we propose an unconditionally secure scheme for encrypting classical messages under a shared key, where attempts to eavesdrop the ciphertext can be detected. If no eavesdropping is detected, we can securely re-use the entire key for encrypting new messages. If eavesdropping is detected, we must discard a number of key bits corresponding to the length of the message, but can re-use almost all of the rest. We show this is essentially optimal. Thus, provided the adversary does not interfere (too much) with the quantum channel, we can securely send an arbitrary number of message bits, independently of the length of the initial key. Moreover, the key-recycling mechanism only requires one-bit feedback. While ordinary quantum key distribution with a classical one time pad could be used instead to obtain a similar functionality, this would need more rounds of interaction and more communication.
Cryptography in the Bounded Quantum Storage Model
Authors: Damgård Ivan B. , Fehr Serge , Salvail Louis , Schaffner Christian
Published: February 2016

We initiate the study of two-party cryptographic primitives with unconditional security, assuming that the adversary's  quantum memory is of bounded size. We show that oblivious transfer and bit commitment can be implemented in this model using protocols where honest parties need no quantum memory, whereas an adversarial player needs quantum memory of size at least n/2 in order to break the protocol, where n is the number of qubits transmitted. This is in sharp contrast to the classical bounded-memory model, where we can only tolerate adversaries with memory of size quadratic in honest players' memory size. Our protocols are efficient, non-interactive and can be implemented using today's technology. On the technical side, a new entropic uncertainty relation involving min-entropy is established.
A Syntactic Correspondence between Context-Sensitive Calculi and Abstract Machines
Authors: Biernacka Malgorzata , Danvy Olivier
Published: February 2016

We present a systematic construction of environment-based abstract machines from context-sensitive calculi of explicit substitutions, and we illustrate it with a series of calculi and machines: Krivine's machine with call/cc, the lambda-mu-calculus, delimited continuations, i/o, stack inspection, proper tail-recursion, and lazy evaluation. Most of the machines already exist but have been obtained independently and are only indirectly related to the corresponding calculi. All of the calculi are new and they make it possible to directly reason about the execution of the corresponding machines. In connection with the functional correspondence between evaluation functions and abstract machines initiated by Reynolds, the present syntactic correspondence makes it possible to construct reduction-free normalization functions out of reduction-based ones, which was an open problem in the area of normalization by evaluation.
A Simple Proof of a Folklore Theorem about Delimited Control
Authors: Biernacki Dariusz , Danvy Olivier
Published: February 2016

We formalize and prove the folklore theorem that the static delimited-control operators shift and reset can be simulated in terms of the dynamic delimited-control operators control and prompt. The proof is based on small-step operational semantics.
On Obtaining the Boyer-Moore String-Matching Algorithm by Partial Evaluation
Authors: Danvy Olivier , Rohde Henning Korsholm
Published: February 2016

We present the first derivation of the search phase of the Boyer-Moore string-matching algorithm by partial evaluation of an inefficient string matcher. The derivation hinges on identifying the bad-character-shift heuristic as a binding-time improvement, bounded static variation. An inefficient string matcher incorporating this binding-time improvement specializes into the search phase of the Horspool algorithm, which is a simplified variant of the Boyer-Moore algorithm. Combining the bad-character-shift binding-time improvement with our previous results yields a new binding-time-improved string matcher that specializes into the search phase of the Boyer-Moore algorithm.
Bisimilarity is not Finitely Based over BPA with Interrupt
Authors: Aceto Luca , Fokkink Willem Jan , Ingólfsdóttir Anna , Nain Sumit
Published: February 2016

This paper shows that bisimulation equivalence does not afford a finite equational axiomatization over the language obtained by enriching Bergstra and Klop's Basic Process Algebra with the interrupt operator. Moreover, it is shown that the collection of closed equations over this language is also not finitely based. In sharp contrast to these results, the collection of closed equations over the language BPA enriched with the disrupt operator is proven to be finitely based.