Search

Reverse engineering tools are required to handle the complexity of software products and the unique requirements of many different tasks, like software analysis and visualization. Thus, reverse engineering tools should adapt to a variety of cases. Static Code Analysis (SCA) is a technique for analyzing and exploring software source code without running it. Manual review of software source code puts additional effort on software developers and is a tedious, error-prone, and costly job. This paper proposes an original approach (called ScaMaha) for Object-Oriented (OO) source code analysis and visualization based on SCA. ScaMaha is a modular, flexible, and extensible reverse engineering tool. ScaMaha revolves around a new meta-model and a new code parser, analyzer, and visualizer. ScaMaha parser extracts software source code based on the Abstract Syntax Tree (AST) and stores this code as a code file. The code file includes all software code identifiers, relations, and structural information. ScaMaha analyzer studies and exploits the code files to generate useful information regarding software source code. The software metrics file gives unique metrics regarding software systems, such as the number of method access relations. Software source code visualization plays an important role in software comprehension. Thus, ScaMaha visualizer exploits code files to visualize different aspects of software source code. The visualizer generates unique graphs about software source code, like the visualization of inheritance relations. ScaMaha tool was applied to several case studies from small to large software systems, such as drawing shapes, mobile photo, health watcher, rhino, and ArgoUML. Results show the scalability, performance, soundness, and accuracy of ScaMaha tool. Evaluation metrics, such as precision and recall, demonstrate the accuracy of ScaMaha ..., Comment: 20 pages, 16 figures, 3 tables, 8 listings, and 90 references

Algebraic methods applied to the reconstruction of Sparse-view Computed Tomography (CT) can provide both a high image quality and a decrease in the dose received by patients, although with an increased reconstruction time since their computational costs are higher. In our work, we present a new algebraic implementation that obtains an exact solution to the system of linear equations that models the problem and based on single-precision floating-point arithmetic. By applying Out-Of-Core (OOC) techniques, the dimensions of the system can be increased regardless of the main memory size and as long as there is enough secondary storage (disk). These techniques have allowed to process images of 768 x 768 pixels. A comparative study of our method on a GPU using both single-precision and double-precision arithmetic has been carried out. The goal is to assess the single-precision arithmetic implementation both in terms of time improvement and quality of the reconstructed images to determine if it is sufficient to consider it a viable option. Results using single-precision arithmetic approximately halves the reconstruction time of the double-precision implementation, whereas the obtained images retain all internal structures despite having higher noise levels., Comment: 22 pages, 12 figures, 9 tables

This paper presents SPI-DP, a novel first-order optimizer capable of optimizing robot programs with respect to both high-level task objectives and motion-level constraints. To that end, we introduce DGPMP2-ND, a differentiable collision-free motion planner for serial N-DoF kinematics, and integrate it into an iterative, gradient-based optimization approach for generic, parameterized robot program representations. SPI-DP allows first-order optimization of planned trajectories and program parameters with respect to objectives such as cycle time or smoothness subject to e.g. collision constraints, while enabling humans to understand, modify or even certify the optimized programs. We provide a comprehensive evaluation on two practical household and industrial applications., Comment: 8 pages, 6 figures, submitted to the 2025 IEEE International Conference on Robotics & Automation (ICRA)

The recent discovery that GaAs(Si,B) is a bright cryogenic scintillator with no apparent afterglow offers new opportunities for detecting rare, low-energy, electronic excitations from interacting dark matter. This paper presents Monte Carlo calculations of the scintillation photon detection efficiencies of optical cavities using three current cryogenic photodetector technologies. In order of photon detection efficiency these are: (1) Ge/TES: germanium absorbers that convert interacting photons to athermal phonons that are readout by transition edge sensors, (2) KID: kinetic induction detectors that respond to the breaking of cooper pairs by a change in resonance frequency, and (3) SNSPD: superconducting nanowire single photon detectors, where a photon briefly transitions a thin wire from superconducting to normal. The detection efficiencies depend strongly on the n-type GaAs absolute absorption coefficient KA, which is a part of the narrow beam absorption that has never been directly measured. However, the high cryogenic scintillation luminosity of GaAs(Si,B) sets an upper limit on KA of 0.03/cm. Using that value and properties published for Ge/TES, KID, and SNSPD photodetectors, this work calculates that those photodetectors attached to opposing faces of a 1 cm3 cubic GaAs(Si,B) crystal in an optical cavity with gold mirrors would have scintillation photon detection efficiencies of 35%, 25%, and 8%, respectively. Larger values would be expected for lower values of KA., Comment: 15 pages, 6 figures, 5 tables

