39815337
Making Timed Automata Communicate
A computation model is introduced in which real-time constraints as well as data communications can be explicitely expressed. The model is presented in a graphical form. Its semantics is studied and algorithms to compute bisimulation equivalences for such graphs are proposed.
26308486
Model checking real-time value-passing systems
In this paper, to model check real-time value-passing systems, a formal languageTimed Symbolic Transition Graph and a logic system namedTimed Predicate μ-Calculus are proposed. An algorithm is presented which is local in that it generates and investigates the reachable state space in top-down fashion and maintains the partition for time evaluations as coarse as possible whileon-the-fly instantiating data variables. It can deal with not only data variables with finite value domain, but also the so calleddata independent variables with infinite value domain. To authors knowledge, this is the first algorithm for model checking timed systems containing value-passing features.
34879998
On fault tolerance of 3-dimensional mesh networks
In this paper, the concept ofk-submesh andk-submesh connectivity fault tolerance model is proposed. And the fault tolerance of 3-D mesh networks is studied under a more realistic model in which each network node has an independent failure probability. It is first observed that if the node failure probability is fixed, then the connectivity probability of 3-D mesh networks can be arbitrarily small when the network size is sufficiently large. Thus, it is practically important for multicomputer system manufacturer to determine the upper bound for node failure probability when the probability of network connectivity and the network size are given. A novel technique is developed to formally derive lower bounds on the connectivity probability for 3-D mesh networks. The study shows that 3-D mesh networks of practical size can tolerate a large number of faulty nodes thus are reliable enough for multicomputer systems. A number of advantages of 3-D mesh networks over other popular network topologies are given. Compared to 2-D mesh networks, 3-D mesh networks are much stronger in tolerating faulty nodes, while for practical network size, the fault tolerance of 3-D mesh networks is comparable with that of hypercube networks but enjoys much lower node degree.
36959305
Overlap matrices and total imbedding distributions
Abstract The concept of genus distribution of graphs is generalized to include nonorientable imbeddings. Explicit computations of the total imbedding distributions for several interesting graph classes are given. These computations are an illustration of the power of a theorem by Mohar that relates topological types of imbedding surfaces to ranks of the corresponding overlap matrices.
10895534
Aspect-Based Instrumentation for Locating Memory Leaks in Java Programs
Despite the built-in garbage collector, Java programs can still suffer the memory leak problem resulted from the unhealthy programming style of retaining unwanted references. This paper presents an aspect-based tool for assisting programmers in locating such references to fix the problem. This tool, FindLeaks, utilizes an aspect to collect memory consumption statistics and object references created during a program's execution and analyzes them for detecting memory leaks. The distinctive feature of FindLeaks is that it reports not only suspected classes of leaking objects but also where in the source the unwanted references were created. Besides, this paper also reports some preliminary experience with FindLeaks.
18252662
On Constrained Minimum Vertex Covers of Bipartite Graphs: Improved Algorithms
The constrained minimum vertex cover problem on bipartite graphs arises from the extensively studied fault coverage problem for reconfigurable arrays. In this paper, we develop a new algorithm for the problem, in which classical results in matching theory and recently developed techniques in parameterized computation are nicely combined and extended. The algorithm is practically efficient with running time bounded by O(1.26k + kn), where k is the size of the constrained minimum vertex cover in the input graph. The algorithm is a significant improvement over the previous algorithms for the problem.
10445420
Modeling and Predicting Future Trajectories of Moving Objects in a Constrained Network
Advances in wireless sensor networks and positioning technologies enable traffic management (e.g. routing traffic) that uses real-time data monitored by GPS-enabled cars. Location management has become an enabling technology in such application. The location modeling and trajectory prediction of moving objects are the fundamental components of location management in mobile locationaware applications. In this paper, we model the road network and moving objects in a graph of cellular automata (GCA), which makes full use of the constraints of the network and the stochastic behavior of the traffic. A simulation-based method based on graphs of cellular automata is proposed to predict future trajectories. Our technique strongly differs from the linear prediction method, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changes. The experiments, carried on two different datasets, show that the simulation-based prediction method provides higher accuracy than the linear prediction method.