Efficient top-down set-sharing analysis using cliques

Abstract. We study the problem of efficient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a top-down framework. In particular, we define the new abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. We use cliques both as an alternative representation and as widening, defining several widening operators. Our experimental evaluation supports the conclusión that, for inferring set-sharing, as it was the case for inferring pair-sharing, precisión losses are limited, while useful efficieney gains are obtained. We also derive useful conclusions regarding the interactions between thresholds, precisión, efficieney and cost of widening. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.

Two efficient representations for set-sharing analysis in logic programs

Set-Sharing analysis, the classic Jacobs and Langen's domain, has been widely used to infer several interesting properties of programs at compile-time such as occurs-check reduction, automatic parallelization, flnite-tree analysis, etc. However, performing abstract uniflcation over this domain implies the use of a closure operation which makes the number of sharing groups grow exponentially. Much attention has been given in the literature to mitígate this key inefficiency in this otherwise very useful domain. In this paper we present two novel alternative representations for the traditional set-sharing domain, tSH and tNSH. which compress efficiently the number of elements into fewer elements enabling more efficient abstract operations, including abstract uniflcation, without any loss of accuracy. Our experimental evaluation supports that both representations can reduce dramatically the number of sharing groups showing they can be more practical solutions towards scalable set-sharing.

A study of set-sharing analysis via cliques

We study the problem of efñcient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a topdown framework. In particular, we define the abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. Our experimental evaluation supports the conclusión that, for inferring set-sharing, as it was the case for inferring pair-sharing, precisión losses are limited, while useful efñciency gains are obtained. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.

Efficient representations for set-sharing analysis

Abstract is not available.

Precise set sharin analysis for java-style programs (and proofs).

Finding useful sharing information between instances in object- oriented programs has recently been the focus of much research. The applications of such static analysis are multiple: by knowing which variables definitely do not share in memory we can apply conventional compiler optimizations, find coarse-grained parallelism opportunities, or, more importantly, verify certain correctness aspects of programs even in the absence of annotations. In this paper we introduce a framework for deriving precise sharing information based on abstract interpretation for a Java-like language. Our analysis achieves precision in various ways, including supporting multivariance, which allows separating different contexts. We propose a combined Set Sharing + Nullity + Classes domain which captures which instances do not share and which ones are definitively null, and which uses the classes to refine the static information when inheritance is present. The use of a set sharing abstraction allows a more precise representation of the existing sharings and is crucial in achieving precision during interprocedural analysis. Carrying the domains in a combined way facilitates the interaction among them in the presence of multivariance in the analysis. We show through examples and experimentally that both the set sharing part of the domain as well as the combined domain provide more accurate information than previous work based on pair sharing domains, at reasonable cost.

Precise set sharing and nullity analysis for java-style program

Finding useful sharing information between instances in object- oriented programs has been recently the focus of much research. The applications of such static analysis are multiple: by knowing which variables share in memory we can apply conventional compiler optimizations, find coarse-grained parallelism opportunities, or, more importantly,erify certain correctness aspects of programs even in the absence of annotations In this paper we introduce a framework for deriving precise sharing information based on abstract interpretation for a Java-like language. Our analysis achieves precision in various ways. The analysis is multivariant, which allows separating different contexts. We propose a combined Set Sharing + Nullity + Classes domain which captures which instances share and which ones do not or are definitively null, and which uses the classes to refine the static information when inheritance is present. Carrying the domains in a combined way facilitates the interaction among the domains in the presence of mutivariance in the analysis. We show that both the set sharing part of the domain as well as the combined domain provide more accurate information than previous work based on pair sharing domains, at reasonable cost.

Shadow Analysis of Soil Surface Roughness Compared to the Chain Set Method and Direct Measurement of Micro-relief.

Erosion potential and the effects of tillage can be evaluated from quantitative descriptions of soil surface roughness. The present study therefore aimed to fill the need for a reliable, low-cost and convenient method to measure that parameter. Based on the interpretation of micro-topographic shadows, this new procedure is primarily designed for use in the field after tillage. The principle underlying shadow analysis is the direct relationship between soil surface roughness and the shadows cast by soil structures under fixed sunlight conditions. The results obtained with this method were compared to the statistical indexes used to interpret field readings recorded by a pin meter. The tests were conducted on 4-m2 sandy loam and sandy clay loam plots divided into 1-m2 subplots tilled with three different tools: chisel, tiller and roller. The highly significant correlation between the statistical indexes and shadow analysis results obtained in the laboratory as well as in the field for all the soil?tool combinations proved that both variability (CV) and dispersion (SD) are accommodated by the new method. This procedure simplifies the interpretation of soil surface roughness and shortens the time involved in field operations by a factor ranging from 12 to 20.

