Augmented Post Systems: Syntax, Semantics, and Applications

Abstract

Augmented Post systems (APS) are string-operating Prolog-like knowledge representation, affiliated with the “Set of Strings” Framework (SSF). APS descriptive and logical inference capabilities provide natural integration of Big Data with online analytic processing. This chapter is dedicated to strict formal definition of APS syntax, mathematical and operational semantics, and to its most valuable implementational issues, as well as to APS application to Big Data, Internet of Things, cyberphysical industry, and cybersecurity areas.

1. Introduction

The background of “set of strings” Framework (SSF) [1, 2, 3, 4], developed for adequate modeling of Big Data, is the representation of database as an updated Set of Strings, whose structure is defined by the current metadatabase (MDB), being a set of context-free generation rules in the sense of N. Chomsky [5].

Augmented Post systems (APS), considered in this chapter, are result of deep integration in the one toolkit of two well-known formalisms—classical string-generating formal grammars and string-operating logical systems, proposed by E. Post [6].

By this, the main features of APS are:

1. Deep connectivity with “Set of Strings” representation of databases.

2. Deductive capabilities, similar to those, which are inherent to various deductive extensions of the relational model of data, as well as to Prolog and Datalog [7, 8, 9, 10, 11, 12].

The second feature provides selection of not only data, presenting in string databases (SDB) in the explicit form, but also data, which may be constructed (derived) from the explicit data by means of logical inference.

This chapter is dedicated to the formal definition and substantial description of APS and their applications. The terminology and abbreviations are the same, as have been used when describing SSF.

Section 2 is dedicated to the definition of syntax and mathematical semantics of APS, and Section 3 to their operational semantics. Procedural connection to APS is described in Section 4, and flow-processing APS (FAPS), based on the aforementioned connection, are described in Section 5. Implementation issues and applications of APS family are considered in Section 6. The conclusion contains proposals on further development of SSF.

2. Syntax and mathematical semantics of the augmented Post systems

The augmented Post system $P\mathit{=}<S,D>$ is the composition of set S of the so-called augmented, or string (S-), productions, and set D of context-free generating rules, being metadatabase. Following the terminology of knowledge engineering, we shall call P also as APS-represented knowledge base (for short, APS KB).

S-production $\sigma =<q,d>$ is couple, the first component of which, named body, has the form of postproduction:

$$s_0\leftarrow s_1,\dots ,s_m,$$ E1

where $m\ge 0$ and $s_0,s_1,\dots ,s_m$ are terms.

Term $s_0$ is called header, while terms $s_1,\dots ,s_m$ are called conditions. The set of conditions is unordered, i.e., S-productions:

$$<s_0\leftarrow s_{i_1},\dots ,s_{i_m},d>,$$ E2

and

$$<s_0\leftarrow s_{j_1},\dots ,s_{j_m},d>,$$ E3

where $\left\{i_1,\dots ,i_m\right\}=\left\{j_1,\dots ,j_m\right\}=\left\{1,\dots ,m\right\}$ are identical. The aforementioned set of conditions may be empty in general case, i.e., $m=0$ . The S-production with the empty conditions set looking like

$$<s_0\leftarrow ,d>,$$ E4

is called S-axiom.

Component $d$ of S-production $\sigma =<q,d>$ is set of rules $\gamma \to \beta$ and is called here variables declaration.

Rule $\gamma \to \beta \in d$ is called variable declaration of $\gamma$ , which defines $\mathrm{V}\left(\gamma ,\beta \right)$ set of possible values (domain) of this variable:

$$\mathrm{V}\left(\gamma ,\beta \right)=\left\{u\right|\beta \begin{array}{c}\ast \\ ⟹\\ G\end{array}u\&u\in V^{\ast }\},$$ E5

where $G$ is CF-grammar, corresponding to metadatabase $D$ . It is essential that there is one and only one variable declaration $\gamma \to \beta$ for every variable $\gamma$ , having place in the body of S-production. S-production $\sigma ,$ which body $s_0\leftarrow s_1,\dots ,s_m$ has no any variables, i.e.,

$$s_i\in V^{\ast },$$ E6

for all $i=0,1,\dots ,m$ , is called concrete S-production (for short CS-production). CS-production:

$$<s_0\leftarrow ,d>,$$ E7

such that $s_0\in V^{+},d=\left\{\varnothing \right\}$ is called CS-axiom.

S-production $\sigma =<q,d>$ defines set of CS-productions $\overline{\sigma }$ in the following way:

$$\overline{\sigma }=\bigcup _{\delta \in \overline{d}}<s_0\left[\delta \right]\leftarrow s_1\left[\delta \right],\dots ,s_m\left[\delta \right],\left\{\varnothing \right\}>,$$ E8

$$\overline{d}=\bigcup _{\mathrm{V}\left(u_1,{\gamma }_1,{\beta }_1\right)}\dots \bigcup _{\mathrm{V}\left(u_k,{\gamma }_k,{\beta }_k\right)}\left\{\left\{{\gamma }_1\to u_1,\dots ,{\gamma }_k\to u_k\right\}\right\},$$ E9

where $s_i\left[\delta \right]$ are strings in terminal alphabet $V$ , which are created by the replacement of variables ${\gamma }_1,\dots ,{\gamma }_k$ by strings $u_1,\dots ,u_k$ in the same alphabet, respectively; all occurrences of one and the same variable ${\gamma }_i$ in all terms $s_0,s_1,\dots ,s_m$ are replaced by one and the same string $u_i$ .

If

$$\left(\forall <w_0\leftarrow w_1,\dots ,w_m,\left\{\varnothing \right\}>\in \overline{\sigma }\right)$$

