bluuebunny/crossref_metadata_2025 huggingface dataset:
Retrieval of xCO2 from ground-based mid-infrared (NDACC) solar absorption spectra and comparison to TCCON
Authors: Buschmann Matthias , Deutscher Nicholas M. , Sherlock Vanessa , Palm Mathias , Warneke Thorsten , Notholt Justus
Published: February 2016

Abstract. High-resolution solar absorption spectra, taken within the Network for the Detection of Atmospheric Composition Change Infrared Working Group (NDACC-IRWG) in the mid-infrared spectral region, are used to infer partial or total column abundances of many gases. In this paper we present the retrieval of a column-averaged mole fraction of carbon dioxide from NDACC-IRWG spectra taken with a Fourier transform infrared (FTIR) spectrometer at the site in Ny-Ålesund, Spitsbergen. The retrieved time series is compared to colocated standard TCCON (Total Carbon Column Observing Network) measurements of column-averaged dry-air mole fractions of CO2 (denoted by xCO2). Comparing the NDACC and TCCON retrievals, we find that the sensitivity of the NDACC retrieval is lower in the troposphere (by a factor of 2) and higher in the stratosphere, compared to TCCON. Thus, the NDACC retrieval is less sensitive to tropospheric changes (e.g., the seasonal cycle) in the column average.
Temporal variation in carbon and nitrogen sequestration rates in boreal soils across a variety of ecosystems
Authors: Manies K. L. , Harden J. W. , Fuller C. C. , Turetsky M. R.
Published: February 2016

Abstract. Boreal soils play a critical role in the global carbon (C) cycle; therefore, it is important to understand the mechanisms that control soil C accumulation and loss for this region. Examining C & nitrogen (N) accumulation rates averaged over decades to centuries may provide additional understanding of the dominant mechanisms for their storage, which can be masked by seasonal and interannual variability when investigated over the short-term. We examined longer-term accumulation rates, using 210Pb and 14C to date soil layers, for a wide variety of boreal ecosystems: a black spruce forest, a shrub ecosystem, a tussock grass ecosystem, a sedge dominated ecosystem, and a rich fen. All ecosystems had similar decadal C accumulation rates, averaging 84 ± 42 gC m−2 yr−1. Long-term (century) C accumulation rates were slower than decadal rates, averaging 14 ± 5 gC m−2 yr−1 for all ecosystems except the rich fen, for which the long-term C accumulation rates was more similar to decadal rates (44 ± 5 gC m−2 yr−1 and 76 ± 9 gC m−2 yr−1, respectively). The rich fen also had significantly higher long-term N accumulation rates (2.66 gN m−2 yr−1). The lowest N accumulation rate, on both a decadal and long-term basis, was found in the black spruce forest (0.22 and 1.4 gN m−2 yr−1, respectively). Our results suggest that long-term C and N cycling at the rich fen is fundamentally different from the other ecosystems, likely due to differences in the predominant mechanisms for nutrient cycling (for C) and reduced amounts of disturbance by fire (for C & N). This result implies that most shifts in ecosystem vegetation across the boreal region, driven by either climate or succession, will not significantly impact regional C or N dynamics over years to decades. However, ecosystem transitions to or from a rich fen will promote significant shifts in soil C and N storage.
Spatial and temporal variations in plant Water Use Efficiency inferred from tree-ring, eddy covariance and atmospheric observations
Authors: Groenendijk Margriet , Cox Peter M. , Booth Ben B. B. , Dekker Stefan C. , Huntingford Chris
Published: February 2016

Abstract. Plant Water Use Efficiency (WUE), which is the ratio of the uptake of carbon dioxide through photosynthesis to the loss of water through transpiration, is a very useful metric of the functioning of the land biosphere. WUE is expected to increase with atmospheric CO2, but to decline with increasing atmospheric evaporative demand – which can arise from increases in near-surface temperature or decreases in relative humidity. We have used Δ13C measurements from tree-rings, along with eddy-covariance measurements from Fluxnet sites, to estimate the sensitivities of WUE to changes in CO2 and atmospheric humidity deficit. This enables us to reconstruct fractional changes in WUE, based on changes in atmospheric climate and CO2, for the entire period of the instrumental global climate record. We estimate that overall WUE increased from 1900 to 2010 by 48 ± 22 %, which is more than double that simulated by the latest Earth System Models. This long-term trend is largely driven by increases in CO2, but significant inter-annual variability and regional differences are evident due to variations in temperature and relative humidity. There are several highly populated regions, such as Western Europe and East Asia, where the rate of increase of WUE has declined sharply in the last two decades.
Embedding TQM in UAE translation organizations
Authors: Alhashmi Mariam
Published: February 2016