Over the past decade, reactive frameworks and languages have become the dominant programming paradigm in front-end web development. In this paradigm, user actions change application state, and those changes propagate reactively to derived state and to the display, reducing the likelihood that various parts of the data model and user-facing view will become out of sync due to programmer error. In this paper, we explore the application of relational programming to the specification and synchronized evolution of model and view across time in response to user input. To that end, we present a reactive Javascript implementation of miniKanren and an integrated reactive programming model oriented towards the challenges of front-end web development., Comment: 20 pages, 4 figures

The glycocalyx is a complex layer of carbohydrate and protein molecules that surrounds the cell membrane of many types of mammalian cells. It serves several important functions, including cell adhesion and communication, and maintain cell shape and stability, especially in the case of erythrocytes. Alteration of glycocalyx composition represents a cardiovascular health threatening. For example, in diabetes mellitus glycocalyx of erythrocytes and of endothelial cells is known to be impaired, a potential source of blood occlusion in microcirculation, which may lead to blindness, and renal failure of patients. The impact of glycocalyx impairment on erythrocyte aggregation remains a largely unexplored research area. We conduct here in vitro-experiments in microfluidic devices in order to investigate erythrocytes aggregation incubated with amylase, an enzyme that partially breaks down glycocalyx molecules. It is found that incubation of erythrocytes by amylase leads to a dramatic increase of their aggregation and stability and alters the aggregates morphologies. Confocal microscopy analysis reveals a significant degradation of the glycocalyx layer, correlated with enhanced erythrocytes aggregation. An increased erythrocyte aggregation in vivo should affect oxygen and other metabolites delivery to organs and tissues. This study brings new elements about elucidation of microscopic origins of erythrocyte aggregation and their potential impact on cardiovascular pathologies.

In this paper, we propose a method for aligning models with their realization through the application of model-based systems engineering. Our approach is divided into three steps. (1) Firstly, we leverage domain expertise and the Unified Architecture Framework to establish a reference model that fundamentally describes some domain. (2) Subsequently, we instantiate the reference model as specific models tailored to different scenarios within the domain. (3) Finally, we incorporate corresponding run logic directly into both the reference model and the specific models. In total, we thus provide a practical means to ensure that every implementation result is justified by business demand. We demonstrate our approach using the example of maritime object detection as a specific application (specific model / implementation element) of automatic target recognition as a service reoccurring in various forms (reference model element). Our approach facilitates a more seamless integration of models and implementation, fostering enhanced Business-IT alignment.

The burgeoning influence of Large Language Models (LLMs) in shaping public discourse and decision-making underscores the imperative to address inherent biases within these AI systems. In the wake of AI's expansive integration across sectors, addressing racial bias in LLMs has never been more critical. This paper introduces a novel framework called Comprehensive Bias Neutralization Framework (CBNF) which embodies an innovative approach to quantifying and mitigating biases within LLMs. Our framework combines the Large Language Model Bias Index (LLMBI) [Oketunji, A., Anas, M., Saina, D., (2023)] and Bias removaL with No Demographics (BLIND) [Orgad, H., Belinkov, Y. (2023)] methodologies to create a new metric called Bias Intelligence Quotient (BiQ)which detects, measures, and mitigates racial bias in LLMs without reliance on demographic annotations. By introducing a new metric called BiQ that enhances LLMBI with additional fairness metrics, CBNF offers a multi-dimensional metric for bias assessment, underscoring the necessity of a nuanced approach to fairness in AI [Mehrabi et al., 2021]. This paper presents a detailed analysis of Latimer AI (a language model incrementally trained on black history and culture) in comparison to ChatGPT 3.5, illustrating Latimer AI's efficacy in detecting racial, cultural, and gender biases through targeted training and refined bias mitigation strategies [Latimer & Bender, 2023]., Comment: 41 pages

