Types and associated type families for hardware simulation and synthesis

In this article we overview the design and implementation of the second generation of Kansas Lava. Driven by the needs and experiences of implementing telemetry decoders and other circuits, we have made a number of improvements to both the external API and the internal representations used. We have retained our dual shallow/deep representation of signals in general, but now have a number of externally visible abstractions for combinatorial and sequential circuits, and enabled signals. We introduce these abstractions, as well as our abstractions for reading and writing memory. Internally, we found the need to represent unknown values inside our circuits, so we made aggressive use of associated type families to lift our values to allow unknowns, in a principled and regular way. We discuss this design decision, how it unfortunately complicates the internals of Kansas Lava, and how we mitigate this complexity. Finally, when connecting Kansas Lava to the real world, the standardized idiom of using named input and output ports is provided by Kansas Lava using a new monad, called Fabric. We present the design of this Fabric monad, and illustrate its use in a small but complete example.     

An exploratory study of the impact of antipatterns on class change- and fault-proneness

Antipatterns are poor design choices that are conjectured to make object-oriented systems harder to maintain. We investigate the impact of antipatterns on classes in object-oriented systems by studying the relation between the presence of antipatterns and the change- and fault-proneness of the classes. We detect 13 antipatterns in 54 releases of ArgoUML, Eclipse, Mylyn, and Rhino, and analyse (1) to what extent classes participating in antipatterns have higher odds to change or to be subject to fault-fixing than other classes, (2) to what extent these odds (if higher) are due to the sizes of the classes or to the presence of antipatterns, and (3) what kinds of changes affect classes participating in antipatterns. We show that, in almost all releases of the four systems, classes participating in antipatterns are more change-and fault-prone than others. We also show that size alone cannot explain the higher odds of classes with antipatterns to underwent a (fault-fixing) change than other classes. Finally, we show that structural changes affect more classes with antipatterns than others. We provide qualitative explanations of the increase of change- and fault-proneness in classes participating in antipatterns using release notes and bug reports. The obtained results justify a posteriori previous work on the specification and detection of antipatterns and could help to better focus quality assurance and testing activities.     

Transaction models for Web accessibility

The Web has evolved into a dominant digital medium for conducting many types of online transactions such as shopping, paying bills, making travel plans, etc. Such transactions typically involve a number of steps spanning several Web pages. For sighted users these steps are relatively straightforward to do with graphical Web browsers. But they pose tremendous challenges for visually impaired individuals. This is because screen readers, the dominant assistive technology used by visually impaired users, function by speaking out the screen’s content serially. Consequently, using them for conducting transactions can cause considerable information overload. But usually one needs to browse only a small fragment of a Web page to do a step of a transaction (e.g., choosing an item from a search results list). Based on this observation this paper presents a model-directed transaction framework to identify, extract and aurally render only the “relevant” page fragments in each step of a transaction. The framework uses a process model to encode the state of the transaction and a concept model to identify the page fragments relevant for the transaction in that state. We also present algorithms to mine such models from click stream data generated by transactions and experimental evidence of the practical effectiveness of our models in improving user experience when conducting online transactions with non-visual modalities.     

A space and time efficient algorithm for SimRank computation

SimRank has become an important similarity measure to rank web documents based on a graph model on hyperlinks. The existing approaches for conducting SimRank computation adopt an iteration paradigm. The most efficient deterministic technique yields O(n³)O\left(n^3\right) worst-case time per iteration with the space requirement O(n²)O\left(n^2\right), where n is the number of nodes (web documents). In this paper, we propose novel optimization techniques such that each iteration takes O (min{ n ·m , n^r })O \left(\min \left\{ n \cdot m , n^r \right\}\right) time and O ( n + m )O \left( n + m \right) space, where m is the number of edges in a web-graph model and r ≤ log₂ 7. In addition, we extend the similarity transition matrix to prevent random surfers getting stuck, and devise a pruning technique to eliminate impractical similarities for each iteration. Moreover, we also develop a reordering technique combined with an over-relaxation method, not only speeding up the convergence rate of the existing techniques, but achieving I/O efficiency as well. We conduct extensive experiments on both synthetic and real data sets to demonstrate the efficiency and effectiveness of our iteration techniques.     

Link quality estimation in wireless multi-hop networks using Kernel based methods

A new approach for link modelling in wireless multi-hop networks is described for portable devices, based on Kernel Regression Statistics. A non-parametric estimation of errors in the wireless medium provides an efficient and accurate model of link errors between any two nodes. This estimation results from the analysis of the inter-arrival time between any periodically sent packets. The obtained results prove that it is possible to infer on link quality without having unrealistic assumptions or additional overhead, by using Kernel Methods. Moreover, similar performances were achieved for different scenarios, without requiring model recalculations. The presented results show that the proposed link quality estimation can be used in order to improve wireless connectivity and ubiquity in future networks.     

EASEA: specification and execution of evolutionary algorithms on GPGPU

EASEA is a framework designed to help non-expert programmers to optimize their problems by evolutionary computation. It allows to generate code targeted for standard CPU architectures, GPGPU-equipped machines as well as distributed memory clusters. In this paper, EASEA is presented by its underlying algorithms and by some example problems. Achievable speedups are also shown onto different NVIDIA GPGPUs cards for different optimization algorithm families.     

Extension of the DEMATEL method in an uncertain linguistic environment

The decision making trial and evaluation laboratory (DEMATEL) method is a useful tool for analyzing correlations among factors using crisp values. However, the crisp values are inadequate to model real-life situations due to the fuzziness and uncertainty that are frequently involved in judgments of experts. The aim of this paper is to extend the DEMATEL method to an uncertain linguistic environment. In this paper, the correlation information among factors provided by experts is in the form of uncertain linguistic terms. A formula is first presented to transform correlation information from uncertain linguistic terms to trapezoidal fuzzy numbers. Then, we aggregate the transformed correlation information of each expert into group information using the operations of trapezoidal fuzzy numbers. The importance and classification of factors are determined via fuzzy matrix operations. Furthermore, a causal diagram is constructed to vividly show the different roles of factors. Finally, an example is used to illustrate the procedure of the proposed method.     

Mutual learning of multi-consciousness agents,including an ego for an autonomous vehicle

In this paper, we propose a multi-agent learning system for the control of an intelligent robot, based on a model of the human consciousnesses, including the ego. We pay attention to the intelligent learning processes of human beings. We try to give a robot a high learning ability by modeling the roles of the human consciousnesses, including the ego. In most ordinary methods, the instructions for learning are given from outside the system only. In the proposed method, the instructions are given not only from outside, but also from inside (from other agents in the system). Therefore, the robot can learn efficiently because it has more instructions than usual. The learning is also more flexible, since an agent learns by instructions from other agents while the learning agent and one of the instructing agents exchange roles according to changes in the environment. We experimentally verified that the proposed method is efficient by using an actual robot.