Although there is a long tradition of active translation work in the Arab world, some see a need to make improvements. The number of translation projects in the region has grown exponentially in recent years, with a notable increase in translations into Arabic from English, as well as from other languages. Achieving high quality translations continues to require high levels of linguistic and cultural competence from translation professionals; however, new forms of management are required in the context of technological change, computerization, increased specialization and complexity in the process of translation. The practice of translating has therefore become a corporate rather than an individual task, and is often performed in the form of projects within specialized translation and publishing organizations. This research addresses a gap in research in this field, relating to the evaluation of quality management of English to Arabic translation projects, and to the relative neglect of Total Quality Management (TQM) and associated tools in the management of translation projects as relevant means to improve processes in this field. This paper explores English to Arabic translation projects in the United Arab Emirates and puts forward a specific framework for implementing TQM in translation project organizations, including suggested key quality indicators and key performance indicators.
Mapping the Gulfs of translation studies
Authors: Basalamah Salah
Published: February 2016

This paper is concerned with an evaluative overview of Translation Studies (TS) as a rapidly growing interdiscipline through the different attempts to map it. Its main preoccupation is first to examine the trends of some contemporary research in Translation Studies and describe the growing fragmentation it is undergoing. Second and as a matter of consequence, it will also overview some teaching trends by looking at some of the most favored streams of specializations at the postgraduate levels using examples from universities in North America and the Gulf. This will finally allow the author to assess the extent and impact of the mutual distances and ignorance these subfields may encounter within the same discipline, namely through a comparison with sociology, and the way it has established the subfield of metasociology and how this experience could extend to TS.
Divergence of the Populations of Yellow Wagtail Motacilla flaval Linnaeus, 1758, And Citrine Wagtail Motacilla citreola Pallas, 1776, (Motacillidae, Passeriformes) in Middle Volga Region of Russia
Authors: Artemieva E.A. , Mishchenko A.V. , Makarov D.K.
Published: February 2016

Blood samples of so-called “yellow” wagtails collected in geographical areas of Middle Volga breeding populations of these species were studied. After mtDNA isolation barcoding of studied species of "yellow" wagtails was performed. Site of gene cytochromec-oxidase I was amplified. This gene was used as a genetic marker for the comparison of obtained samples. After sequencing and sequence alignment of gene cytochrome c-oxidase I, based on the comparison of genetic distances between specimens of the studied species using Jalview software, phylogenetic trees of populations of species Motacilla flava L. and Motacilla citreola Pall. were constructed.
Diversity and dynamics of populations of mites in nectarine trees (Prunus persica var. nucipersica) (Rosaceae)
Authors: Baldo Fernando Berton , Raga Adalton , Mineiro Jeferson Luiz de Carvalho , Castro Jairo Lopez de
Published: February 2016

The international literature does not provide much information about the incidence of species of mites in nectarine cultivars. The purpose of the present study was to determine diversity and dynamics of populations of mites and their interactions in different nectarine cultivars in the southwestern region of the State of São Paulo, Brazil. These mites were split into 15 families, 22 genders and 28 species. Aculus fockeui (Nalepa & Trouessant) (Eriophyidae) was the most abundant species, with 90.2 % of the mites collected. The populations of A. fockeui displayed specific periods with greater number of individuals. Phytoseiidae showed the highest richness of species. Ricoseius loxocheles (De Leon) and Euseius ho (De Leon) were the most abundant predators. Euseius ho population showed a positive correlation with rainfall.
Atypical dermoscopic presentation of an acral congenital melanocytic nevus in an adult: parallel ridge pattern and its histologic correlation
Authors: Roldan-Marin Rodrigo , González-de-Cossío-Hernández Ana Cecilia , Lammoglia-Ordiales Lorena , Martínez-Luna Eduwiges , Toussaint-Caire Sonia , Ferrara Gerardo
Published: February 2016

Acral melanoma is the most frequent subtype in Asian and Mexican mestizo population. Dermoscopy is a noninvasive diagnostic technique that helps the differential diagnosis of pigmented skin lesions on acral volar skin.
We herein present a case of acral congenital melanocytic nevus with a parallel ridge dermoscopic pattern. Since the parallel ridge pattern in a melanocytic lesion of the acral skin is classically ascribed to melanoma, the present case can be definitely labeled as ‘atypical’ and worth of being elucidated in its histopathological correlates.
Parallel-ridge pattern on dermatoscopy: observation in a case of purpura traumatica pedis
Authors: Feci Luca , Fimiani Michele , Rubegni Pietro
Published: February 2016

Dermatologists are often referred urgent cases of acral hematoma by general practitioners and sports medicine specialists for the purpose of excluding warts, nevi or melanoma. Acral hematoma is often a cause of anxiety to patients and their families. Here, we report a case of purpura traumatica pedis, referred to us as suspected plantar melanoma because of the finding of parallel-ridge pattern on dermatoscopic examination. To avoid unnecessary and costly procedures, doctors should inquire about any episode of physical exertion before the onset of purpura, recording the lesion’s anatomic site (e.g., unilateral vs. bilateral involvement) and clinical features.
Pale halo surrounding a homogenous bluish-purplish central area: dermoscopic clue for eccrine hidrocystoma
Authors: Duman Nilay , Duman Deniz , Sahin Sedef
Published: February 2016