Lineability of the set of holomorphic mappings with dense range

Let U be an open subset of a separable Banach space. Let F be the collection of all holomorphic mappings f from the open unit disc D � C into U such that f(D) is dense in U. We prove the lineability and density of F in appropriate spaces for diferent choices of U. RESUMEN. Sea U un subconjunto abierto de un espacio de Banach separable. Sea F el conjunto de funciones holomorfas f definidas en el disco unidad D del plano complejo con valores en U tales que f(D) es denso en U. En el artículo se demuestra la lineabilidad y densidad del conjunto F para diferentes elecciones de U.

Image analysis by moment invariants using a set of step-like basis functions

Moment invariants have been thoroughly studied and repeatedly proposed as one of the most powerful tools for 2D shape identification. In this paper a set of such descriptors is proposed, being the basis functions discontinuous in a finite number of points. The goal of using discontinuous functions is to avoid the Gibbs phenomenon, and therefore to yield a better approximation capability for discontinuous signals, as images. Moreover, the proposed set of moments allows the definition of rotation invariants, being this the other main design concern. Translation and scale invariance are achieved by means of standard image normalization. Tests are conducted to evaluate the behavior of these descriptors in noisy environments, where images are corrupted with Gaussian noise up to different SNR values. Results are compared to those obtained using Zernike moments, showing that the proposed descriptor has the same performance in image retrieval tasks in noisy environments, but demanding much less computational power for every stage in the query chain.

Set agreement and the loneliness failure detector in crash-recovery systems

The set agreement problem states that from n proposed values at most n-1 can be decided. Traditionally, this problem is solved using a failure detector in asynchronous systems where processes may crash but not recover, where processes have different identities, and where all processes initially know the membership. In this paper we study the set agreement problem and the weakest failure detector L used to solve it in asynchronous message passing systems where processes may crash and recover, with homonyms (i.e., processes may have equal identities) and without a complete initial knowledge of the membership.

Detecting false testimonies in reputation systems using self-organizing maps

It has been demonstrated that rating trust and reputation of individual nodes is an effective approach in distributed environments in order to improve security, support decision-making and promote node collaboration. Nevertheless, these systems are vulnerable to deliberate false or unfair testimonies. In one scenario, the attackers collude to give negative feedback on the victim in order to lower or destroy its reputation. This attack is known as bad mouthing attack. In another scenario, a number of entities agree to give positive feedback on an entity (often with adversarial intentions). This attack is known as ballot stuffing. Both attack types can significantly deteriorate the performances of the network. The existing solutions for coping with these attacks are mainly concentrated on prevention techniques. In this work, we propose a solution that detects and isolates the abovementioned attackers, impeding them in this way to further spread their malicious activity. The approach is based on detecting outliers using clustering, in this case self-organizing maps. An important advantage of this approach is that we have no restrictions on training data, and thus there is no need for any data pre-processing. Testing results demonstrate the capability of the approach in detecting both bad mouthing and ballot stuffing attack in various scenarios.

A Semi-Lagrangian Particle Level Set Finite Element Method for Interface Problems

We present a quasi-monotone semi-Lagrangian particle level set (QMSL-PLS) method for moving interfaces. The QMSL method is a blend of first order monotone and second order semi-Lagrangian methods. The QMSL-PLS method is easy to implement, efficient, and well adapted for unstructured, either simplicial or hexahedral, meshes. We prove that it is unconditionally stable in the maximum discrete norm, � · �h,∞, and the error analysis shows that when the level set solution u(t) is in the Sobolev space Wr+1,∞(D), r ≥ 0, the convergence in the maximum norm is of the form (KT/Δt)min(1,Δt � v �h,∞ /h)((1 − α)hp + hq), p = min(2, r + 1), and q = min(3, r + 1),where v is a velocity. This means that at high CFL numbers, that is, when Δt > h, the error is O( (1−α)hp+hq) Δt ), whereas at CFL numbers less than 1, the error is O((1 − α)hp−1 + hq−1)). We have tested our method with satisfactory results in benchmark problems such as the Zalesak’s slotted disk, the single vortex flow, and the rising bubble.

Temporal segmentation tool for high-quality real time video editing software

The increasing use of video editing software requires faster and more efficient editing tools. As a first step, these tools perform a temporal segmentation in shots that allows a later building of indexes describing the video content. Here, we propose a novel real-time high-quality shot detection strategy, suitable for the last generation of video editing software requiring both low computational cost and high quality results. While abrupt transitions are detected through a very fast pixel-based analysis, gradual transitions are obtained from an efficient edge-based analysis. Both analyses are reinforced with a motion analysis that helps to detect and discard false detections. This motion analysis is carried out exclusively over a reduced set of candidate transitions, thus maintaining the computational requirements demanded by new applications to fulfill user needs.

