Olivier Gauwin

Joachim Niehren

Yves Roos

Streaming Tree Automata

Keywords: tree automata, XML databases, query languages, streaming

Streaming validation and querying of XML documents are often based on automata for tree-like structures. We propose a new notion of streaming tree automata in order to unify the two main approaches, which have not been linked so far: automata for nested words or equivalently visibly pushdown automata, and respectively pushdown forest automata.

Introduction

Streaming evaluation of XML documents means to process XML trees in document order. Streaming is useful in various XML applications requiring validation, typing, and querying. In this article, we subscribe to fundamental approaches to XML processing based on tree automata [START_REF] Alur | Marrying words and trees[END_REF] that are complementary to standardization oriented formalisms such as DTDs [START_REF] Martens | Which XML schemas admit 1-pass preorder typing?[END_REF], XPath [START_REF] Kumar | Stream processing of XPath queries with predicates[END_REF] or XQuery [START_REF] Koch | FluXQuery: An optimizing XQuery processor for streaming XML data[END_REF][START_REF] Fernandez | XQuery streaming à la carte[END_REF].

Various notions of finite automata for tree-like structures have been proposed for streaming purpose. Tree walking automata are a traditional example [START_REF] Aho | Translations on a contextfree grammar[END_REF], but they do not capture all regular tree languages [START_REF] Miko | Treewalking automata do not recognize all regular languages[END_REF] even when permitting pebbles [START_REF] Miko Laj Bojańczyk | Expressive power of pebbles automata[END_REF]. Finite automata operating on linearizations of trees are another approach [START_REF] Segoufin | Validating streaming XML documents[END_REF][START_REF] Segoufin | Constant-memory validation of streaming XML documents against DTDs[END_REF], but again, not all regular tree languages can be expressed. What is missing is the availability of a stack, as used in implementations of tree automata. This raises the question of how to characterize the particularities of such stacks.

This question has been approached in two independent research lines. The first line started in 2004

Email addresses: olivier.gauwin@inria.fr (Olivier Gauwin), www.grappa.univ-lille3.fr/ ∼ niehren (Joachim Niehren), yves.roos@lifl.fr (Yves Roos).

in the context of program verification, when Alur and Madhusudan [START_REF] Alur | Visibly pushdown languages[END_REF] introduced visibly pushdown automata for this purpose. More recently, their relevance for XML streaming tasks was highlighted [START_REF] Kumar | Visibly pushdown automata for streaming XML[END_REF], and Alur [START_REF] Alur | Marrying words and trees[END_REF] reformulated these into nested word automata (NWAs). The second line started as early as 1998, when Neumann and Seidl proposed pushdown forest automata (PFAs) for XML query evaluation. The similarity between NWAs and PFAs has been noticed only very recently [START_REF] Kumar | Visibly pushdown automata for streaming XML[END_REF]. In this paper, we formalize and prove the precise equivalence.

As a first contribution, we propose streaming tree automata (STAs) by reformulating runs of NWAs so that they directly operate on unranked trees (rather than encodings thereof). We believe that this reformulation is natural and useful elsewhere. As a second contribution, we use STAs in order to establish an equivalence between PFAs and NWAs. Our proof is based on the comparison of runs. This has the advantage to link run-based queries defined with such automata, too. These queries capture MSOdefinable n-ary queries [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF]. Query answering algorithms for PFAs [START_REF] Berlea | Binary queries for document trees[END_REF] can be lifted easily to STAs too. 2. Trees, Events, and Runs of Automata XML documents, and other forms of semistructured data, are frequently abstracted into labeled unranked trees. Let Σ be a finite set of labels. An unranked tree t ∈ T Σ is either a constant a ∈ Σ or a pair a(t 1 , . . . , t n ), where a ∈ Σ is a label, and (t 1 , . . . , t n ) is a sequence of trees in T Σ with n ≥ 1. We write nod (t) ⊆ N * for the set of nodes of a tree t. If t is the constant a then nod (t) = {ǫ}. Otherwise, nod (a(t 1 , . . . ,

Preprint submitted to Information Processing Letters

t n )) = {ǫ} ∪ {i.π | π ∈ nod (t i )}.
Here, ǫ is the empty word standing for the root of t, and the word i.π is the concatenation of letter i with word π. We write lab t (π) for the unique label of node π in t.

The preorder traversal over t produces a totally ordered set of events. Once initiated, it visits every node twice, once when opening (entering) the subtree it roots, and once when closing (leaving) it:

events(t) = {start} ∪ ({open, close} × nod (t))
The unique predecessor pred (e) for e ∈ events(t) except {start} is the event preceding e in the preorder traversal of t, as illustrated in Fig. 1.

We will use a uniform syntax for different kinds of tree automata operating in document order. They all have two finite collections of states stat = stat n ⊎ stat e called node states and event states respectively, and subsets init, final ⊆ stat e of initial and final states. Furthermore, they provide a finite set rul of rules whose forms may differ according to the concrete automata notion. Whenever useful, we will index the components of an automaton A by upper index

A so that A = (Σ A , stat A , init A , final A , rul A ).
Runs of automata A on trees t ∈ T Σ are pairs r = (r e , r n ) where r e : events(t) → stat A e and r n : nod (t) → stat A n assign states to events and nodes, such that r e (start) ∈ init A . Runs must be licensed by the rules of the automaton; what this means depends on the particular class. A run r is called successful if r e (close, ǫ) ∈ final A . The language recog-nized by A, denoted by L(A), is the set of all trees t ∈ T Σ on which A permits a successful run.

