^September October – 2008 ^November

Minesweeper is a popular single player game. It has been shown that the Minesweeper consistency problem is NP-complete and the Minesweeper counting problem is #P-complete. We present a polynomial algorithm for solving these problems for minesweeper graphs with bounded tree width. There is a close connection between the minesweeper problems and general CSP problems.

Modern software engineering heavily relies on clearly specified interfaces for separation of concerns among designers implementing components and programmers using those components. The interface of a component describes the functionality and constraints on the correct usage in a succinct manner. The need for interfaces is evident for assembling complex systems from components, but more so in modern control applications where a network of sensors and actuators is deployed to achieve complex control objectives. The notion of an interface for a control component must incorporate information about timing and resource needs, information that is nor represented in current programing interfaces.

In the talk, I'll propose formal languages as an interface for resource sharing and timing. For example, imagine two components that share some resource (e.g. CPU), allocated in a time-triggered manner. With the proposed interface, each component specifies a formal language over the alphabet {0,1} of "safe schedules", i.e., if w=w(1),w(2),… is in this languages, and the component gets the resource in every time slot t for which w(t)=1, then the component meets its performance requirements. The main advantage of this interface is that it allows modular analysis of each component and, then, constraints can be combined using languages intersection.

I'll present theoretical results concerning applications of the above approach to software control systems (where controllers are implemented by a software that shares resources). I'll also introduce a Real-Time-Java based tool, called RTComposer, that supports the proposed methodology. In RTComposer, scheduling specifications can be given as periodic tasks, or using temporal logic, or as omega-automata, or stability requirements. Components can be added dynamically, and non-real-time components are allowed. The benefits of the approach will be demonstrated and applications to wireless sensor/actuator networks based on the WirelessHART protocol and to distributed control systems based on the Control Area Network (CAN) bus (used, e.g., in automotive applications) will be discussed.

The topology of metabolic networks may provide important insights not only into the metabolic capacity of species, but also into the habitats in which they evolved. In this talk I will present several analyses of metabolic networks and show how various ecological insights can be obtained from genomic-based data. I will first introduce various factors that affect the structure of metabolic networks, and specifically the environmental and genetic determinants that affect network modularity. I will then present the first large-scale computational reconstruction of metabolic growth environments, analyzing the metabolic networks of hundreds of species and using a graph-theory based algorithm to identify for each species a set of seed compounds that must be exogenously acquired. Such seed sets form ecological "interfaces" between metabolic networks and their surroundings, approximating the effective biochemical environment of each species. The seed sets' composition significantly correlates with several properties characterizing the species' environments and agrees with biological observations concerning major adaptations (e.g. obligate parasitism). Phylogenetic analysis of the seed sets reveals the complex dynamics governing gain and loss of biosynthetic capacity across the phylogenetic tree. I will further present an extension of this framework, accounting for interactions between species, by introducing a pair-wise, topology-based measure of biosynthetic support, which reflects the extent to which the nutritional requirements of one species could be satisfied by the biosynthetic capacity of another. I will show that this measure is aligned with host-parasite interactions and facilitates successful prediction of such interactions on a large-scale. Integrating this method with phylogenetic analysis and calculating the biosynthetic support of ancestral Firmicutes species further reveal a large-scale evolutionary trend of biosynthetic capacity loss in parasites. Finally, I will discuss the application of this approach to the analysis of microbial communities and metagenomic data of the human microbiota and outline future research directions; The "reverse ecology" approach demonstrated in these analyses lays the foundations for further studying the complex web of interactions characterizing various ecosystems and the evolutionary interplay between organisms and their habitats on a large scale.