A circular program creates a data structure whose computation depends upon itself or refers to itself. The technique is used to implement the classic data structures circular and doubly-linked lists, threaded trees and queues, in a functional programming language. These structures are normally thought to require updatable variables found in imperative languages. For example, a functional program to perform the breadth-first traversal of a tree is given. Some of the examples result in circular data structures when evaluated. Some examples are particularly space-efficient by avoiding the creation of intermediate temporary structures which would otherwise later become garbage. Lastly, the technique can be applied in an imperative language to give an elegant program.

Cutting and packing problems are present in many, at first glance unconnected, areas, therefore it's beneficial to have a good understanding of their underlying structure, to select proper techniques for finding solutions. Cutting and packing problems are a class of combinatorial problems in which there are specified two classes of objects: big and small items and the task is to place the small items within big items. Even in the 1-dimensional case, bin-packing is strongly NP-hard (Garey 1978), which suggests, that exact solutions may not be found in a reasonable time for bigger instances. In the literature, there are presented many various approaches to packing problems, e.g. mixed-integer programming, approximation algorithms, heuristic solutions, and local search algorithms, including metaheuristic approaches like Tabu Search or Simulated Annealing. The main goal of this work is to review existing solutions, survey the variants arising from the industry applications, present a solution based on constraint programming and compare its performance with the results in the literature. Optimization with constraint programming is a method searching for the global optima, hence it may require a higher workload compared to the heuristic and local search approaches, which may finish in a local optimum. The performance of the presented model will be measured on test data used in the literature, which were used in many articles presenting a variety of approaches to three-dimensional container packing, which will allow us to compare the efficiency of the constraint programming model with other methods used in the operational research.

We study the arithmetical structures on the complete graph $K_9$. Our method is based on studying the solutions to writing the unit as a sum of 9 unit fractions. We work from the perspective of the Diophantine equation and use some elementary properties on the $p$-adic valuations. The proofs are assisted by trees and automata., Comment: 73 pages

An equivalence relation can be constructed from a given (homogeneous, binary) relation in two steps: first, construct the smallest reflexive and transitive relation containing the given relation (the "star" of the relation) and, second, construct the largest symmetric relation that is included in the result of the first step. The fact that the final result is also reflexive and transitive (as well as symmetric), and thus an equivalence relation, is not immediately obvious, although straightforward to prove. Rather than prove that the defining properties of reflexivity and transitivity are satisfied, we establish reflexivity and transitivity constructively by exhibiting a particular starth root -- in a way that emphasises the creative process in its construction. The constructed starth root is fundamental to algorithms that determine the strongly connected components of a graph as well as the decomposition of a graph into its strongly connected components together with an acyclic graph connecting such components., Comment: Accepted for publication in Journal of Functional Programming

This paper describes the verification of the classical software and hardware stack that is used to control cold atom- and superconducting-based quantum computing hardware. The paper serves both as an introduction to quantum computing and to how classical device verification techniques can be employed there. Two main challenges in building a quantum control stack are generating precise deterministic-timing operations at the edge and scaled-out processing in the middle layer. Both challenges are to do with a certain kind of functional performance correctness. And, as usual, the design lives under tight power, memory and latency constraints. The quantum control stack is a complex interaction of algorithms, software runtimes and digital hardware. We take inspiration from modern software approaches to engineering, such as continuous integration and hardware automation, to quickly ship experimental features to customers in the field., Comment: In DVCon Europe 2023