$$\left\{w_0,w_1,\dots ,w_m\right\}\subseteq L\left(G\right),$$ E10

then S-production $\sigma \in S$ is correct to MDB $D$ . This means that all terms of every CS-production from set $\overline{\sigma }$ are words of context-free language $L\left(G\right)$ , and where G is context-free grammar with set of generating rules D.

APS KB $P=<S,D>$ is correct, if all S-productions $\sigma \in S$ are correct to metadatabase $D$ .

Notion of the APS KB extensional, i.e., set of facts, which may be derived from the knowledge base by means of logical inference, is defined as follows.

Let $P=<S,D>$ be correct APS KB. Consider

$$\overline{S}=\bigcup _{\sigma \in S}\overline{\sigma },$$ E11

i.e., $\overline{S}$ is a set of all CS-productions defined by all S-productions of this knowledge base in the sense (8)–(9).

Define

$$W_{\left(0\right)}=\left\{w\right|<w\leftarrow ,\left\{\varnothing \right\}>\in \overline{S}\},$$ E12

$$W_{\left(i+1\right)}=W_{\left(i\right)}\cup \left(\bigcup _{\begin{array}{c}<w_0\leftarrow w_1,\dots ,w_m,\left\{\varnothing \right\}>\in \overline{S}\\ w_1\in W_{\left(i\right)}\\ \dots \\ w_m\in W_{\left(i\right)}\end{array}}\left\{w_0\right\}\right),$$ E13

and extensional $\mathit{Ex}\left(P\right)\text{of}\mathrm{APS}\mathrm{KB}P=<S,D>$ , i.e., set of facts, defined by this knowledge base, is fixed point of the sequence $W_{\left(0\right)},\dots ,W_{\left(i\right)},W_{\left(i+1\right)},\dots$ , which is in general case infinite:

$$\mathit{Ex}\left(\mathit{P}\right)={\mathit{W}}_{\left(\infty \right)}.$$ E14

Evidently, due to P correctness,

$$\mathit{Ex}\left(P\right)\subseteq L\left(G\right),$$ E15

and $\mathit{Ex}\left(P\right)$ is finite, if their exists $i$ such, that

$$W_{\left(i\right)}=W_{\left(i+1\right)}$$ E16

If we consider the notion of extensional of APS KB from the linguistic point of view, then $\mathit{Ex}\left(P\right)$ is a language in alphabet $V,$ which, according to (15), is sublanguage of $L\left(G\right)$ . At the same time, from the point of view of knowledge engineering, $\mathit{Ex}\left(P\right)$ is the join of set of facts $w\in W_{\left(0\right)}$ , which are known explicitly (they are called lower ground facts), and set of facts, which are derived from ground facts and/or another derived facts. As it is easy to see, set of ground facts $W_{\left(0\right)}$ is nothing else, than SDB, while S-productions with nonempty sets of conditions form APS KB intensional, providing the aforementioned inference.

Now we can define semantics of language of queries to APS KB.

Set-theoretical (S-) semantics of this language is similar to S-semantics of SDB query languages:

$$A=\overline{W}\cap I$$ E17

where $\overline{W}$ is APS KB extensional and $I$ is set of facts, which actuality check is the purpose of the query.

Here we shall use the simplest query language, being set of couples $<s,d>$ , where $s$ is term and $d$ is its variable declaration.

Mathematical (M-) semantics of this language is based on (14) and the following evident equation:

$$I=\mathit{Ex}\left(<\left\{<s\leftarrow ,d>\right\},D>\right)$$ E18

Here, $<\left\{<s\leftarrow ,d>\right\},D>$ is correct APS KB, which one-element set of S-productions—selection criterion—contains S-axiom, defining set of facts, which may belong to $\mathit{Ex}\left(P\right)$ .

Example 1. Consider metadatabase from Example 2 of the chapter of this book, describing SSF. We shall add to it the following three rules:

$$<\mathit{\text{fact}}>\to \mathit{\text{SENSOR}}<i>\mathit{AT}<\mathit{\text{time}}>-<\mathit{\text{state}}>,$$

$$<i>\to <\mathit{\text{symbol}}><\mathit{\text{symbol}}>,$$

$$<\mathit{\text{fact}}>\to \mathit{\text{SENSOR}}<i>\mathit{\text{LOCATED}}\mathrm{AT}\mathit{\text{AREA}}<\mathit{\text{name of area}}>.$$

Facts like $\mathit{\text{SENSOR}}\mathit{NN}\mathit{AT}17.00-\mathit{\text{NORMAL}}$ contain information about sensors, which gather and send to the fusion center the data about the state of the atmosphere in the surrounding area. Facts like $\mathit{\text{SENSOR}}\mathit{NN}\mathit{\text{LOCATED}}\mathit{AT}\mathit{\text{AREA}}Y\dots Y$ contain information about sensors’ location.

Consider APS knowledge base $P=<S,D>$ , where MDB $D$ was described higher, and $S$ contains following S-productions:

$${\sigma }_1:<\mathit{\text{AREA}}a\mathit{\text{IS}}s\mathit{AT}t\leftarrow$$

$$\mathit{\text{SENSOR}}e\mathit{AT}t-s,$$

$$\mathit{\text{SENSOR}}e\mathit{\text{LOCATED}}\mathit{AT}\mathit{\text{AREA}}a,$$

$$\{a\to <\mathit{\text{name of area}}>,s\to <\mathit{\text{state}}>,e\to <i>,$$

$$t\to <\mathit{\text{time}}>\}>,$$

$${\mathit{\sigma }}_2:<\mathit{\text{SENSOR}}\mathit{AX}\mathit{AT}16.00-\mathit{\text{NORMAL}}\leftarrow ,\left\{\varnothing \right\}>,$$