A new set of integrals of motion to propagate the perturbed two-body problem

A formulation of the perturbed two-body problem that relies on a new set of orbital elements is presented. The proposed method represents a generalization of the special perturbation method published by Peláez et al. (Celest Mech Dyn Astron 97(2):131?150,2007) for the case of a perturbing force that is partially or totally derivable from a potential. We accomplish this result by employing a generalized Sundman time transformation in the framework of the projective decomposition, which is a known approach for transforming the two-body problem into a set of linear and regular differential equations of motion. Numerical tests, carried out with examples extensively used in the literature, show the remarkable improvement of the performance of the new method for different kinds of perturbations and eccentricities. In particular, one notable result is that the quadratic dependence of the position error on the time-like argument exhibited by Peláez?s method for near-circular motion under the J2 perturbation is transformed into linear.Moreover, themethod reveals to be competitive with two very popular elementmethods derived from theKustaanheimo-Stiefel and Sperling-Burdet regularizations.

La identificaciónde de los daños estructurales, herramienta de la nueva atribución de responsabilidades : análisis crítico de la transición del art. 1591 cc al art. 17 LOE

RESUMEN Su objetivo esencial: Regular el proceso de la edificación, está basado en 3 grandes pilares: 1.- Completar la configuración legal de los agentes que intervienen en el mismo, fijando sus obligaciones para así establecer las responsabilidades. 2.- Fomentar la calidad de los edificios. 3.- Fijar las garantías a los usuarios frente a los posibles daños. Estos tres fundamentos están intensamente relacionados, ya que, las obligaciones y responsabilidades de los agentes son la base de la constitución de las garantías a los usuarios, definidas mediante los requisitos básicos que deben satisfacer los edificios. Partiendo del análisis cualitativo y cuantitativo del grado de cumplimiento del objetivo de la nueva Ley, elaborado a través del estudio de sus tres pilares fundamentales, proponemos medidas tendentes a la plena entrada en vigor de la misma. Para ello se deberá desarrollar el Real Decreto previsto en la Disposición Adicional 2ª, una vez conseguido el grado de madurez de los sectores de la edificación y del seguro. En todo este proceso de estudio hemos podido apreciar que la objetiva identificación de los daños y en especial los que afectan la estabilidad del edificio, constituye una herramienta fundamental para la correcta atribución de responsabilidades a los agentes, basada en la aplicación de los tres grados de responsabilidad “ex lege” por daños materiales y sus plazos de prescripción surgidos del nuevo régimen impuesto por el art. 17 LOE Para avalar esta propuesta hemos analizado: 1.- El entorno económico, general y pormenorizado al sector de la edificación, en Europa y España durante el período comprendido entre los años 1990 y 2013, años previos y posteriores a la entrada en vigor de la Ley, dada la influencia de los ciclos de actividad producidos en la regulación del sector, las responsabilidades atribuidas a los agentes, el fomento de la calidad y las garantías ofrecidas a los adquirentes. 2.- Las diversas legislaciones sobre responsabilidades y garantías de los agentes de la edificación en los países de nuestro entorno económico. 3.- La gestación de la LOE, incidiendo en la evolución de los últimos borradores y su tramitación parlamentaria. 4.- El desarrollo doctrinal de la Transición desde el régimen de responsabilidades, fijado por el art. 1591 de Código Civil, y su Jurisprudencia, hacia el nuevo régimen de responsabilidades establecido por el art. 17 LOE. En esta tarea además de apreciar la asimilación, por parte de los Jueces y Magistrados, de los principios doctrinales de la LOE, hemos observado la labor de los peritos, de cuya experta identificación de las causas de los daños depende la justa y eficaz atribución de responsabilidades. 5 -. El grado de eficacia de la LOE a la vista de la estadística siniestral, de la que ya hay datos consolidados, tras la cancelación de casi 15.000 expedientes de reclamación a Arquitectos. 6 -. También hemos estudiado el grado de cumplimiento con el usuario y propietario de las garantías previstas en el art. 19 de la Ley y en la D.A. 1ª, los efectos reales alcanzados y las tareas pendientes por delante. Analizando la atribución de responsabilidades a los agentes de la edificación, dentro del primer pilar fundamental de la LOE, hemos estudiado las actuaciones de los peritos expertos y su incidencia en este objetivo, previa selección de casos de gran interés y dificultad. Fruto de ello se han formulado propuestas tendentes a la especialización de este colectivo, evitando conductas “irregulares” que tanto daño provocan a los agentes reclamados como a los propietarios afectados. Este daño es evidente pudiendo ocasionar condenas injustas, enriquecimientos ilícitos o bien falsas expectativas de satisfacción de daños mal dictaminados y costosas e ineficaces reparaciones. De cara a la consecución del pilar de la calidad de la edificación, mediante los requisitos básicos planteados por la LOE y desarrollados por el Código Técnico de la Edificación (Real Decreto 314/2006, de 17 de marzo), hemos procesado datos de expedientes de reclamaciones por daños que afectan a edificios ejecutados bajo el nuevo régimen LOE. Con esta base se han analizado las causas generadoras de las diversas lesiones y su frecuencia para que de este análisis puedan establecerse pautas de actuación para su prevención. Finalmente, tras demostrar que las garantías obligatorias impuestas por la LOE sólo abarcan un pequeño porcentaje de los posibles daños a la edificación, insistimos en la necesidad de la plena eficacia de la Ley mediante la aprobación de todas las garantías previstas y para todo tipo de edificaciones. En suma, se ha diseñado la tesis como una matriz abierta en la que podremos continuar incorporando datos de la evolución de la doctrina, la jurisprudencia y la estadística de los daños en la edificación. ABSTRACT The approval of Law 38/1999 on November 5, 1999, (Official Gazette BOE 266/1999 of 11.6.1999, p. 38925), was the culmination of a long period of over 20 years of gestation for which deep agreements were needed between all stakeholders affected. Although several parliamentary groups denounced its incomplete approval, regarding mandatory guarantees to the purchaser, its enactment caused general satisfaction among most of the the building agents. This assessment remains after fourteen years since its partial enactment. Its essential purpose, “to regulate the building process”, is based on 3 pillars: 1.- To complete the legal configuration of the agents involved in it, setting their obligations in order to establish their responsibilities. 2.- To promote the buildings quality. 3.- To specify users´guarantees against possible buildings damage. These three issues are strongly related, since the obligations and responsibilities of the actors are the basis of the users’guarantees constitution, defined by the basic performance required by buildings. Based on the qualitative and quantitative analysis of the fulfillment of the new law’s objectives, made by monitoring the three pillars, we propose measures to the full enactment of this Directive, by the development of the Royal Decree, provided in its Second Additional Provision, once maturity in the sectors of the building and insurance is achieved. Throughout this process of study we have seen that the skill identification of damage, particularly those affecting the stability of the building, is an essential tool for the proper allocation of responsibilities of the new regime installed by the art. 17 LOE, based on the application of the three degrees of responsibility "ex lege" for property damage and limitation periods. To support this proposal, we have analyzed: 1.- The evolution of the building sector in Europe and Spain during the years before and after the enactment of the Law, due to the influence of cycles of activity produced in industry regulation, the responsibilities attributed to agents, promotion of the quality and the assurances given to acquirers. 2.- The scope of various laws on liability and building agents warranties in the countries of our economic environment. 3.- The long period of LOE generation, focusing on the developments in recent drafts and parliamentary procedure. 4.- The doctrinal development in the Transition from the regime of responsibilities, set by art. 1591 of the Civil Code, and its Jurisprudence, to the new liability regime established by art. 17 LOE. In this task, while we have noted assimilation by the Judges and Magistrates of the doctrinal principles of the LOE, we have also analyzed the work of experts, whose skilled identification of the damage causes helps the fair and efficient allocation of responsibilities. 5 - The effectiveness of the LOE based on knowledge of the siniestral statistics, which are already consolidated data, after the cancellation of nearly 15,000 claims to Architects. 6.- We have also studied the degree of compliance with the user and owner guarantees, established in art. 19 and the D.A. 1th of the LOE, exposing the real effects achieved and the pending tasks ahead. Analyzing the allocation of the building agents´ responsibilities, within the first cornerstone of the LOE, we have studied the expert witnesses actions and their impact on this duty, selecting cases of great interest and difficulty in this aim. The result of this enterprise has been to propose the specialization of this group, avoiding "irregular" behaviors that create as much damage as the agents claimed to affected owners. This damage is evident and can cause wrong convictions, illicit enrichment, false expectations and inefficient and costly damage repairs. In order to achieve the pillar of building quality through the basic requirements set by the LOE and developed by the Technical Building Code (Royal Decree 314/ 2006 of 17 March), we have analyzed records of damage claims involving buildings executed under the new regime LOE. On this basis we have analyzed the root causes of various damages and their frequency, from these data it will be easy to propose lines of action for prevention. Finally, after demonstrating that mandatory warranties imposed by LOE cover only a small percentage of the potential building damage, we emphasize the need for the full effectiveness of the Law by the obligation all the guarantees provided in the art. 19 LOE, and for all types of buildings. In conclusion, this thesis is designed as an open matrix in which we will continue including data on the evolution of the doctrine, jurisprudence and the statistics of the damage to the building.