Aging societies, labor shortages and increasing wage costs call for assistance robots capable of autonomously performing a wide array of real-world tasks. Such open-ended robotic manipulation requires not only powerful knowledge representations and reasoning (KR&R) algorithms, but also methods for humans to instruct robots what tasks to perform and how to perform them. In this paper, we present a system for automatically generating executable robot control programs from human task demonstrations in virtual reality (VR). We leverage common-sense knowledge and game engine-based physics to semantically interpret human VR demonstrations, as well as an expressive and general task representation and automatic path planning and code generation, embedded into a state-of-the-art cognitive architecture. We demonstrate our approach in the context of force-sensitive fetch-and-place for a robotic shopping assistant. The source code is available at https://github.com/ease-crc/vr-program-synthesis., Comment: 10 pages, 11 figures, accepted at the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR2023, https://kr.org/KR2023)

String matching is a fundamental problem in algorithm. This study examines the development and construction of two reversible string-matching algorithms: a naive string-matching algorithm and the Rabin-Karp algorithm. The algorithms are used to introduce reversible computing concepts, beginning from basic reversible programming techniques to more advanced considerations about the injectivization of the polynomial hash-update function employed by the Rabin-Karp algorithm. The results are two clean input-preserving reversible algorithms that require no additional space and have the same asymptotic time complexity as their classic irreversible originals. This study aims to contribute to the body of reversible algorithms and to the discipline of reversible programming., Comment: In Proceedings HCVS/VPT 2022, arXiv:2211.10675

In recent years, artificial intelligence has developed in a variety of fields and is now integrated into many aspects of our daily lives. This includes AI speakers,communication robots, and other interactive systems. We are interested in AI speaker like systems in which the robot responds to the user's needs and speech synthesis. We participated in an interactive robot competition to promote the development of interactive robots., Comment: This paper is part of the proceeding of the Dialogue Robot Competition 2022

Developing complex biomolecular workflows is not always straightforward. It requires tedious developments to enable the interoperability between the different biomolecular simulation and analysis tools. Moreover, the need to execute the pipelines on distributed systems increases the complexity of these developments. To address these issues, we propose a methodology to simplify the implementation of these workflows on HPC infrastructures. It combines a library, the BioExcel Building Blocks (BioBBs), that allows scientists to implement biomolecular pipelines as Python scripts, and the PyCOMPSs programming framework which allows to easily convert Python scripts into task-based parallel workflows executed in distributed computing systems such as HPC clusters, clouds, containerized platforms, etc. Using this methodology, we have implemented a set of computational molecular workflows and we have performed several experiments to validate its portability, scalability, reliability and malleability., Comment: Accepted in IEEE eScience conference 2022

In both industrial and service domains, a central benefit of the use of robots is their ability to quickly and reliably execute repetitive tasks. However, even relatively simple peg-in-hole tasks are typically subject to stochastic variations, requiring search motions to find relevant features such as holes. While search improves robustness, it comes at the cost of increased runtime: More exhaustive search will maximize the probability of successfully executing a given task, but will significantly delay any downstream tasks. This trade-off is typically resolved by human experts according to simple heuristics, which are rarely optimal. This paper introduces an automatic, data-driven and heuristic-free approach to optimize robot search strategies. By training a neural model of the search strategy on a large set of simulated stochastic environments, conditioning it on few real-world examples and inverting the model, we can infer search strategies which adapt to the time-variant characteristics of the underlying probability distributions, while requiring very few real-world measurements. We evaluate our approach on two different industrial robots in the context of spiral and probe search for THT electronics assembly., Comment: 7 pages, 5 figures, accepted to the 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2022), Kyoto, Japan For code and data, see https://github.com/benjaminalt/dpse

CFD users of supercomputers usually resort to rule-of-thumb methods to select the number of subdomains (partitions) when relying on MPI-based parallelization. One common approach is to set a minimum number of elements or cells per subdomain, under which the parallel efficiency of the code is "known" to fall below a subjective level, say 80%. The situation is even worse when the user is not aware of the "good" practices for the given code and a huge amount of resources can thus be wasted. This work presents an elastic computing methodology to adapt at runtime the resources allocated to a simulation automatically. The criterion to control the required resources is based on a runtime measure of the communication efficiency of the execution. According to some analytical estimates, the resources are then expanded or reduced to fulfil this criterion and eventually execute an efficient simulation., Comment: 27 pages, 15 figures