Abstract

Eccrine hidrocystomas are benign tumors of the sweat glands that arise from cystic dilatation of the excretory sweat duct. Exact diagnosis requires biopsy and histopathologic examination, from which arises risk of scarring. Dermoscopy could be a useful tool in diagnosing eccrine hidrocystomas. Herein we aim to present dermoscopic features in three female patients with multiple lesions on the face consistent with eccrine hidrocystomas.
Valoración del riesgo de caries infantil en un servicio hospitalario de urgencias
Authors: Crovetto Martínez Rafael , Ortuzar Otxoa Leyre , Martinez Rodriguez Adelina , Fernández Alonso Julia , Escobar-Martínez Antonio
Published: February 2016

La caries es una destrucción de los tejidos mineralizados del diente, siendo la enfermedad crónica más prevalente del  niño.  

Objetivos: Determinar, mediante un estudio de enfermería, la prevalencia de riesgo de caries en los niños que acuden a un Servicio de Urgencias Hospitalarias.  

Método:  Aplicación del formulario validado para la evaluación de riesgo de caries propuesto por la Sociedad Americana de Odontopediatría,  con 14 ítems para niños de más de 7 años y 13 ítems  en menores de esa edad.  La aplicación de dicho formulario ha contemplado la caducidad de la dentición temporal en relación a la edad del niño estudiado.  

Resultados: El formulario se ha completado en 101 niños. El 72.7% de los niños menores de 7 años  y el 89.1% de los mayores de 7 años presentan uno o más factores de alto riesgo para caries infantil, existiendo diferencias notables en los resultados, en función del origen de los niños o de su etnia. Los peores resultados los ofrecen los niños gitanos cuyo riesgo de caries es el 100% en grupos de cualquier edad.  

Conclusiones: Hemos determinado mediante un  estudio de enfermería, la prevalencia de riesgo  de caries infantil. La Enfermería española puede y debe asumir un papel activo en la promoción de la salud oral infantil, aplicando activamente sus conocimientos
Conocimientos y actitudes sobre sexualidad en adolescentes de primer curso de Grado en Educación Infantil y Primaria de la Universidad de Jaén
Authors: Rodríguez Mármol María , Muñoz Cruz Rafael , Sánchez Muñoz Inés
Published: February 2016

Objetivo: Conocer los conocimientos y actitudes sobre sexualidad en los adolescentes de primero de Grado en Educación de la Universidad de Jaén.

Material y Método: Los datos se recogieron a través de un cuestionario anónimo, voluntario y autocumplimentado, el cual se aplicó a una muestra no probabilística por conveniencia de 151 sujetos estudiantes de primer curso de Grado en Educación Infantil y Primaria de la Universidad de Jaén.

Resultados: 118 manifiestan haber mantenido relaciones sexuales con penetración, siendo estas diferencias significativas entre chicas y chicos (p=.034), al igual que para la masturbación en cuanto al sexo (96% de los hombres frente a 19% de las mujeres). También son las mujeres las que practican más el fellatio (p=.031), pero estas prácticas sexuales las realizan con la pareja (p=.01), siendo los chicos los que presentan mayor consumo de alcohol previo al coito (p=.021) y mayor número de parejas sexuales (p=.026). Siguen siendo ellas las que identifican en mayor proporción el papiloma como ITS (p=.02). Y el 27,7% del total conocen el doble método anticonceptivo.

Conclusión: Tres cuartas partes de la muestra han mantenido relaciones coitales haciendo uso de anticonceptivos para evitar el embarazo. Valorando esto junto con un escaso conocimiento del doble método (una cuarta parte del total) y de las infecciones de transmisión sexual, nos lleva a pensar como materia necesaria la educación sexual para estos adolescentes.
Competencias y entorno clinico de aprendizaje en enfermería: autopercepcion de estudiantes avanzados de Uruguay
Authors: De Souza Cruz María Cecilia , Mariscal Crespo Maria Isabel
Published: February 2016

Objetivo: El objetivo del presente trabajo fue describir la percepción del nivel de competencias en relación con el entorno de aprendizaje práctico, por estudiantes de enfermería de Uruguay.

Material y Métodos: Se realizó un estudio observacional, descriptivo, transversal interviniendo 33 estudiantes del último ciclo de Facultad de Enfermería de  Universidad de la República y Universidad Católica del Uruguay. Los datos se recolectaron en el año 2013 utilizando dos instrumentos previamente validados, el Nurse Competence Scale y el Practice Environment Scale-Nursing Work Index.

Resultados: El nivel global de competencias percibido por los estudiantes es Muy Bueno (76.97; VAS: 0-100). La dimensión autoevaluada como más alta fue Rol de Trabajo. La frecuencia de utilización de competencias se ubicó en su mayoría (84.8%) entre utilizadas “muy a menudo” y “ocasionalmente”. El entorno se evaluó mayormente como no favorable (54.5% en desacuerdo). No se pudo establecer relación entre competencias y entorno para la muestra estudiada.