Streaming Tree Automata

Definition 1 A streaming tree automaton (STA) is a tree automaton following the general notation above whose rules are terms of the following forms, where q 0 , q 1 ∈ stat e , a ∈ Σ and γ 0 , γ 1 ∈ stat n : open a q 0 → q 1 γ 1 or close a q 0 γ 0 → q 1 More formally, rules are tuples in {open, close} × Σ×stat e ×stat e ×stat n written in a smoother syntax.

In drawings, we will use the following alternative graphical notation for these rules:

q 0 q 1 open a γ 1 or q 0 q 1 close a γ 0 An STA A licenses a run (r e , r n ) on a tree t if the following are rules of A for all π ∈ nod (t) with a = lab t (π): open a r e (pred (open, π)) → r e (open, π) r n (π) close a r e (pred (close, π)) r n (π) → r e (close, π)
An example for a successful run of the STA in Fig. 3 on tree a(a(b), b) is given in Fig. 4.

An STA is deterministic if it does not have two rules with the same left-hand side and has a unique initial state. Deterministic STAs can recognize all regular languages of unranked trees. The analogous result is well-known for NWAs. It can be shown by encoding (bottom-up and left-to-right) deterministic stepwise tree automata [START_REF] Carme | Querying unranked trees with stepwise tree automata[END_REF][START_REF] Comon | Tree automata techniques and applications[END_REF] into deterministic STAs.

Deterministic STAs are useful for streaming algorithms. They can be obtained by translating extended DTDs that are restrained competition and deterministic [START_REF] Kumar | Visibly pushdown automata for streaming XML[END_REF], so that running such STAs performs one-pass typing. They are equally useful for earliest query answering as shown in follow up work [START_REF] Gauwin | Complexity of earliest query answering with streaming tree automata[END_REF].

For illustration, we present the translation of DTDs to STAs. Given a deterministic DTD with alphabet Σ, we compute the collection of Glushkov automata (G a ) a∈Σ over Σ, which are deterministic finite automata for the regular expressions of the DTD [START_REF] Brüggemann-Klein | Regular expressions into finite automata[END_REF]. Let root ∈ Σ be the root symbol of the DTD.

From the collection of Glushkov automata, we construct a deterministic STA S recognizing the trees validated by the DTD. The states S unify the a : Fig. 4. Successful run of the STA in Fig. 3 states of all Glushkov automata and add a unique initial state I and a unique final state F:

stat S = ⊎ a∈Σ stat Ga ⊎ {I, F}
The rules of the STA S are obtained systematically from those of the Glushkov automata according to the two following inference schemas:

q 0 b → q 1 ∈ rul Ga q 2 ∈ init G b q 3 ∈ final G b open b q 0 → q 2 q 0 ∈ rul S close b q 3 q 0 → q 1 ∈ rul S a = root q 0 ∈ Ga q 1 ∈ final Ga open a I → q 0 I ∈ rul S close a q 1 I → F ∈ rul S
For instance, the STA drawn in Fig. 3 accepts valid documents for the DTD in Fig. 2.

A successful run on tree a(a(b), b) is shown in Fig. 4. This construction preserves determinism, in that DTDs with deterministic Glushkov automata are translated to deterministic STAs.

Nested Word Automata

Nested word automata (NWAs) [START_REF] Alur | Marrying words and trees[END_REF] are equal to STAs syntactically but run on nested words, so they 3 have different semantics. We show that both semantics coincide modulo encoding unranked trees into nested words.

A nested word over Σ is a pair (w, E) where w ∈ Σ * is a word and E ⊆ pos(w) × pos(w) a set of forward edges without overlap. The set pos(w) is the set of integers in {1, . . . , |w|} where |w| is the length of w. We assume that every position in a nested word is adjacent to exactly one edge, and that for every edge, both adjacent positions have the same label. 1A run of an NWA A on a nested word (w, E) annotates all positions of pos(w), the start position 0, and all edges in E by states, as illustrated by the example in Fig. 5. More precisely, a run of A as an NWA consists of two functions r = (r e , r n ) with types r e : pos(w)∪{0} → stat A e and r n : E → stat A n . It is licensed by A if for all edges (i, j) ∈ E adjacent to positions labeled by a, the following tuples belong to rul A : open a r e (i -1) → r e (i) r n (i, j) close a r e (j -1) r n (i, j) → r e (j) Unranked trees t ∈ T Σ can be encoded into nested words nw(t) = (w, E) over Σ. For instance, the nested word for a(a(b), b) is drawn in Fig. 5. More formally, let e 1 . . . e n be the sequence of events in t except start in their total order. The word: w = a 1 . . . a n is the sequence of all a i ∈ Σ labeling the nodes of event e i in t where 1 ≤ i ≤ n. The edges link opening to closing events of the same node, i.e.:

E = {(i, j) | π ∈ nod (t), e i = (open, π), e j = (close, π)}
The function I e : events(t) → pos(nw(t)) ∪ {0} with I e (start) = 0 and I e (e i ) = i for all 1 ≤ i ≤ n is a bijection, as well as function I n : nod (t) → E with I n (π) = (I e ((open, π)), I e ((close, π))). Thus, events of t correspond to positions of nw(t) or 0 and nodes of t to edges of nw(t). The edges of t do not have immediate counterparts in nw(t), but can be infered from the relations of positions in nw(t) nevertheless. Proposition 2 Let A be an STA over Σ and t ∈ T Σ an unranked tree. A run (r n , r e ) on nw(t) is licensed by A as an NWA if and only if the run (r n • I n , r e • I e ) on t is licensed by A as an STA.

