Search

We present a new procedure for testing satisfiability (over the reals) of a conjunction of polynomial equations. There are three possible return values for our procedure: it either returns a model for the input formula, or it says that the input is unsatisfiable, or it fails because the applicability condition for the procedure, called the eigen-condition, is violated. For the class of constraints where the eigen-condition holds, our procedure is a decision procedure. We describe satisfiability-preserving transformations that can potentially convert problems into a form where eigen-condition holds. We experimentally evaluate the procedure on constraints generated by template-based verification and synthesis procedures.

When machine learning (ML) models are used in safety-critical or mission-critical applications (e.g., self driving cars, cyber security, surgical robotics), it is important to ensure that they provide some high-level guarantees (e.g., safety, liveness). We introduce a paradigm called Trusted Machine Learning (TML) for making ML models more trustworthy. We use Markov Decision Processes (MDPs) as the underlying dynamical model and outline three TML approaches: (1) Model Repair, wherein we modify the learned model directly; (2) Data Repair, wherein we modify the data so that re-learning from the modified data results in a trusted model; and (3) Reward Repair, wherein we modify the reward function of the MDP to satisfy the specified logical constraint. We show how these repairs can be done efficiently for probabilistic models (e.g., MDP) when the desired properties are expressed in some appropriate fragment of logic such as temporal logic (for example PCTL, i.e., Probabilistic Computation Tree Logic), first order logic or propositional logic. We illustrate our approaches on case studies from multiple domains, e.g., car controller for obstacle avoidance, and a query routing controller in a wireless sensor network.

Experimenting with futuristic computer workstation design and specifically tailored application models can yield useful insights and result in exciting ways to increase efficiency, effectiveness, and satisfaction for computer users. Designing and building a computer workstation that can track a user’s gaze; sense proximity to the touch surface; and support multi-touch, face recognition etc meant overcoming some unique technological challenges. Coupled with extensions to commonly used applications to report user interactions in a meaningful way, the workstation will allow the development of a rich contextual user model that is accurate enough to enable benefits, such as contextual filtering, task automation, contextual auto-fill, and improved understanding of team collaborations. SRI’s bRIGHT workstation was designed and built to explore these research avenues and investigate how such a context model can be built, identify the key implications in designing an application model that best serves these goals, and discover other related factors. This paper conjectures future research that would support the development of a collaborative context model that could leverage similar benefits for groups of users.

Requirements are informal and semi-formal descriptions of the expected behavior of a complex system from the viewpoints of its stakeholders customers, users, operators, designers, and engineers. However, for the purpose of design, testing, and verification for critical systems, we can transform requirements into formal models that can be analyzed automatically. ARSENAL is a framework and methodology for systematically transforming natural language NL requirements into analyzable formal models and logic specifications. These models can be analyzed for consistency and implementability. The ARSENAL methodology is specialized to individual domains, but the approach is general enough to be adapted to new domains.

In this paper we describe the use of the rewriting logic based Maude tool to model and analyze mammalian signaling pathways. We discuss the representation of the underlying biological concepts and events and describe the use of the new search and model checking capabilities of Maude 2.0 to analyze the modeled network. We also discuss the use of Maude's reflective capability for meta modeling and analyzing the models themselves. The idea of symbolic biological experiments opens up an exciting new world of challenging applications for formal methods in general and for rewriting logic based formalisms in particular.

We formalize the Dolev-Yao model of security protocols, using a notation based on multiset rewriting with existentials. The goals are to provide a simple formal notation for describing security protocols, to formalize the assumptions of the Dolev-Yao model using this notation, and to analyze the complexity of the secrecy problem under various restrictions. We prove that, even for the case where we restrict the size of messages and the depth of message encryption, the secrecy problem is undecidable for the case of an unrestricted number of protocol roles and an unbounded number of new nonces. We also identify several decidable classes, including a DEXP-complete class when the number of nonces is restricted, and an NP-complete class when both the number of nonces and the number of roles is restricted. We point out a remaining open complexity problem, and discuss the implications these results have on the general topic of protocol analysis.

