Mathematics Chasing Complexity

Guest Editor's Introduction • Michael Shafto • October 2010

Theme Articles

This month's theme includes the following featured articles:

Really Rethinking 'Formal Methods'
We must question the assumptions underlying the well-known current formal software development methods to see why they have not been widely adopted and what should be changed. More »

Getting Diagnostic Reasoning off the Ground:
Maturing Technology with Tacsat-3

In cooperation with the US Air Force Research Laboratory and industry, NASA conducted the TacSat-3 Vehicle Systems Management (TVSM) project using the TacSat-3 spacecraft as a hypothetical application of diagnostic technologies. More »

Policy-Based Design of Human-Machine Collaboration
in Manned Space Missions

Team design is an important issue in manned planetary exploration. A computational policy approach for requirements engineering and system implementation provides a way to study team design. More »

Measuring Performance in Real Time during Remote Human-Robot Operations with Adjustable Autonomy
Simulated operations during a recent NASA robotic field test demonstrated real-time computation of performance metrics for human-robot interaction that includes adjustable autonomy. More »

Classification of Physical Interactions
between Two Subjects

How can we use wireless sensor networks not only to detect human action, but also to detect and classify the interactions between subjects? More »

Automatic Translation of UML Sequence Diagrams
into PEPA Models

The UML profile for Modeling and Analysis of Real Time and Embedded systems provides a powerful framework for the specification of non-functional properties of UML models. Learn about an automatic procedure to derive PEPA process algebra models from sequence diagrams to carry out quantitative evaluation. More »

What else is new? »


Mathematics Chasing ComplexityIn commenting on Computer's September 2009 issue in his article "Really Rethinking Formal Methods," David Parnas challenges some of the core claims and assumptions underlying mathematical approaches to software modeling, model-checking, and related formal methods. He notes that there is a significant gap between formal methods and the practical world of software engineering. Not surprisingly, there is also a gap between software engineering and other engineering disciplines. Mathematics, which is supposed to be the common language that unites different science and engineering disciplines, seems to have failed in the case of computer science and software development.

The purpose of this month's theme on Computing Now is to point out some new directions that might lead from formal methods into the traditional science and engineering disciplines and back again to computer science. These same lines of work seem also to be linking discrete mathematics to continuous mathematics, and perhaps to some degree reducing the gap between theoretical computer science and classical mathematics. These new directions have to do, in general, with modeling.

These new directions in modeling arise in part from the inescapable challenges of dealing with increasingly complex systems. These challenges are driving requirements for exceptionally high-fidelity modeling and reliable simulation of hybrid systems, as illustrated by three articles in this theme: "Getting Diagnostic Reasoning off the Ground: Maturing Technology with Tacsat-3" by Ryan Mackey and colleagues, "Policy-Based Design of Human-Machine Collaboration in Manned Space Missions" by Jurriaan van Diggelen and colleagues, and "Measuring Performance in Real Time during Remote Human-Robot Operations with Adjustable Autonomy" by Debra Schreckenghost, Tod Milam, and Terrence Fong. These research efforts illustrate the use of high-fidelity simulation, agent-based architectures, and empirical analog-environment studies to increase understanding of and confidence in complex aerospace systems. All these methods, however, have limitations—limitations that are well-known in the world of formal methods. They all depend on searching a tiny subset of the space of possible system states.

Researchers in computer science, hybrid control theory, system health management, and human-system interaction have become quite familiar with the state-space explosion problem, and they have begun to do something about it. One line of work that seems promising involves sophisticated physical modeling. In their article "Classification of Physical Interactions between Two Subjects," Ruzena Bajcsy and colleagues, for example, are trying to solve theoretical and practical problems of interacting systems with complex nonlinear dynamics. This work primarily concerns complex physical interactions. Mirco Tribastone and Stephen Gilmore in "Automatic Translation of UML Sequence Diagrams into PEPA Models," on the other hand, are interested in complex communication and control interactions as represented by UML diagrams.

For our thematic purposes, however, these two efforts represent an emerging direction that could help reduce the gaps Parnas has described. The methods that Bajcsy and colleagues use for physical modeling are not far removed from methods that are equally applicable to hybrid control systems. The Performance Evaluation Process Algebra methodology of Tribastone and Gilmore, while firmly rooted in formal methods, has recently been extended to biology, chemistry, and other areas of science and engineering. Both of these efforts illustrate the current trend toward integrating discrete and continuous mathematics, providing a more flexible tool-kit for analyzing, designing, and controlling complex systems. For more information on this topic, please take a look at these related links.

Michael ShaftoMichael Shafto is a deputy chief technologist at the NASA Ames Research Center. Contact him at



Page Ratings Page Ratings

Average (0 Votes)

Article Comments

Please login to post comments.

What's New

Seven Digital Steps to Avoid Utter Hell
Human civilization faces dramatic challenges that digital technology can help to resolve. More »

Trust and the Internet
The Internet's nearly 2 billion users probably trust Internet applications more than they should. We should improve our security practices so as to mitigate risk and engender justifiable trust in the system. More »

How to Do Application Logging Right
As threats shift toward applications and more companies struggle with compliance mandates, the need for useful, comprehensive application logging can only increase. Here's some guidance on application logging. More »

It's Time to Eat! Using Mobile Games to Promote Healthy Eating
Time to Eat, a mobile-phone-based game, motivates children to practice healthy eating habits. An examination of the game's design provides insight into the potential of deploying health games on mobile phones. More »

Wireless Interconnect and the Potential for Carbon Nanotubes
Excellent emission and absorption characteristics make CNTs a promising optical approach to on-chip wireless communication. More »

The Case for Full-Throttle Computing: An Alternative to Datacenter Design Strategy
Datacenters can minimize the total computing costs by consolidating latency-sensitive workloads on large servers and filling any remaining capacity with batch-like workloads. More »

In Memoriam: Jim Thomas, 1946–2010
Friends and colleagues celebrate the life and career of industry luminary Jim Thomas. More »

Finding What You Want
When we adopt augmentative technologies, we usually find that we have to adjust our ideas, goals, and habits to fit our new tool. More »

Enabling Autonomous Exploration via the Solar System Internet
Space missions typically operate via direct communications to and from Earth. Different protocols and processes are needed to support information sharing not relayed via Earth. More »

We're All in This Together
Steve Berczuk interviews Yi Lv about the change process of introducing Scrum into organizations with different cultural, geographic, and size attributes. More »

Accelerating the Media Business with MPEG Extensible Middleware
The MXM protocols and APIs support rapid deployment of media applications, providing efficient access to individual system components and improved portability. More »

Reproducible Research Roundtable
Roundtable participants identified ways of making computational research details readily available, which is a crucial step in addressing the current credibility crisis. More »

Lies—Damn Lies—and the Internet
The "truth bias" gives spammers a head start in computer-mediated communication: Humans are just too gullible. More »