New analytical expressions are found for the Levi-Civita symbol using the Kronecker delta symbol. The expressions are derived up to 3 dimensions, extended to higher dimensions, and confirmed in Matlab for 5 dimensions. The expressions can be re-cast in terms of elementary and/or special functions, which lead to the conclusion that the Levi-Civita Symbol can be treated as a generalized, discrete function, Comment: This is the 5th version of the manuscript, and wholly supersedes the previous versions. In the previous versions, the generalized function G was sometimes confused with the epsilon itself. In this (fifth) version, it is clarified that G is merely a function used in alternative expressions of the epsilon

Crowd-sourced traffic data offer great promise in environmental modeling. However, archives of such traffic data are typically not made available for research; instead, the data must be acquired in real time. The objective of this paper is to present methods we developed for acquiring and analyzing time series of real-time crowd-sourced traffic data. We present scripts, which can be run in Unix/Linux like computational environments, to automatically download tiles of crowd-sourced Google traffic congestion maps for a user-specifiable region of interest. Broad and international applicability of our method is demonstrated for Manhattan in New York City and Mexico City. We also demonstrate that Google traffic data can be used to quantify decreases in traffic congestion due to social distancing policies implemented to curb the COVID-19 pandemic in the South Bronx in New York City., Comment: 19 pages, 8 figures, 1 table

The trend toward open science increases the pressure on authors to provide access to the source code and data they used to compute the results reported in their scientific papers. Since sharing materials reproducibly is challenging, several projects have developed solutions to support the release of executable analyses alongside articles. We reviewed 11 applications that can assist researchers in adhering to reproducibility principles. The applications were found through a literature search and interactions with the reproducible research community. An application was included in our analysis if it was actively maintained at the time the data for this paper was collected, supports the publication of executable code and data, is connected to the scholarly publication process. By investigating the software documentation and published articles, we compared the applications across 19 criteria, e.g. features that support authors in creating and readers in studying executable papers. From the 11 applications, eight allow publishers to self-host the system for free, whereas three provide paid services. Authors can submit an executable analysis using Jupyter Notebooks or R Markdown documents (10 applications support these formats). All approaches provide features to assist readers in studying the materials, e.g., one-click reproducible results or tools for manipulating the analysis parameters. Six applications allow for modifying materials after publication. The applications support authors to publish reproducible research predominantly with literate programming. Concerning readers, most applications provide user interfaces to inspect and manipulate the computational analysis., Comment: 8 pages, 2 tables

An experiment is described that confirms the security of a well-studied class of cryptographic protocols (Dolev-Yao intruder model) can be verified by two-way nondeterministic pushdown automata (2NPDA). A nondeterministic pushdown program checks whether the intersection of a regular language (the protocol to verify) and a given Dyck language containing all canceling words is empty. If it is not, an intruder can reveal secret messages sent between trusted users. The verification is guaranteed to terminate in cubic time at most on a 2NPDA-simulator. The interpretive approach used in this experiment simplifies the verification, by separating the nondeterministic pushdown logic and program control, and makes it more predictable. We describe the interpretive approach and the known transformational solutions, and show they share interesting features. Also noteworthy is how abstract results from automata theory can solve practical problems by programming language means., Comment: In Proceedings MARS/VPT 2018, arXiv:1803.08668

Actor coordination armoured with a suitable protocol description language has been a pressing problem in the actors community. We study the applicability of multiparty session type (MPST) protocols for verification of actor programs. We incorporate sessions to actors by introducing minimum additions to the model such as the notion of actor roles and protocol mailboxes. The framework uses Scribble, which is a protocol description language based on multiparty session types. Our programming model supports actor-like syntax and runtime verification mechanism guaranteeing communication safety of the participating entities. An actor can implement multiple roles in a similar way as an object can implement multiple interfaces. Multiple roles allow for cooperative inter-concurrency in a single actor. We demonstrate our framework by designing and implementing a session actor library in Python and its runtime verification mechanism. Benchmark results demonstrate that the runtime checks induce negligible overhead. We evaluate the applicability of our verification framework to specify actor interactions by implementing twelve examples from an actor benchmark suit.

