Proc R Soc A

mathematical modeling, artificial intelligence, category theory

John D. Foley

# Operads for complex system design specification, analysis and synthesis

John D. Foley1 Spencer Breiner2 Eswaran Subrahmanian2,3 and John M. Dusel1
1Metron, Inc., 1818 Library St., Reston, VA, USA
2US National Institute of Standards and Technology, Gaithersburg, MD, USA
3Carnegie Mellon University, Pittsburgh, PA, USA<EMAIL_ADDRESS>
###### Abstract

As the complexity and heterogeneity of a system grows, the challenge of
specifying, documenting and synthesizing correct, machine-readable designs
increases dramatically. Separation of the system into manageable parts is
needed to support analysis at various levels of granularity so that the system
is maintainable and adaptable over its life cycle. In this paper, we argue
that operads provide an effective knowledge representation to address these
challenges. Formal documentation of a syntactically correct design is built up
during design synthesis, guided by semantic reasoning about design
effectiveness. Throughout, the ability to decompose the system into parts and
reconstitute the whole is maintained. We describe recent progress in effective
modeling under this paradigm and directions for future work to systematically
address scalability challenges for complex system design.

###### keywords:

complex systems, system design, automated reasoning, compositionality, applied
category theory, operads

††journal: rspa

##  1 Introduction

We solve complex problems by separating them into manageable parts [2, 86].
Human designers do this intuitively, but details can quickly overwhelm
intuition. Multiple aspects of a problem may lead to distinct decompositions
and complementary models of a system–e.g. competing considerations for
cyberphysical systems [63, 87]–or simulation of behavior at many levels of
fidelity–e.g. in modeling and simulation [88]–leading to a spectrum of models
which are challenging to align. We argue that operads, formal tools developed
to compose geometric and algebraic objects, are uniquely suited to separate
complex systems into manageable parts and maintain alignment across
complementary models.

(1)(2)(3)SyntaxAbstractsystem
designs$\mapsto$ComposingdesignsSemanticsComputationalmodels$\mapsto$Composingmodels

Figure 1: Separating concerns with operads: (1) Composition separates
subsystem designs (green boundaries –); (2) Functorial semantics separate
abstract systems from computational model instances (red boundaries –); (3)
Natural transformations separate and align (blue boundary –) complementary
models ($\square$,  $\diamond$ ).

Operads provide three ways to separate concerns for complex systems: (1)
designs for subsystems are separated into composable modules; (2) syntactic
designs to compose systems are separated from the semantic data that model
them; and (3) separate semantic models can be aligned to evaluate systems in
different ways. The three relationships are illustrated in Figure 1.

Hierarchical decomposition (Fig. 1, –) is nothing new. Both products and
processes are broken down to solve problems from design to daily maintenance.
Operads provide a precise language to manage complex modeling details that the
intuitive–and highly beneficial–practice of decomposition uncovers, e.g.,
managing multiple, complementary decompositions and models.

Operads separate the syntax to compose subsystems from the semantic data
modeling them (Fig. 1, –). Syntax consists of abstract “operations” to design
the parts and architecture of a system. Semantics define how to interpret and
evaluate these abstract blueprints. Operad syntax is typically lightweight and
declarative. Operations can often be represented both graphically and
algebraically (Fig. 4), formalizing intuitive design diagrams. Operad
semantics model specific aspects of a system and can range from fast to
computationally expensive.

The most powerful way operads separate is by aligning complementary models
while maintaining compatibility with system decompositions (Fig. 1, –).
Reconciling complementary models is a persistent and pervasive issue across
domains [84, 26, 29, 66, 63, 27, 79, 69]. Historically, Eilenberg & Mac Lane
[34] invented _natural transformations_ to align computational models of
topological spaces. Operads use natural transformations to align hierarchical
decompositions, which is particularly well-suited to system design.

This paper articulates a uniform and systematic foundation for system design
and analysis. In essence, the syntax of an operad defines _what can be_ put
together, which is a prerequisite to decide _what should be_ put together.
Interfaces define which designs are _syntactically_ feasible, but key
_semantic_ information must be expressed to evaluate candidate designs.
Formulating system models within operad theory enforces the intellectual
hygiene required to make sure that different concerns stay separated while
working together to solve complex design problems.

We note five strengths of this foundation that result from the three ways
operads separate a complex problem and key sections of the paper that provide
illustrations.

Expressive, unifying meta-language. A meta- or multi-modeling [18] language is
needed to express and relate multiple representations. The key feature of
operad-based meta-modeling is its focus on coherent mappings between models
(Fig. 1, –, –), as opposed to a universal modeling context, like UML, OWL,
etc., which is inevitably under or over expressive for particular use cases.
Unification allows complementary models to work in concert, as we see in Sec.
5 for function and control. Network operads—originally developed to design
systems—were applied to task behavior. This power to unify and express becomes
especially important when reasoning across domains with largely independent
modeling histories; compare, e.g., [87]. (22.2, 22.4, 3, 44.1, 5)

Minimal data needed for specification. Data needed to set up each
representation of a problem is minimal in two ways: (1) any framework must
provide similar, generative data; and (2) each level only needs to specify
data relevant to that level. Each representation is self-sufficient and can be
crafted to efficiently address a limited portion of the full problem. The
modeler can pick and choose relevant representations and extend the meta-model
as needed. (4, 66.2)

Efficient exploration of formal correct designs. An operad precisely defines
how to iteratively construct designs or adapt designs by substituting
different subsystems. Constructing syntactically invalid designs is not
possible, restricting the relevant design space, and correctness is preserved
when moving across models. Semantic reasoning guides synthesis–potentially at
several levels of detail. This facilitates lazy evaluation: first syntactic
correctness is guaranteed, then multitudes of coarse models are explored
before committing to later, more expensive evaluations. The basic moves of
iteration, substitution, and moving across levels constitute a rich framework
for exploration. We obtain not only an effective design but also formal
documentation of the models which justify this choice. (22.2–2.3, 6, 77.5)

Separates representation from exploitation. Operads and algebras provide
structure and representation for a problem. Exploitation of this structure and
representation is a separate concern. As Herbert Simon noted during his Nobel
Prize speech [85]: “…decision makers can satisfice either by finding optimum
solutions for a simplified world, or by finding satisfactory solutions for a
more realistic world.” This is an either-or proposition for a simple
representation. By laying the problem across multiple semantic models, useful
data structures for each model–e.g. logical, evolutionary or planning
frameworks–can be exploited by algorithms that draw on operad-based iteration
and substitution. (6, 77.5)

Hierarchical analysis and synthesis. Operads naturally capture options for the
hierarchical decomposition of a system, either within a semantic model to
break up large scale problems or across models to gradually increase modeling
fidelity. (22.1, 5,66.3, 77.1)

###  1.1 Contribution to design literature

There are well-known examples of the successful exploitation of separation.
For instance, electronic design automation (EDA) has had decades of success
leveraging hierarchical separation of systems and components to achieve very
large scale integration (VLSI) of complex electronic systems [16, 36, 82]. We
do not argue that operads are needed for extremely modular domains. Instead,
operads may help broaden the base of domains that benefit from separation and
provide a means to integrate and unify treatment across domains. On the other
hand, for highly integral domains the ability to separate in practically
useful ways may be limited [89, 102]. The recent applications we present help
illustrate where operads may prove useful in the near and longer term; see
77.3 for further discussion.

Compared to related literature, this article is application driven and outward
focused. Interest in applying operads and category theory to systems
engineering has surged [21, 38, 53, 67, 71, 94] as part of a broader wave
applying category theory to design databases, software, proteins, etc. [22,
31, 40, 46, 91, 92, 93]. While much of loc. cit. matches applications to
existing theoretical tools, the present article describes recent _application
driven_ advancements and overviews _specific methods_ developed to address
challenges presented by domain problems. We introduce operads for design to a
general scientific audience by explaining what the operads do relative to
broadly applied techniques and how specific domain problems are modeled.
Research directions are presented with an eye towards opening up
interdisciplinary partnerships and continuing application driven
investigations to build on recent insights.

###  1.2 Organization of the paper

The present article captures an intermediate stage of technical maturity:
operad-based design has shown its practicality by lowering barriers of entry
for applied practitioners and demonstrating applied examples across many
domains. However, it has not realized its full potential as an applied meta-
language. Much of this recent progress is not focused solely on the analytic
power of operads to separate concerns. Significant progress on explicit
specification of domain models and techniques to automatically synthesize
designs from basic building blocks has been made. Illustrative use cases and
successful applications for design specification, analysis and synthesis
organize the exposition.

Section 2 introduces operads for design by analogy to other modeling
approaches. Our main examples are introduced in Section 3. Section 4 describes
how concrete domains can be specified with minimal combinatorial data,
lowering barriers to apply operads. Section 5 concerns analysis of a system
with operads. Automated synthesis is discussed in Section 6. Future research
directions are outlined in Section 7, which includes a list of open problems.

Ex. 33.1SpecificationSection 4Ex. 33.2 Analysis Section 5Ex. 33.3 Synthesis
Section 6GeneratorsCompositionalityScalability Figure 2: Organization of the
paper around applied examples introduced in Sec. 3.

Notations. Throughout, we maintain the following notional conventions for:

  * •

syntax operads (Fig. 1, left), capitalized calligraphy: $\mathcal{O}$

  * •

types (Fig. 1, edges on left), capitalized teletype:
$\mathtt{X},\mathtt{Y},\mathtt{Z},\ldots$

  * •

operations (Fig. 1, nodes on left), uncapitalized teletype:
$\mathtt{f},\mathtt{g},\mathtt{h},\ldots$

  * •

semantic contexts (Fig. 1, right), capitalized bold:
$\mathbf{Sem},\mathbf{Set},\mathbf{Rel},\dots$

  * •

functors from syntax to semantics (Fig. 1, arrows across red), capitalized
sans serif: $\mathsf{Model}\colon{\mathcal{O}}\to\mathbf{Sem}$;

  * •

alignment of semantic models via natural transformations (Fig. 1, double arrow
across blue), uncapitalized sans serif:
$\mathsf{align}\colon\mathsf{Model_{1}}\Rightarrow\mathsf{Model_{2}}$;

##  2 Applying operads to design

We introduce operads by an analogy, explaining what an operad is and
motivating its usefulness for systems modeling and analysis. The theory [64,
70, 103] pulls together many different intuitions. Here we highlight four
analogies or ‘views’ of an operad: hierarchical representations (tree view),
strongly-typed programming languages (API 111Application Programming Interface
view), algebraic equations (equational view) and system cartography (map-
maker’s view). Each view motivates operad concepts; see Table 1.

The paradigm of this paper is based on a typed operad, also known as a
‘colored operad’ [103] or ‘symmetric multicategory’ [64, 2.2.21]. A typed
operad ${\mathcal{O}}$ has:

  * •

A set $T$ of types.

  * •

Sets of operations
${\mathcal{O}}(\mathtt{X_{1}},\ldots,\mathtt{X_{n}};\mathtt{Y})$ where
$\mathtt{X_{i}},\mathtt{Y}\in T$ and we write
$\mathtt{f}\colon\langle\mathtt{X_{i}}\rangle\to\mathtt{Y}$ to indicate that
$\mathtt{f}\in{\mathcal{O}}(\mathtt{X_{1}},\ldots,\mathtt{X_{n}};\mathtt{Y})$.

  * •

A specific way to compose any operation
$\mathtt{f}\colon\langle\mathtt{Y_{i}}\rangle\to\mathtt{Z}$ with
$\mathtt{g_{i}}\colon\langle\mathtt{X_{ij}}\rangle\to\mathtt{Y_{i}}$ whose
output types match the inputs of $f$ to obtain a composite
$\mathtt{f}\circ(\mathtt{g_{1}},\dots,\mathtt{g_{n}})=\mathtt{h}\colon\langle\mathtt{X_{ij}}\rangle\to\mathtt{Z}$.

These data are subject to rules [103, 11.2] governing permutation of arguments
and assuring that iterative composition is coherent, analogous to
associativity for ordinary categories [68, I].

Table 1: The theory of operads draws on many familiar ideas, establishing a dictionary between contexts. Operads | Tree | API | Equational | Systems
---|---|---|---|---
Types | Edges | Data types | Variables | Boundaries
Operations | Nodes | Methods | Operators | Architectures
Composites | Trees | Scripts | Evaluation | Nesting
Algebras | Labels | Implementations | Values | Models

###  2.1 The tree view

Hierarchies are everywhere, from scientific and engineered systems to
government, business and everyday life; they help to decompose complex
problems into more manageable pieces. The fundamental constituent of an
operad, called an _operation_ , represents a single step in a hierarchical
decomposition. We can think of this as a single branching in a labeled tree,
e.g.:

$\mathtt{op}$$\mathtt{System}$$\mathtt{Sub_{1}}$$\mathtt{Sub_{2}}$

Formally, this represents an element
$\mathtt{op}\in{\mathcal{O}}(\mathtt{Sub_{1}},\mathtt{Sub_{2}};\mathtt{System})$.
More generally, we can form new operations—trees—by _composition_. Given
further refinements for the two subsystems $\mathtt{Sub_{1}}$ and
$\mathtt{Sub_{2}}$, by $\mathtt{op_{1}}$ and $\mathtt{op_{2}}$, respectively,
we have three composites:

$\begin{array}[]{ccc}\scalebox{0.85}{ \leavevmode\hbox to98.66pt{\vbox
to100.79pt{\pgfpicture\makeatletter\hbox{\hskip
57.14551pt\lower-64.61296pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{10.75293pt}{0.0pt}\pgfsys@curveto{10.75293pt}{5.93875pt}{5.93875pt}{10.75293pt}{0.0pt}{10.75293pt}\pgfsys@curveto{-5.93875pt}{10.75293pt}{-10.75293pt}{5.93875pt}{-10.75293pt}{0.0pt}\pgfsys@curveto{-10.75293pt}{-5.93875pt}{-5.93875pt}{-10.75293pt}{0.0pt}{-10.75293pt}\pgfsys@curveto{5.93875pt}{-10.75293pt}{10.75293pt}{-5.93875pt}{10.75293pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.27779pt}{-1.18056pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-10.57571pt}{-28.45276pt}\pgfsys@curveto{-10.57571pt}{-22.50798pt}{-15.39479pt}{-17.6889pt}{-21.33957pt}{-17.6889pt}\pgfsys@curveto{-27.28435pt}{-17.6889pt}{-32.10342pt}{-22.50798pt}{-32.10342pt}{-28.45276pt}\pgfsys@curveto{-32.10342pt}{-34.39754pt}{-27.28435pt}{-39.21661pt}{-21.33957pt}{-39.21661pt}\pgfsys@curveto{-15.39479pt}{-39.21661pt}{-10.57571pt}{-34.39754pt}{-10.57571pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{-21.33957pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-28.01736pt}{-29.63332pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op_{1}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.72226pt}{26.00832pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{System}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-53.8125pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{11}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-18.24655pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{12}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{18.7194pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{2}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{10.95293pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-6.57181pt}{-8.76236pt}\pgfsys@lineto{-14.7612pt}{-19.68166pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{4.8987pt}{-9.79639pt}\pgfsys@lineto{24.50134pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-27.9181pt}{-37.22353pt}\pgfsys@lineto{-36.7494pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-16.43616pt}{-38.2591pt}\pgfsys@lineto{-11.0663pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }&\scalebox{0.85}{
\leavevmode\hbox to112.89pt{\vbox
to100.79pt{\pgfpicture\makeatletter\hbox{\hskip
48.63231pt\lower-64.61296pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{10.75293pt}{0.0pt}\pgfsys@curveto{10.75293pt}{5.93875pt}{5.93875pt}{10.75293pt}{0.0pt}{10.75293pt}\pgfsys@curveto{-5.93875pt}{10.75293pt}{-10.75293pt}{5.93875pt}{-10.75293pt}{0.0pt}\pgfsys@curveto{-10.75293pt}{-5.93875pt}{-5.93875pt}{-10.75293pt}{0.0pt}{-10.75293pt}\pgfsys@curveto{5.93875pt}{-10.75293pt}{10.75293pt}{-5.93875pt}{10.75293pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.27779pt}{-1.18056pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{32.10342pt}{-28.45276pt}\pgfsys@curveto{32.10342pt}{-22.50798pt}{27.28435pt}{-17.6889pt}{21.33957pt}{-17.6889pt}\pgfsys@curveto{15.39479pt}{-17.6889pt}{10.57571pt}{-22.50798pt}{10.57571pt}{-28.45276pt}\pgfsys@curveto{10.57571pt}{-34.39754pt}{15.39479pt}{-39.21661pt}{21.33957pt}{-39.21661pt}\pgfsys@curveto{27.28435pt}{-39.21661pt}{32.10342pt}{-34.39754pt}{32.10342pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{21.33957pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{14.66177pt}{-29.63332pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op_{2}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.72226pt}{26.00832pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{System}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-18.24655pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{21}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{10.2062pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{22}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{38.65897pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{23}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-45.2993pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{1}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{10.95293pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{6.57181pt}{-8.76236pt}\pgfsys@lineto{14.7612pt}{-19.68166pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-5.80553pt}{-9.28781pt}\pgfsys@lineto{-30.62671pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{29.09235pt}{-36.2052pt}\pgfsys@lineto{41.88611pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{21.33957pt}{-39.41661pt}\pgfsys@lineto{21.33957pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{13.58679pt}{-36.2052pt}\pgfsys@lineto{0.79303pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}} }&\scalebox{0.85}{
\leavevmode\hbox to149.86pt{\vbox
to100.79pt{\pgfpicture\makeatletter\hbox{\hskip
71.37189pt\lower-64.61296pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{10.75293pt}{0.0pt}\pgfsys@curveto{10.75293pt}{5.93875pt}{5.93875pt}{10.75293pt}{0.0pt}{10.75293pt}\pgfsys@curveto{-5.93875pt}{10.75293pt}{-10.75293pt}{5.93875pt}{-10.75293pt}{0.0pt}\pgfsys@curveto{-10.75293pt}{-5.93875pt}{-5.93875pt}{-10.75293pt}{0.0pt}{-10.75293pt}\pgfsys@curveto{5.93875pt}{-10.75293pt}{10.75293pt}{-5.93875pt}{10.75293pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.27779pt}{-1.18056pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-24.8021pt}{-28.45276pt}\pgfsys@curveto{-24.8021pt}{-22.50798pt}{-29.62117pt}{-17.6889pt}{-35.56595pt}{-17.6889pt}\pgfsys@curveto{-41.51073pt}{-17.6889pt}{-46.3298pt}{-22.50798pt}{-46.3298pt}{-28.45276pt}\pgfsys@curveto{-46.3298pt}{-34.39754pt}{-41.51073pt}{-39.21661pt}{-35.56595pt}{-39.21661pt}\pgfsys@curveto{-29.62117pt}{-39.21661pt}{-24.8021pt}{-34.39754pt}{-24.8021pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{-35.56595pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-42.24374pt}{-29.63332pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op_{1}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.72226pt}{26.00832pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{System}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-68.03888pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{11}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-32.47293pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{12}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{10.95293pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-8.5528pt}{-6.84222pt}\pgfsys@lineto{-27.00462pt}{-21.6037pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-42.14449pt}{-37.22353pt}\pgfsys@lineto{-50.97578pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-30.66254pt}{-38.2591pt}\pgfsys@lineto{-25.29268pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{46.3298pt}{-28.45276pt}\pgfsys@curveto{46.3298pt}{-22.50798pt}{41.51073pt}{-17.6889pt}{35.56595pt}{-17.6889pt}\pgfsys@curveto{29.62117pt}{-17.6889pt}{24.8021pt}{-22.50798pt}{24.8021pt}{-28.45276pt}\pgfsys@curveto{24.8021pt}{-34.39754pt}{29.62117pt}{-39.21661pt}{35.56595pt}{-39.21661pt}\pgfsys@curveto{41.51073pt}{-39.21661pt}{46.3298pt}{-34.39754pt}{46.3298pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{35.56595pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{28.88815pt}{-29.63332pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op_{2}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.02017pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{21}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{24.43259pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{22}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{52.88535pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{23}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{10.95293pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{8.5528pt}{-6.84222pt}\pgfsys@lineto{27.00462pt}{-21.6037pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{27.81317pt}{-36.2052pt}\pgfsys@lineto{15.01941pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{35.56595pt}{-39.41661pt}\pgfsys@lineto{35.56595pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{43.31873pt}{-36.2052pt}\pgfsys@lineto{56.11249pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\end{array}$ (1)

Together with the original operation, these represent four views of the same
system at different levels of granularity; compare, e.g., [65, Fig. 2]. This
reveals an important point: an operad provides a collection of interrelated
models that fit together to represent a complex system.

The relationship between models is constrained by the _principle of
compositionality_ : the whole is determined by its parts _and_ their
organization. Here, the whole is the root, the parts are the leaves, and each
tree is an organizational structure. Formally, _associativity axioms_ , which
generalize those of ordinary categories, enforce compositionality. For
example, composing the left-hand tree above with $\mathtt{op_{2}}$ must give
the same result as composing the center tree with $\mathtt{op_{1}}$. Both give
the tree on the right, since they are built up from the same operations. In
day-to-day modeling these axioms are mostly invisible, ensuring that
everything “just works”, but the formal definitions [103, 11.2] provide
explicit requirements and desiderata for modeling languages “under the hood”.

Operads encourage principled approaches to emergence by emphasizing the
organization of a system. Colloquially speaking, an emergent system is “more
than the sum of its parts”; operations provide a means to describe these
nonlinearities. This does not explain emergent phenomena, which requires
detailed semantic modeling, but begins to break up the problem with separate
(but related) representation of components and their interactions. The
interplay between these elements can be complex and unexpected, even when the
individual elements are quite simple.222For example, diffusion rates
(components) and activation/inhibition (interactions) generate zebra’s stripes
in Turing’s model of morphogenesis [99]. Compositional models may develop and
exhibit emergence as interactions between components are organized, in much
the same way as the systems they represent.

###  2.2 The API view

For most applications, trees bear labels: fault trees, decision trees, syntax
trees, dependency trees and file directories, to name a few. A tree’s labels
indicate its semantics either explicitly with numbers and symbols or
implicitly through naming and intention.

In an operad, nodes identify operations while edges—called _types_ —restrict
the space of valid compositions. This is in analogy to type checking in
strongly-typed programming languages, where we can only compose operations
when types match. In the API view, the operations are abstract method
declarations:

> def op(x1 : Sub1, x2 : Sub2) : System,
> ---
> def op1(y1 : Sub11, y2 : Sub12) : Sub1,
> def op2(z1 : Sub21, z2 : Sub22, z3 : Sub23) : Sub2.

Composites are essentially scripted methods defined in the API. For example,

> def treeLeft(y1 : Sub11, y2 : Sub12, x2 : Sub2) : System
>  = op(op1(y1, y2), x2),

is a script for left-most tree above. However, the compiler will complain with
an invalid syntax error for any script where the types don’t match, say

> def badTree(y1 : Sub11, y2 : Sub12, x2 : Sub2) : System
>  = op(x2 ,op1(y1, y2)),

If an operad is an API—a collection of abstract types and methods—then an
_operad algebra_ $\mathsf{A}$ is a concrete implementation. An algebra
declares: 1) a set of instances for each type; 2) a function for each
operation, taking instances as arguments and returning a single instance for
the composite system. That is, $\mathsf{A}\colon{\mathcal{O}}\to\mathbf{Set}$
has:

  * •

for each type $\mathtt{X}\in T$, a set $\mathsf{A}(\mathtt{X})$ of instances
of type $\mathtt{X}$, and

  * •

for each operation
$\mathtt{f}\colon\langle\mathtt{X_{i}}\rangle\to\mathtt{Y}$, the function
$\mathsf{A}(\mathtt{f})$ acts on input elements
$a_{i}\in\mathsf{A}(\mathtt{X_{i}})$ to obtain a single output element
$\mathsf{A}(\mathtt{f})(a_{1},\dots,a_{n})\in\mathsf{A}(\mathtt{Y}).$

Required coherence rules [103, 13.2] are analogous to the definition of a
functor into $\mathbf{Set}$ [68, I.3]. For example, we might declare a state
space for each subsystem, and a function to calculate the overall system state
given subsystem states. Alternatively, we might assign key performance
indicators (KPIs) for each level in a system and explicit formulae to
aggregate them. The main thing to remember is: just as an abstract method has
many implementations, an operad has many algebras. Just like an API, the
operad provides a common syntax for a range of specific models, suited for
specific purposes.

Unlike a traditional API, an operad provides an explicit framework to express
and reason about semantic relationships between _different_ implementations.
These different implementations are linked by type-indexed mappings between
instances called _algebra homomorphisms_. For example, we might like to
extract KPIs from system state. The principle of compositionality places
strong conditions on this extraction: the KPIs extracted from the overall
system state must agree with the KPIs obtained by aggregating subsystem KPIs.
That is, in terms of trees and in pseudocode:

$\mathsf{KPI}(\mathtt{op})$$\mathsf{extr}(\mathtt{Sub_{1}})$$\mathsf{extr}(\mathtt{Sub_{2}})$$\mathsf{KPI}(\mathtt{System})$$\mathsf{State}(\mathtt{Sub_{1}})$$\mathsf{State}(\mathtt{Sub_{2}})$$\mathsf{KPI}(\mathtt{Sub_{1}})$$\mathsf{KPI}(\mathtt{Sub_{2}})$ | = |  $\mathsf{State}(\mathtt{op})$$\mathsf{extr}(\mathtt{System})$ $\mathsf{KPI}(\mathtt{System})$$\mathsf{State}(\mathtt{Sub_{1}})$$\mathsf{State}(\mathtt{Sub_{2}})$$\mathsf{State}(\mathtt{System})$
---|---|---
KPI(op)(extr(x1), extr(x2)) | == |  extr(State(op)(x1, x2)).

For any state instances for $\mathtt{Sub_{1}}$ and $\mathtt{Sub_{2}}$ at the
base of the tree, the two computations must produce the same KPIs for the
overall system at the top of the tree. Here $\mathsf{KPI}(\mathtt{op})$ and
$\mathsf{State}(\mathtt{op})$ implement $\mathtt{op}$ in the two algebras,
while $\mathsf{extr}(-)$ are _components_ of the algebra homomorphism to
extract KPIs. Similar to associativity, these compositionality conditions
guarantee that extracting KPIs “just works” when decomposing a system
hierarchically.

###  2.3 The equational view

We have just seen an equation between trees that represent implementations.
Because an operad can be studied without reference to an implementation, we
can also define equations between abstract trees. This observation leads to
another view of an operad: as a system of equations.

The first thing to note is that equations occur within the sets of operations
${\mathcal{O}}(\mathtt{X_{1}},\ldots,\mathtt{X_{n}};\mathtt{Y})$; an equation
between two operations only makes sense if the input and output types match.
Second, if one side of an equation $\mathtt{f}=\mathtt{f}^{\prime}$ occurs as
a subtree in a larger operation $\mathtt{g}$, substitution generates a new
equation $\mathtt{g}=\mathtt{g^{\prime}}$. Two trees are equal if and only if
they are connected by a chain of such substitutions (and associativity
equations). In general, deciding whether two trees are equal (the word
problem) may be intractable. Third, we can often interpret composition of
operations as a normal-form computation:

$\begin{array}[]{ccccc}\begin{array}[]{c}\scalebox{0.85}{ \leavevmode\hbox
to149.86pt{\vbox to100.79pt{\pgfpicture\makeatletter\hbox{\hskip
71.37189pt\lower-64.61296pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{10.75293pt}{0.0pt}\pgfsys@curveto{10.75293pt}{5.93875pt}{5.93875pt}{10.75293pt}{0.0pt}{10.75293pt}\pgfsys@curveto{-5.93875pt}{10.75293pt}{-10.75293pt}{5.93875pt}{-10.75293pt}{0.0pt}\pgfsys@curveto{-10.75293pt}{-5.93875pt}{-5.93875pt}{-10.75293pt}{0.0pt}{-10.75293pt}\pgfsys@curveto{5.93875pt}{-10.75293pt}{10.75293pt}{-5.93875pt}{10.75293pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.27779pt}{-1.18056pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{-24.8021pt}{-28.45276pt}\pgfsys@curveto{-24.8021pt}{-22.50798pt}{-29.62117pt}{-17.6889pt}{-35.56595pt}{-17.6889pt}\pgfsys@curveto{-41.51073pt}{-17.6889pt}{-46.3298pt}{-22.50798pt}{-46.3298pt}{-28.45276pt}\pgfsys@curveto{-46.3298pt}{-34.39754pt}{-41.51073pt}{-39.21661pt}{-35.56595pt}{-39.21661pt}\pgfsys@curveto{-29.62117pt}{-39.21661pt}{-24.8021pt}{-34.39754pt}{-24.8021pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{-35.56595pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-42.24374pt}{-29.63332pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op_{1}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.72226pt}{26.00832pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{System}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-68.03888pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{11}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-32.47293pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{12}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{10.95293pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-8.5528pt}{-6.84222pt}\pgfsys@lineto{-27.00462pt}{-21.6037pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-42.14449pt}{-37.22353pt}\pgfsys@lineto{-50.97578pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-30.66254pt}{-38.2591pt}\pgfsys@lineto{-25.29268pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{46.3298pt}{-28.45276pt}\pgfsys@curveto{46.3298pt}{-22.50798pt}{41.51073pt}{-17.6889pt}{35.56595pt}{-17.6889pt}\pgfsys@curveto{29.62117pt}{-17.6889pt}{24.8021pt}{-22.50798pt}{24.8021pt}{-28.45276pt}\pgfsys@curveto{24.8021pt}{-34.39754pt}{29.62117pt}{-39.21661pt}{35.56595pt}{-39.21661pt}\pgfsys@curveto{41.51073pt}{-39.21661pt}{46.3298pt}{-34.39754pt}{46.3298pt}{-28.45276pt}\pgfsys@closepath\pgfsys@moveto{35.56595pt}{-28.45276pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{28.88815pt}{-29.63332pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{op_{2}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.02017pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{21}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{24.43259pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{22}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{52.88535pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{23}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{10.95293pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{{}}
{{{{{}}{}{}{}{}{{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{8.5528pt}{-6.84222pt}\pgfsys@lineto{27.00462pt}{-21.6037pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{27.81317pt}{-36.2052pt}\pgfsys@lineto{15.01941pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{35.56595pt}{-39.41661pt}\pgfsys@lineto{35.56595pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{43.31873pt}{-36.2052pt}\pgfsys@lineto{56.11249pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys<EMAIL_ADDRESS>\leavevmode\hbox to149.86pt{\vbox
to100.79pt{\pgfpicture\makeatletter\hbox{\hskip
71.37189pt\lower-64.61296pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{
}\nullfont\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{}}{}
{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{38.52913pt}{-14.22638pt}\pgfsys@curveto{38.52913pt}{-7.71782pt}{21.27931pt}{-2.44173pt}{0.0pt}{-2.44173pt}\pgfsys@curveto{-21.27931pt}{-2.44173pt}{-38.52913pt}{-7.71782pt}{-38.52913pt}{-14.22638pt}\pgfsys@curveto{-38.52913pt}{-20.73494pt}{-21.27931pt}{-26.01103pt}{0.0pt}{-26.01103pt}\pgfsys@curveto{21.27931pt}{-26.01103pt}{38.52913pt}{-20.73494pt}{38.52913pt}{-14.22638pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{-14.22638pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-23.91118pt}{-16.72638pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\hbox{{$\mathtt{op}(\mathtt{op_{1}},\mathtt{op_{2}})$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-15.72226pt}{26.00832pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{System}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-68.03888pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{11}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-32.47293pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{12}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{-2.24173pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-14.7728pt}{-25.3049pt}\pgfsys@lineto{-46.36618pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{-5.92259pt}{-26.07002pt}\pgfsys@lineto{-17.3873pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-4.02017pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{21}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{24.43259pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{22}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{52.88535pt}{-59.47551pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\mathtt{Sub_{23}}$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{0.0pt}{-2.24173pt}\pgfsys@lineto{0.0pt}{20.53088pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{1.99507pt}{-26.19511pt}\pgfsys@lineto{5.79585pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{9.67163pt}{-25.83138pt}\pgfsys@lineto{28.97888pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} {{}}{}{ {}{}{}} {{{{{}}{
{}{}}{}{}{{}{}}}}}{}{{{{{}}{}{}{}{}{}{{}}}}}{{}}{}{}{}{}\pgfsys@moveto{16.30753pt}{-25.09679pt}\pgfsys@lineto{52.1619pt}{-48.99808pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}\end{array}\end{array}$

We then compare composed operations directly to decide equality. For example,
there is an operad whose operations are matrices. Composition computes a
normal form for a composite operation by block diagonals and matrix
multiplication,

$\begin{array}[]{ccccc}\begin{array}[]{l}op:n\times(m_{1}+m_{2})\\\
op_{1}:m_{1}\times(k_{11}+k_{12})\\\
op_{2}:m_{2}\times(k_{21}+k_{22}+k_{23})\\\ \end{array}&\longmapsto&\Big{(}\
op\ \Big{)}\cdot\begin{pmatrix}\ op_{1}\ &0\\\ \\\ 0&\ op_{2}\ \\\
\end{pmatrix}.\end{array}$

Operad axioms constrain composition. For example, the axiom mentioned in 22.1
corresponds to:

$\Big{(}\ op\ \Big{)}\cdot\begin{pmatrix}op_{1}&0\\\ \\\ 0&I_{m_{2}}\\\
\end{pmatrix}\cdot\begin{pmatrix}I_{k_{11}}&0&0\\\ 0&I_{k_{12}}&0\\\
0&0&op_{2}\\\ \end{pmatrix}=\Big{(}\ op\
\Big{)}\cdot\begin{pmatrix}I_{m_{1}}&0\\\ \\\ 0&op_{2}\\\
\end{pmatrix}\cdot\begin{pmatrix}op_{1}&0&0&0\\\ 0&I_{k_{21}}&0&0\\\
0&0&I_{k_{22}}&0\\\ 0&0&0&I_{k_{23}}\\\ \end{pmatrix}.$

The key point is that any algebra that implements the operad must satisfy
_all_ of the equations that it specifies. Type discipline controls which
operations can compose; equations between operations control the resulting
composites. Declaring equations between operations provides additional
contracts for the API. For instance, any unary operation
$\mathtt{f}\colon\mathtt{X}\to\mathtt{X}$ (a loop) generates an infinite
sequence of composites
$\mathsf{id}_{\mathtt{X}},\mathtt{f},\mathtt{f}^{2},\mathtt{f}^{3},\ldots$.
Sometimes this is a feature of the problem at hand, but in other cases we can
short-circuit the infinite regress with assumptions like idempotence
($\mathtt{f}^{2}=\mathtt{f}$) or cyclicity
($\mathtt{f}^{n}=\mathsf{id}_{\mathtt{X}}$) and ensure that algebras contain
no infinite loops.

###  2.4 The systems view

When we apply operads to study systems, we often think of an operation
$\mathtt{f}\colon\langle\mathtt{X_{i}}\rangle\to Y$ as a system architecture.
Intuitively $\mathtt{Y}$ is the system and the
$\mathtt{X_{1}},\ldots,\mathtt{X_{n}}$ are the components, but this is a bit
misleading. It is better to think of types as boundaries or interfaces, rather
than systems. Instead, $\mathtt{f}$ is the system architecture, with component
interfaces $\mathtt{X_{i}}$ and environmental interface $\mathtt{Y}$.
Composition formalizes the familiar idea [65, Fig. 2] that one engineer’s
system is the next’s component; it acts by nesting subsystem architectures
within higher-level architectures.

Once we establish a system architecture, we would like to use this structure
to organize our data and analyses of the system. Moreover, according to the
principle of compositionality, we should be able to construct a system-level
analysis from an operation by analyzing the component-level inputs and
synthesizing these descriptions according to the given operations.

The process of extracting computations from operations is called _functorial
semantics_ , in which a model is represented as a mapping
$\mathsf{M}\colon\mathbf{Syntax}\longrightarrow\mathbf{Semantics}$. The syntax
defines a system-specific architectural design. Semantics are universal and
provide a computational context to interpret specific models. Matrices,
probabilities, proofs, and dynamical equations all have their own rules for
composition, corresponding to different semantic operads.

The mapping $\mathsf{M}$ encodes, for each operation, the data, assumptions
and design artifacts (e.g., geometric models) needed to construct the relevant
computational representations for the architecture, its components and the
environment. From this, the system model as a whole is determined by
composition in the semantic context. The algebras
($\mathsf{State}$,$\mathsf{KPI}$) described in 22.2 are typical examples, with
syntax ${\mathcal{O}}$ and taking semantic values in sets and functions. The
mappings themselves, called _functors_ , map types and operations
($\mathtt{System}$, $\mathtt{op}$) to their semantic values, while preserving
how composition builds up complex operations.

The functorial perspective allows complementary models–e.g. system state vs.
KPIs–to be attached to the same design. This includes varying the semantic
context as well as modeling details; see Sec. 5 for examples of non-
deterministic semantics. Though functorial models may be radically different,
they describe the _same system_ , as reflected by the overlapping syntax.

In many cases, relevant models are _not_ independent, like system state and
KPIs. Natural transformations, like the extraction homomorphism in 22.2,
provide a means to align ostensibly independent representations. Since models
are mappings, we often visualize natural transformations as a two-dimensional
cells:

$\textstyle{{\mathcal{O}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{State}}$$\scriptstyle{\mathsf{KPI}}$

$\Rightarrow$

$\textstyle{\mathbf{Set}.}$ (2)

Formal conditions guarantee that when moving from syntax to semantics [103,
13.2] or between representations [64, 2.3.5], reasoning about how systems
decompose hierarchically “just works.”

Since functors and higher cells assure coherence with hierarchical
decomposition, we can use them to build up a desired model in stages, working
backwards from simpler models:

$\textstyle{\mathcal{O}_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\textsf{Extension}_{1}\
\ }$$\scriptstyle{\mathsf{Model}_{2}\textrm{ is defined
by}}$$\textstyle{\mathbf{Sem_{2}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\hskip
9.04166pt\textsf{Reduction}_{2}}$$\textstyle{\mathcal{O}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\textsf{Model}_{1}\textrm{
is defined by}}$$\scriptstyle{\textsf{Extension}_{2}\ \
}$$\textstyle{\mathbf{Sem}_{1}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\hskip
9.04166pt\textsf{Reduction}_{1}}$$\textstyle{\mathcal{O}_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\textsf{Model}_{0}}$$\textstyle{\mathbf{Sem}_{0}}$

This is a powerful technique for at least two reasons. First, complexity can
be built up in stages by layering on details. Second, complex models built at
later stages are partially validated through their coherence with simpler
ones. The latter point is the foundation for lazy evaluation: many coarse
models can be explored before ever constructing expensive models.

Separating out the different roles within a model encourages efficiency and
reuse. An architecture (operation) developed for one analysis can be
repurposed with strong coherence between models (algebra instances) indexed by
the same conceptual types. The syntax/semantics distinction also helps address
some thornier meta-modeling issues. For example, syntactic types can
distinguish conceptually distinct entities while still mapping to the same
semantic entities. We obtain the flexibility of structural or duck typing in
the semantics without sacrificing the type safety provided by the syntax.

##  3 Main examples

Though operads are general tools [64, 70, 103], we focus on two classes of
operads applied to system design: wiring diagram operads and network operads.
These are complementary. Wiring diagrams provide a top-down view of the
system, whereas network operads are bottom-up. This section introduces 3
examples that help ground the exposition as in Fig. 2.

###  3.1 Specification

Network operads describe atomic types of systems and ways to link them
together with operations. These features enable: (1) specification of atomic
building blocks for a domain problem; and (2) bottom up synthesis of designs
from atomic systems and links. A general theory of network operads [6, 7, 73,
74] was recently developed under the Defense Advanced Research Projects Agency
(DARPA) Complex Adaptive System Composition and Design Environment (CASCADE)
program. Minimal data can be used to specify a functor–called a network model
[6, 4.2]–which constructs a network operad [6, 7.2] customized to a domain
problem.

| $\mathtt{Boat}$ | $\mathtt{Helo}$ | $\mathtt{UAV}$ | $\mathtt{QD}$
---|---|---|---|---
$\mathtt{Cut}$ | 1 | 1 | 1 | 1
$\mathtt{Boat}$ |  |  | 1 | 1
$\mathtt{FW}$ |  |  |  | 1
$\mathtt{FSAR}$ |  |  |  | 1
$\mathtt{Helo}$ |  |  |  | 1
(a) Examples of carrying relationships in ${\mathcal{O}}_{Sail}$

$\bullet$ $\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$ $\mathtt{QD}$ (b)
Operation $\mathtt{f}\in{{\mathcal{O}}}_{Sail}$ to specify carrying

Figure 3:  Which types are allowed to carry other types–indicated with
$1$–specify an operad ${\mathcal{O}}_{Sail}$; $\mathtt{f}$ specifies that a
$\mathtt{Helo}$ ($\bullet$) and a $\mathtt{QD}$ ($\bullet$) are carried by a
$\mathtt{Cut}$ ($\bullet$) and another $\mathtt{QD}$ ($\bullet$) is carried on
the $\mathtt{Helo}$ ($\bullet$).

The first example illustrates designs of search and rescue (SAR)
architectures. The domain problem was inspired by the 1979 Fastnet Race and
the 1998 Sydney to Hobart Yacht Race and we refer to it as the sailboat
problem. It illustrates how network operads facilitate the specification of a
model with combinatorial data called a network template. For example, Fig. 3
shows the carrying relationships between different system types to model
(e.g., a $\mathtt{Boat}$ can carry a $\mathtt{UAV}$ (Unmanned Aerial Vehicle)
but a $\mathtt{Helo}$ cannot). This data specifies a network operad
${\mathcal{O}}_{Sail}$ whose: (1) objects are lists of atomic system types;
(2) operations describe systems carrying other systems; and (3) composition
combines carrying instructions. We discuss this example in greater detail in
Sec. 4.

Functional Decomposition | Control Decomposition
---|---
$\bullet$ $\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$ $\mathtt{QD}$$\mathtt{Lab}$$\mathtt{Box}$$\mathtt{Bath}$$\mathtt{Chassis}$$\mathtt{Optics}$$\mathtt{Intfr}$$\mathtt{TempSys}$$\mathtt{LengthSys}$$\mathtt{LSI}$$\mathtt{f}\left\\{\rule{0.0pt}{32.86288pt}\right.$$\mathtt{l}\left\\{\rule{0.0pt}{35.56593pt}\right.$$\left.\rule{0.0pt}{35.56593pt}\right\\}\mathtt{t}$ |  $\bullet$ $\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$ $\mathtt{QD}$$\mathtt{Lab}$$\mathtt{Box}$$\mathtt{Optics}$$\mathtt{Intfr}$$\mathtt{Chassis}$$\mathtt{Bath}$$\mathtt{Sensors}$$\mathtt{Actuators}$$\mathtt{LSI}$$\mathtt{g}\left\\{\rule{0.0pt}{32.72049pt}\right.$$\mathtt{s}\left\\{\rule{0.0pt}{35.56593pt}\right.$$\left.\rule{0.0pt}{35.56593pt}\right\\}\mathtt{a}$
Operad Equation:
$\mathtt{f}(\mathtt{l},\mathtt{t})=\mathtt{g}(\mathtt{s},\mathtt{a})$
$\bullet$ $\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\mathtt{Optics}$$\mathtt{Chassis}$$\mathtt{Intfr}$$\mathtt{Lab}$$\mathtt{Box}$$\mathtt{Bath}$
$\mathtt{LSI}$$\mathtt{laser}$$\mathtt{intensity}$$\mathtt{intensity}$$\mathtt{focus}$$\mathtt{drive}$$\mathtt{fringe}$$\mathtt{heat}_{1}$$\mathtt{heat}_{2}$$\mathtt{setPt}$$\mathtt{H_{2}O}$$\mathtt{temp}$$\mathtt{TempSys}$$\mathtt{LengthSys}$$\mathtt{Sensors}$$\mathtt{Actuators}$
Figure 4: An equation in a wiring diagram operad operations expresses a common
refinement of hierarchies.

###  3.2 Analysis

A wiring diagram operad describes the interface each system exposes, making it
clear what can be put together [90, 94, 104]. The designer has to specify
precisely how information and physical quantities are shared among components,
while respecting their interfaces. The operad facilitates top-down analysis of
a design by capturing different ways to decompose a composite system.

The second example analyzes a precision-measurement system called the Length
Scale Interferometer (LSI) with wiring diagrams. It helps illustrate the
qualitative features of operads over and above other modeling approaches and
the potential to exploit their analytic power to separate concerns. Figure 4
illustrates joint analysis of the LSI to address different aspects of the
design problem: functional roles of subsystems and control of the composite
system. This analysis example supports these illustrations in Sec. 5.

$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$ $\mathtt{HC130}$

(a) Specification of primitive tasks $:=$ transitions

$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$
$\mathtt{HC130}$$\phantom{{|}}\tau_{1}$$\phantom{{|}}\tau_{2}$$\phantom{{|}}\tau_{4}$$(a,0)$$(b,1)$$(c,2)$$(c,2)$$((d,d),(4,4))$

(b) Coordinate tasks to compose

Figure 5: Primitive operations are composed for two UH60s ($\bullet$) to
rendezvous at $c$ and maneuver together to $d$. Each primitive operation is
indexed by a transition; types and space-time points must match to compose.

###  3.3 Synthesis

The third example describes the automated design of mission task plans for SAR
using network operads. The SAR tasking example illustrates the expressive
power of applying existing operads and their potential to streamline and
automate design synthesis. Fig. 5(a) is analogous to Fig. 3, but whereas a
sparse matrix specify an architecture problem, here a Petri net is used to
model coordinated groups of agents.

For the SAR tasking problem, much of the complexity results from agents’ need
to coordinate in space and time–e.g. when a helicopter is refueled in the air,
as in $\tau_{3}$ of Fig. 5(a). To facilitate coordination, the types of the
network operad are systematically extended via a network model whose target
categories add space and time dimensions; compare, e.g., [7]. In this way,
task plans are constrained at the level of syntax to enforce these key
coordination constraints; see, e.g., Fig. 5(b) where two UH60s at the same
space-time point ($\bullet$ $(c,2)$) maneuver together to $d$. We describe
automated synthesis for this example in Sec. 6.

##  4 Cookbook modeling of domain problems

In this section we describe some techniques for constructing operads and their
algebras, using an example-driven, cookbook-style approach. We emphasize
recent developments for network operads and dive deeper into the SAR
architecture problem.

###  4.1 Network models

The theory of network models provides a general method to construct an operad
${\mathcal{O}}$ by mixing combinatorial and compositional structures. Note
that this lives one level of abstraction _above_ operads; we are interested in
_constructing_ a language to model systems–e.g. for a specific domain. This
provides a powerful alternative to coming up with operads one-by-one. A
general construction allows the applied practitioner to cook-up a domain-
specific syntax to compose systems by specifying some combinatorial
ingredients.

The first step is to specify what the networks to be composed by
${\mathcal{O}}$ look like. Often this is some sort of graph, but what kind?
Are nodes typed (e.g., colored)? Are edges symmetric or directed? Are loops or
parallel edges allowed? What about $n$-way relationships for $n>2$ (hyper-
edges)? We can mix, match and combine such combinatorial data to define
different _network models_ , which specify the system types and kinds of
relationships between them relevant to some domain problem. The network model
describes the operations we need to compose the networks specific to the
problem at hand.

Three compositional structures which describe the algebra of operations. The
_disjoint_ or _parallel_ structure combines two operations for networks with
$m$ and $n$ nodes, respectively, into a single operation for networks with
$m+n$ nodes. More restrictively, the _overlay_ or _in series_ structure
superimposes two operations to design networks on $n$ nodes. The former
structure combines separate operations to support modular development of
designs; the latter supports an incremental design process, either on top of
existing designs or from scratch. The last ingredient permutes nodes in a
network, which assures coherence between different ordering of the nodes. This
last structure is often straightforward to specify. If it is not, one should
consider if symmetry is being respected in a natural way.

We can distill the main idea behind overlay by asking, what happens when we
add an edge to a network? It depends on the kind of network being composed by
${\mathcal{O}}$:

In a simple graph | but in a labeled graph | and in a multigraph
---|---|---
|  $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y}$ |  |  $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y}$ |  |  $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y}$
| \+ $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y}$ |  | +$\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y}$ |  | \+ $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y}$
| $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y,}$ |  |  $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{2}$$\textstyle{y,}$ |  | $\textstyle{x\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{y.}$

These differences are controlled by a _monoid_ 333A set with a binary
operation, usually written $\cdot$ unless the operation is commutative
($m+n=n+m$). A monoid is always associative, $\ell\cdot(m\cdot n)=(\ell\cdot
m)\cdot n$ and has a unit $e$ satisfying $e\cdot m=m=m\cdot e$–e.g.
multiplication of $n\times n$ matrices., which provides each $+$ shown. Above,
the monoids are bitwise OR, addition, and maximum, respectively. As a further
example, if edge addition is controlled by $\mathbb{Z}/2\mathbb{Z}$ then $+$
will have a toggling effect.

Consider simple graphs. Given a set of nodes $\mathtt{n}$, write
$U_{\mathtt{n}}$ for the set of all undirected pairs $i\neq j$ (a.k.a. simple
edges $i\mathchar 45\relax\mathchar 45\relax j$), so that
$|U_{\mathtt{n}}|={\binom{|\mathtt{n}|}{2}}$. Then we can represent a simple
graph over $\mathtt{n}$ as a $U_{\mathtt{n}}$-indexed vector of bits $\langle
b_{i\mathchar 45\relax\mathchar 45\relax j}\rangle$ describing which edges to
‘turn on’ for a design. Each bit defines whether or not to add an $i\mathchar
45\relax\mathchar 45\relax j$ edge to the network and the overlay
compositional structure is given by the monoid
$\mathsf{SG}(\mathtt{n}):=\mathbf{Bit}^{U_{\mathtt{n}}}$, whose $+$ is bitwise
OR for the product over simple edges–i.e. adding $i\mathchar 45\relax\mathchar
45\relax j$ then adding $i\mathchar 45\relax\mathchar 45\relax j$ is the same
as adding $i\mathchar 45\relax\mathchar 45\relax j$ a single time. The
disjoint structure
$\sqcup:\mathsf{SG}(\mathtt{m})\times\mathsf{SG}(\mathtt{n})\longrightarrow\mathsf{SG}(\mathtt{m+n})$
forms the disjoint sum of the graphs $g$ and $h$. Finally, permutations act by
permuting the nodes of a simple graph. Together, these compositional
structures define a network model
$\mathsf{SG}\colon\mathcal{S}\to\mathbf{Mon}$ which determines how operations
are composed in the constructed network operad; see, Fig. 6 or [6, 3.2, 7.2]
for complete technical details.

$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$
$\mathtt{HC130}$$\phantom{{|}}\tau_{1}$$\phantom{{|}}\tau_{2}$$\phantom{{|}}\tau_{4}$$(a,0)$$(b,1)$$(c,2)$$(c,2)$$((d,d),(4,4))$$2$$2$$2$$2$$2$$4$$\sqcup$$\mapsto$$2$$2$$4$$4$$+$$\mapsto$$2$$2$$4$

Figure 6: Parallel ($\sqcup$) and in series ($+$) compositional structures
define how to combine operations.

This definition has an analogue for $\mathbb{N}$-weighted graphs,
$\mathsf{LG}(\mathtt{n}):=(\mathbb{N},+)^{U_{\mathtt{n}}}$, with overlay given
by sum of edge weights and another for multi-graphs,
$\mathsf{MG}(\mathtt{n}):=(\mathbb{N},\max)^{U_{\mathtt{n}}}$, with overlay
equivalent to union of multisets; see [6, 3.3, 3.4] for details. More
generally, we can label edges with the elements of _any_ monoid. Many of these
examples are strange—binary addition makes edges cancel when they add—but
their formal construction is straightforward; see [6, Thm. 3.1].

Equivalently, we can view the undirected edges in $U_{\mathtt{n}}$ as
generators, subject to certain idempotence and commutativity relations:
$\mathsf{SG}(\mathtt{n}):=\langle e\in U_{\mathtt{n}}|e\cdot e=e,e\cdot
e^{\prime}=e^{\prime}\cdot e\rangle.$ Here the idempotence relations come from
$\mathbf{Bit}$ while the commutativity relations promote the single copies of
$\mathbf{Bit}$ for each $i\mathchar 45\relax\mathchar 45\relax j$ to a well-
defined network model. Similar tricks work for lots of other network
templates; we just change the set of generators to allow for new
relationships. For example, to allow self-loops, we add loop edge generators
$L_{\mathtt{n}}=\mathtt{n}+U_{\mathtt{n}}$ to express relationships from a
node $i$ to itself. Likewise, network operads for directed graphs can be
constructed by using generators $D_{\mathtt{n}}=\mathtt{n}\times\mathtt{n}$,
and one can also introduce higher-arity relationships.

In all cases, the formal definition of a network model assures that all the
combinatorial and compositional ingredients work well together; one precise
statement of “working well together” is given in [6, 2.3]. Once a _network
template_ —which expresses minimal data to declare the ingredients for a
network model—is codified in a theorem as in [6, 3.1], it can be reused in a
wide variety of domains to set up the specifics of composition.

###  4.2 Cooking with operads

The prototype for network operads is a simple network operad, which models
only one kind of thing, such as aircraft. The types of a simple network operad
are natural numbers, which serve to indicate how many aircraft are in a
design. Operations of the simple network operad are simple graphs on some
number of vertices. For example, Fig. 6 above shows a simple network operad to
describe a design for point-to-point communication between aircraft.

Structural network operads extend this prototype in two directions: (1) a
greater diversity of things-to-be-modeled is supported by an expanded
collection of types; and (2) more sorts of links or relationships between
things are expressed via operations. To illustrate the impact of network
templates, suppose we are modeling heterogeneous system types with multiple
kinds interactions. For simplicity we consider simple interactions, which can
be undirected or directed.

A _network template_ need only declare the _primitive_ ways system types can
interact to define a network model–e.g. a list of tuples $\textrm{(directed :
carrying, }\mathtt{Helo},\textrm{ }\mathtt{Cut}\textrm{)}$. This data is
minimal in two ways: (1) _any_ framework must provide data to specify
potentially valid interactions; and (2) this approach allows _only_ those
interactions that make sense upon looking at the types of the systems
involved. Thus, interactions must be syntactically correct when constructing
system designs.

Presently, we will consider an example from the DARPA CASCADE program: the
sailboat problem introduced in 33.1. This SAR application problem was inspired
by the 1979 Fastnet Race and the 1998 Sydney to Hobart Yacht Race, in which
severe weather conditions resulted in many damaged vessels distributed over a
large area. Both events were tragic, with 19 and 6 deaths, respectively, and
remain beyond the scale of current search and rescue planning. Various larger
assets—e.g. ships, airplanes, helicopters—could be based at ports and ferry
smaller search and rescue units—e.g. small boats, quadcopters—to the search
area.

Specifically, there were 8 atomic types to model:
$P=\\{\mathtt{Port},\mathtt{Cut},\mathtt{Boat},\mathtt{FW},\mathtt{FSAR},\mathtt{Helo},\mathtt{UAV},\mathtt{QD}\\}.$
The primary relationship to specify a structural design is various assets
carrying another types, so only one kind of interaction is needed: carrying.
This relationship is directed; e.g., a cutter ($\mathtt{Cut}$) can carry a
helicopter ($\mathtt{Helo}$) but not the other way around. Specifying allowed
relationships amounts to specifying pairs of type $(p,p^{\prime})\in P\times
P$ such that type $p^{\prime}$ can carry type $p$; see Fig. 3 for examples.
Fig. 3 data is extended to: (1) specify to that $\mathtt{Port}$ can carry all
types other than $\mathtt{Port}$, $\mathtt{UAV}$ and $\mathtt{QD}$; (2)
conform to an input file format to declare simple directed or undirected
interactions, e.g, the JSON format in Fig. 7.

{‘colors’ : [‘port’, ‘cut’, …, ‘qd’],
‘directed’ : {
‘carrying’: {
‘cut’: [‘port’],
‘boat’: [‘port’, ‘cut’],
…,
‘qd’: [‘cut’, …, ‘helo’] } } }

(a) Network template data to specify the operad ${{\mathcal{O}}}_{Sail}$

$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$
$\mathtt{HC130}$$\phantom{{|}}\tau_{1}$$\phantom{{|}}\tau_{2}$$\phantom{{|}}\tau_{4}$$(a,0)$$(b,1)$$(c,2)$$(c,2)$$((d,d),(4,4))$$2$$2$$2$$2$$2$$4$$\sqcup$$\mapsto$$2$$2$$4$$4$$+$$\mapsto$$2$$2$$4$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$ $\mathtt{QD}$ (b) Example
operation $\mathtt{f}\in{{\mathcal{O}}}_{Sail}$

Figure 7: After specifying ${{\mathcal{O}}}_{Sail}$, $\mathtt{f}$ places a
$\mathtt{QD}$ ($\bullet$) on a $\mathtt{Cut}$ ($\bullet$) and another
$\mathtt{QD}$ ($\bullet$) on a $\mathtt{Helo}$ ($\bullet$).

If another type of system or kind of interaction is needed, then the file is
appropriately extended. For example, we can include buoys by appending Buoy to
the array of colors and augmenting the relationships in the carrying node. Or,
we can model the undirected (symmetric) relationship of communication by
including an entry such as ‘undirected’: {‘communication’: {‘port‘: [‘cut’,
...], ...}}. Moreover, modifications to network templates–such as ignoring
(undirected : communication) or combining $\mathtt{QD}$ and $\mathtt{UAV}$
into a single type–naturally induce mappings between the associated operads
[6, 5.8].

###  4.3 Cooking with algebras

Because all designs are generated from primitive operations to add edges, it
is sufficient to define how primitive operations act in order to define an
algebra. For the sailboat problem, semantics are oriented to enable the
delivery of a high capacity for search—known in the literature as search
effort [97, 3.1]—in a timely manner. Given key parameters for each asset–e.g.
speed, endurance, search efficiency across kinds of target and conditions,
parent platform, initial locations–and descriptions of the search
environment–e.g. expected search distribution, its approximate evolution over
time–the expected number of surviving crew members found by the system can be
estimated [97, Ch. 3].

Among these data, the parent platform and initial locations vary within a
scenario and the rest describe the semantics of a given scenario. In fact, we
assume all platforms must trace their geographical location to one of a small
number of base locations, so that the system responds from bases, but is
organized to support rapid search. Once bases are selected, the decision
problem is a choice of operation: what to bring (type of the composite system)
and how to organize it (operation to carry atomic systems). Data for the
operational context specifies a particular algebra; see, e.g., Table 2. Just
as for the operad, this data is lightweight and configurable.

Table 2: Example properties captured in algebra for sailboat problem including time on station (ToS), speed for search (S) and max speed (R), and sweep widths measuring search efficiency for target types person in water (PIW), crew in raft (CIR) and demasted sailboats (DS) adrift.  Type |  Cost ($) |  ToS (hr) |  Speed (kn) S R |  Sweep Width (nmi) PIW CIR DS
---|---|---|---|---
$\mathtt{Cut}$ |  200M |  $\infty$ |  11 28 |  0.5 4.7 8.5
$\mathtt{Boat}$ |  500K |  6 |  22 35 |  0.4 4.2 7.5
$\mathtt{FW}$ |  60M |  9 |  180 220 |  0.1 2.2 7.6
$\mathtt{FSAR}$ |  72M |  10 |  180 235 |  0.5 12.1 16.6
$\mathtt{Helo}$ |  9M |  4 |  90 180 |  0.5 1.5 4.8
$\mathtt{UAV}$ |  250K |  3 |  30 45 |  0.5 1.8 4.5
$\mathtt{QD}$ |  15K |  4 |  35 52 |  0.5 1.5 4.8

Related cookbook approaches. Though we emphasized network operads, the
generators approach is often studied and lends itself to encoding such
combinatorially data with a “template,” in a cookbook fashion. The generators
approach to “wiring” has been developed into a theory of hypergraph categories
[38, 41], which induce wiring diagram operads. Explicit presentations for
various wiring diagram operads are given in [104]. Augmenting monoidal
categories with combinatorially specified data has also been investigated,
e.g. in [42].

##  5 Functorial Systems Analysis

In this section we demonstrate the use of functorial semantics in systems
analysis. As in 22.4, a functor establishes a relationship between a syntactic
or combinatorial model of a system (components, architecture) and some
computational refinement of that description. This provides a means to
consider a given system from different perspectives, and also to relate those
viewpoints to one another. To drive the discussion, we will focus on the
Length Scale Interferometer (LSI) and its wiring diagram model introduced in
33.2.

###  5.1 Wiring diagrams

Operads can be applied to organize both qualitative and quantitative
descriptions of hierarchical systems. Because operations can be built up
iteratively from simpler ones to specify a complete design, different ways to
build up a given design provide distinct avenues for analysis.

Figure 4 shows a wiring diagram representation of a precision measurement
instrument called the Length Scale Interferometer (LSI) designed and operated
by the US National Institute of Standards and Technology (NIST). Object types
are system or component boundaries; Fig. 4 has: 6 components, the exterior,
and 4 interior boundaries. Each boundary has an interface specifying its
possible interactions, which are implicit in Fig. 4, but define explicit types
in the operad.

An operation in this context represents one step in a hierarchical
decomposition, as in 22.1. For example, the blue boxes in Fig. 4 represent a
functional decomposition of the LSI into length-measurement and temperature-
regulation subsystems:
$\mathtt{f}\colon\mathtt{LengthSys},\mathtt{TempSys}\to\mathtt{LSI}$. These
are coupled via (the index of refraction of) a $\mathtt{laser}$ interaction
and linked to interactions at the system boundary. The operation $\mathtt{f}$
specifies the connections between blue and black boundaries.

Composition in a wiring diagram operad is defined by nesting. For this
functional decomposition, two further decompositions $\mathtt{l}$ and
$\mathtt{t}$ describe the components and interactions within
$\mathtt{LengthSys}$ and $\mathtt{TempSys}$, respectively. The wiring diagram
in Fig. 4 is the composite $\mathtt{f}(\mathtt{l},\mathtt{t})$.

This approach cleanly handles multiple decompositions. Here the red boxes
define a second, control-theoretic decomposition
$\mathtt{g}:\mathtt{Sensors},\mathtt{Actuators}\to\mathtt{LSI}$.
Unsurprisingly, the system is tightly coupled from this viewpoint, with heat
flow to maintain the desired temperature, mechanical action to modify the path
of the laser, and a feedback loop to maintain the position of the optical
focus based on measured intensity. The fact that these two viewpoints specify
the _same_ system design is expressed by the equation:
$\mathtt{f}(\mathtt{l},\mathtt{t})=\mathtt{g}(\mathtt{s},\mathtt{a})$; see
22.3 for related discussion.

###  5.2 A probabilistic functor

Wiring diagrams can be applied to document, organize and validate a wide
variety of system-specific analytic models. Each model is codified as an
algebra, a functor from syntax to semantics (22.4). For the example of this
section, all models have the same source (syntax), indicating that we are
considering the same system, but the target semantics vary by application. We
have already seen some functorial models: the algebras in 44.3. These can be
interpreted as functors from the carrying operad ${\mathcal{O}}_{Sail}$ to the
operad of sets and functions $\mathbf{Set}$. Though $\mathbf{Set}$ is the
“default” target for operad algebras, there are many alternative semantic
contexts tailored to different types of analysis. Here we target an operad of
probabilities $\mathbf{Prob}$, providing a simple model of nondeterministic
component failure.

The data for the functor is shown in Table 3. Model data is indexed by
operations444Types and operations, more generally, but the types carry no data
in this simple example. in the domain, an operad $\mathcal{W}$ extracted from
the wiring diagram in Fig. 4. The functor assigns each operation to a
probability distribution that specifies the chance of a failure in each
subsystem, assuming some error within the super-system. For example, the
length measurement and temperature regulation subsystems are responsible for
40% and 60% of errors in the LSI, respectively. This defines a Bernoulli
distribution $P_{\mathtt{f}}$. Similarly, the decomposition $\mathtt{t}$ of
the temperature system defines a categorical distribution with 3 outcomes:
$\mathtt{Box}$, $\mathtt{Bath}$ and $\mathtt{Lab}$.

Relative probabilities compose by multiplication. This allows us to compute
more complex distributions for nested diagrams. For the operation shown in
Fig. 4, this indicates that the bath leads to nearly half of all errors
($60\%\times 80\%=48\%$) in the system.

Operad equations must be preserved in the semantics. Since
$\mathtt{f}(\mathtt{l},\mathtt{t})=\mathtt{g}(\mathtt{s},\mathtt{a})$, failure
probabilities of source components don’t depend on whether we think of them in
terms of functionality or control. For the bath, this relative failure
probability is

$\overbrace{60\%}^{P_{\mathtt{f}}}\times\overbrace{80\%}^{P_{\mathtt{t}}}=48\%=\overbrace{72\%}^{P_{\mathtt{g}}}\times\overbrace{66.7\%}^{P_{\mathtt{a}}},$

and five analogous equations hold for the other source components.

Functorial semantics separates concerns: different operad algebras answer
different questions. Here we considered _if_ a component will fail. The LSI
example is developed further in [20, 4] by a second algebra describing _how_ a
component might fail, with Boolean causal models to propagate failures. The
two perspectives are complementary, and loc. cit. explores integrating them
with algebra homomorphisms (22.4).

Table 3: Failure probabilities form an operad algebra for LSI component failure. $P_{\mathtt{f}}$ | $ls$ | $\mapsto$ | 40% | $P_{\mathtt{g}}$ | $sn$ | $\mapsto$ | 28%
---|---|---|---|---|---|---|---
$ts$ | $\mapsto$ | 60% | $ac$ | $\mapsto$ | 72%
$P_{\mathtt{l}}$ | $in$ | $\mapsto$ | 10% | $P_{\mathtt{s}}$ | $lb$ | $\mapsto$ | 21.4%
$\mathtt{op}$ | $\mapsto$ | 30% | $bt$ | $\mapsto$ | 21.4%
$ch$ | $\mapsto$ | 60% | $\mathtt{op}$ | $\mapsto$ | 42.9%
$P_{\mathtt{t}}$ | $ba$ | $\mapsto$ | 80% | $in$ | $\mapsto$ | 14.3%
$bx$ | $\mapsto$ | 10% | $P_{\mathtt{a}}$ | $ch$ | $\mapsto$ | 33.3%
$lb$ | $\mapsto$ | 10% | $ba$ | $\mapsto$ | 66.7%

###  5.3 Interacting semantics

Its toy-example simplicity aside, the formulation of a failure model
$\mathcal{W}\to\mathbf{Prob}$, as in Table 3 is limited in at least two
respects. First, it tells us _which_ components fail, but not _how_ or _why_.
Second, the model is static, but system diagnosis is nearly always a dynamic
process. We give a high-level sketch of an extended analysis to illustrate the
integration of overlapping functorial models.

The first step is to characterize some additional information about the types
in $\mathcal{W}$ (i.e., system boundaries). We start with the dual notions of
_requirements_ and _failure modes_. For example, in the temperature regulation
subsystem of the LSI we have

$\begin{array}[]{ccc}T_{\mathtt{laser}}\leq
20.02^{\circ}\textrm{C}&\leftrightarrow&T_{\mathtt{laser}}\textsf{ too
high}\\\\[2.15277pt] 19.98^{\circ}\textrm{C}\leq
T_{\mathtt{laser}}&\leftrightarrow&T_{\mathtt{laser}}\textsf{ too low}\\\
\vdots&&\vdots\end{array}$

Requirements at different levels of decomposition are linked by traceability
relations. These subsystem requirements trace up to the measurement
uncertainty for the LSI as a whole. Dually, an out-of-band temperature at the
subsystem level can be traced back to a bad measurement in the $\mathtt{Box}$
enclosure, a short in the $\mathtt{Bath}$ heater or fluctuations in the
$\mathtt{Lab}$ environment.

Traceability is compositional: requirements decompose and failures bubble up.
This defines an operad algebra555Many operads are defined from ordinary
categories using a symmetric monoidal products [56, 7]. If a category carries
more than one product, we use a superscript to indicate which is in use. The
the disjoint union (+) corresponds to the disjunctive composition “a failure
in one component _or_ another; soon we will use the Cartesian product $\times$
to consider the conjunctive relationship between “the state of one component
_and_ the other”. $\mathsf{Req}:\mathcal{W}\to\mathbf{Rel}^{+}$. Functoriality
expresses the composition of traceability requirement across levels. See [20,
5] discussion of how to link these relations with Table 3 data.

For dynamics, we need _state_. We start with a state space for each
interaction among components. For example, consider the $\mathtt{laser}$
interaction coupling $\mathtt{Chassis}$, $\mathtt{Intfr}$, and $\mathtt{Box}$.
The most relevant features of the laser are its vacuum wavelength
$\lambda_{0}$ and the ambient temperature, pressure and humidity (needed to
correct for refraction). This corresponds to a four-dimensional state-space
(or a subset thereof)

$\mathsf{State}(\mathtt{laser})\cong\overbrace{[-273.15,\infty)]}^{T_{\mathtt{laser}}}\times\overbrace{[0,\infty)]}^{P_{\mathtt{laser}}}\times\overbrace{[0,1]}^{RH_{\mathtt{laser}}}\times\overbrace{[0,\infty)}^{\lambda_{0}}\subseteq\mathbb{R}^{4}.$

A larger product defines an _external state space_ at each system boundary

$\begin{array}[]{rl}\mathsf{State}(\mathtt{TempSys})=&\mathsf{State}(\mathtt{laser})\times\mathsf{State}(\mathtt{temp})^{2}\times\mathsf{State}(\mathtt{setPt})\times\mathsf{State}(\mathtt{H_{2}O})\\\\[4.30554pt]
\mathsf{State}(\mathtt{Box})=&\mathsf{State}(\mathtt{laser})\times\mathsf{State}({\mathtt{temp}})\times\mathsf{State}(\mathtt{heat})^{2}\\\
\vdots\\\ \end{array}$

Similarly, we can define an _internal state space_ for each operation by
taking the product over all the interactions that appear in that diagram. We
can decompose the internal state space in terms of either the system boundary
or the components666Coupled variables are formalized through a partial product
called the pullback, a common generalization of the Cartesian product, subset
intersection and inverse image constructions.:

$\begin{array}[]{rcl}\mathsf{State}(\mathtt{f})&\cong&\mathsf{State}(\mathtt{LSI})\times\overbrace{\mathsf{State}(\mathtt{laser})}^{\mathclap{\textrm{hidden
variable}}}\\\\[4.30554pt]
&\cong&\mathsf{State}(\mathtt{LengthSys})\times\mathclap{\underbrace{\underset{\mathsf{State}(\mathtt{laser})}{}}_{\textrm{coupled
variable}}}\mathsf{State}(\mathtt{TempSys})\end{array}$

The projections from these (partial) products form a relation, and these
compose to define a functor $\mathcal{W}\to\mathbf{Rel}^{\times}$:

$\textstyle{\mathtt{LSI}}$$\textstyle{\mathtt{LengthSys},\
\mathtt{TempSys}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathtt{f}\in\mathcal{W}}$$\textstyle{\mathsf{State}(\mathtt{LSI})}$$\textstyle{{\overbrace{\mathsf{State}(\mathtt{f})}^{\in\mathbf{Rel}^{\times}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{0}}$$\scriptstyle{\langle
p_{1},p_{2}\rangle}$$\textstyle{\mathsf{State}(\mathtt{LengthSys})\times\mathsf{State}(\mathtt{TempSys})}$$\textstyle{{\overbrace{\left\langle{\scriptscriptstyle\ldots},\mbox{$\tiny\begin{pmatrix}1\\\
2\\\ 3\end{pmatrix}$},\mbox{$\tiny\begin{pmatrix}8\\\
9\end{pmatrix}$},{\scriptscriptstyle\ldots}\right\rangle}^{p_{0}(s)}}}$$\textstyle{{\overbrace{\left\langle{\scriptscriptstyle\ldots},\underbrace{\mbox{$\tiny\begin{pmatrix}1\\\
2\\\
3\end{pmatrix}$}}_{\mathclap{\mathtt{fringe}}},\underbrace{\mbox{$\tiny\begin{pmatrix}4\\\
5\\\ 6\\\
7\end{pmatrix}$}}_{\mathclap{\mathtt{laser}}},\underbrace{\mbox{$\tiny\begin{pmatrix}8\\\
9\end{pmatrix}$}}_{\mathclap{\mathtt{H_{2}O}}},{\scriptscriptstyle\ldots}\right\rangle}^{s\in\mathsf{State}(\mathtt{f})}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\left\langle{\overbrace{\left\langle{\scriptscriptstyle\ldots},\mbox{$\tiny\begin{pmatrix}1\\\
2\\\ 3\end{pmatrix}$},\mbox{$\tiny\begin{pmatrix}4\\\ 5\\\ 6\\\
7\end{pmatrix}$}\right\rangle}^{p_{1}(s)}},{\overbrace{\left\langle\mbox{$\tiny\begin{pmatrix}4\\\
5\\\ 6\\\ 7\end{pmatrix}$},\mbox{$\tiny\begin{pmatrix}8\\\
9\end{pmatrix}$},{\scriptscriptstyle\ldots}\right\rangle}^{p_{2}(s)}}\right\rangle}$

Each requirement $R\in\mathsf{Req}(\mathtt{X})$ defines a subset
$|R|\subseteq\mathsf{State}(\mathtt{X})$, and a state is _valid_ if it
satisfies all the requirements: $\mathsf{Val}(\mathtt{X})=\bigcap_{R}|R|$.
Using pullbacks (inverse image) we can translate validity to internal state
spaces in two different ways. External validity (left square) checks that a
system satisfies its contracts; joint validity (right square) couples
component requirements to define the allowed joint states.

$\textstyle{\mathsf{Val}(\mathtt{LSI})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{XVal}(\mathtt{f})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{JVal}(\mathtt{f})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{Val}(\mathtt{LengthSys})\times\mathsf{Val}(\mathtt{TempSys})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{State}(\mathtt{LSI})}$$\textstyle{\mathsf{State}(\mathtt{f})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{p_{0}}$$\textstyle{\mathsf{State}(\mathtt{f})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\langle
p_{1},p_{2}\rangle}$$\textstyle{\mathsf{State}(\mathtt{LengthSys})\times\mathsf{State}(\mathtt{TempSys})}$

A requirement model is _sound_ if joint validity entails external validity,
corresponding to the dashed arrow above. With some work, one can show that
these diagrams form the operations in an operad of entailments $\mathbf{Ent}$;
see [21, 6] for a similar construction. The intuition is quite clear:

$\begin{array}[]{crcl}&\textrm{component reqs.}&\Rightarrow&\textrm{subsystem
reqs.}\\\ +&\textrm{subsystem reqs.}&\Rightarrow&\textrm{system reqs.}\\\
\hline\cr&\textrm{component reqs.}&\Rightarrow&\textrm{system reqs.}\\\
\end{array}$

There is a functor $\mathsf{Context}:\mathbf{Ent}\to\mathbf{Rel}^{\times}$,
which extracts the relation across the bottom row of each entailment. Noting
that the $\mathsf{State}$ relations occur in the validity entailment, we can
reformulate requirement specification as a _lifting problem_ (Fig. 8(a)):
given functors $\mathsf{State}$ and $\mathsf{Context}$, find a factorization
$\mathsf{Val}$ making the triangle commute. The second and third diagrams
(Fig. 8(b)–8(c)) show how to extend the lifting problem with prior knowledge,
in this case a top-level requirement and a known (e.g., off the shelf)
component capability.

$\textstyle{\mathbf{Ent}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{Context}}$$\textstyle{\mathcal{W}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{State}}$$\scriptstyle{\mathsf{Val}}$$\textstyle{\mathbf{Rel}^{\times}}$

(a) Free Specification

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathtt{LSI}}$$\scriptstyle{\lambda_{0}\cdot\mathtt{fringe}=L_{\mathtt{drive}}}$$\textstyle{\mathbf{Ent}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{Context}}$$\textstyle{\mathcal{W}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{State}}$$\scriptstyle{\mathsf{Val}}$$\textstyle{\mathbf{Rel}^{\times}}$

(b) Top-down requirement

$\textstyle{1\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathtt{Intfr}}$$\scriptstyle{\varepsilon_{\mathtt{fringe}}\leq\frac{\lambda_{0}}{8}}$$\textstyle{\mathbf{Ent}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{Context}}$$\textstyle{\mathcal{W}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\mathsf{State}}$$\scriptstyle{\mathsf{Val}}$$\textstyle{\mathbf{Rel}^{\times}}$

(c) Bottom-up requirement

Figure 8: Requirement specification expressed as lifting problems.

Finally we are ready to admit dynamics, but it turns out that we have already
done most of the work. All that is needed is to modify the spaces attached to
our interactions. In particular, we can distinguish between static and dynamic
state variables; for the $\mathtt{laser}$, $T$, $P$ and $RH$ are dynamic while
$\lambda_{0}$ is static. Now we replace the static values
$T,P,RH\in\mathbb{R}$ by functions $T(t),P(t),RH(t)\in\mathbb{R}^{T}$, thought
of as _trajectories_ through the state space over a timeline $t\in\tau$. For
example, we have

$\mathsf{Traj}(\mathtt{laser})\subseteq\overbrace{(\mathbb{R}^{\tau})^{3}}^{T,P,RH}\times\overbrace{\mathbb{R}}^{\lambda_{0}}.$

From this, we construct $\mathsf{Traj}:\mathcal{W}\to\mathbf{Rel}^{\times}$
using exactly the same recipe as above. Trajectories and states are related by
a pair of algebra homomorphisms
$and$const$.Thefirstpicksoutainstantaneousstateforeachpointintime,whilethesecondidentifiesconstantfunctions,whichdescribefixed-
pointsofthedynamics:$$\begin{array}[]{ccc}\textrm{Global view}&&\textrm{Local
view}\\\ \hline\cr\vbox{\lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
8.1389pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 32.1389pt\raise
0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathbf{Rel}^{\times}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
65.37808pt\raise-8.41386pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.75pt\hbox{$\scriptstyle{-\times\tau}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern
81.0778pt\raise-20.50468pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces{\hbox{\kern
40.16394pt\raise-16.4968pt\hbox{\hbox{\kern
0.0pt\raise-2.50002pt\hbox{$\scriptstyle{\displaystyle\Downarrow}$}}}}}\ignorespaces\ignorespaces{\hbox{\kern
41.60835pt\raise-13.7472pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{$\scriptstyle{}$}}}\kern 3.0pt}}}}}}\ignorespaces{\hbox{\kern
40.16394pt\raise-41.24158pt\hbox{\hbox{\kern
0.0pt\raise-2.50002pt\hbox{$\scriptstyle{\displaystyle\Downarrow}$}}}}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
44.60835pt\raise-38.49196pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.15279pt\hbox{$\scriptstyle{\mathsf{const}}$}}}\kern
3.0pt}}}}}}\ignorespaces{}{\hbox{\kern 90.54726pt\raise 0.0pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern-8.1389pt\raise-27.49438pt\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathcal{W}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces{}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
6.74547pt\raise-7.67497pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.71112pt\hbox{$\scriptstyle{\mathsf{Traj}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 39.74214pt\raise-3.0pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces{\hbox{\lx@xy@drawline@}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
38.80139pt\raise-27.49438pt\hbox{\hbox{\kern
0.0pt\raise-2.39166pt\hbox{$\scriptstyle{\mathsf{State}}$}}}}}{\hbox{\lx@xy@droprule}}\ignorespaces{\hbox{\kern
81.0778pt\raise-27.49438pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{}{}{{}{}{}{}{}{}{}{}{}{}{}{}{}}{}\ignorespaces\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{{}{}{{}}{{}{}{}}{}}}}\ignorespaces{}\ignorespaces{}{}{}{{}{}}\ignorespaces\ignorespaces{\hbox{\kern
37.1528pt\raise-55.0943pt\hbox{{}\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.71112pt\hbox{$\scriptstyle{\mathsf{Traj}}$}}}\kern
3.0pt}}}}}}\ignorespaces{}{}{}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{\hbox{\kern
90.16716pt\raise-30.49342pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}\ignorespaces\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{{}{}{}{{}}{{}{}{}\lx@xy@spline@}{}}}}\ignorespaces{}\ignorespaces\hbox{\hbox{\kern
0.0pt\raise 0.0pt\hbox{{}{}{{}}{{}{}{}}{}}}}\ignorespaces{}{\hbox{\kern
41.60835pt\raise-27.49438pt\hbox{\hbox{\kern 0.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
81.0778pt\raise-27.49438pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\mathbf{Rel}^{\times}}$}}}}}}}\ignorespaces}}}}\ignorespaces}&&\vbox{\lx@xy@svg{\hbox{\raise
0.0pt\hbox{\kern
33.78299pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathsf{Traj}(\mathtt{LSI})\times
T\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
0.0pt\raise-14.45831pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern
0.0pt\raise-2.39166pt\hbox{$\scriptstyle{{\mathtt{LSI}}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-18.41663pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathsf{State}(\mathtt{LSI})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\kern
0.0pt\raise-43.37494pt\hbox{{}\hbox{\kern 0.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\hbox{\hbox{\kern
0.0pt\raise-1.46945pt\hbox{$\scriptstyle{\mathsf{const}_{\mathtt{LSI}}}$}}}\kern
3.0pt}}}}}}\ignorespaces{\hbox{\kern 0.0pt\raise-47.33325pt\hbox{\hbox{\kern
0.0pt\raise
0.0pt\hbox{\lx@xy@tip{1}\lx@xy@tip{-1}}}}}}{\hbox{\lx@xy@droprule}}{\hbox{\lx<EMAIL_ADDRESS>0.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\mathsf{Traj}(\mathtt{LSI})}$}}}}}}}\ignorespaces}}}}\ignorespaces}\end{array}$$\par
Theproblemisthatthestatespaceexplodes;functionspacesareverylarge.Nonetheless,allofthesystemintegrationlogicisidentical,andusingtheentailmentoperad$Ent$,wecanbuildinadditionalrestrictionstolimitthesearchspace.Inparticular,wecanrestrictattentiontothesubsetoffunctionsthatsatisfiesaparticulardifferentialequationorstate-
transitionrelationship.Thisdrasticallylimitsthesetofvalidtrajectories,thoughtheresultingsetmaybedifficulttocharacterizeandthemethodsforexploringitwillvarybycontext.\par{\bf
Relatedanalyticapplications.}Wiringdiagramshaveanestablishedappliedliteratureforsystemdesignproblems,see,e.g.,\cite[cite]{[\@@bibref{}{CyberWire,
Seven, OpWire, CatSci, SpivakTan,
OpenDyn}{}{}]}.Morebroadly,theanalyticstrengthofcategorytheorytoexpresscompositionalityandfunctionalsemanticsisexploredinnumerousrecentappliedworks
--e.g.\ engineeringdiagrams\cite[cite]{[\@@bibref{}{ PaLin, Props,
OpenPetriNets, OpenCM, CoyaThesis, Seven,
DigitalCircuits}{}{}]},Markovprocesses\cite[cite]{[\@@bibref{}{CompMark,
BioMark}{}{}]},databaseintegration\cite[cite]{[\@@bibref{}{BSW, Seven,
CompPow, CatSci, SpivakKent, SpivakWis,
MultiManu}{}{}]},behaviorallogic\cite[cite]{[\@@bibref{}{Seven, ToposSem,
TempType,
SheafEvent}{}{}]},naturallanguageprocessing\cite[cite]{[\@@bibref{}{FoundNLP,
SentNPL, QuantNL}{}{}]},machinelearning\cite[cite]{[\@@bibref{}{Len,
BackProp}{}{}]},cybersecurity\cite[cite]{[\@@bibref{}{YonedaHack,
SemanticsCyber,
CyberWire}{}{}]},quantumcomputation\cite[cite]{[\@@bibref{}{OptQuant,
ReduceQuant, Quantomatic}{}{}]}andopengames\cite[cite]{[\@@bibref{}{GameGraph,
GameMixed, CompGame}{}{}]}.\par$

##  6 Automated synthesis with network operads

An operad acting on an algebra provides a starting point to automatically
generate and evaluate candidate designs. Formally correct designs (operations
in some operad) combine basic systems (elements of some algebra of that
operad) into a composite system.

###  6.1 Sailboat example

Consider the sailboat problem introduced in 33.1 and revisited in 44.2–4.3.
Network operads describe assets and ports carrying each other while algebra-
based semantics guided the search for effective designs by capturing the
impact of available search effort. To apply this model to automate design
synthesis, algorithms explored designs within budget constraints based on
costs in Table 2. Exploration iteratively composed up to budget constraints
and operational limits on carrying777Though not used for this application, it
turns of that degree limits–e.g. how many quadcopters a helicopter can
carry–can be encoded directly into operad operations; the relevant mathematics
was worked out in [73].. With these analytic models, greater sophistication
was not needed; other combinatorial search algorithms–e.g. simulated
annealing–are readily applied to large search spaces. The most effective
designs could ferry a large number of low cost search and rescue units–e.g.
quadcopters ($\mathtt{QD}$)–quickly to the scene–e.g. via helicopters
($\mathtt{Helo}$).

###  6.2 Tasking example

Surprisingly, network operads—originally developed to design systems—can also
be applied to “task" them: in other words, declare their behavior. An elegant
example of this approach is given in [7] where “catalyst" agents enable
behavioral options for a system.

The SAR tasking problem. The sailboat problem is limited by search: once
sailboat crew members are found, their recovery is relatively straightforward.
In hostile environments, recovery of isolated personnel (IPs) can become very
complex. The challenge is balancing the time criticality of recovery with the
risk to the rescuers by judiciously orchestrating recovery teams888The
recovery of downed airman Gene Hambleton, call sign Bat 21 Bravo, during the
Vietnam War is a historical example of ill-fated SAR risk management.
Hambleton’s eventual recovery cost 5 additional aircraft being shot down and
11 deaths; for comparison, a total 71 rescuers and 45 aircraft were lost to
save 3,883 lives during Vietnam War SAR [23]. . Consider the potential
challenges of a large scale earthquake during severe drought conditions which
precipitates multiple wildfires over a large area. The 2020 Creek Fire near
Fresno, CA required multiple mass rescue operations (MROs) to rescue over 100
people in each case by pulling in National Guard, Navy and Marine assets to
serve as search and rescue units (SRUs) [52, 62]. Though MRO scenarios are
actively considered by U.S. SAR organizations, the additional challenge of
concurrent MROs distributed over a large area is not typically studied.

In this SAR tasking example, multiple, geographically distributed IP groups
compete for limited SRUs. The potential of coordinating multiple agent
types—e.g., fire fighting airplanes together with helicopters—to jointly
overcome environment risks is considered as well as aerial refueling options
for SRUs to extend their range. Depending on available assets, recovery
demands and risks, a mission plan may need to work around some key agent
types–e.g. refueling assets–and maximize the impact of others–e.g. moving
protective assets between recovery teams.

Under CASCADE, tasking operations were built up from primitive tasks that
coordinate multiple agent types to form a composite task plan. Novel concepts
to coordinate teams of SRUs are readily modeled with full representation of
the diversity of potential mission plan solutions.

Network models for tasking. A network model for tasking defines atomic agent
types $C$ and possible task plans for each list of agent types. Whereas a
network model to design structure
$\mathsf{\Gamma}\colon\mathcal{S}(C)\to\mathbf{Mon}$ has values that are
possible graphical designs, a network model to task behavior
$\mathsf{\Lambda}\colon\mathcal{S}(C)\to\mathbf{Cat}$ has values that are
categories whose morphisms index possible task plans for the assembled types;
compare, e.g., [7, Thm. 9]. Each morphism declares a sequence of tasks for
each agent–many of which will be coordinated with other agents.

If the system is comprised of only a single UH-60 helicopter, its possible
tasks are captured in $\mathsf{\Lambda}(\mathtt{UH60})$. In this application,
these tasks are paths in a graph describing ‘safe maneuvers.’ For unsafe
maneuvers, UH-60s travel in pairs–or perhaps with escorts such as a HC-130 or
CH-47 equipped with a Modular Airborne Fire Fighting System (MAFFS). Anything
one UH-60 can do, so can two, but not vice versa. Thus there is a proper
inclusion
$\mathsf{\Lambda}(\mathtt{UH60})\times\mathsf{\Lambda}(\mathtt{UH60})\subsetneq\mathsf{\Lambda}(\mathtt{UH60}\otimes\mathtt{UH60})$.
Similarly,
$\mathsf{\Lambda}(\mathtt{UH60})\times\mathsf{\Lambda}(\mathtt{HC130})\subsetneq\mathsf{\Lambda}(\mathtt{UH60}\otimes\mathtt{HC130})$
since once both a UH-60 and HC-130 are present, a joint behavior of midair
refueling of the UH-60 by the HC-130 becomes possible. Formally, these
inclusions are lax structure maps–e.g.
$\Phi_{(\mathtt{UH60},\mathtt{UH60})}\colon\mathsf{\Lambda}(\mathtt{UH60})\times\mathsf{\Lambda}(\mathtt{UH60})\to\mathsf{\Lambda}(\mathtt{UH60}\otimes\mathtt{UH60})$,
specifies: given tasks for a single UH-60 (left coordinate) and tasks for
another UH-60 (right coordinate), define the corresponding joint tasking of
the pair. Here the joint tasking is: each UH-60 operates independently within
the safe graph. On the other hand, tasks in
$\mathsf{\Lambda}(\mathtt{UH60}\otimes\mathtt{UH60})$ to maneuver in unsafe
regions can not be constructed from independent taskings of each UH-60. Such
tasks must be set for some pair or other allowed team–e.g. a CH-47 teamed with
an UH-60.

$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$
$\mathtt{HC130}$$\phantom{{|}}\tau_{1}$$\phantom{{|}}\tau_{2}$$\phantom{{|}}\tau_{4}$$(a,0)$$(b,1)$$(c,2)$$(c,2)$$((d,d),(4,4))$$2$$2$$2$$2$$2$$4$$\sqcup$$\mapsto$$2$$2$$4$$4$$+$$\mapsto$$2$$2$$4$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$ $\mathtt{HC130}$

(a) Four primitive tasks specified in a Petri net; arcs indicate types
involved in each task.

$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$$\mathtt{UH60}$
$\mathtt{UH60}$$\mathtt{UH60}+\mathtt{HC130}$$\mathtt{UH60}+\mathtt{HC130}$$2\mathtt{UH60}$$2\mathtt{UH60}$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$
$\mathtt{HC130}$$\phantom{{|}}\tau_{1}$$\phantom{{|}}\tau_{2}$$\phantom{{|}}\tau_{4}$$(a,0)$$(b,1)$$(c,2)$$(c,2)$$((d,d),(4,4))$$2$$2$$2$$2$$2$$4$$\sqcup$$\mapsto$$2$$2$$4$$4$$+$$\mapsto$$2$$2$$4$$\bullet$
$\mathtt{Cut}$$\bullet$ $\mathtt{Helo}$$\bullet$
$\mathtt{QD}$$\;\;a\;\;$$\;\;b\;\;$$\;\;c\;\;$$\;\;d\;\;$$\;\phantom{\Big{|}}\tau_{1}\;$$\;\phantom{\Big{|}}\tau_{2}\;$$\;\phantom{\Big{|}}\tau_{3}\;$$\;\phantom{\Big{|}}\tau_{4}\;$$\bullet$
$\mathtt{UH60}$$\bullet$ $\mathtt{HC130}$

${\mathsf{\Lambda}(\mathtt{UH60}\otimes\mathtt{UH60})}$${\mathsf{\Lambda}(\mathtt{UH60})}$${\mathsf{\Lambda}(\mathtt{UH60}\otimes\mathtt{HC130})}$${{\begin{array}[]{c}M(\mathtt{UH60}\otimes\mathtt{UH60})\\\
\scalebox{0.5}{\mbox{$\displaystyle\begin{bmatrix}-1&0&1&0&0&0&0&0\\\
0&-1&1&0&0&0&0&0\\\ 0&0&0&0&-1&0&1&0\\\ 0&0&0&0&0&-1&1&0\\\
0&0&-1&1&0&0&-1&1\end{bmatrix}$}}\\\ {}\hfil\\\
M^{s}(\mathtt{UH60}\otimes\mathtt{UH60})\\\
\scalebox{0.5}{\mbox{$\displaystyle\begin{bmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&0&0&1&0&0&0\\\ 0&0&0&0&0&1&0&0\\\
0&0&1&0&0&0&1&0\end{bmatrix}$}}\end{array}}}$${{\begin{array}[]{c}M(\mathtt{UH60})\\\
\scalebox{1.0}{\mbox{$\displaystyle\begin{bmatrix}-1&0&1&0\\\
0&-1&1&0\end{bmatrix}$}}\\\ {}\hfil\\\ M^{s}(\mathtt{UH60})\\\
\scalebox{1.0}{\mbox{$\displaystyle\begin{bmatrix}1&0&0&0\\\
0&1&0&0\end{bmatrix}$}}\end{array}}}$${{\begin{array}[]{c}M(\mathtt{UH60}\otimes\mathtt{HC130})\\\
\scalebox{0.75}{\mbox{$\displaystyle\begin{bmatrix}-1&0&1&0&0&0&0&0\\\
0&-1&1&0&0&0&0&0\\\ 0&0&0&0&0&0&0&0\\\ \end{bmatrix}$}}\\\ {}\hfil\\\
M^{s}(\mathtt{UH60}\otimes\mathtt{HC130})\\\
\scalebox{0.75}{\mbox{$\displaystyle\begin{bmatrix}1&0&0&0&0&0&0&0\\\
0&1&0&0&0&0&0&0\\\ 0&0&1&0&0&0&1&0\\\ \end{bmatrix}$}}\end{array}}}$Network
Model Constraint Matrices  (b) More primitive tasks become possible as
available agent types increase. Type update matrices $M(-)$ and target to
source constraint matrices $M^{s}(-)$ translate type changing and matching,
resp.

Figure 9: Specified primitive tasks determine an operad ${\mathcal{O}}_{SAR}$
and a constraint program to explore operations.

Applying the cookbook: operads. While the above discussion sketches how to
specify a network model for tasking, which constructs a network operad [6],
these precise details [37] need not concern the applied practitioner999That
is, a Petri net specifies the network model
$\mathsf{\Lambda}\colon\mathcal{S}(C)\to\mathbf{Cat}$ to task behavior. The
construction of $\mathsf{\Lambda}$ [37] is similar to the construction
described in [7, Thm. 9], but adapted to colored Petri nets whose transitions
preserve the number of tokens of each color; see, e.g., Fig. 9(a). Compared to
[7, Thm. 9], $C$ corresponds to token colors, rather than catalysts [7, Def.
6], and species index discrete coordination locations. Target categories
encode allowed paths for each atomic agent type, (cont.)
9 (cont.), e.g., for Fig. 9(a) $\mathsf{\Lambda}(\mathtt{UH60})$ is (freely)
generated by objects $\\{a,b,c,d\\}$ and morphisms $\tau_{1}\colon a\to c$ and
$\tau_{2}\colon a\to c$, whereas $\mathsf{\Lambda}(\mathtt{HC130})$ is just by
generated $\\{a,b,c,d\\}$ since no transition involves a single
$\mathtt{HC130}$. By describing each target category as an appropriate
subcategory of a product of path categories, the symmetric group action is
given permuting coordinates, which allows the role of each atomic agent in a
task to be specified.. It is sufficient to provide a Petri net as template,
from which a network operad is constructed. Whereas a template to design
structures defines the basic ways system types can interact, a template to
task behavior defines the primitive tasks for agent types $C$, which are token
colors in the Petri net.

No specification of ‘staying put’ tasks are needed; these are implicit. All
other primitive tasks are (sparsely) declared. For example, each edge of the
‘safe graph’ for a solo UH-60 declares: (1) a single agent of type
$\mathtt{UH60}$ participates in this ‘traverse edge’ task; and (2)
participation is possible if a $\mathtt{UH60}$ is available at the source of
the edge. Likewise, each edge of the ‘unsafe graph’ for pairs of UH-60s should
declare similar information for pairs, but what about operations to refuel an
UH-60 with a HC-130? It turns out that transitions in a Petri net carry
sufficient data [7, 37] and have a successful history of specifying generators
for a monoidal category [9, 72, 8]. The Petri net Fig. 9(a) shows examples
where, for simplicity, tasks to traverse edges are only shown in the left to
right direction. This sparse declaration is readily extended–e.g. to add
recovery focused CH-47s, which tested their operational limits to rescue as
many as 46 people during the 2020 Creek Fire–$C$ and the set of transitions
are augmented to encode the new options for primitive tasks.

This specification of syntax is almost sufficient for the SAR tasking problem
and would be for situations where only the sequence of tasks for each agent
needs to be planned. When tasking SAR agents, _when_ tasks are performed is
semantically important because where and how long air-based agents ‘stay put’
impacts success: (1) fuel burned varies dramatically for ground vs. air
locations; (2) risk incurred varies dramatically for safe vs. unsafe
locations. For comparison, in a ground-based domain without environmental
costs, these considerations might be approximately invariant relative to the
time tasks occur, and therefore, can be omitted from tasking syntax.

Timing information creates little added burden for building a
template–transitions declaring primitive tasks need only be given durations
derivable from scenario data–and it is technically straightforward to add a
time dimension to the network model.

Constraints from syntax. A direct translation of primitive tasks to decision
variables for a constraint program is possible. For syntax, the idea is very
simple: enforce type matching constraints on composing operad morphisms. Here
we will briefly indicate the original mixed integer linear program developed
for SAR tasking; later this formulation was reworked to leverage the
scheduling toolkit of the CPLEX optimization software package.

To illustrate the concept, let us first consider the constraint program for an
operad to plan tasks without time and then add the time dimension101010Simply
increasingly dimensionality is not computationally wise–which was the point of
exploring the CPLEX scheduling toolkit to address the time dimension–but this
model still serves as a conceptual reference point.. Operad types are
translated to boolean vectors $m_{j}$–whose entries capture individual agents
at discrete coordination locations. Parallel composition of primitive
operations is expressed with boolean vectors $\Sigma_{j}$ indexed over
primitive tasks for specific agents. Type vectors $m_{j}$ indicate the
coordination location each agent with value one; operation vectors
$\Sigma_{j}$ indicate which tasks are planned in parallel.

Assuming an operation with task vector $\Sigma_{j}$ and source vector $m_{j}$,
the target is $m_{j+1}=m_{j}+M\Sigma_{j}$ where $M$ describes the relationship
between source and target for primitive tasks. Rows of $M$ correspond to
primitive tasks while columns correspond to individual agents. The target to
source constraint for single step of in-series composition is $m_{j+1}\geq