The goal of the BioSPICE program is to create a framework that provides biologists access to the most current computational tools. At the program midpoint, the BioSPICE member community has produced a software system that comprises contributions from approximately 20 participating laboratories integrated under the BioSPICE Dashboard and a methodology for continued software integration. These contributed software modules are the BioSPICE Dashboard, a graphical environment that combines Open Agent Architecture and NetBeans software technologies in a coherent, biologist-friendly user interface. The current Dashboard permits data sources, models, simulation engines, and output displays provided by different investigators and running on different machines to work together across a distributed, heterogeneous network. Among several other features, the Dashboard enables users to create graphical workflows by configuring and connecting available BioSPICE components. Anticipated future enhancements to BioSPICE include a notebook capability that will permit researchers to browse and compile data to support model building, a biological model repository, and tools to support the development, control, and data reduction of wet-lab experiments. In addition to the BioSPICE software products, a project website supports information exchange and community building.

We describe a technique for addressing individual nanoscale wires with microscale control wires without using lithographic-scale processing to define nanoscale dimensions. Such a scheme is necessary to exploit sublithographic nanoscale storage and computational devices. Our technique uses modulation doping to address individual nanowires and self-assembly to organize them into nanoscale-pitch decoder arrays. We show that if coded nanowires are chosen at random from a sufficiently large population, we can ensure that a large fraction of the selected nanowires have unique addresses. For example, we show that N lines can be uniquely addressed over 99% of the time using no more than /spl lceil/2.2log/sub 2/(N)/spl rceil/+11 address wires. We further show a hybrid decoder scheme that only needs to address N=O(W/sub litho-pitch//W/sub nano-pitch/) wires at a time through this stochastic scheme; as a result, the number of unique codes required for the nanowires does not grow with decoder size. We give an O(N/sup 2/) procedure to discover the addresses which are present. We also demonstrate schemes that tolerate the misalignment of nanowires which can occur during the self-assembly process.

This paper is a tribute to Jose Meseguer, from the rest of us in the Maude team, reviewing the past, the present, and the future of the language and system with which we have been working for around two decades under his leadership. After reviewing the origins and the language’s main features, we present the latest additions to the language and some features currently under development. This paper is not an introduction to Maude, and some familiarity with it and with rewriting logic are indeed assumed.

Despite advances in recent years in the area of mandatory access control in database systems, today's information repositories remain vulnerable to inference and data association attacks that can result in serious information leakage. Without support for coping against these attacks, sensitive information can be put at risk because of release of other (less sensitive) related information. The ability to protect information diclosure against such improper leakage would be of great benefit to governmental, public, and private institutions, which are, today more than ever, required to make portions of their data available for external release. In this paper we address the problem of classifying information by enforcing explicit data classification as well as inference and association constraints. We formulate the problem of determining a classification that ensures satisfaction of the constraints, while at the same time guaranteeing that information will not be overclassified. We present an approach to the solution of this problem and give an algorithm implementing it which is linear in simple cases, and quadratic in the general case. We also analyze a variant of the problem that is NP-complete.

Natural language (supplemented with diagrams and some mathematical notations) is convenient for succinct communication of technical descriptions between the various stakeholders (e.g., customers, designers, implementers) involved in the design of software systems. However, natural language descriptions can be informal, incomplete, imprecise and ambiguous, and cannot be processed easily by design and analysis tools. Formal languages, on the other hand, formulate design requirements in a precise and unambiguous mathematical notation, but are more difficult to master and use. We propose a methodology for connecting semi-formal requirements with formal descriptions through an intermediate representation. We have implemented this methodology in a research prototype called Automatic Requirements Specification Extraction from Natural Language (ARSENAL). The main novelty of ARSENAL lies in its ability to generate a fully-specified complete formal model automatically from natural language requirements. ARSENAL extracts relations from text using semantic parsing and progressively refines them over multiple stages to create a final composite model. Currently, ARSENAL generates formal models in linear-time temporal logic (LTL), but the approach can be adapted for other models, e.g., probabilistic relational models like Markov Logic Networks (MLN). The formal models of the requirements can be used to check important design and system properties, e.g., consistency, satisfiability, realizability. ARSENAL has a modular and flexible architecture that facilitates porting it from one domain to another. We evaluated ARSENAL on complex requirements from two real-world case studies: the Time-Triggered Ethernet (TTEthernet) communication platform used in space, and FAA-Isolette infant incubators used in NICU. We systematically evaluated various aspects of ARSENAL -- the accuracy of the natural language processing stage, the degree of automation, and robustness to noise.

We present an approach for detecting sensor spoofing attacks on a cyber-physical system. Our approach consists of two steps. In the first step, we construct a safety envelope of the system. Under nominal conditions (that is, when there are no attacks), the system always stays inside its safety envelope. In the second step, we build an attack detector: a monitor that executes synchronously with the system and raises an alarm whenever the system state falls outside the safety envelope. We synthesize safety envelopes using a modifed machine learning procedure applied on data collected from the system when it is not under attack. We present experimental results that show effectiveness of our approach, and also validate the several novel features that we introduced in our learning procedure.

The development of new classes of distributed applications such as telephony, remote video, and virtual reality introduces new quality requirements that make inadequate even the current best-effort service model provided by international networks. Recent research activity has proposed new approaches to accommodate these new application requirements. While exploiting the resource needs of different applications to use the network resources efficiently, these approaches require the maintenance of a considerable amount of state information at the network nodes. Correctness and availability of such information are the basic requirements for the proper working of the network. In this paper we present a system, called Global Infrastructure Protection System (GIPS), to control improper modifications to this state information. We illustrate the GIPS's architecture and identify topology conditions to guarantee the distributed fault tolerant detection of anomalies. The system is based on the use of a hierarchical structure to organize and maintain the information at each node. Improper network states are described through rules that characterize state information updates that may result anomalous (or uncommon) with respect to the network status, past events occurred, or statistical measures. We introduce a notation to represent state information coming from heterogeneous protocols, and statistical operators to examine the history of state updates accumulated during operation. Finally, we present some examples using our notation to express heuristical rules detecting anomalous operations in a network.

Although there have been attempts to develop code transformations that yield tamper-resistant software, no reliable software-only methods are known. This paper studies the hardware implementation of a form of execute-only memory (XOM) that allows instructions stored in memory to be executed but not otherwise manipulated. To support XOM code we use a machine that supports internal compartments---a process in one compartment cannot read data from another compartment. All data that leaves the machine is encrypted, since we assume external memory is not secure. The design of this machine poses some interesting trade-offs between security, efficiency, and flexibility. We explore some of the potential security issues as one pushes the machine to become more efficient and flexible. Although security carries a performance penalty, our analysis indicates that it is possible to create a normal multi-tasking machine where nearly all applications can be run in XOM mode. While a virtual XOM machine is possible, the underlying hardware needs to support a unique private key, private memory, and traps on cache misses. For efficient operation, hardware assist to provide fast symmetric ciphers is also required.

We present a new procedure for testing satisfiability (over the reals) of a conjunction of polynomial equations. There are three possible return values for our procedure: it either returns a model for the input formula, or it says that the input is unsatisfiable, or it fails because the applicability condition for the procedure, called the eigen-condition, is violated. For the class of constraints where the eigen-condition holds, our procedure is a decision procedure. We describe satisfiability-preserving transformations that can potentially convert problems into a form where eigen-condition holds. We experimentally evaluate the procedure and discuss applicability.

A reconfigurable fault tolerant system achieves the attributes of dependability of operations through fault detection, fault isolation and reconfiguration, typically referred to as the FDIR paradigm. Fault diagnosis is a key component of this approach, requiring an accurate determination of the health and state of the system. An imprecise state assessment can lead to catastrophic failure due to an optimistic diagnosis, or conversely, result in underutilization of resources because of a pessimistic diagnosis. Differing from classical testing and other off-line diagnostic approaches, we develop procedures for maximal utilization of the system state information to provide for continual, on-line diagnosis and reconfiguration capabilities as an integral part of the system operations. Our diagnosis approach, unlike existing techniques, does not require administered testing to gather syndrome information but is based on monitoring the system message traffic among redundant system functions. We present comprehensive on-line diagnosis algorithms capable of handling a continuum of faults of varying severity at the node and link level. Not only are the proposed algorithms on-line in nature, but are themselves tolerant to faults in the diagnostic process. Formal analysis is presented for all proposed algorithms. These proofs offer both insight into the algorithm operations and facilitate a rigorous formal verification of the developed algorithms.

We present a methodology for the probabilistic modeling of failure dependencies in large, complex systems using Markov Logic Networks (MLNs), a state-of-the-art probabilistic relational modeling technique in machine learning. We illustrate this modeling methodology on example system architectures, and show how the the Probabilistic Consistency Engine (PCE) tool can create and analyze failure-dependency models. We compare MLN-based analysis with analytical symbolic analysis to validate our approach. The latter method yields bounds on the expected system behaviors for different component-failure probabilities, but it requires closed-form representations and is therefore often an impractical approach for complex system analysis. The MLN-based method facilitates techniques of early design analysis for reliability (e.g., probabilistic sensitivity analysis). We analyze two examples - a portion of the Time-Triggered Ethernet (TTEthernet) communication platform used in space, and an architecture based on Honeywell's Cabin Air Compressor(CAC) - that highlight the value of the MLN-based approach for analyzing failure dependencies in complex cyber-physical systems.

§ 1. Introduction. Perhaps the most surprising recent development in complexity theory is the discovery that the class NP can be characterized using a form of randomized proof checker that only examines a constant number of bits of the “proof” that a string is in a language [6, 5, 31, 3, 4]. More specifically, writing ∣x∣ for the length of a string x, a language L in the class NP of languages recognizable in Nondeterministic polynomial time is traditionally given by a polynomial p and a polynomial-time predicate P such that a string x is in L iff there is some string y satisfying P(x, y), where ∣y∣ ≤ p (∣x∣). Intuitively, we can think of a string y as a possible proof that x ϵ L, with the predicate P some kind of proof checker that distinguishes good proofs from bad ones. A string x is therefore in a language L ϵ NP if there is a short proof that x ϵ L, and not in L otherwise. The surprising discovery is that the deterministic proof checker that reads the entire input and proof can be replaced by a probabilistic verifier that on input x and possible proof y, where y is presented in a certain way, flips at most O (log ∣x∣) coins and reads at most a constant number of bits of x and y. Obviously, a probabilistic verifier that does not read the whole proof will sometimes make mistakes. However, the surprising and essentially non-intuitive mathematical fact is that for each language L in NP, it is possible to find a polynomial q and verifier V flipping a logarithmic number of coins and reading a constant number of bits such that, for any x ϵ L, there exists y with ∣y∣ ≤ q(∣x∣) and with V (x, y) accepting with probability 1 and, for x ∉ L, there is no y with ∣y∣ ≤ q(∣x∣) and with V (x, y) accepting with probability ≥ 1/4. This idea canalsobeextended to PSPACE [10, 9], using a game that alternates between two players instead of a proof presented by a “single player.”

Proof search in linear logic is known to be difficult: the provability of propositional linear logic formulas is undecidable. Even without the modalities, multiplicative-additive fragment of propositional linear logic, mall , is known to be PSPACE-complete, and the pure multiplicative fragment, mll , is known to be np -complete. However, this still leaves open the possibility that there might be proof search heuristics (perhaps involving randomization) that often lead to a proof if there is one, or always lead to something close to a proof. One approach to these problems is to study strategies for proof games. A class of linear logic proof games is developed, each with a numeric score that depends on the number of certain preferred axioms used in a complete or partial proof tree. Using recent techniques for proving lower bounds on optimization problems, the complexity of these games is analyzed for the fragment mll extended with additive constants and for the fragment MALL. It is shown that no efficient heuristics exist unless there is an unexpected collapse in the complexity hierarchy.

This paper introduces the basic concepts of the rewriting logic language Maude and discusses its implementation. Maude is a wide-spectrum language supporting formal specification, rapid prototyping, and parallel programming. Maude's rewriting logic paradigm includes the functional and object-oriented paradigms as sublanguages. The fact that rewriting logic is reflective leads to novel metaprogramming capabilities that can greatly increase software reusability and adaptability. Control of the rewriting computation is achieved through internal strategy languages defined inside the logic. Maude's rewrite engine is designed with the explicit goal of being highly extensible and of supporting rapid prototyping and formal methods applications, but its semi-compilation techniques allow it to meet those goals with good performance.

The decision problem is studied for the nonmodal or multiplicative-additive fragment of first-order linear logic. This fragment is shown to be NEXPTIME-hard. The hardness proof combines Shapiro's logic programming simulation of nondeterministic Turing machines with the standard proof of the PSPACE-hardness of quantified boolean formula validity, utilizing some of the surprisingly powerful and expressive machinery of linear logic.

Linear logic is a resource-aware logic that is based on an analysis of the classical proof rules of contraction (copying) and weakening (throwing away). In this paper we study the decision problem for the multiplicative fragment of linear logic without quantifiers or propositions: the constant-only case. We show that this fragment is NP-complete. Earlier work by Kanovich showed that propositional multiplicative linear logic is NP-complete. With Natarajan Shankar, the first author developed a simplified proof for the propositional case. The structure of this simplified proof is utilized here with a new encoding which uses only constants. The end product is the somewhat surprising result that simply evaluating expressions in true, false, and, and or in multiplicative linear logic (1, ⊥ ⊗ ) is NP-complete. By conversativity results not proven here, the NP-hardness of larger fragments of linear logic follows.

Modern state-of-the-art nanodevices exhibit remarkable electronic properties, but the current assembly techniques yield very high defect and fault rates. Static errors can be addressed at fabrication time by testing and reconfiguration, but soft errors are problematic since their arrival rates are expected to vary over the lifetime of a part. Usual designs consider error correcting codes that tolerate the maximum failure rate expected over the entire lifetime. In this paper, we propose using a special variant of low-density parity codes (LDPCs) — Euclidean Geometry LDPC (EG-LDPC) codes — to enable dynamic changes in the level of fault tolerance. EG-LDPC codes have high error correcting ability (for large words they can approach the optimal Shannon limit) and they are sparse (circuit implementation requires small fan-in). In addition, a special property of EG-LDPC codes enables us to dynamically adjust the error correcting capacity for improved system performance (e.g., lower power consumption) during periods of expected low fault arrival rate. We present a system architecture for nanomemory based on nanoPLA building blocks using EG-LDPCs, where the encoder/decoder could also have faults, and analyze the fault detection and correction capabilities considering dynamic fault tolerance.

An emerging generation of mission-critical systems employs distributed, dynamically reconfigurable open architectures. These systems may include a variety of devices that sense and affect their environment and the configuration of the system itself. We call such systems Networked Cyber-Physical Systems (NCPS). NCPS can provide complex, situation-aware, and often critical services in applications such as distributed sensing and surveillance, crisis response, self-assembling structures or systems, networked satellite and unmanned vehicle missions, or distributed critical infrastructure monitoring and control. In this paper we lay out research directions centered around a new paradigm for the design of NCPS based on a notion of software fractionation that we are currently exploring which can serve as the basis for a new generation of runtime assurance techniques. The idea of software fractionation is inspired by and complementary to hardware fractionation -- the basis for the fractionated satellites of DARPA's F6 program. Fractionated software has the potential of leading to software that is more robust, leveraging both diversity and redundancy. It raises the level of abstraction at which assurance techniques are applied. We specifically propose research in just-in-time verification and validation techniques, which are agile -- adapting to changing situations and requirements, and efficient -- focusing on properties of immediate concern in the context of locally reachable states, thus largely avoiding the state space explosion problem. We propose an underlying reflective architecture that maintains models of itself, the environment, and the mission that is key for adaptation, verification, and validation.

A new generation of mission-critical systems is emerging that employs distributed, dynamically reconfigurable open architectures. These systems may include a variety of devices that sense and affect their environment and the configuration of the system itself. We call such systems Networked Cyber- Physical Systems (NCPS). NCPS can provide complex, situation-aware, and often critical services in applications such as distributed sensing and surveillance, crisis response, self-assembling structures or systems, networked satellite and unmanned vehicle missions, or distributed critical infrastructure monitoring and control. NCPS are of special interest to the Navy in view of the increasing need for coordination of a wide spectrum of maritime sensing and information gathering technologies, ranging from smart mobile buoys to autonomous underwater vehicles and their integration into a global network with maritime, space, and ground domains. NCPS must be reactive and maintain an overall situation, location, and time awareness that emerges from the exchange of knowledge. They must achieve system goals through local, asynchronous actions, using (distributed) control loops through which the environment provides essential feedback. They must deal with uncertainty and partial knowledge, and be capable of a wide spectrum of operations between autonomy and cooperation to adapt to resource constraints and disruptions in communication. General principles and tools are needed for building robust, effective NCPS. A key observation is that the current level of abstraction at which software and systems are designed is a barrier to innovation at the hardware and networking level and at the same time is not suitable to enable rapid design/deployment or distributed control of large-scale distributed software systems and in particular the flexibility, dynamically reconfigurable, mission-critical NCPS of the future.

Linear logic, introduced by Girard, is a refinement of classical logic with a natural, intrinsic accounting of resources. This accounting is made possible by removing the ‘structural’ rules of contraction and weakening, adding a modal operator and adding finer versions of the propositional connectives. Linear logic has fundamental logical interest and applications to computer science, particularly to Petri nets, concurrency, storage allocation, garbage collection and the control structure of logic programs. In addition, there is a direct correspondence between polynomial-time computation and proof normalization in a bounded form of linear logic. In this paper we show that unlike most other propositional (quantifier-free) logics, full propositional linear logic is undecidable. Further, we prove that without the modal storage operator, which indicates unboundedness of resources, the decision problem becomes PSPACE-complete. We also establish membership in NP for the multiplicative fragment, NP-completeness for the multiplicative fragment extended with unrestricted weakening, and undecidability for fragments of noncommutative propositional linear logic.

The continued scaling of device dimensions is leading toward devices where only a handful of dopant atoms or charges can make the difference between a one and a zero in the of state of represented bit, by enhancing or depleting channel conduction. Thus very minor static imperfections in dopant distribution, dielectric properties, or device geometry, and dynamic conditions associated with heat, radiation, or aging can perturb a device out of specification and cause electrical errors. Thus we might expect to soon see devices with millions of static defects and thousands of soft errors in very short time periods. Both static defects and dynamic faults at these scales present huge challenges. Classical methods for fault or defect tolerance at a higher level of architecture (eg. N-modular-redundancy) can be impractically expensive, and some approaches to diagnosis and reconfiguration require immense reliable memories or impractical test and reconfiguration times. Efficient and effective means are needed that exploit structure inherent in one layer of architecture to provide key properties to enable reliable execution at other levels.

Maude is a high-performance reflective language and system supporting both equational and rewriting logic specification and programming for a wide range of applications, and has a relatively large worldwide user and open-source developer base. This paper introduces novel features of Maude 2.4 including support for unification and narrowing. Unification is supported in Core Maude, the core rewriting engine of Maude, with commands and metalevel functions for order-sorted unification modulo some frequently occurring equational axioms. Narrowing is currently supported in its Full Maude extension. We also give a brief summary of the most important features of Maude 2.4 that were not part of Maude 2.0 and earlier releases. These features include communication with external objects, a new implementation of its module algebra, and new predefined libraries. We also review some new Maude applications.

A network of reactions is a commonly used paradigm for representing knowledge about a biological process. How does one understand such generic networks and answer queries using them? In this paper, we present a novel approach based on translation of generic reaction networks to Boolean weighted MaxSAT. The Boolean weighted MaxSAT instance is generated by encoding the equilibrium configurations of a reaction network by weighted boolean clauses. The important feature of this translation is that it uses reactions, rather than the species, as the boolean variables. Existing weighted MaxSAT solvers are used to solve the generated instances and find equilibrium configurations. This method of analyzing reaction networks is generic, flexible and scales to large models of reaction networks. We present a few case studies to validate our claims.

During the development of the Maude system we have put special emphasis on the creation of metaprogramming facilities to allow the generation of execution environments for a wide variety of languages and logics. The first most obvious area where Maude can be used as a metalanguage is in building language extensions for Maude itself. Our experience in this regard—first reported in [107], and further documented in [108, 98, 99, 109]—is very encouraging.

This chapter describes the equational specification in Maude of a series of typical data structures, complementing in this way the list and set data structures provided as predefined modules in Maude and described in Section 9.12.

This chapter explains how to use the facilities provided by the predefined modules META-LEVEL and LOOP-MODE for constructing user interfaces and metalanguage applications, in which Maude is used not only to define a domain-specific language or tool, but also to build an environment for the given language or tool. In such applications, the LOOP-MODE module can be used to handle the input/ output and to maintain the persistent state of the language environment or tool. This chapter also describes an approach based on actors to endow Maude with interactive capabilities.

Informally, a reflective logic is a logic in which important aspects of its metatheory can be represented at the object level in a consistent way, so that the object-level representation correctly simulates the relevant metatheoretic aspects. In other words, a reflective logic is a logic which can be faithfully interpreted in itself. Maude’s language design and implementation make systematic use of the fact that rewriting logic is reflective [66, 56, 67, 68]. This makes the metatheory of rewriting logic accessible to the user in a clear and principled way. However, since a naive implementation of reflection can be computationally expensive, a good implementation must provide efficient ways of performing reflective computations. This chapter explains how this is achieved in Maude through its predefined META-LEVEL module, that can be found in the prelude.maude file.

In Full Maude, concurrent object-oriented systems can be defined by means of object-oriented modules—introduced by the keyword omod...endom—using a syntax more convenient than that of system modules, because it assumes acquaintance with the basic entities, such as objects, messages and configurations, and supports linguistic distinctions appropriate for the object-oriented case.

Distributed systems can be naturally modeled in Maude as multisets of entities, loosely coupled by some suitable communication mechanism. An important example is object-based distributed systems in which the entities are objects, each with a unique identity, and the communication mechanism is message passing.

In Section 4.4.1 we have introduced equational attributes as a means of declaring some equational properties of binary operators that allow Maude to use these properties efficiently in a built-in way in parsing and in matching modulo such equational axioms. We recall that Maude supports the following equational attributes: assoc (associativity), comm (commutativity), id:\(\langle Term\rangle\) (identity, with the corresponding term for the identity element), with variations for left identity and right identity, and idem (idempotency).

This chapter introduces the basic syntactic ingredients of all Maude specifications: identifiers, module names, sort names, and operator declarations. Other syntactic parts of Maude specifications, like equations and rules, will appear in the following chapters.

A rewrite theory, specified in Maude as a system module, provides an executable mathematical model of a concurrent system. We can use the Maude specification to simulate the concurrent system so specified. But we can do more. Under appropriate conditions we can check that our mathematical model satisfies some important properties, or obtain a useful counterexample showing that the property in question is violated. This kind of model-checking analysis can be quite general. Chapter 13 will explain how, under appropriate finite reachability assumptions, we can model check any linear time temporal logic (LTL) property of a system specified in Maude as a system module. This chapter focuses on a simpler, yet very useful, model-checking capability, namely, the model checking of invariants, which can be accomplished just by using the search command.

This chapter gives an overview of some application areas of rewriting logic and Maude, with pointers to papers and web sites where more information can be found. Some of the material is adapted, with some modifications and extensions, from [199, 3, 217]. Since Maude is a general-purpose declarative programming language, there is in principle no limit to the applications that could be developed using it. Therefore, the areas discussed, although quite diverse, are only a sample of types of applications for which Maude seems particularly well suited. But there are many others. For example, the availability of built-in internet sockets in Maude 2.2 (see Section 11.4.1) opens up interesting possibilities for a new style of declarative internet programming which have already begun to be exploited (see Chapter 16).

There are several approaches to debugging and optimizing Maude programs: tracing, term coloring, using the debugger, and using the profiler.

As pointed out in Section 1.4, given a Maude system module, we can distinguish two levels of specification: a system specification level, provided by the rewrite theory specified by that system module which defines the behavior of the system, and a property specification level, given by some property (or properties) φ that we want to state and prove about our module.