This paper introduces a new metaobject, the generalizer, which complements the existing specializer metaobject. With the help of examples, we show that this metaobject allows for the efficient implementation of complex non-class-based dispatch within the framework of existing metaobject protocols. We present our modifications to the generic function invocation protocol from the Art of the Metaobject Protocol; in combination with previous work, this produces a fully-functional extension of the existing mechanism for method selection and combination, including support for method combination completely independent from method selection. We discuss our implementation, within the SBCL implementation of Common Lisp, and in that context compare the performance of the new protocol with the standard one, demonstrating that the new protocol can be tolerably efficient., Comment: 8 pages; version accepted for presentation at 2014 European Lisp Symposium. http://eprints.gold.ac.uk/9924/

We contrast the use of weakest preconditions for the correct construction of procedures with the cumulative subgoal fulfillment (CSF) approach. An example of Cohen and Monin is used for this purpose. The CSF construction process is demonstrated., Comment: 12 pages

In this paper we introduce a generic model for multiplicative algorithms which is suitable for the MapReduce parallel programming paradigm. We implement three typical machine learning algorithms to demonstrate how similarity comparison, gradient descent, power method and other classic learning techniques fit this model well. Two versions of large-scale matrix multiplication are discussed in this paper, and different methods are developed for both cases with regard to their unique computational characteristics and problem settings. In contrast to earlier research, we focus on fundamental linear algebra techniques that establish a generic approach for a range of algorithms, rather than specific ways of scaling up algorithms one at a time. Experiments show promising results when evaluated on both speedup and accuracy. Compared with a standard implementation with computational complexity $O(m^3)$ in the worst case, the large-scale matrix multiplication experiments prove our design is considerably more efficient and maintains a good speedup as the number of cores increases. Algorithm-specific experiments also produce encouraging results on runtime performance.

In this paper we introduce the concept of generalized d-graph (admitting cycles) as special dependency-graphs for modelling dynamic programming (DP) problems. We describe the d-graph versions of three famous single-source shortest algorithms (The algorithm based on the topological order of the vertices, Dijkstra algorithm and Bellman-Ford algorithm), which can be viewed as general DP strategies in the case of three different class of optimization problems. The new modelling method also makes possible to classify DP problems and the corresponding DP strategies in term of graph theory.

We investigate ways in which an algorithm can improve its expected performance by fine-tuning itself automatically with respect to an unknown input distribution D. We assume here that D is of product type. More precisely, suppose that we need to process a sequence I_1, I_2, ... of inputs I = (x_1, x_2, ..., x_n) of some fixed length n, where each x_i is drawn independently from some arbitrary, unknown distribution D_i. The goal is to design an algorithm for these inputs so that eventually the expected running time will be optimal for the input distribution D = D_1 * D_2 * ... * D_n. We give such self-improving algorithms for two problems: (i) sorting a sequence of numbers and (ii) computing the Delaunay triangulation of a planar point set. Both algorithms achieve optimal expected limiting complexity. The algorithms begin with a training phase during which they collect information about the input distribution, followed by a stationary regime in which the algorithms settle to their optimized incarnations., Comment: 26 pages, 8 figures, preliminary versions appeared at SODA 2006 and SoCG 2008. Thorough revision to improve the presentation of the paper