As a consequence, the runs of A on t and nw(t) correspond bijectively, and t is accepted by A as an STA if and only if nw(t) is accepted by A as an NWA.

Nested words (w, E) encoding unranked trees satisfy the following restriction: no hedges: there exists an edge (1, |w|) ∈ E. Conversely, all nested words satisfying this condition encode some unranked tree. Every edge (i, j) in E corresponds to one node π of this tree, using the common label of i and j. As no overlap occurs, positions between i and j can be translated into a sequence of trees, the children of π. The no hedges condition ensures that this sequence of trees has a unique root.

Pushdown Forest Automata

We recall PFAs from Neumann and Seidl [START_REF] Neumann | Locating Matches of Tree Patterns in Forests[END_REF] which operate on sequences of unranked trees (called forests there). We reformulate the original recursive definition of PFAs evaluators by formalizing a corresponding notion of runs. We restrict ourselves to tree languages, in that we define runs on trees only. This is no serious restriction, since our results extend easily to sequences of trees. Definition 3 A pushdown forest automaton (PFA) is a tree automaton following the general notation whose rules are of the following forms, where q 0 , q 1 ∈ stat e , γ, γ 1 ∈ stat n and a ∈ Σ: down a q 0 → q 1 side q 0 γ → q 1 up a q 0 → γ 1 Event states are originally called forest states and node states correspond to the original tree states. PFAs traverse trees in document order. When leaving a node π, two rules are used. First, an up-rule maps the node to some node state. Second, a siderule assigns an event state to the closing event of the node. up-rules can be eliminated, but are kept here as in the original definition.

More formally, PFAs P permit runs r = (r e , r n ) on trees t if P contains the following rules for all nodes π ∈ nod (t) with a label a ∈ Σ:

I a a b b 1 F 1 2 4 3 4 3 4' 3' 4' 3'
(a) Example of run

1 b 4 (b) down b 1 → 4 a 3 3' (c) up a 3 → 3 ′ a 1 2 3' (d) side 1 3 ′ → 2

Translations between STA and PFA

We present polynomial time translations between weak STAs and PFAs and vice versa, which preserve runs up to simple correspondences and thus languages.

Weakness. Following [START_REF] Alur | Marrying words and trees[END_REF], we call an STA weak if stat n = stat e and all rules have the form open a q 0 → q 1 q 0 or close a q 0 q 1 → q 2 . As proved in Theorem 1 of [START_REF] Alur | Marrying words and trees[END_REF] for NWAs, every STA A is equivalent to some weak STA B of size at most

|B| = O(|stat A e |•|stat A n |). To see this, let stat B n = stat B e = stat A e × stat A n , with init B = init A × stat A n and final B = final A × stat A n .
The rules of B are derived from those of A according to the following two inference schemas.

open a q → q 1 γ 1 ∈ rul A γ 2 ∈ stat A n open a (q, γ 1 ) → (q 1 , γ 2 ) (q, γ 1 ) ∈ rul B close a q γ → q 1 ∈ rul A γ 1 , γ 2 ∈ stat A n q 2 ∈ stat A e close a (q, γ 1 ) (q 2 , γ) → (q 1 , γ 2 ) ∈ rul B
From PFAs to weak STAs. We transform PFAs P into weak STAs s(P ) by removing intermediate tree states, identifying rules for down and open, and combining rules for up and side into close. Let stat s(P ) = stat P e , init s(P ) = init P , and final s(P ) = final P , and let the following schemas define the rules of s(P ): down a q 0 → q 1 ∈ rul P open a q 0 → q 1 q 0 ∈ rul s(P ) up a q 1 → γ 1 ∈ rul P side q 0 γ 1 → q 2 ∈ rul P close a q 1 q 0 → q 2 ∈ rul s(P )

From weak STAs to PFAs. Let A be a weak STA. We define a corresponding PFA p(A) such that s(p(A)) = A. This shows that p(A) and A recognize the same tree language. Let stat open a q 0 → q 1 q 0 ∈ rul A down a q 0 → q 1 ∈ rul p(A) close a q 0 q 1 → q 2 ∈ rul A up a q 0 → (a, q 0 ) ∈ rul p(A) side q 1 (a, q 0 ) → q 2 ∈ rul p(A) Theorem 4 Every PFA can be converted into an STA accepting the same language, and vice versa.

PROOF. First, we prove that L(s(P )) = L(P ). This translation preserves the first function r e of runs. Since s(P ) is weak, this function is sufficient to define a whole run of s(P ). Conversely, given a run of s(P ) on t, we can easily build the second function r n as every close rule used in r e is generated using an intermediate tree state. These translations preserve acceptance, so L(P ) = L(s(P )).

Second, we show that for all weak STAs A, s(p(A)) = A. Recall that weakness can be assumed w.l.o.g. Translations of open and down rules are exactly symmetric. The double inclusion of close rules of A and s(p(A)) can be easily checked. Initial and final states are also preserved.

Thus, PFAs can be converted into weak STAs with fewer states so that the tree languages are preserved. Vice versa, there exists a language preserving translation which may increase the number of states by a factor of |Σ|.