Conclusiones: Los estudiantes avanzados tienen un muy buen nivel de competencias. La autoevaluación, a través de instrumentos como el NCS, es una herramienta fundamental para la evaluación de las competencias alcanzadas. Es imprescindible continuar investigando acerca del entorno y otros factores que puedan influir en las competencias
A Functional Correspondence between Evaluators and Abstract Machines
Authors: Ager Mads Sig , Biernacki Dariusz , Danvy Olivier , Midtgaard Jan
Published: February 2016

We bridge the gap between functional evaluators and abstract machines for the lambda-calculus, using closure conversion, transformation into continuation-passing style, and defunctionalization of continuations.

We illustrate this bridge by deriving Krivine's abstract machine from an ordinary call-by-name evaluator and by deriving an ordinary call-by-value evaluator from Felleisen et al.'s CEK machine. The first derivation is strikingly simpler than what can be found in the literature. The second one is new. Together, they show that Krivine's abstract machine and the CEK machine correspond to the call-by-name and call-by-value facets of an ordinary evaluator for the lambda-calculus.

 We then reveal the denotational content of Hannan and Miller's CLS machine and of Landin's SECD machine. We formally compare the corresponding evaluators and we illustrate some relative degrees of freedom in the design spaces of evaluators and of abstract machines for the lambda-calculus with computational effects.

For the purpose of this work, we distinguish between virtual machines, which have an instruction set, and abstract machines, which do not. The Categorical Abstract Machine, for example, has an instruction set, but Krivine's machine, the CEK machine, the CLS machine, and the SECD machine do not; they directly operate on lambda-terms instead. We present the abstract machine that corresponds to the Categorical Abstract Machine.
Syntactic Formats for Free: An Abstract Approach to Process Equivalence
Authors: Klin Bartek , Sobocinski Pawel
Published: February 2016

A framework of Plotkin and Turis, originally aimed at providing an abstract notion of bisimulation, is modified to cover other operational equivalences and preorders. Combined with bialgebraic methods, it yields a technique for deriving syntactic formats for transition system specifications, which guarantee operational preorders to be precongruences. The technique is applied to the trace prorder, the completed trace preorder and the failures preorder. In the latter two cases, new syntactic formats guaranteeing precongruence properties are introduced.
Scalable Key-Escrow
Authors: Damgård Ivan B. , Jurik Mads J.
Published: February 2016

We propose a cryptosystem that has an inherent key escrow mechanism. This leads us to propose a session based public verifiable key escrow system that greatly improves the amount of key material the escrow servers have to keep in order to decrypt an encryption. In our scheme the servers will only have a single secret sharing, as opposed to a single key from every escrowed player. This is done while still having the properties: 1) public verifiable: the user proves to everyone that the encryption can indeed be escrowed, and 2) no secret leakage: no matter how many decryptions a law enforcement agency is presented, it will gain no more information on the users private key, than it couldn't have calculated itself.
A Runtime System for XML Transformations in Java
Authors: Christensen Aske Simon , Kirkegaard Christian , Møller Anders
Published: February 2016

We show that it is possible to extend a general-purpose programming language with a convenient high-level data-type for manipulating XML documents while permitting (1) precise static analysis for guaranteeing validity of the constructed XML documents relative to the given DTD schemas, and (2) a runtime system where the operations can be performed efficiently. The system, named XACT, is based on a notion of immutable XML templates and uses XPath for deconstructing documents. A companion paper presents the program analysis; this paper focuses on the efficient runtime representation.
On the Computational Collapse of Quantum Information
Authors: Crépeau Claude , Dumais Paul , Mayers Dominic , Salvail Louis
Published: February 2016

We analyze the situation where computationally binding string commitment schemes are used to force the receiver of a BB84 encoding of a classical bitstring to measure upon reception. Since measuring induces an irreversible collapse to the received quantum state, even given extra information after the measurement does not allow the receiver to evaluate reliably some predicates apply to the classical bits encoded in the state. This fundamental quantum primitive is called quantum measure commitment (QMC) and allows for secure two-party computation of classical functions. An adversary to QMC is one that can both provide valid proof of having measured the received states while still able to evaluate a predicate applied to the classical content of the encoding. We give the first quantum black-box reduction for the security of QMC to the binding property of the string commitment. We characterize a class of quantum adversaries against QMC that can be transformed into adversaries against a weak form for the binding property of the string commitment. Our result provides a construction for 1--2-oblivious transfer that is computationally secure against the receiver and unconditionally secure against the sender from any string commitment scheme satisfying a weak binding property.
New Algorithms for Exact Satisfiability
Authors: Byskov Jesper Makholm , Madsen Bolette Ammitzbøll , Skjernaa Bjarke
Published: February 2016

