Search

Monotonicity in concurrent systems stipulates that, in any global state, extant system actions remain executable when new processes are added to the state. This concept is not only natural and common in multi-threaded software, but also useful: if every thread's memory is finite, monotonicity often guarantees the decidability of safety property verification even when the number of running threads is unknown. In this paper, we show that the act of obtaining finite-data thread abstractions for model checking can be at odds with monotonicity: Predicate-abstracting certain widely used monotone software results in non-monotone multi-threaded Boolean programs - the monotonicity is lost in the abstraction. As a result, well-established sound and complete safety checking algorithms become inapplicable; in fact, safety checking turns out to be undecidable for the obtained class of unbounded-thread Boolean programs. We demonstrate how the abstract programs can be modified into monotone ones, without affecting safety properties of the non-monotone abstraction. This significantly improves earlier approaches of enforcing monotonicity via overapproximations.

Introduction: Insects of the subfamily Triatominae are vectors of Trypanosoma cruzi, the Chagas disease parasite, and their flying behavior has epidemiological importance. The flying capacity is strikingly different across and within Triatominae species, as well as between sexes or individuals. Many Triatoma infestans individuals have wings but no flying muscles. In other Triatominae species, no clear relationships were found between wing length and flying behavior. If wing presence or size is not reflective of the flying behavior, which other parts of the body could be considered as reliable markers of this important function? Methods: The genus Mepraia has exceptional characteristics with invariably wingless females and wingless or winged males. We calculated the porous surface exposed to odorant molecules to estimate the olfactory capacity of Mepraia spinolai. The head shape and thorax size were estimated using the geometric morphometric approach and traditional morphometric techniques, respectively. Results: Alary polymorphism in M. spinolai was significantly associated with consistent modification of the thorax size, head shape, and notable change in the estimated olfactory capacity. The macropterous individuals had a larger olfactory surface and thorax size and significantly different head shape compared to those of the micropterous individuals. Conclusions: We concluded that these structural changes could be associated with the flying potential of Triatominae. Thus, morphological attributes not found on wings could help determine the likely flying potential of the bugs.

We study the reachability problem of a quantum system modeled by a quantum automaton, namely, a set of processes each of which is formalized as a quantum unitary transformation. The reachable sets are chosen to be boolean combinations of (closed) subspaces of the state Hilbert space of the quantum system. Four different reachability properties are considered: eventually reachable, globally reachable, ultimately forever reachable, and infinitely often reachable. The main result of this paper is that all of the four reachability properties are undecidable in general; however, the last three become decidable if the reachable sets are boolean combinations without negation. © 2014 Springer-Verlag.