The runs of STAs and corresponding PFAs assign the same event states to opening and closing events. This means that they define the same runbased queries, when selecting in event states only. This is illustrated in Fig. 6(a), by a run of the PFA corresponding to the STA of the previous example Fig. [START_REF] Berlea | Binary queries for document trees[END_REF].

As a consequence, we can rely on the query answering algorithm for pushdown forest automata [START_REF] Berlea | Binary queries for document trees[END_REF] for answering run-based weak STA queries. Removing the weakness limitation does not impose any problem. This way, we obtain a query answering algorithm for n-ary queries defined by STAs and thus NWAs.

Conclusion

We proposed STAs in order to prove the equivalence of NWAs and PFAs. The main advantage of STAs is that they directly operate on unranked trees rather than encodings thereof. We believe that deterministic STAs are the most natural tree automata notion for all kinds of XML streaming tasks. Adding weakness looks simpler but sometimes implies to put useless information in states.

Fig. 1 .

 1 Fig. 1. The total ordering on events(a(a(b), b))

4 Fig. 2 . 2 Fig. 3 .

 4223 Fig. 2. Glushkov automata for DTD a → ab + b and b → ǫ

Fig. 5 .

 5 Fig.5. Successful run of the NWA in Fig.3

Fig. 6 .

 6 Fig. 6. Run of a PFA

  p(A) e= stat A and stat p(A) n = Σ × stat A , initial and final states remaining the same. The following inference schemas detail how the rules of p(A) are inferred from A.

More general definitions of nested words in the literature do permit dangling edges, internal positions, and unmatched labels, that we exclude here.

Acknowledgments

The authors thank Anne-Cécile Caron, Luc Ségoufin and Sophie Tison for insightful work and discussions. This work was partially supported by the Enumeration project ANR-07-blanc.


Sabah Al-Fedaghi
email: sabah.alfedaghi@ku.edu.kw

Diagrammatic Formalism for Complex Systems: More than One Way to Eventize a Railcar System

Keywords: Conceptual modeling, system development process, static model, dynamic model, behavioral model

This paper is in the intersection of software engineering and system engineering, two intimately intertwined disciplines. A dominating theme in this paper is the integral conceptualization of systems at large, as well as an underlying concern with software systems. In the software development life cycle, challenges still exist in translating requirements into a design artifact and then into an implementation (e.g., coding), then validating the results. From our perspective, software engineering requires an integrating paradigm toward a unified modeling orientation. Many methodologies, languages, and tools exist for facilitating system development processes. This paper is a venture into project development. To focus the materials, we concentrate on Harel's novel (and classic) development environment, which integrates a scenario-based engineering object orientation and statecharts through developing a railcar system. The railcar system is used as a detailed sample of translating requirements into a design artifact and then into an implementation, then validating the result. The project is re-cased as a single integrated modeling endeavor to be contrasted with the scenario and statecharts' development. The result of this scheme is an enriched understanding through experimenting with and contrasting various development methods of software projects.

Introduction

This paper is in the intersection of software engineering and system engineering, two intimately intertwined disciplines [START_REF] Yang | Ontology Learning for Systems Engineering Body of Knowledge[END_REF]. A dominating theme in the research work is the integral conceptualization of systems. To understand such integration, consider Buede and Miller's [START_REF] Buede | The Engineering Design of Systems Models and Methods[END_REF] definition of a system as -a collection of hardware, software, people, facilities, and procedures organized to accomplish some common objectives.‖ This same definition is used in the adopted model in this paper, the so called thinging machine (TM). An abstract thinging machine is constructed from an intertwining net of hardware, software, person, facility, and procedure thinging submachines organized to accomplish common objectives. We will demonstrate the assembly of such machines with the case study of a railcar system [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF]. The main component of this system is software. Thus, our underlying concern is with the development of software systems. In software development life cycles, challenges still exist in translating the requirement layer into a design layer and then into an implementation code layer, then validating the correctness of the results [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF].

Difficulties in Software and System Engineering

We view difficulties with software engineering as a special case of difficulties in system engineering. According to Yang [START_REF] Yang | Ontology Learning for Systems Engineering Body of Knowledge[END_REF], the major reason for system failure costs is a lack of adequate information exchange and communication within projects [START_REF] Van Ruijven | Ontology for Systems Engineering[END_REF], as a quarter of these failures arise during a system's design phase. This can be traced to a lack of efficient collaborations between parties involved in the system's life cycle processes. According to Hallberg et al. [START_REF] Hallberg | Ontology for Systems Development[END_REF], no -unambiguous‖ and comprehensive use of concepts exists in the systems development field [START_REF] Yang | Ontology Learning for Systems Engineering Body of Knowledge[END_REF]. This causes misunderstandings, misinterpretations, and irritations when one is developing systems, which inhibit the emerging system's functioning and usability [START_REF] Yang | Ontology Learning for Systems Engineering Body of Knowledge[END_REF]. Additionally, according to Ernadot [START_REF] Ernadote | Ontology-Based Pattern for System Engineering[END_REF], present system engineering standards remain document centric, making their model-based transition very difficult. The prerequisite of model-based engineering is to achieve a logically rigorous specification of all processes (i.e., what things/objects exist in the ontology, what events are, and how they evolve). observe that current system development standards fail to handle such issues explicitly because their textual descriptions often have terminological ambiguity and relational inconsistencies.

Needs