The Exact Satisfiability problem is to determine if a CNF-formula has a truth assignment satisfying exactly one literal in each clause; Exact 3-Satisfiability is the version in which each clause contains at most three literals. In this paper, we present algorithms for Exact Satisfiability and Exact 3-Satisfiability running in time O(2^{0.2325n}) and O(2^{0.1379n}), respectively. The previously best algorithms have running times O(2^{0.2441n}) for Exact Satisfiability (Monien, Speckenmeyer and Vornberger (1981)) and O(2^{0.1626n}) for Exact 3-Satisfiability (Kulikov and independently Porschen, Randerath and Speckenmeyer (2002)). We extend the case analyses of these papers and observe, that a formula not satisfying any of our cases has a small number of variables, for which we can try all possible truth assignments and for each such assignment solve the remaining part of the formula in polynomial time.
Adhesive Categories
Authors: Lack Stephen , Sobocinski Pawel
Published: February 2016

We introduce adhesive categories, which are categories with structure ensuring that pushouts along monomorphisms are well-behaved. Many types of graphical structures used in computer science are shown to be examples of adhesive categories. Double-pushout graph rewriting generalises well to rewriting on arbitrary adhesive categories.
The Role of Quantifier Alternations in Cut Elimination
Authors: Gerhardy Philipp
Published: February 2016

Extending previous results from the author's master's thesis, subsequently published in the proceedings of CSL 2003, on the complexity of cut elimination for the sequent calculus LK, we discuss the role of quantifier alternations and develop a measure to describe the complexity of cut elimination in terms of quantifier alternations in cut formulas and contractions on such formulas.
Recursive Ping-Pong Protocols
Authors: Hüttel Hans , Srba Jirí
Published: February 2016

This paper introduces a process calculus with recursion which allows us to express an unbounded number of runs of the ping-pong protocols introduced by Dolev and Yao. We study the decidability issues associated with two common approaches to checking security properties, namely reachability analysis and bisimulation checking. Our main result is that our channel-free and memory-less calculus is Turing powerful, assuming that at least three principals are involved. We also investigate the expressive power of the calculus in the case of two participants. Here, our main results are that reachability and, under certain conditions, also strong bisimilarity become decidable.
Danfoss EKC Trial Project Deliverables
Authors: Larsen Kim G. , Larsen Ulrik , Nielsen Brian , Skou Arne , Wasowski Andrzej
Published: February 2016

This report documents the results of the Danfoss EKC trial project on model based development using IAR visualState. We present a formal state-model of a refrigeration controller based on a specification given by Danfoss. We report results on modeling, verification, simulation, and code-generation. It is found that the IAR visualState is a promising tool for this application domain, but that improvements must be done to code-generation and automatic test generation.
A Two-Layer Approach to the Computability and Complexity of Real Numbers
Authors: Lambov Branimir
Published: February 2016

We present a new approach to computability of real numbers in which real functions have type-1 representations, which also includes the ability to reason about the complexity of real numbers and functions. We discuss how this allows efficient implementations of exact real numbers and also present a new real number system that is based on it.
Bounds on Iterations of Asymptotically Quasi-Nonexpansive Mappings
Authors: Kohlenbach Ulrich , Lambov Branimir
Published: February 2016

This paper establishes explicit quantitative bounds on the computation of approximate fixed points of asymptotically (quasi-) nonexpansive mappings f by means of iterative processes. Here f is a selfmapping of a convex subset C of a uniformly convex normed space X. We consider general Krasnoselski-Mann iterations with and without error terms. As a consequence of our quantitative analysis we also get new qualitative results which show that the assumption on the existence of fixed points of f can be replaced by the existence of approximate fixed points only. We explain how the existence of effective uniform bounds in this context can be inferred already a-priorily by a logical metatheorem recently proved by the first author. Our bounds were in fact found with the help of the general logical machinery behind the proof of this metatheorem. The proofs we present here are, however, completely self-contained and do not require any tools from logic.
Congruences for Contextual Graph-Rewriting
Authors: Sassone Vladimiro , Sobocinski Pawel
Published: February 2016

We introduce a comprehensive operational semantic theory of graph rewriting. The central idea is recasting rewriting frameworks as Leifer and Milner's reactive systems. Consequently, graph rewriting systems are associated with canonical labelled transition systems, on which bisimulation equivalence is a congruence with respect to arbitrary graph contexts (cospans of graphs). This construction is derived from a more general theorem of much wider applicability. Expressed in abstract categorical terms, the central technical contribution of the paper is the construction of groupoidal relative pushouts, introduced and developed by the authors in recent work, in suitable cospan categories over arbitrary adhesive categories. As a consequence, we both generalise and shed light on rewriting via borrowed contexts due to Ehrig and König.
An Algorithm for Exact Satisfiability Analysed with the Number of Clauses as Parameter
Authors: Madsen Bolette Ammitzbøll
Published: February 2016

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of poly(L) . m!, where m is the number of clauses and L is the length of the formula. Skjernaa has given an algorithm for Exact Satisfiability with time bound poly(L) . 2^m but using exponential space. We leave the following problem open: Is there an algorithm for Exact Satisfiability using only polynomial space with a time bound of c^m, where c is a constant and m is the number of clauses?
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.
Refocusing in Reduction Semantics
Authors: Danvy Olivier , Nielsen Lasse R.
Published: February 2016