$${\mathit{\sigma }}_3:<\mathit{\text{SENSOR}}\mathit{FY}\mathit{AT}11.30-\mathit{\text{SMOKED}}\leftarrow ,\left\{\varnothing \right\}>,$$

$${\mathit{\sigma }}_4:<\mathit{\text{SENSOR}}\mathit{AX}\mathit{\text{LOCATED}}\mathit{AT}\mathit{\text{AREA HIGHLANDS}}\leftarrow ,\left\{\varnothing \right\}>,$$

$${\mathit{\sigma }}_5:<\mathit{\text{SENSOR}}\mathit{FY}\mathit{\text{LOCATED}}\mathit{AT}\mathit{\text{AREA GREEN VALLEY}}\leftarrow ,\left\{\varnothing \right\}>.$$

As seen, ${\sigma }_2-{\sigma }_5$ are concrete S-productions, and set $W_{\left(0\right)}$ , corresponding to this APS KB, consists of ground facts, being headers of these CS-productions.

Query, whose purpose is to get information about smoked areas, may be as follows:

$$<\mathit{\text{AREA}}z\mathit{\text{IS SMOKED}}\mathit{AT}t,\left\{z\to <\mathit{\text{name of area}}>,t\to <\mathit{\text{time}}>\right\}>,$$

while query, whose purpose is to get information about sensor $\mathit{FY}$ location, may look like

$$<\mathit{\text{SENSOR}}\mathit{YF}\mathit{\text{LOCATED}}\mathit{AT}\mathit{\text{AREA}}v,$$

$$\left\{v\to <\mathit{\text{name of area}}>\right\}>.$$

Evidently, this knowledge base extensional is

$$\{\mathit{\text{AREA HIGHLANDS IS}}\mathit{AT}\mathit{\text{NORMAL STATE}}\mathit{AT}16.00,$$

$$\mathit{\text{AREA GREEN VALLEY IS SMOKED}}\mathit{AT}11.30,$$

$$\mathit{\text{SENSOR}}\mathit{AX}\mathit{AT}16.00-\mathit{\text{NORMAL}},$$

$$\mathit{\text{SENFOR}}\mathit{FY}\mathit{AT}11.30-\mathit{\text{SMOKED}},$$

$$\mathit{\text{SENSOR}}\mathit{AX}\mathit{\text{LOCATED}}\mathit{AT}\mathit{\text{AREA HIGHLANDS}},$$

$\mathit{\text{SENSOR}}\mathit{FY}\mathit{\text{LOCATED}}\mathit{AT}\mathit{\text{AREA GREEN VALLEY}}\}$ . $∎.$

3. Operational semantics of APS

The background of operational (O-) semantics of the considered query language is the so-called S-unification, which is generalization of well-known unification, introduced by J. Robinson in [7] and used in the resolution procedures, developed for the first-order predicate logic. (In fact, S-unification is a strict generalized definition of heuristically described unification, which, as it was shown in [1], is incorrect in the case of multiple occurrences of at least one variable to one of the unified terms.)

We shall consider basic concept of S-unification and then describe operational semantics of used query language, corresponding to (11–18) and defining main features of the controlled logical inference of answers to queries to APS KB.

Let $<s,d>$ be a query and $<s_0^i,d_i>$ is couple, formed from S-production:

$${\sigma }_i:<s_0^i\leftarrow s_1^i,\dots ,s_{m_i}^i,d_i>$$ E19

As may be seen easily, the answer to $<s,d>$ may contain headers of the CS-productions, being concretizations of ${\sigma }_i$ , i.e., belonging to set ${\overline{\sigma }}_i$ , if

$$W_{{\sigma }_i}^{s,d}=\mathit{Ex}\left(<\left\{<s\leftarrow ,d>\right\},D>\right)\cap$$

$$\mathit{Ex}\left(<\left\{<s_0^i\leftarrow ,d_i>\right\},D>\right)\ne \left\{\varnothing \right\}$$ E20

This condition is equivalent to the existence of solution of word equation on context-free language (WECFL):

$$\left[s=s_o^i,d\cup d_i\right],$$ E21

(for correctness, sets of variables of terms $s$ and $s_o^i$ would not intersect, that is, simply implemented by variables renaming, if this condition is not satisfied).

Result of WECFL (21) solution is the new declaration of variables of S-production ${\sigma }_i$ , “concreted” in accordance with query $<s,d>$ . This concretization will be denoted as $d_i\left(\frac{s_o^i}{s,d}\right);$ it is obtained by replacing variable declarations ${\beta }_j^i$ of term $s_0^i$ by new ones ${\overline{\beta }}_j^i$ , which are more informative (“concrete,” “precise”), regarding initial declarations in $d_i.$ This concretization is adequate to query $<s,d>$ in such a way, that CS-productions, whose headers may enter the answer to this query, may be created at the following steps of inference.

Logics of S-unification are illustrated in Figure 1, followed by Example 2.

Figure 1.

Graphical illustration of S-unification.

Example 2. Consider query $<s,d>$ , where

$$s=\mathit{\text{AREA}}e \mathit{\text{IS NORMAL}}\mathit{AT}t,$$

$$d=\left\{e\to <\mathit{\text{name of area}}>,t\to <\mathit{\text{time}}>\right\},$$

and S-production ${\sigma }_1$ from Example 10, where

$$s_0^1=\mathit{\text{AREA}}a\mathit{\text{IS}}s\mathit{AT}t,$$

$$d_1=\left\{a\to <\mathit{\text{name of area}}>,s\to <\mathit{\text{state}}>,e\to <i>,t\to <\mathit{\text{time}}>\right\}.$$