The international standard of ISO/IEC/IEEE 15288: 2015, Systems and Software Engineering -System Life Cycle Processes provides generic top-level process descriptions to support systems engineering [START_REF] Yang | An Ontology Model for Systems Engineering Derived from ISO/IEC/IEEE 15288: 2015: Systems and Software Engineering-System Life Cycle Processes[END_REF]. According to Yang, Cormican, and Yu [START_REF] Yang | An Ontology Model for Systems Engineering Derived from ISO/IEC/IEEE 15288: 2015: Systems and Software Engineering-System Life Cycle Processes[END_REF], due to dependence on an input-processoutput (IPO) diagram, the processes defined in the standard lack a whole and systemic blueprint. They require the tracing of each input or output so that each can be specified and detailed. No model is provided to define each process, classify elements, clarify the relationships, and unify the terminology.

From our perspective, system and software engineering require an integrating paradigm that shifts their direction to focusing on unifying notions, instead of divergence and variation. The basic premise of this paper is that a crucial instrument that assists in the software development process is a single integrated conceptual model that stakeholders from various professional backgrounds understand and discuss, and that can be tested and validated, either manually or automatically, at various layers [START_REF] Dori | Model-Based Systems Engineering with OPM and SysML[END_REF][START_REF] Dori | What Is a System? An Ontological Framework[END_REF].

Overview of the Paper

In the next section, we relate the paper to the general topic of system development. Of special importance in this context is modeling compositions using diagrammatic representations, which can increase understanding and motivate discussions about interactions before systems are effectively designed. This leads to -possibly reducing risks and costs associated to system misbehaviors discovered in advanced stages of the development process‖ [START_REF] Ramos | Extending Statecharts to Model System Interactions[END_REF]. Clearly, this subject is very broad; thus, we focus on a single detailed system: a railcar system. Section 3 reviews the basic TM modeling. Section 4 provides a new contribution in the form of a TM example, which includes a comparison with known state machines. In particular, the example demonstrates the explicit representation of events and behavior in TM modeling. The following sections include detailed specifications for recasting the selected railcar system using TM modeling. The hope is that this model project demonstrates the viability of TM modeling for system development.

Related Works

Many methodologies, languages, and tools exist for facilitating the software development process. To produce concrete results that disclose the features of the aforementioned TM model, we recast a fully detailed system scheme from Harel et al.'s [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF] project, which involves a novel development environment that integrates a scenario-based engineering object orientation and statechart formalism for system development [START_REF] Dori | What Is a System? An Ontological Framework[END_REF]. Their integration enables semantically rich execution as well as the sharing of and interfacing with objects and events. It can be used to create and enhance testable models from the early stage, which involves requirements elicitation, to the detailed design stage [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF]. According to Harel et al. [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF], scenario-based specifications are characterized by their inter-object nature, and a scenario can contain a flow of events involving any number of objects, both internal and external, including subsystems and human users.

Our perspective is different from Harel et al.'s approach [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF] and other similar methodologies and modeling techniques (e.g., UML and SysML). These methodologies achieve success in modeling projects based on the multiplicity of their specifications (e.g., statecharts for objects) and the variation of their representations (heterogeneous types of UML diagrammatic notions). However, they fail to furnish a nucleus around which various phases of the engineering process evolve. However significant the need is for different views of the system, a basic need still exists for an underlying model that links views and events together in a uniform, vertically multilevel conceptual structure.

Thinging Machines

The TM model articulates the ontology of the world in terms of an entity that is simultaneously a thing and a machine, called a thimac [START_REF] Al-Fedaghi | Conceptual Temporal Modeling Applied to Databases[END_REF][START_REF] Al-Fedaghi | Computer Program Decomposition and Dynamic/Behavioral Modeling[END_REF][START_REF] Al-Fedaghi | UML Modeling to TM Modeling and Back[END_REF]. A thimac is like a double-sided coin. One side of the coin exhibits the characterizations that the thimac assumes; on the other side, operational processes emerge, which provide a dynamism that goes beyond structures or things to embrace other things in the thimac. A thimac preserves individuality and simultaneously is understood to be a cluster of regions (bundles, to be defined later) from which dynamics originate, in the form of events (to be defined later)see Fig. 1.

A thing is subjected to doing (e.g., a tree is a thing that is planted, cut, etc.), and a machine does (e.g., a tree is a machine that absorbs carbon dioxide and uses sunlight to make oxygen). The tree thing and the tree machine are two faces of the tree thimac. A thing is viewed based on Heidegger's [START_REF] Heidegger | The Thing[END_REF] notion of thinging, in which a thing is a flux of five static generic actions that, with time, transform into atomic event constellations within specified acceptable behaviors (see Fig. 2).

The simplest type of machine is shown in Fig. 3. The actions in the machine (also called stages) are as follows: Arrive: A thing moves to another machine. Accept: A thing enters a machine. For simplification, we assume that all arriving things are accepted; hence, we can combine the thing's arrival and acceptance into the receive stage.

Thimac (Abstract) Machine

Regions of events

Thing, e.g., railcar system

Release: A thing is marked as ready for transfer outside of the machine (e.g., passengers in an airport wait to board their plane following passport clearance). Process: A thing is changed in form, but no new thing results. Create: A new thing is born in a machine. Transfer: A thing is input into or output from a machine.