The evaluation function of a reduction semantics (i.e., a small-step operational semantics with an explicit representation of the reduction context) is canonically defined as the transitive closure of (1) decomposing a term into a reduction context and a redex, (2) contracting this redex, and (3) plugging the contractum in the context. Directly implementing this evaluation function therefore yields an interpreter with a worst-case overhead, for each step, that is linear in the size of the input term.

We present sufficient conditions over the constituents of a reduction semantics to circumvent this overhead, by replacing the composition of (3) plugging and (1) decomposing by a single ``refocus'' function mapping a contractum and a context into a new context and a new redex, if any. We also show how to construct such a refocus function, we prove the correctness of this construction, and we analyze the complexity of the resulting refocus function.

The refocused evaluation function of a reduction semantics implements the transitive closure of the refocus function, i.e., a ``pre-abstract machine.'' Fusing the refocus function with the trampoline function computing the transitive closure gives a state-transition function, i.e., an abstract machine. This abstract machine clearly separates between the transitions implementing the congruence rules of the reduction semantics and the transitions implementing its reduction rules. The construction of a refocus function therefore shows how to mechanically obtain an abstract machine out of a reduction semantics, which was done previously on a case-by-case basis.

We illustrate refocusing by mechanically constructing Felleisen et al.'s CK machine from a call-by-value reduction semantics of the lambda-calculus, and by constructing a substitution-based version of Krivine's machine from a call-by-name reduction semantics of the lambda-calculus. We also mechanically construct three one-pass CPS transformers from three quadratic context-based CPS transformers for the lambda-calculus.
Constructive Action Semantics for Core ML
Authors: Iversen Jørgen , Mosses Peter D.
Published: February 2016

Usually, the majority of language constructs found in a programming language can also be found in many other languages, because language design is based on reuse. This should be reflected in the way we give semantics to programming languages. It can be achieved by making a language description consist of a collection of modules, each defining a single language construct. The description of a single language construct should be language independent, so that it can be reused in other descriptions without any changes. We call a language description framework ``constructive'' when it supports independent description of individual constructs.

We present a case study in constructive semantic description. The case study is a description of Core ML, consisting of a mapping from it to BAS (Basic Abstract Syntax) and action semantic descriptions of the individual BAS constructs. The latter are written in ASDF (Action Semantics Definition Formalism), a formalism specially designed for writing action semantic descriptions of single language constructs. Tool support is provided by the ASF+SDF Meta-Environment and by the Action Environment, which is a new extension of the ASF+SDF Meta-Environment.
Optimal Strategies in Priced Timed Game Automata
Authors: Bouyer Patricia , Cassez Franck , Fleury Emmanuel , Larsen Kim G.
Published: February 2016

Priced timed (game) automata extends timed (game) automata with costs on both locations and transitions. In this paper we focus on reachability games for priced timed game automata and prove that the optimal cost for winning such a game is computable under conditions concerning the non-zenoness of cost. Under stronger conditions (strictness of constraints) we prove in addition that it is decidable whether there is an optimal strategy in which case an optimal strategy can be computed. Our results extend previous decidability result which requires the underlying game automata to be acyclic. Finally, our results are encoded in a first prototype in HyTech which is applied on a small case-study.
Sur un Exemple de Patrick Greussay
Authors: Danvy Olivier
Published: February 2016

This note was written at the occasion of the retirement of Jean-Francois Perrot at the Universite Pierre et Marie Curie (Paris VI). In an attempt to emulate his academic spirit, we revisit an example proposed by Patrick Greussay in his doctoral thesis: how to verify in sublinear time whether a Calder mobile is well balanced. Rather than divining one solution or another, we derive a spectrum of solutions, starting from the original specification of the problem. We also prove their correctness.
From Interpreter to Logic Engine by Defunctionalization
Authors: Biernacki Dariusz , Danvy Olivier
Published: February 2016

Starting from a continuation-based interpreter for a simple logic programming language, propositional Prolog with cut, we derive the corresponding logic engine in the form of an abstract machine. The derivation originates in previous work (our article at PPDP 2003) where it was applied to the lambda-calculus. The key transformation here is Reynolds's defunctionalization that transforms a tail-recursive, continuation-passing interpreter into a transition system, i.e., an abstract machine. Similar denotational and operational semantics were studied by de Bruin and de Vink (their article at TAPSOFT 1989), and we compare their study with our derivation. Additionally, we present a direct-style interpreter of propositional Prolog expressed with control operators for delimited continuations.
Highly Undecidable Questions for Process Algebras
Authors: Jancar Petr , Srba Jirí
Published: February 2016