With the advent of Grid and application technologies, scientists and engineers are building more and more complex applications to manage and process large data sets, and execute scientific experiments on distributed resources. Such application scenarios require means for composing and executing complex workflows. Therefore, many efforts have been made towards the development of workflow management systems for Grid computing. In this paper, we propose a taxonomy that characterizes and classifies various approaches for building and executing workflows on Grids. We also survey several representative Grid workflow systems developed by various projects world-wide to demonstrate the comprehensiveness of the taxonomy. The taxonomy not only highlights the design and engineering similarities and differences of state-of-the-art in Grid workflow systems, but also identifies the areas that need further research., Comment: 29 pages, 15 figures

We describe the design and early implementation of an extensible, component-based software architecture for natural language engineering applications which interfaces with high performance distributed computing services. The architecture leverages existing linguistic resource description and discovery mechanisms based on metadata descriptions, combining these in a compatible fashion with other software definition abstractions. Within this architecture, application design is highly flexible, allowing disparate components to be combined to suit the overall application functionality, and formally described independently of processing concerns. An application specification language provides abstraction from the programming environment and allows ease of interface with high performance computational grids via a broker.

We describe a proposal for an extensible, component-based software architecture for natural language engineering applications. Our model leverages existing linguistic resource description and discovery mechanisms based on extended Dublin Core metadata. In addition, the application design is flexible, allowing disparate components to be combined to suit the overall application functionality. An application specification language provides abstraction from the programming environment and allows ease of interface with computational grids via a broker.

We present an efficient lock-free algorithm for parallel accessible hash tables with open addressing, which promises more robust performance and reliability than conventional lock-based implementations. ``Lock-free'' means that it is guaranteed that always at least one process completes its operation within a bounded number of steps. For a single processor architecture our solution is as efficient as sequential hash tables. On a multiprocessor architecture this is also the case when all processors have comparable speeds. The algorithm allows processors that have widely different speeds or come to a halt. It can easily be implemented using C-like languages and requires on average only constant time for insertion, deletion or accessing of elements. The algorithm allows the hash tables to grow and shrink when needed. Lock-free algorithms are hard to design correctly, even when apparently straightforward. Ensuring the correctness of the design at the earliest possible stage is a major challenge in any responsible system development. In view of the complexity of the algorithm, we turned to the interactive theorem prover PVS for mechanical support. We employ standard deductive verification techniques to prove around 200 invariance properties of our algorithm, and describe how this is achieved with the theorem prover PVS.

This thesis is devoted to the study of a calculus that describes the application of conditional rewriting rules and the obtained results at the same level of representation. We introduce the rewriting calculus, also called the rho-calculus, which generalizes the first order term rewriting and lambda-calculus, and makes possible the representation of the non-determinism. In our approach the abstraction operator as well as the application operator are objects of calculus. The result of a reduction in the rewriting calculus is either an empty set representing the application failure, or a singleton representing a deterministic result, or a set having several elements representing a not-deterministic choice of results. In this thesis we concentrate on the properties of the rewriting calculus where a syntactic matching is used in order to bind the variables to their current values. We define evaluation strategies ensuring the confluence of the calculus and we show that these strategies become trivial for restrictions of the general rewriting calculus to simpler calculi like the lambda-calculus. The rewriting calculus is not terminating in the untyped case but the strong normalization is obtained for the simply typed calculus. In the rewriting calculus extended with an operator allowing to test the application failure we define terms representing innermost and outermost normalizations with respect to a set of rewriting rules. By using these terms, we obtain a natural and concise description of the conditional rewriting. Finally, starting from the representation of the conditional rewriting rules, we show how the rewriting calculus can be used to give a semantics to ELAN, a language based on the application of rewriting rules controlled by strategies., Comment: PhD Thesis in French

This paper presents a new distributed computational model of distributed systems called the phase web that extends V. Pratt's orthocurrence relation from 1986. The model uses mutual-exclusion to express sequence, and a new kind of hierarchy to replace event sequences, posets, and pomsets. The model explicitly connects computation to a discrete Clifford algebra that is in turn extended into homology and co-homology, wherein the recursive nature of objects and boundaries becomes apparent and itself subject to hierarchical recursion. Topsy, a programming environment embodying the phase web, is available from www.cs.auc.dk/topsy., Comment: 16 pages, 3 figures