Additionally, the TM model includes storage and triggering (denoted by a dashed arrow in this study's figures), which initiates a flow of things from one machine to another. Multiple machines can interact with each other through the movement of things or by triggering stages. Triggering is a transformation from one series of movements to another (e.g., electricity triggers cold air).

TM Modeling Example

The purpose of this section is to demonstrate TM modeling in contrast to other modeling-in this case, for describing a state machine. Specifically, we show that state diagrams model static and not behavioral descriptions.

General Description of TM Modeling

TM modeling produces three levels of description: static, dynamic, and behavioral models. A static description provides logical and complete descriptions of machines and intermachines in the modeled system. The description constructs the whole model as a machine. Each machine in the model still has its own machinery, as a machine and as part of the model as a machine. The whole assembly is a TM; for example, the whole model is created, processed, released, transferred, and/or received, and every submachine creates, processes, releases, transfers, and/or receives things (machines). The -or‖ indicates that some machines may not consist of all five actions. Additionally, each machine in the assembly has links to other outside machines. For simplicity, we will not include -create‖ in every machine and assume that the mere presence of the machine implies that it is created. Additionally, we will not surround each machine or submachine by a rectangle, especially when the (flow) thing inside the machine is coming from another machine.

At the static level, only structurality exists. In addition, no change occurs. The meaning of staticity can be illustrated as shown in Fig. 4 (left). It can be said that the movement of the ball occurs where it changes locations. However, time is not incorporated into the static model, in the sense that time does not appear in the picture. The illusion of time as a spatial quantity is inevitable as soon as time is spatialized [START_REF] Deleuze | Bergsonism. Zone Books[END_REF]. In such a picture, the ball may be specified as appearing first in the middle, then at the right end, and finally at the left end. That is, no time specification exists for which position follows another position. The representation specifies logical space relationships, not temporal ones. If time is involved, we would have a single ball in Fig. 4 instead of six balls. Thus, the static model can include contradictions as shown in Fig. 4 (right), in which traffic in two directions is permitted on a one-lane street. In the static model, such a description is permitted because time is not included in such a description. When time is involved, traffic is permitted in one direction, say at night, and it is permitted in the opposite direction during the day.

A static model is a single picture of all relevant machines. As a thing, it may be susceptible to dynamics. In the model, dynamics refers to an assembly of machines. For example, John is applauding; his hands are clapping each other. These dynamics are capabilities that are not in the static model because they involve portions of the model. To inject such dynamics, we must divide the description into decompositions that change within the static model. Accordingly, we must decompose the static model into regions that may make changes. The identification of these regions produces the dynamic model. To realize these potential changes, we must inject time into these regions to create events. An event is a static region (the location of the change) and a time submachine. Finally, the events gather into a chronological order to form the behavioral model.

Example of TM Modeling

According to Excel software [START_REF]Excel Software: State Model. Excel Software[END_REF], tables are an effective way of expressing information about states and events in modeling. This is illustrated in the state transition table shown in Fig. 5. Fig. 6 shows the corresponding TM models for the given states and actions. Note that events are not included because they are second-level notions and will be included when the TM behavioral model is developed. In Fig. 6, first, money is seen entering the machine (to the right of the thick vertical line, circle 1). This makes the machine receive the money (2) and process it [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF]. In this process, verification is performed as follows:

-If it fails (4), a rejection-for example, a message-is sent out ( 5). -If it passes, the equivalent coins are released (7).

-The coin storage is processed (8) to determine whether sufficient funds exist.

Accordingly, if sufficient funds are available, no further action is taken, and the machine waits for the next detection of input money [START_REF] Dori | Model-Based Systems Engineering with OPM and SysML[END_REF].

-If insufficient funds [START_REF] Dori | What Is a System? An Ontological Framework[END_REF] are available, the -out of money‖ light is turned ON [START_REF] Ramos | Extending Statecharts to Model System Interactions[END_REF]. -If additional funds are provided [START_REF] Al-Fedaghi | Conceptual Temporal Modeling Applied to Databases[END_REF], the -out of money‖ light is turned OFF [START_REF] Al-Fedaghi | Computer Program Decomposition and Dynamic/Behavioral Modeling[END_REF].

One clear observation from Fig. 6 is that it does not include anything about time. To illustrate this, consider the definition of time in a TM for the event money refill as shown in Fig. 7. Note that the event money refill is different from the series (order) of actions for money refill as will be discussed later.

An event is a machine including at least three submachines: the region (of the event), time, and the event itself. Thus, the static description in Fig. 6 can be decomposed into regions of events as shown in Fig. 8. There, the static TM model is decomposed into the following. In contrast to state machines, TM modeling explicitly introduces time to construct events by using these decompositions as regions of events. Accordingly, we represent the event in a region by E (for event), with the region's name being a subscript. Thus, we have the events of E A , E B , E C , E D , E E , E F , E G , E H , and E I . Fig. 9 shows the chronology of these events that form the machine's behavior.

Examining the state machine represented by the table in Fig. 5, we see that states are just regions or locations in the TM static representation. The state verify dollar is a region in the static description where a potential event exists. Verify dollar is a space without time embedded in it. Thus, if we have the sequence of states (verify dollar, dispensing coins), then this sequence does not reflect a behavior because the sequence of verify dollar on Feb. 2000, dispense coins on Jan. 2021 is a correct sequence of states but is not acceptable behavior.

To reach behavior, we must add time to states. Accordingly, states are static and are not behavioral descriptions. This observation is important in system development based on states and statechart diagrams.

The Railcar System

Several papers have discussed a railcar system [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF][START_REF] Harel | Executable Object Modeling with Statecharts[END_REF][START_REF] Ali | Modeling and Calculation of Scenarios Reliability in Component-Based Software Systems[END_REF][START_REF] Ali | Strategy for Scalable Scenarios Modeling and Calculation in Early Software Reliability Engineering[END_REF][START_REF] Liu | A Formal Semantics for Complete UML State Machines with Communications[END_REF]. The system involves six terminals located on a cyclic path. Each pair of adjacent terminals is connected by two rail tracks, one for clockwise and one for counterclockwise travel. Several railcars transport passengers between terminals. A control center receives, processes, and sends data to various components (see the partial picture in Fig. 10). Each terminal has a parking area containing four parallel platforms.

According to Harel et al. [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF], statecharts [START_REF] Harel | Statecharts: A Visual Formalism for Complex Systems[END_REF] augment conventional state machines with notations and semantic definitions for the concurrency and hierarchy necessary to specify and then directly execute complex behavior. An objectoriented version of the statechart language has become the basis for the state-based language of the UML. Additionally, statecharts have become the visual formalism of choice for intra-object behavior specification [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF]. This intra-object behavior is typically specified in the UML sequence diagrams; however, -the translation from an inter-object, scenario-based specification to implementation is a central issue in software engineering, and constitutes a substantial part of many software development efforts‖ [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF]. A main objective of the railcar system example is to -present an overall development philosophy, which supports a natural integration of inter-object and intra-object methodologies‖ [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF]. Fig. 11 shows a sample diagram that Harel et al. [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF] uses in modeling the railcar system.

The purpose of our showing portions of this diagram is to contrast them later with what we called the integral conceptualization of systems in the introduction of this paper, as TM will use a single diagram with multilevel semantics (e.g., static and behavioral).

In addition to the different modeling styles, the points to watch in developing the railcar system are as follows:  Modeling projects based on a multiplicity of specifications (e.g., statecharts for objects) and variations of representations (heterogeneous types of UML diagrammatic notions)  Modeling projects based on a nucleus around which various phases of the engineering process evolve, with an underlying model linking various views and events together into a uniform, vertically multi-level conceptual structure.

Additionally, Harel et al. [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF] do not provide a formal definition of an event, even though the word is repeated more than 50 times in the article.

Apparently, they took the notion of events from UML. However, they mention, -One of the main technical issues […] was what mechanism to use for interobject interaction.

[…] we adopted the two mechanisms: An object can generate an event,

[and] an object can invoke an operation of another object‖ [START_REF] Harel | Integrating Inter-Object Scenarios with Intra-object Statecharts for Developing Reactive Systems[END_REF].

Here, the central issue is the claim of having rigorously defined semantics of precise model behavior over time. Events in such an orientation are even more important of a notion than that of objects.

To emphasize the issue under discussion, here, we reexamine what an event is in TM. Consider a phenomenon such as depressing a button, denoted as -a.‖ This is called an event (see Harel [START_REF] Ali | Modeling and Calculation of Scenarios Reliability in Component-Based Software Systems[END_REF]). In TM, a is a type of (series) action. It involves the flow of a hand to process the button. This description is just a specification, just as how x + y is a description and not something happens in reality. Similarly, depressing a button is not an event but rather a type of event.

Hence, a state machines (and consequently statecharts) cannot express events, let alone behavior. Depressing a button becomes an event when it emerges as -a + time‖-that is, a (as a series of actions [e.g., create, process, etc.]; see Fig. 2 in section 2) emerges within time, which imposes its features on a. For example, the series of (waking up, eating breakfast, going to work) is not a series of events even if each action is specified with a time stamp. For example, the series of (waking up at 6 AM on 8/1/2020, eating breakfast at 7 AM on 8/1/2020, going to work at 9 AM on 8/1/2021) is not a series of events because time specification has its own rules. The state and statechart diagram are just static descriptions of a system, just as class and sequence diagrams are. In TM, time is a secondlevel aspect in modeling that lifts the entire model to another dimension. This type of thinking guides the recasting of the railcar system as follows.

Modeling the Railcar System

From our perspective, the railcar system can be viewed as follows:

(a) The processes in each terminal are repeated in each of the six terminals. Thus, we can concentrate on one terminal.

(b) Inside each terminal are two halves that mirror each other, with each serving one direction of travel. Hence, the functional design is repeated in each half of the terminal. (c) An important feature of the system is the existence of parking areas in the terminals. We will also assume that only two spots are available in the parking system (P): P1 and P2. Hence, Fig. 12 shows the resulting architectural description of any terminal.

(d) In addition to the terminals, we will assume that the whole railcar system is divided into four types of 100-yard areas as shown in Fig. 13, where -T denotes a terminal, -B is the area just before the terminal, -A is the area just after the terminal, and -C is the area next to A. Note that the sequence of A, C will be repeated until the next terminal is reached, where C becomes B.

We start by modeling the traffic going from top to bottom. When a railcar enters an area, the area is flagged as occupied, and the flag is set to unoccupied when the railcar leaves the area as shown in Fig. 14 for the four types of areas. Additionally, special consideration exists for a possible conflict between an approaching railcar entering the terminal and a railcar leaving the parking lots. We give priority to the first railcar over the latter. Thus, when a rail car enters B, it flags approaching to block any railcar coming from P. As soon as an approaching railcar receives the signal that T is unoccupied: -It reserves it (dash arrow pointing down) as occupied even though it is still in A. This is to ensure that no railcar comes from P, as the occupied flag blocks other railcars from entering, in addition to the approaching flag (note the OR operation).

-The approaching railcar can now leave B and enter T; thus, B is set to unoccupied, and the approaching flag is reset.

We start at the top-right corner of Fig. 15 (number 1 in green), where the railcar is about to enter B.  Fig. 15 The static model of one terminal of the railcar system.

 As soon as the railcar crosses to B (2), it sets the flags as occupied and approaching (3), which blocks any railcar from coming from P to T (4).  As the railcar approaches, the railcar itself is processed; for example, the railcar slows down, stops, and watches for the unoccupied flag (5 and 6) being set by the last railcar to leave T (5). If T is not occupied (6), the approaching railcar makes T occupied even before entering T (7).  Now, the railcar leaves B, setting its status to unoccupied and resetting the approaching flag [START_REF] Yang | An Ontology Model for Systems Engineering Derived from ISO/IEC/IEEE 15288: 2015: Systems and Software Engineering-System Life Cycle Processes[END_REF]. It moves to the terminal, where it parks for 90 seconds [START_REF] Dori | Model-Based Systems Engineering with OPM and SysML[END_REF].  After stopping in the terminal for 90 seconds, the railcar either continues its travel trail [START_REF] Dori | What Is a System? An Ontological Framework[END_REF] or goes to park in terminal P1 or P2, assuming that one of them is available [START_REF] Ramos | Extending Statecharts to Model System Interactions[END_REF]. In the latter case, the railcar enters the parking facilities (12); it enters either P1 or P2 (13).  If the rail car enters P (12), it parks in P1 or P2 (13). Later, if a railcar leaves P, it goes back to the station (14 and 15).  If the railcar goes ahead to its journey station (10), then before leaving T, a check occurs as to whether A is unoccupied. This flag is set to A itself by the last railcar to leave it (16); otherwise, the railcar in T waits. Hence, when A is not occupied, the railcar moves into A, making it occupied (17). The same thing is repeated for any consecutive areas, such as A and C: -Determining whether the next area is unoccupied (18 and 19) before moving in.

-Making the area occupied upon moving in, and triggering unoccupied when moving out (20 and 21). Now, we partition the static model in an attempt to identify the regions where events are situated or occur, as well as to prepare for specifying the system's chronology, thus specifying the system's behavior. Here, we see the in state (statecharts) that these static regions are misidentified as the loci of behavior.

According to the state-machine literature, these loci are triggered by (outside) events-for example, pressing a key that changes them (e.g., from terminal is empty to terminal is occupied). However, this change is a logical change, not a temporal one. The terminal is empty in the 19th century changing to become occupied in the 21st century is a change in the corresponding state machine because the order of change is satisfactory. Similarly, such a familiar example of ordering a product in the 19th century that leads to delivering the product in the 21st century is acceptable in state machines because they are timeless logical machines. In TM, the decompositions of the static model are further assimilated with time to define events.

The set of events in the railcar system is given as follows (see Fig. 16). Event 1 (E 1 ): Assuming B is unoccupied, the railcar enters B, making it occupied. Event 2 (E 2 ): Approaching is set. Event 3 (E 3 ): Traffic from P1 and P2 is blocked. Event 4 (E 4 ): The railcar in B is processed (being slowed, stopped) while the railcar waits for the decision on whether it can enter the terminal. Event 5 (E 5 ): Unoccupied of T is set by the last railcar to leave the terminal. If the system starts from nothing, then unoccupied should be set initially. Event 6 (E 6 ): The railcar sets the terminal to occupied and then leaves B, changing the area's status to unoccupied and resetting approaching. Event 7 (E 7 ): The railcar enters T. Event 8 (E 8 ): The railcar stops in the terminal for 90 seconds. Event 9 (E 9 ): A is flagged as unoccupied by the last railcar to leave that area. Event 10 (E 10 ): The railcar leaves T, setting the terminal status to unoccupied and the status of A to occupied. Event 11 (E 11 ): C is flagged as unoccupied by the last railcar to leave that area. Event 12 (E 12 ): The railcar leaves B, changing B's status to unoccupied. Event 13 (E 13 ): The railcar moves to C, changing C's status to occupied. Event 14 (E 14 ): In T, the railcar moves to park in P1 or P2. We assume that empty parking spots are globally known. Event 15 (E 15 ): A railcar moves out of P1 or P2 to T, changing T's status to occupied. Fig. 17 shows the resultant behavior of the railcar system. Of course, such a behavior is recurrent in other terminals.

Conclusion

In the software development life cycle, challenges still exist in translating requirements into a design artifact and then into an implementation, then validating the results. Many methodologies, languages, and tools exist for facilitating system development processes. This paper is a venture into project development. We concentrate on a specific methodology used in Harel et al.'s novel development environment, which integrates a scenario-based engineering object orientation and statecharts into developing a railcar system. The railcar system is used as a detailed sample of translating requirements into a design artifact and then into an implementation, then validating the results. The project is recased as a single integrated modeling endeavor, to be contrasted with scenario/statechart development. This scheme enriches understanding through experimenting with and contrasting various development methods for software projects. For example, our claim that state machines are timeless logical machines seems to be an important issue that, of course, requires further consideration of the notions of events and states.

Fig. 1

 1 Fig.1Illustration of the thimac as a thing/machine (left) and its dynamics, which are specified by decomposing the machine into regions of events (right).

A:

  Detection of money B: Processing of the money C: Verification is failed, and a rejection is sent. D: Verification is passed, and coins are dispensed. E: Coins are processed F: Coins are insufficient, and the out-of-money light is turned ON. G: Money is sufficient. H: Money is refilled. I: The out-of-money light is turned OFF.