We show Sigma^1_1-completeness of weak bisimilarity for PA (process algebra), and of weak simulation preorder/equivalence for PDA (pushdown automata), PA and PN (Petri nets). We also show Pi^1_1-hardness of weak omega-trace equivalence for the (sub)classes BPA (basic process algebra) and BPP (basic parallel processes).
On the Recursive Enumerability of Fixed-Point Combinators
Authors: Goldberg Mayer
Published: February 2016

We show that the set of fixed-point combinators forms a recursively-enumerable subset of a larger set of terms we call non-standard fixed-point combinators. These terms are observationally equivalent to fixed-point combinators in any computable context, but the set of on-standard fixed-point combinators is not recursively enumerable.
On the Dynamic Extent of Delimited Continuations
Authors: Biernacki Dariusz , Danvy Olivier , Shan Chung-chieh
Published: February 2016

We show that breadth-first traversal exploits the difference between the static delimited-control operator `shift' (alias `S') and the dynamic delimited-control operator `control' (alias `F'). For the last 15 years, this difference has been repeatedly mentioned in the literature but it has only been illustrated with one-line toy examples. Breadth-first traversal fills this vacuum.
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.
A Framework for Concrete Reputation-Systems
Authors: Krukow Karl , Nielsen Mogens , Sassone Vladimiro
Published: February 2016

In a reputation-based trust-management system, agents maintain information about the past behaviour of other agents. This information is used to guide future trust-based decisions about interaction. However, while trust management is a component in security decision-making, few existing reputation-based trust-management systems aim to provide any formal security-guarantees. We provide a mathematical framework for a class of simple reputation-based systems. In these systems, decisions about interaction are taken based on policies that are exact requirements on agents' past histories. We present a basic declarative language, based on pure-past linear temporal logic, intended for writing simple policies. While the basic language is reasonably expressive, we extend it to encompass more practical policies, including several known from the literature. A naturally occurring problem becomes how to efficiently re-evaluate a policy when new behavioural information is available. Efficient algorithms for the basic language are presented and analyzed, and we outline algorithms for the extended languages as well.
An Operational Semantics for Trust Policies.
Authors: Krukow Karl
Published: February 2016

In the trust-structure model of trust management, principals specify their trusting relationships with other principals in terms of trust policies. In their paper on trust structures, Carbone et al. present a language for trust policies, and provide a suitable denotational semantics. The semantics ensures that for any collection of trust policies, there is always a unique global trust-state, compatible with all the policies, specifying everyone's degree of trust in everyone else. However, as the authors themselves point out, the language lacks an operational model: the global trust-state is a well-defined mathematical object, but it is not clear how principals can actually compute it. This becomes even more apparent when one considers the intended application environment: vast numbers of autonomous principals, distributed and possibly mobile. We provide a compositional operational semantics for a language of trust policies. The operational semantics is given in terms of a composition of I/O automata. We prove that this semantics is faithful to its corresponding denotational semantics, in the sense that any run of the I/O automaton ``converges to'' the denotational semantics of the policies. Furthermore, as I/O automata are a natural model of asynchronous distributed computation, the semantics leads to an algorithm for distributedly computing the trust-state, which is suitable in the application environment.
Static Validation of XSL Transformations
Authors: Møller Anders , Olesen Mads Østerby , Schwartzbach Michael I.
Published: February 2016

XSL Transformations (XSLT) is a programming language for defining transformations between XML languages. The structure of these languages is formally described by schemas, for example using DTD, which allows individual documents to be validated. However, existing XSLT tools offer no static guarantees that, under the assumption that the input is valid relative to the input schema, the output of the transformation is valid relative to the output schema.

We present a validation technique for XSLT based on the summary graph formalism introduced in the static analysis of JWIG Web services. Being able to provide static guarantees, we can detect a large class of errors in an XSLT stylesheet at the time it is written instead of later when it has been deployed, and thereby provide benefits similar to those of static type checkers for modern programming languages.

Our analysis takes a pragmatic approach that focuses its precision on the essential language features but still handles the entire XSLT 1.0 language. We evaluate the analysis precision on a range of real stylesheets and demonstrate how it may be useful in practice.
On the Static and Dynamic Extents of Delimited Continuations
Authors: Biernacki Dariusz , Danvy Olivier , Shan Chung-chieh
Published: February 2016

We show that breadth-first traversal exploits the difference between the static delimited-control operator shift (alias S) and the dynamic delimited-control operator control (alias F). For the last 15 years, this difference has been repeatedly mentioned in the literature but it has only been illustrated with one-line toy examples. Breadth-first traversal fills this vacuum.

We also point out where static delimited continuations naturally give rise to the notion of control stack whereas dynamic delimited continuations can be made to account for a notion of `control queue.'.
Denotational Aspects of Untyped Normalization by Evaluation
Authors: Filinski Andrzej , Rohde Henning Korsholm
Published: February 2016

We show that the standard normalization-by-evaluation construction for the simply-typed lambda_{beta eta}-calculus has a natural counterpart for the untyped lambda_beta-calculus, with the central type-indexed logical relation replaced by a "recursively defined'' invariant relation, in the style of Pitts. In fact, the construction can be seen as generalizing a computational-adequacy argument for an untyped, call-by-name language to normalization instead of evaluation.

In the untyped setting, not all terms have normal forms, so the normalization function is necessarily partial. We establish its correctness in the senses of soundness (the output term, if any, is in normal form and beta-equivalent to the input term); identification ( beta-equivalent terms are mapped to the same result); and completeness (the function is defined for all terms that do have normal forms). We also show how the semantic construction enables a simple yet formal correctness proof for the normalization algorithm, expressed as a functional program in an ML-like call-by-value language.

Finally, we generalize the construction to produce an infinitary variant of normal forms, namely Böhm trees. We show that the three-part characterization of correctness, as well as the proofs, extend naturally to this generalization.
Static Analysis for Event-Based XML Processing
Authors: Møller Anders
Published: February 2016

Event-based processing of XML data - as exemplified by the popular SAX framework - is a powerful alternative to using W3C's DOM or similar tree-based APIs. The event-based approach is particularly superior when processing large XML documents in a streaming fashion with minimal memory consumption.

This paper discusses challenges and presents some considerations for creating program analyses for SAX applications. In particular, we consider the problem of statically guaranteeing that a given SAX application always produces only well-formed and valid XML output.
A Rational Deconstruction of Landin's J Operator
Authors: Danvy Olivier , Millikin Kevin
Published: February 2016

Landin's J operator was the first control operator for functional languages, and was specified with an extension of the SECD machine. Through a series of meaning-preserving transformations (transformation into continuation-passing style (CPS) and defunctionalization) and their left inverses (transformation into direct style and refunctionalization), we present a compositional evaluation function corresponding to this extension of the SECD machine. We then characterize the J operator in terms of CPS and in terms of delimited-control operators in the CPS hierarchy. Finally, we present a motivated wish to see Landin's name added to the list of co-discoverers of continuations.
Analyzing Ambiguity of Context-Free Grammars
Authors: Brabrand Claus , Giegerich Robert , Møller Anders
Published: February 2016

It has been known since 1962 that the ambiguity problem for context-free grammars is undecidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures.

We observe that there is a simple linguistic characterization of the grammar ambiguity problem, and we show how to exploit this to conservatively approximate the problem based on local regular approximations and grammar unfoldings. As an application, we consider grammars that occur in RNA analysis in bioinformatics, and we demonstrate that our static analysis of context-free grammars is sufficiently precise and efficient to be practically useful.
The Saga of the Axiomatization of Parallel Composition
Authors: Aceto Luca , Ingólfsdóttir Anna
Published: February 2016

This paper surveys some classic and recent results on the finite axiomatizability of bisimilarity over CCS-like languages. It focuses, in particular, on non-finite axiomatizability results stemming from the semantic interplay between parallel composition and nondeterministic choice. The paper also highlights the role that auxiliary operators, such as Bergstra and Klop's left and communication merge and Hennessy's merge operator, play in the search for a finite, equational axiomatization of parallel composition both for classic process algebras and for their real-time extensions.
Temporal Logics Beyond Regularity
Authors: Lange Martin
Published: February 2016

Non-regular program correctness properties play an important role in the specification of unbounded buffers, recursive procedures, etc. This thesis surveys results about the relative expressive power and complexity of temporal logics which are capable of defining non-regular properties. In particular, it features Propositional Dynamic Logic of Context-Free Programs, Fixpoint Logic with Chop, the Modal Iteration Calculus, and Higher-Order Fixpoint Logic.

Regarding expressive power we consider two classes of structures: arbitrary transition systems as well as finite words as a subclass of the former. The latter is meant to give an intuitive account of the logics' expressive powers by relating them to known language classes defined in terms of grammars or Turing Machines.

 Regarding the computational complexity of temporal logics beyond regularity we focus on their model checking problems since their satisfiability problems are all highly undecidable. Their model checking complexities range between polynomial time and non-elementary.
Control-Flow Analysis of Functional Programs
Authors: Midtgaard Jan
Published: February 2016

We present a survey of control-flow analysis of functional programs, which has been the subject of extensive investigation throughout the past 25 years. Analyses of the control flow of functional programs have been formulated in multiple settings and have led to many different approximations, starting with the seminal works of Jones, Shivers, and Sestoft. In this paper we survey control-flow analysis of functional programs by structuring the multitude of formulations and approximations and comparing them.
Characteristic Formulae: From Automata to Logic
Authors: Aceto Luca , Ingólfsdóttir Anna
Published: February 2016

This paper discusses the classic notion of characteristic formulae for processes using variations on Hennessy-Milner logic as the underlying logical specification language. It is shown how to characterize logically (states of) finite labelled transition systems modulo bisimilarity using a single formula in Hennessy-Milner logic with recursion. Moreover, characteristic formulae for timed automata with respect to timed bisimilarity and the faster-than preorder of Moller and Tofts are offered in terms of the logic L_nu of Laroussinie, Larsen and Weise.