According to (21),

$${\mathit{s}}_0^1\left[{\mathit{d}}_1\right]=\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS}}<\mathit{\text{state}}>\mathit{AT}<\mathit{\text{time}}>,$$

$$\mathit{s}\left[\mathit{d}\right]=\mathit{\text{AREA}}<\mathit{\text{name of area}}>\mathit{\text{IS}}\mathit{\text{NORMAL}}\mathit{AT}<\mathit{\text{time}}>,$$

$$d_1\left(\frac{s_0^1}{s,d}\right)=d_1-\left\{s\to <\mathit{\text{state}}>\right\}\cup \left\{s\to \mathit{\text{NORMAL}}\right\}=$$

$$=\{a\to <\mathit{\text{name of area}}>,s\to \mathit{\text{NORMAL}},e\to <i>,$$

$t\to <\mathit{\text{time}}>\}$ . $∎$

S-unification provides opportunity of answer derivation by controlled logical inference, which is implemented by the axiomatic system, which contains only three inference rules—top-down successful S-resolution, top-down unsuccessful S-resolution, and bottom-up S-resolution [1, 2]. Here we shall describe more natural and understandable procedural representation of the considered O-semantics, which fully corresponds to the aforementioned axiomatics.

This representation contains two recursively interconnected algorithmically defined functions.

The first of them $Q$ has two input variables $s$ and $d$ , which values represent query $<s,d>$ , and one output variable A, which value, returned after $Q$ termination, is the answer to this query, as defined by (17).

The second function $\mathit{RB}$ has also two input variables, $\phi$ and $d$ , which values represent, respectively, the so-called residual body $\mathit{RB}$ of S-production (subset of body of S-production, including terms, which until current call were not used for the derivation of new queries) and variable declaration, obtained after previous steps of logical inference. Function $\mathit{RB}$ returns set $\mathcal{D}$ of variable declarations, each corresponding to one element of answer to the query $<s,d>$ , where $s\in \phi$ is the next term, extracted from $\mathit{RB}$ . By this, input variables declaration $d$ is made “more precise.”

Text of function $Q$ is as follows:

$$\begin{array}{l}1Q:\mathbf{\text{function}}\left(s,d\right)\mathbf{\text{returns}}\left(A\right);\\ 2\mathbf{\text{variables}}(\left(s,s_0\right)\mathbf{\text{term}},\left(d,,,d^{\prime },\delta ,{\delta }^{\prime }\right)\mathbf{\text{declaration}},\phi \mathbf{set}\mathbf{\text{of\hspace{0.17em}terms}},\\ 3A\mathbf{set}\mathbf{\text{of\hspace{0.17em}words\hspace{0.17em}\hspace{0.17em}initial}}\left(\left\{\varnothing \right\}\right))\mathbf{\text{local}};\\ 4\mathbf{\text{variables}}\left(S\mathbf{set}\mathbf{\text{of\hspace{0.17em}productions}},D\mathbf{set}\mathbf{\text{of\hspace{0.17em}context}}-\mathbf{\text{free\hspace{0.17em}rules}}\right)\mathbf{\text{global}}\mathbf{;}\\ 5\mathbf{do}<s_0,\phi ,d^{\prime }>\in S;\\ 6\delta ≔d^{\prime }\left(\frac{s_0}{s,d}\right);\\ 7\mathbf{\text{if}}\delta \ne \nabla \\ 8\mathbf{\text{then}}\mathbf{do}{\delta }^{\prime }\in \mathit{RB}\left(\phi ,\delta \right);\\ 9A:\cup \left\{s_0\left[{\delta }^{\prime }\right]\right\};\\ 10\mathbf{end}{\delta }^{\prime };\\ 11\mathbf{end}S;\\ 12\mathbf{end}Q\end{array}$$

As seen, lines 2–4 contain declarations of variables, used lower in the function body. It is essential that there are two variables declared as global, namely, S (set of S-productions) and D (metadatabase). Nevertheless the last one is not used in the body, it is presumed that MDB is used inside S-unification (line 6). The initial value of local variable $A$ is an empty set.

The main part of Q is loop (lines 5–11) on S-productions, entering set S and represented in the form of triples $<s_0,\phi ,d^{\prime }>$ , where $s_0$ is header; $\phi$ is body of S-production, being set of terms; and $d^{\prime }$ is its variable declaration. The first operator inside loop (line 6) implements S-unification of query $<s,d>$ and couple $<s_0,d^{\prime }>$ . If this S-unification is successful (i.e., its result is not a special value $\nabla$ ), then loop on elements of set of variable declarations, obtained by function RB, is executed (lines 8–10). The values of input variables of function RB are $\phi$ (set of terms, entering body of the current S-production) and $\delta$ (result of the aforementioned S-unification). Each ${\delta }^{\prime }$ , being set of variable declarations of the form $\gamma \to u$ , where $u\in V^{\ast }$ , is used for making facts $s_0\left[{\delta }^{\prime }\right]$ by substitution right parts of those declarations to term $s_0$ , and all such facts are joined to the output set $A$ (line 9).

Text of function RB, in turn, is as follows:

$$\begin{array}{l}1\mathit{RB}:\mathbf{\text{function}}\left(\phi ,d\right)\mathbf{\text{returns}}\left(\mathcal{D}\right);\\ 2\mathbf{\text{variables}}(\phi \mathbf{set}\mathbf{\text{of\hspace{0.17em}terms}},d\mathbf{\text{declaration}},s\mathbf{\text{term}},w\mathbf{\text{fact}},\\ 3\mathcal{D}\mathbf{set}\mathbf{\text{of\hspace{0.17em}declarations\hspace{0.17em}\hspace{0.17em}initial}}\left(\left\{\varnothing \right\}\right)\mathbf{\text{local}};\\ 4\mathbf{\text{variables}}\left(D\mathbf{set}\mathbf{\text{of\hspace{0.17em}context}}\mathbf{-}\mathbf{\text{free}}\mathbf{\text{rules}}\right)\mathbf{\text{global}};\\ 5\text{if}\phi =\left\{\varnothing \right\}\\ 6\mathbf{\text{then}}\mathcal{D}≔\left\{d\right\};\\ 7\mathbf{\text{else}}\mathbf{do}s\in \phi ;\\ 8\mathbf{do}w\in Q\left(s,d\right);\\ 9\mathcal{D}:\cup \mathit{RB}\left(\phi -\left\{s\right\},d\left(\frac{s}{w,\left\{\varnothing \right\}}\right)\right);\\ 10\mathbf{end}w;\\ 11\mathbf{end}s;\\ 12\mathbf{end}\mathit{RB}\end{array}$$

Here lines 2–4, as in the text of Q, are declarations of variables, used in the RB body. RB execution begins by check, whether set $\phi$ is empty (line 5): if so, search of terms of S-production body is already finished (or, as partial case, it is empty because S-production is axiom), and the returned value is one-element set $\left\{d\right\}$ , where $d$ is the same, as input value. Otherwise loop on terms, entering residual body, is executed (lines 7–11). Every selected term $s$ is used in query $<s,d>$ to KB <S,D>, which is processed by recursive call Q (s,d), and loop on all facts, entering answer to this query, is executed (lines 8–10). The body of this loop contains single operator (line 9), providing accumulation of set $\mathcal{D}$ as a result of recursive call of the same function RB with the first input variable being $\phi -\left\{s\right\}$ (i.e., set of terms of the body of the processed S-production, reduced by extraction of the processed term $s$ ) and the second input variable value being $d\left(\frac{s}{w,\left\{\varnothing \right\}}\right)$ (i.e., S-production variables declaration, made “more precise” according to result of S-unification of query $<s,d>$ and fact $w$ ).

As it is easy to see, execution of loop $s\in \phi$ provides generation of $n!$ sequences of terms of body of S-production, i.e., all possible permutations of these terms.

Let $Q\left(s,d\right)$ be finite result of function Q application to the query $<s,d>$ and APS KB <S,D>. There is theorem on the correctness of the described operational semantics of the augmented Post systems [2].

Theorem 1. $Q\left(s,d\right)=\mathit{Ex}\left(S,D\right)\cap \mathit{Ex}\left(<\left\{s\leftarrow \right\},\left\{d\right\}>\right).$

In fact, Q and RB collaborative operation provides top-down derivation of the set of CS-productions, involved in creation of non-ground facts, which enter the answer to the query $<s,d>$ , in full accordance with bottom-up definition of M-semantics of APS. (Ground facts are simply selected by one-step application of Q and RB.)

As seen from this description, logical inference is implemented in a wavelike manner. “Direct waves,” including generated queries, which contain “more and more concrete” variables declarations, are “spreading” until S-axioms are reached. This leads to the creation of CS-productions, and “back waves” start until a new set of facts, being answer to some intermediate (or, finally, initial) query, is assembled. Both direct and back waves meet one another and “interfere,” producing new queries. As may be seen, APS operational semantics corresponds to the universal mode of inference (all facts, being goal of the query, are derived), unlike existential mode (anyone fact from the possibly multifact set), which is inherent to known resolution procedures. By this, full accordance of APS O-semantics to its S- and M-semantics is achieved.

4. Procedural connection to APS KB

One of the most important features of any knowledge representation model are embedded tools of the procedural connection, providing interaction of “rigid” (non-updated by knowledge engineers) software modules with inference process and data exchange between inference engine and the aforementioned modules.

Background of the procedural connection to APS knowledge bases are program (P-) productions.

P-production is couple $<s_0\Leftarrow p,d>,$ where term $s_0$ is header and set $d$ variable declaration; $s_0$ and $d$ are declarative component of the procedural connection. Symbol $"\Leftarrow "$ is the divider, distinct from $"\leftarrow "$ , and $p$ is the name of the connected program (software module), which has its own extensional $W_p\subseteq \mathit{Ex}\left(<\left\{<s_0\leftarrow ,d>\right\},D>\right)\subseteq L\left(G\right)$ .

Couple $<s_0,d>$ is called cover of the connected program $p$ . In general case one and the same program may be connected to APS KB by several P-productions with different covers.

Example 3. Program named MULT for multiplication of integer numbers may be connected to knowledge base by P-production:

$$<a\ast b=c\Leftarrow \text{MULT},\left\{a\to <\text{integer}>,b\to <\text{integer}>,c\to <\text{integer}>\right\}>.$$

MULT extensional is an infinite set containing strings like $1\ast 1=1,0\ast 5=0,311\ast -1=-311$ , etc. $∎$

Let $\mathrm{\Pi }$ be the set of names of programs, connected to APS KB. The extensional of this KB will differ from (12) to (14) by the only feature; instead of (12) the following is used:

$$W_{\left(0\right)}=\left(\underset{p\in \mathrm{\Pi }}{\cup }{W}_p\right)\cup \{w\mid \left\{w\leftarrow ,\left\{\phi \right\}>\in \overline{S}\right\},$$ E22

i.e., $W_{\left(0\right)}$ is a join of extensionals of all connected programs and set of ground facts, being heads of CS-axioms. Until general case will be discussed, we shall consider programs with the so-called static extentionals, whose basic feature is $W_p=\text{const}$ for all period of query processing.

Concerning operational semantics, it is sufficient to extend function Q by operators, providing call of the “perspective” connected programs via unified application programs interface and joining resulting sets to the accumulated answers. The extension is as follows:

$$\begin{array}{l}12\mathbf{do}<s_0,p,d^{\prime }>\in S;\\ 13\delta ≔d^{\prime }\left(\frac{s_0}{s,d}\right);\\ 14\mathbf{\text{if}}\delta \ne \nabla \\ 15\mathbf{\text{then}}A:\cup p\left(s_0,\delta \right);\\ 16\mathbf{end}S;\end{array}$$

As seen, after search on S-production set (lines 5–11), similar search on P-production set would be executed (lines 12–16). If S-unification of query $<s,d>$ and program $p$ cover $<s_0,d^{\prime }>$ is successful, program call is executed, and its result—set of words, denoted $p\left(s_0,\delta \right)$ —is joined to the accumulated set $A$ . This fully corresponds to (22).

As seen, search on the set $S$ is nondeterministic (there is no any predefined order on this set, except S-productions processing before P-productions; but in general case, this ordering, of course, is not mandatory). This obstacle creates some difficulties in implementation of calls of the connected programs, when input data are less informative, than it is necessary for computation (e.g., $\text{MULT}\left(a\ast b=c,\{a\to <\mathit{\text{integer}}>,b\to 4,c\to <\mathit{\text{integer}}>\}\right)$ . By this, result of such call may be infinite set, even if there would be an opportunity to implement this operation using tools for N-facts processing, developed in [1, 2, 3, 4].

To avoid such difficulty, it would be reasonable to implant to S- and P-productions some information, which may cut off “dangerous” branches.

There is a simple tool for logical inference control within APS knowledge representation. Namely, variables, which the declarations after S-unification would have right parts, consisting only of terminal symbols (i.e., there would be no incomplete information, associated with non-terminals, inside these declarations), are marked by point over arrow in the initial descriptions, having place in P- and S-productions. Such variables are called complete. In example 3 declarations of variables $a$ and $b$ would be $a\dot{\to }<\text{integer}>,b\dot{\to }<\text{integer}>$ , so query

$$<c\ast e=f,\left\{c\to 1,e\to 4,f\to <\mathit{\text{integer}}>\right\}>$$

while inference will result in program MULT call, while query

$<x\ast a=s,\left\{x\to <\mathit{\text{integer}}>,a\to 135,s\to <\mathit{\text{integer}}>\right\}>$ will not, because of information incompleteness of the declaration of $x$ , which is a complete variable. Negative result of S-unification in the case of such incompleteness is, as higher, denoted by symbol ∇.

Let us consider now the general case, where extensionals of programs, connected to APS KB, are not static, i.e., may vary while answer derivation. The simplest examples of such kind of programs are database management systems.

To connect DBMS, operating key-addressed databases, it is sufficient to join to APS KB P-production:

$$<?k=d\Leftarrow \mathit{\text{DBMS}},\left\{k\dot{\to }<\mathit{key}>,d\to <\mathit{\text{data}}>\right\}>$$

for queries (variable $k$ , denoting key, is complete), as well as

$$<k≔d\Leftarrow \mathit{\text{DBMS}},\left\{k\dot{\to }<\mathit{key}>,d\dot{\to }<\mathit{\text{data}}>\right\}>$$

for update operations (both variables $k$ and $d$ , corresponding to key and data, are complete).

DBMS, operating databases with symmetric access, may be connected in a following way. In order to minimize redundant search while queries processing, some substrings of facts may be declared indexed (used for creation and maintenance of dynamic search trees, as it is described in [2, 3]). So some covers of the relational DBMS, corresponding to some subsets of DB, may contain complete variables, with declarations like $\gamma \dot{\to }u$ , where → u defines domain of the indexed attribute of the relation. Covers, providing inclusion to SDB, contain only complete variables. (If DBMS operate SDB with incomplete information, any variable may be incomplete.)

5. Flow-processing APS

Described approach to the procedural connection makes easy integration of the distributed hardware components, linked by the computer network, into a single system with the single operation process. This may be done by procedural connection of the corresponding hardware drivers and implementation of the so-called flow-processing augmented Post systems.

FAPS KB includes along with S- and P-productions also the so-called flow (F-) productions having the form of

$$<s_0\to s_1,\dots ,s_m,s_{m+1},d>$$ E23

where terms $s_0$ , called activator, and $s_{m+1}$ , called actor, contain only complete variables and symbol “ $\to$ ” (inverse to “ $\leftarrow$ ”, used in S-production) divides activator and body, including, along with actor, conditions $s_1,\dots ,s_m$ . This structure is rather usual as well as operational semantics of F-productions, which is defined by function F, similar to Q and RB, and interconnected with them into integrated algorithmics.

We assume that F-productions are represented in the knowledge base as couples $<s_0,\phi ,s,d>$ , where $s_0$ is activator, $\phi$ is set of terms-conditions, and $s$ is actor, while $d$ is variable declaration. By this, APS KB contains three types of objects, corresponding to three types of productions:

1. $<s_0,\phi ,d>$ , where $\phi$ is set of terms (S-productions);

2. $<s_0,p,d>$ , where $p$ is string, being name of the connected program (P-productions);

3. $<s_0,\phi ,s,d>$ (F-productions).

All these objects are accumulated to set S, which, along with metadatabase D, present in the bodies of functions Q, RB, and F as global variable.

Function F is as follows:

$$\begin{array}{l}1F:\mathbf{\text{function}}\left(w\right);\\ 2\mathbf{\text{variables}}\left(\left(s_0,s^{\prime }\right)\mathbf{\text{term}},\left(d,\delta ,{\delta }^{\prime }\right)\mathbf{\text{declaration}},w\mathbf{\text{word}},\phi \mathbf{set}\mathbf{\text{of\hspace{0.17em}terms}}\right)\mathbf{\text{local}};\\ 3\mathbf{\text{variables}}\left(S\mathbf{set}\mathbf{\text{of\hspace{0.17em}productions}},D\mathbf{set}\mathbf{\text{of\hspace{0.17em}context}}\mathbf{-}\mathbf{\text{free\hspace{0.17em}rules}}\right)\mathbf{\text{global}};\\ 4\mathbf{do}<s_0,\phi ,s,d>\in S;\\ 5\delta ≔d^{\prime }\left(\frac{s_0}{w,\left\{\varnothing \right\}}\right);\\ 6\mathbf{\text{if}}\delta \ne \nabla \\ 7\mathbf{\text{then}}\mathbf{do}{\delta }^{\prime }\in \mathit{RB}\left(\phi ,\delta \right);\\ 8F\left(s\left[{\delta }^{\prime }\right]\right);\\ 9\mathbf{end}{\delta }^{\prime };\\ 10\mathbf{end}S;\\ 11\mathbf{\text{terminate}};\\ 12\mathbf{end}F\end{array}$$

As seen, the search on F-productions set (lines 4–10) provides selection of such F-productions, which are activated by input message $w$ . The set of conditions of every activated F-production is interpreted as residual body of S-production (lines 7–9). Every variable declaration ${\delta }^{\prime }$ , obtained as a result of this interpretation, is used for the creation of new message by substitution of ${\delta }^{\prime }$ to actor $s$ . This message is used as input value for function F recursive application. So the wave of messages, triggered by initial message, is generated, modeling well-known blackboard architecture. This wave propagation of any programs (including DBMS, software/hardware drivers, providing activation and operation of various devices, as well as networking middleware) may be applied. Operator terminate (line 11) stops F execution, so no return to the parent call is performed.

Various practice-oriented dialects of APS, providing various effective technologies of non-procedural programming (multiactivating, triggers, terms with negators, decision tables, etc.), were developed; also described operational semantics of APS and its extensions were redefined for highly parallel hardware environment [1, 2]. Taking into account nondeterministic nature of operational semantics of APS family, some additional tools for logical inference control were introduced in [1, 2].

Let us consider now the main features of APS application to the most advanced areas—Big Data, Internet of Things, cyberphysical industry, and cybersecurity—forming the future digital economy information infrastructure (DEII) [13, 14]. In all aforementioned applications, APS knowledge representation plays interconnecting and flexifying role, providing fast integration of various heterogeneous systems and fast adaptation of their operation logic to the highly volatile environment. In fact, APS simplify to the maximally possible level the most complicated problem of interoperability of any a priori developed systems; APS KB is nothing but “glue,” which in the simplest regular way integrates them together.

6. Implementational issues and applications of APS

DEII is the result of integration of three basic paradigms: network-centricity, Big Data, and Internet of Things (Figure 2).

Figure 2.

Basic paradigms of digital economy information infrastructure.

Network-centricity provides interconnection of any subjects of digital economy (DE), integrating human society and technosphere into global technosocium, operating as a global megasystem for the mankind wealth and prosperity. Big Data provides storage of great amounts of data from multiple heterogeneous sources and use of these data for rational everyday operation of the aforementioned megasystem and its permanent improvement. The Internet of Things, whose more precise and correct name would be Internet of Devices, provides creation, development, and operation of the aforementioned future global technosphere, including cyberphysical industry, based on additive manufacturing technologies, deeply robotized smart logistics, smart energy generation and delivery systems, and life resources infrastructure (food, water, living houses, etc.), as well as digital banking and finance infrastructure. All these segments, containing many billions of interconnected devices, provide implementation of such ambitious initiatives as Smart City and Smart Nation, inevitably leading to the Smart World as a well-understood and achievable goal of mankind evolution.

The most complicated problem to be solved for DEII creation and development is providing its flexibility, i.e., rapid correction of operation logic of various DEII elements and sets of elements to the constantly occurring changes of the environment, as well as to changes in our knowledge about nature, human society, and technosphere. It is evident that sufficient flexibility of DEII may be achieved only on the background of knowledge engineering, leading to the knowledge-based digital economy.

As shown in Figure 3, every subject of the DEII (no matter, human, or device), being associated with unique address of the address space of global information infrastructure, is supported by local knowledge base (LKB), applied by knowledge interpreter-corrector (KIC) for processing of input information flow, as well as local database, used and updated while aforementioned processing. Here LKB may contain not only “soft” component, i.e., rules, defining logic of input messages processing, but also “firm” component, i.e., “rigid” (nonmodified) software modules and systems (up to DBMS clients and servers), connected to LKB by the common interface, and called while rules interpretation (their sets are marked CP, e.g. Connected Programs, with lower indices).

Figure 3.

Linearized representation of the knowledge-based digital economy information infrastructure.

The described approach may be effectively implemented, if there would be some unified data item, providing unified representation of operation logic of any system, joining any set of DE subjects.

The possible practical outcome of the SSF is the creation of toolkit, providing the described higher approach to DEII implementation upon string as the aforementioned unified data item. This outcome in the integrated form is placed in Figure 4, where APS family of string-operation knowledge representation models is explicated.

Figure 4.

Integrated representation of APS family of knowledge representation models.

The operational semantics of the simplest practically used model from this family, whose background is FAPS, is shown in Figure 5.

Figure 5.

Basic operation semantics of multiactivated flow APS.

As seen, input messages, which are transported to the local subject of DEII by means of network infrastructure, are recorded on the external blackboard (in fact, there are two blackboards used: external, for messages from the external sources, and internal, for messages generated while current external message processing). Every next message (string) $w$ is navigated by special associative index (binary/ternary tree) to the activators $s_o^i$ . Selected activators are used for solving the corresponding WECFL (to simplify variable declarations and accelerate messages parsing, the so-called ultragrammars were introduced in [1, 2]), and if solutions do exist, they are transferred to the rest part of the F-production, in which the terms may provide access to databases with symmetric access (DBSA) or key-addressed databases (KADB) SQL-like or NoSQL queries and updates; check database integrity before updates (by applying constraints defined by the corresponding sets of productions); activate devices by their drivers, connected to LKB by proper P-productions; perform some nontrivial processing by connected “firm” software products; and also send messages, which are created strings to the internal blackboard or, by lower-level communication software, to another local subject (i.e., their external blackboards).

As seen, described dialect of APS family provides flexible implementation of operations, necessary for Big Data and Internet of Things, as well as its cyberphysical manufacturing segment, i.e., industrial Internet of Things. In the simplest case, strings, being transferred to 3D printers by their driver’s calls, may be STL files containing layer descriptions of the printed material objects [15].

The main feature, which is, in fact, core for all APS family, is “additivity” of the local knowledge bases. Namely, the occurrence of any new device or human, generating earlier unknown and unprocessed messages, is supported by addition to LKB of subjects (again devices or humans), communicating with source of such messages, new elements with activators, providing initiation of their processing. Such occurrence results, finally, in creation and sending new messages to another subjects. Such “additivity” may be called “vertical” (new types of messages are supported by the addition of new F-productions with new activators to LKB). However, horizontal “additivity” is also supported, when new F-productions with proper activators are added for internal messages, which are sent by some modules of LKB while processing external messages. By this, internal messages processing becomes “deeper.” As seen, FAPS provide sufficiently regular and refined technology of the distributed system software development and debugging.

Let us underline that unlike well-known tools from the object programming area, which also support interconnection between modules by messages and use blackboard for such processing, in the case of flow APS, new message receivers are not known, and thus, there is no opportunity for its determination in the text of the program module. By this, APS-based knowledge engineering approach to software making principally differs from object programming as well as any other approaches from the more or less procedural programming.

Let us pay some attention to such important area of flow APS application as cybersecurity, which is critical for DEII normal operation.

Dynamically extended spectrum and complexity of cyberattacks, implementing today advanced persistent threats (APT), have led to the necessity of development of more and more sophisticated tools for early recognition and prevention of APT. The most efficient of such tools are based on the security information and event management (SIEM) paradigm [16, 17, 18, 19], whose background technologies are deep packets inspection/deep packets processing (DPI/DPP) [20, 21] and data leakage prevention (DLP) [22, 23]. The first operates flows of bit packets, providing their fusion in order to recognize elaborately covered signatures of known cyberattacks, while the second operates usually traffic from the application level of the OSI model. However, both operate strings (no matter, bit, symbol, or combined), and by this reason the described higher FAPS are the perfect tool for the SIEM implementation, especially at security operation centers (SOC), providing fusion of the primary data, passing to SOC from large amount of software and hardware traffic sensors from the security perimeter of the protected system. (Such sensors may be also effectively implemented on the FAPS background.) It is very important that SIEM is solidly based on three pillars: Big Data, which are stored fragments of the network traffic, caught at many network links in a 24 × 7 regime; data mining; and knowledge engineering. This area is the hardest known case of data mining and knowledge-based technologies application: cybersecurity knowledge engineers, by analyzing accumulated enormous volumes of primary data items, must quickly understand signatures of the prepared or already performed cyberattacks, developed by the smartest people from the global cybercrime and states special services teams; and rapidly correct LKBs or extend them by new sets of productions, providing early recognition and neutralizing such attacks. This combination of very large volumes of data and knowledge with hard real-time regime of SOC operation (e.g., SOC of the Russia largest financial group Sberbank neutralizes daily over 14,000 cyberattacks from all over the world [24]) makes cybersecurity application of data and knowledge engineering the most important from both practical and theoretical points of view.

7. Conclusion

The described “Set of Strings” Framework is based on integration of three research areas—knowledge/data engineering, theory of grammars, and information theory—which until now are very close but rather isolated from one another. Synergetic effect, which may be the main result of such integration, would be useful for the development of the unified theory, necessary for convergence of Big Data, data mining, artificial intelligence, and Internet of Things. Such convergence is extremely needed for solution of all spectrum of problems of digital economy.

The most valuable directions of the SSF future development may be the following:

1. Metainference and machine learning in APS KB.

2. N-facts concretization in SDB with incomplete information (SDBI) and APS KB, using functional dependencies, associated usually with the relational data model.

3. Contradictory SDBI and APS KB management.

4. SDBI and APS KB with metadatabases, describing two- and three-dimensional objects.

5. SSF ideology and techniques transfer to the numeric data with the help of the SSF-associated theory of recursive multisets and multiset grammars/metagrammars, developed for the solution of problems of planning and scheduling in digital economy [25, 26, 27, 28].

6. Hardware implementation of key elements of SSF in the data flow and other high-parallel computer environments.

The author is highly interested in the cooperation with computer scientists and engineers, who may spend some research effort participating in the development of the listed directions and the SSF at all.

Acknowledgments

The author expresses gratitude to the editor for useful advices. The author is grateful to Prof. Noam Chomsky for words of support to the development of the “Set of Strings” Framework. The author is also thankful to Prof. Jeffrey Ullman for useful remarks on the current state of the theory of grammars.