Search

Cyber-physical systems (CPSs) integrate discrete computations with continuous physical processes and can be highly nonlinear and nondeterministic. Unlike the verification of CPS, which is difficult to handle, the falsification of CPS fulfills certain requirements from testing by seeking witness behavior of these systems and is easier to conduct. However, existing falsification techniques may fail to support the general complex CPS in practice because they usually focus on certain restricted classes of systems. In this article, we present a path-oriented, derivative-free approach to falsify safety properties in nonlinear and nondeterministic CPS. In our approach, we model the behavior of CPS by hybrid automata. Then, we enumerate candidate paths of hybrid automata (HA), transform the feasibility of candidate paths into optimization problems, and solve these optimization problems by our newly proposed classification model-based, derivative-free optimization algorithm. We also provide two novel pruning techniques to further improve the efficiency and efficacy of our approach: 1) a nested optimization structure with better model refinements for continuous search space pruning and 2) a hardly feasible path prefixes guided backtracking for discrete search space pruning. We implement our approach into a tool called PDF. Our experiments showed that PDF supported the safety falsification of CPS in all of our benchmarks, and it achieved success rates no lower than 95% in only seconds on 22/28 of the benchmarks. [ABSTRACT FROM AUTHOR]

The main drawback of implementing the traditional diagnoser for Discrete-Event Systems proposed in the literature is that its state set can be very large, requiring the use of a large amount of memory to store the diagnoser for complex systems. In this paper, we propose a greedy algorithm for the computation of a reduced diagnoser, that preserves the diagnosability of the system language and the same diagnosis delay as the original diagnoser. The reduction algorithm is based on merging states of the original diagnoser, and uses a free parameter to choose which and in what order states should be merged with a view to trying to obtain a diagnoser with the smallest possible number of states. [ABSTRACT FROM AUTHOR]

The problem of model construction of finite state machines (FSMs) from observed data is addressed by borrowing the methods and ideas of system identification in control theory. The construction contains three steps. Firstly, the dynamic matrix of FSM to be constructed is built from observed input and output data, the result is a logical matrix (LM). In the second stage, the obtained dynamic matrix is first represented as an exponent of an LM; then the LM is used as the structure matrix of the FSM to be built. Finally, an FSM making the observed data verified the known dynamic equation is constructed according to the one-to-one correspondence between structure matrices and FSMs. In addition, some theoretic results are presented: several necessary and sufficient conditions for the exponent representability of LMs; classification of LMs (LMs are classified into two categories, type-1 and type-2 ones, according to their exponent representability); and methods of representing each kind of LM as an exponent form of an LM. [ABSTRACT FROM AUTHOR]

In this article, we define $\lambda$ -approximate simulations and bisimulations for fuzzy automata over complete Heyting algebras. The value $\lambda$ presents the degree of language similarity or equality between observed fuzzy automata. Algorithms for computing the greatest $\lambda$ -approximate simulations and bisimulations are given. We show that $\lambda$ -approximate simulations and bisimulations on a fuzzy automaton can be effectively used for factorization of fuzzy automata. We present the algorithm that splits the interval of the degrees of language similarity or equality into subintervals with the same minimal corresponding factor fuzzy automata. [ABSTRACT FROM AUTHOR]

Many biomedical systems and some engineering systems can be modeled as fuzzy discrete event systems. In this article, fuzzy discrete event systems with constraints (FDESwC) are introduced and detectabilities of FDESwC are investigated. While detectabilities of conventional crisp discrete event systems (DES) have been investigated before, detectabilities of FDESwC are much more complex because the state space of FDESwC is infinite, unlike that of crisp DES. To overcome this difficulty, trajectories of FDESwC bounded by $N$ observations are considered and $N$ -detectabilities are introduced. $N$ -detectabilities of crisp DES are first defined and proved to be equivalent to detectabilities if $N$ is sufficiently large. Fuzzy $N$ -detectabilities of FDESwC are then defined. An algorithm is derived to check fuzzy $N$ -detectabilities. While fuzzy detectabilities require to determine which state the system is in, this requirement can be relaxed in some applications. To do so, fuzzy $D$ -detectabilities are introduced and investigated, where the requirement is to distinguish certain pairs of states. [ABSTRACT FROM AUTHOR]

Manufacturing systems may be subject to external attacks and failures, so it is important to deal with the recovery of the system after these situations. This article deals with the problem of recovering a manufacturing system, modeled as a discrete event system (DES) using the supervisory control theory (SCT), when the control structure, called supervisor, desynchronizes from the physical plant. The desynchronization may be seen as plant and supervisor being in uncorresponding states. The recovery of the system may be attained if there is a word, the synchronizing word, that regardless the state of each one of them, brings the system and supervisor back to a known state. The concepts of synchronizing automata are used to do so. In this article, we show under what conditions a set of synchronizing plants and specifications leads to a synchronizing supervisor obtained by the SCT. The problem is extended to cope with multiple supervisors, proposing a local recovery when possible. We also present a simple way to model problems, composed of machines and buffers, as synchronizing automata such that it is always possible do restore synchronization between the control (supervisor) and the plant. Note to Practitioners—Given the unpredictability of faults and malicious attacks occurring in industrial systems, recovery strategies are crucial for a harmonic operation of the plant. The possibility of leading the system to a known state, recovering control, is of extreme importance to the safety of industrial processes. The method proposed in this article uses well-known concepts of supervisory control theory (SCT) of discrete event systems (DESs), introducing the recovery process (using recovery events) in the modeling phase such that it is possible to isolate and fix only the part of the control system subject to the fault. The result of the proposed approach allows the implementation of such control system with the recovery procedure directly in the programmable logic controllers (PLCs). [ABSTRACT FROM AUTHOR]

The article surveys some selected topics in descriptive set theory, showing how the problem of classifying sets according to their complexity has been tackled since Cantor's creation of the subject to current research. [ABSTRACT FROM AUTHOR]

A novel type of hardware accelerators called automata processors (APs) have been proposed to accelerate finite-state automata. The bone structure of an AP is a hierarchical routing matrix that connects many memory arrays. With this structure, an AP can process an input symbol every clock cycle, and hence achieve much higher performance compared to conventional architectures. However, the design automation for the APs is not well researched. This article proposes a fully automated tool named APmap for mapping the automata to APs that use a two-level routing matrix. APmap first partitions a large automaton into small graphs and then maps them. Multiple transformations are applied to the automaton by APmap to meet hardware constraints. The experiments on a standard benchmark suite show that our approach leads to around 19% less storage utilization compared to state-of-the-art. [ABSTRACT FROM AUTHOR]

In recent decades, deadlock control for automated manufacturing systems has been an active area. Most researchers have assumed that allocated resources, such as sensors, actuators, and controllers never fail. However, this case is not prevalent in practice due to the unexpected failure of resources. Thus, the objective of robust control is presented in this article. Several methods have been developed along this direction, such as methods that combine neighborhood constraints and the modified Banker’s algorithm, as well as methods based on critical places. To explore their effectiveness and performance, we not only conduct a comparison investigation but also develop new theoretical results. According to the experimental results, critical place-based approaches are simpler, more efficient, and more comprehensive than the Banker’s algorithm-based approaches in response to resource failures. This article is motivated by the control of production Petri nets; however, the results are also applicable to other more complex systems. [ABSTRACT FROM AUTHOR]

Priced timed automata (PTA) are discrete-event system models with temporal constraints and a cost function and are used to pose optimal scheduling and routing problems. To date, solutions to these problems have been found offline and executed open loop.This open-loop control strategy makes it impossible to account for disturbances, i.e., changes in costs or scheduling constraints over time. To address this shortcoming, this work’s first contribution is a closed-loop model predictive control (MPC) framework for PTA, enabling decision-making based on real-time model updates. To ensure the feasibility of an MPC problem, it is often desirable to soften constraints. However, the contemporary PTA theory does not consider soft constraints. Thus, this work’s second contribution is to integrate constraint softening with PTA control by harnessing the capabilities of new solvers enabled by the recasting of the models and control problem into first-order logic by employing modified encoding schemes based on existing works. Finally, the proposed control framework and implementation are demonstrated in a simulation case study on the guidance of a product through a manufacturing system. [ABSTRACT FROM AUTHOR]

Model-based testing has been highlighted in the last few decades. Many improvements have been proposed for this testing method. One improvement is the use of extended regular expressions (EREs) for modeling software behavior, and then using the ERE model to generate test paths. To improve the theory of test generation based on the ERE model, this article presents an algebraic system, named transition algebra, by extending Kleene algebra. Eight operations and their corresponding operational properties, including basic and nonbasic operational properties, are designed for transition algebra, and all such properties are proven. Five examples are given to illustrate the use of ERE modeling and algebraic operations. To ensure the automatic generation of test paths from the ERE model, the article proves that any ERE model constructed by transition algebra can be converted to a set of transition sequences. Compared to Kleene algebra with tests, transition algebra has more operations to build a powerful ERE model and more operational properties to process the ERE model for the generation of test paths. [ABSTRACT FROM AUTHOR]

In logic locking, the finite-state machine (FSM) embedded in a sequential circuit is often chosen to be obfuscated. Such an obfuscation scheme using a class of nongroup additive cellular automata (CA) called $D1 * CA$ and $D1 * CA_{\mathrm{ dual}}$ to obfuscate each state transition of an FSM has been proposed previously. Since $D1 * CA$ and $D1 * CA_{\mathrm{ dual}}$ provide high testability even in the absence of scan-based design-for-testability techniques, they conceal the sequential elements, thus thwarting several existing scan-chain attacks. In this article, we introduce a novel attack to extract the secret key used to obfuscate each state transition of the FSM, by utilizing the information leaked by the leftmost CA cell, which is obtained via an oracle query to the obfuscated circuit. The proposed attack has two variants: 1) when the combinational circuit of the Interrupt Logic is not logic encrypted and 2) when the Interrupt Logic is logic encrypted with a $k$ -bit key. The first attack variant has a complexity of $\mathcal {O}(n \cdot m)$ , where $n$ denotes the number of transitions in the FSM, and $m$ denotes the maximum transition cycle length of the underlying $D1 * CA$. The second attack variant has a complexity of $\mathcal {O}(n\cdot q_{\mathrm{ max}})$ , where $q_{\mathrm{ max}}$ denotes the maximum number of oracle queries (equal to the number of primary inputs involved in that state transition), followed by a SAT-attack to extract the $k$ -bit key of the corresponding Interrupt Logic. The experimental evaluation of the attack on CA-based obfuscated benchmark circuits establishes the effectiveness of our proposed attack. [ABSTRACT FROM AUTHOR]

Implementing operational strategies is a sustainable and effective way for providing good bus serviceability, but the effects of the strategies on other traffic participants, e.g., cars, have drawn little attention. This paper thus aims to explore the effects of the mutual interference between buses and private cars, when applying a bus control strategy to a regular transit line. Three threshold-based strategies are compared, including (a) holding control (HC); (b) limited boarding control (LBC) and (c) holding combined with limited boarding control (H-LBC). A cellular automaton based model is proposed to depict the interaction between cars and buses, and the model parameters are calibrated using data collected from a real-life bus route in Beijing, China. The control strategies are evaluated by their benefits for three stakeholders involved in the system, including passengers, bus operator and car drivers. Simulation results show that a good bus control strategy does not only improve the efficiencies of bus operating and passenger travel, but also speed up the car running by alleviating traffic congestion. In turn, the car volume is an important factor when setting the optimal parameter for control strategies. Moreover, the comparison suggests that H-LBC outperforms the other two strategies in improving the service level for passengers, buses as well as cars, especially under crowded scenarios. [ABSTRACT FROM AUTHOR]

Play is a very important activity for children development and there are evidences that it can be an added value when used for educational purposes. Research about how to integrate play in education points to the importance of teacher role, namely how children play can be scaffold and guided. However, there is also lack of agreement about how to guide children playing and the impact of the guidance in the activity development and competences promoted. Given the characteristics of automata, especially the fact that they include a narrative and a mechanism, they can be used within a play based pedagogy, to implement activities related to plan and construct toys and to promote competences as observation, problem solving, creativity in the STEM areas. To explore this potential of moving toys to promote STEM in the early years of schooling is the aim of the Erasmus + AutoSTEM project. This work aims to describe the main objectives and resources of the AutoSTEM project, including the description of a workshop to construct a toy with a sliding mechanism, the Jelly Bird. The procedures involved the presentation and observation of the toy, detailed instructions on how to construct it, the decoration and the elaboration of a narrative about it. 23 children from the 2nd year of basic education participated in the workshop. The analysis of the prototypes shows that all the participants built them properly. Also some alternative ideas to the proposal initially presented emerged, as well as a diversity of narratives. These data suggest that the instructions enhanced the construction of the prototype, but did not inhibit the creativity of the work developed.

The motivation and interest of children and young people in science areas remains a challenge for contemporary education, and there is also evidence of the importance of its promotion since the early years of schooling as well as the use of interdisciplinary approaches. The Erasmus + AutoSTEM project aims to analyse the potential of constructing automata or “moving toys” as a motivation strategy for learning in the areas of science, technology, engineering and mathematics (STEM), in the early years of schooling. The characteristics of the automata, namely the fact that they have a narrative part and a mechanism, allow, in a playful approach, to implement activities related to the planning and construction of those toys and to enhance skills such as observation, problem solving, creativity and also skills in the referred STEM areas. In this work, the description of the implementation and evaluation of automata workshops in a school of the 1st year of basic education is made. The data were collected based on direct observation focusing on dimensions of engagement and a questionnaire regarding interest, perception of learning, difficulties experienced, suggestions for improvement. Results evidence that the children showed curiosity for the prototypes presented, having immediately designed their own project, explored materials and completed the construction, in some cases with their own proposals. The perceived difficulties vary according to the age, as well as the type of mechanism chosen.

In recent years, opacity has received increasing attention in terms of analyzing security and privacy problems. Opacity is a confidentiality property that characterizes a system's ability to hide its secret information from any external intruders. A systematic overview of opacity in the context of discrete event systems (DESs) was conducted; this paper firstly reviews the verification methods and computational complexity of the opacity in DESs using the formalisms of automata and Petri nets. When the system is verified to be non-opaque, the approaches that synthesize an opaque system are summarized. Finally, the future research directions and open problems of opacity in DES are also reviewed.

This paper aims at tracking down, by looking at late medieval and early modern discussions over the ontological status of artifacts, the main steps of the process through which nature became theorized on a mechanistic model in the early 17th century. The adopted methodology consists in examining how inventions such as mechanical clocks and automata forced philosophers to modify traditional criteria based on an intrinsic principle of motion and rest for defining natural beings. The paper studies different strategies designed in the transitional period 1300–1600 for making these inventions compatible with classical definitions of nature and artifacts. In the first part of the paper, it is shown that, even if virtually all medieval philosophers acknowledged an ontological distinction between artifacts and natural beings, these different strategies demonstrate a growing concern about the consistency of the art/nature distinction. The next part of the paper studies how mechanical clocks, even before the Scientific Revolution, served as theoretical models for applying mechanistic views to different objects (be they cosmological, physical or biological). The epistemological function of clocks appears to stem from different factors (like the specific manufacturing of late medieval clocks as well as the evolution of 16th-century mechanics) that are listed in this second part of the paper. These factors, combined with the definitional issues raised by automata, explain that clocks became the symbol of a new approach to natural philosophy, characterized by the collapse of the art/nature distinction and the “mechanization of nature”.

In recent years, there has been a growing need and interest in formally reasoning about the quality of software and hardware systems. As opposed to traditional verification, in which one considers the question of whether a system satisfies a given specification or not, reasoning about quality addresses the question of how well the system satisfies the specification. We distinguish between two approaches to specifying quality. The first, propositional quality, extends the specification formalism with propositional quality operators, which prioritize and weight different satisfaction possibilities. The second, temporal quality, refines the "eventually" operators of the specification formalism with discounting operators, whose semantics takes into an account the delay incurred in their satisfaction. In this article, we introduce two quantitative extensions of Linear Temporal Logic (LTL), one by propositional quality operators and one by discounting operators. In both logics, the satisfaction value of a specification is a number in [0, 1], which describes the quality of the satisfaction. We demonstrate the usefulness of both extensions and study the decidability and complexity of the decision and search problems for them as well as for extensions of LTL that combine both types of operators. [ABSTRACT FROM AUTHOR]

This paper presents an approach to automatically amend an erroneous model of an implementation using a safety specification as the basis to ensure safety. Industrially, safety PLCs are common to ensure safe operations. However, before its commissioning, the implemented safety code must be tested for faults caused by spurious transitions and missing safety transitions. Spurious transitions are implemented events that are not prescribed by the safety specification, while missing safety transitions are unimplemented safety events that are prescribed by the safety specification. The presence of these faults can result in material or human damage. The proposed approach requires the model of an implementation to be trace equivalent with the given safety specification only in terms of traces composed of safety events, which is captured by the notion of safe-IOCOS. If the implementation emits other than the specified safety events then the implementation is not safe-IOCOS and requires amendment. This is achieved by removing the spurious transitions and adding the missing safety events in the implementation using synthesis techniques from the supervisory control theory. The infimal controllable superlanguage is used to compute the infimal safety extension , which adds the missing safety transitions. It is shown how the resulting model of an implementation after amendment is both safe-IOCOS and controllable with respect to the specification. [ABSTRACT FROM AUTHOR]

The majority of existing linear temporal logic (LTL) planning methods rely on the construction of a discrete product automaton, which combines a discrete abstraction of robot mobility and a Büchi automaton that captures the LTL specification. Representing this product automaton as a graph and using graph search techniques, optimal plans that satisfy the LTL task can be synthesized. However, constructing expressive discrete abstractions makes the synthesis problem computationally intractable. In this article, we propose a new sampling-based LTL planning algorithm that does not require any discrete abstraction of robot mobility. Instead, it incrementally builds trees that explore the product state-space, until a maximum number of iterations is reached or a feasible plan is found. The use of trees makes data storage and graph search tractable, which significantly increases the scalability of our algorithm. To accelerate the construction of feasible plans, we introduce bias in the sampling process, which is guided by transitions in the Büchi automaton that belong to the shortest path to the accepting states. We show that our planning algorithm, with and without bias, is probabilistically complete and asymptotically optimal. Finally, we present numerical experiments showing that our method outperforms relevant temporal logic planning methods. [ABSTRACT FROM AUTHOR]

The current study aims to establish a connection between graphs and automata theory, which appar- ently demonstrate different mathematical structures. Through searching out some properties of one of these structures, we try to find some new properties of the other structure as well. This will result in obtaining some unknown properties. At first, a novel automaton called zero-forcing (Z-F) finite automata is defined according to the notion of a zero-forcing set of a graph. It is shown that for a given graph and for some zero forcing sets, various Z-F-finite automata will be obtained. In addition, the language and the closure properties of Z-F-finite automata, in particular; union, connection, and serial connection are studied. Moreover, considering some properties of graphs such as the closed trail, connected and complete; some new features for Z-F-finite automata are presented. Further, it is shown that there is not any finite graph such that f be a part of the language of its Z-F-finite automata. Actually, it is proved that for every given graph, the Z-F-finite automata of it does not show any closed trail containing all edges for every zero forcing set, but if the graph G has been a closed trail containing all edges, then the Z-F-finite automata of it has a weak closed trail containing all edges. Some examples are also given to clarify these new notions. [ABSTRACT FROM AUTHOR]

Model checking is a powerful technique for verifying the correctness of systems with respect to the requirements. While some errors happen in the property, the model itself, or the environment, we think that satisfaction of the property is meaningless (vacuous) satisfaction. It misleads users of model-checking that a system is correct. Traditional temporal logic vacuity detection is based on a syntactic definition. It is undesirable because vacuity detection would depend on syntactic formalization choices that have no effect on the semantics. This article presents an automaton-based semantic vacuity detection method which synthesizes the property into the automaton and detects the vacuity by detecting the reachability of the automaton state. Compared with the traditional syntactic-based vacuity detection, the proposed method is well suited for detecting vacuity with respect to multiple occurrences of a sub-formula. At the same time, we do not distinguish the temporal logic language. As long as the property can be synthesized into an automaton, this method can be well applied. We extend the vacuity to the satisfaction of real-time properties. The real experiments show that this method is applied efficiently in practical vacuity detection. To our knowledge, it is the first attempt to present and solve practical vacuity in an automaton view. [ABSTRACT FROM AUTHOR]

Time sensitive networking (TSN) is an emerging technology for in-vehicle networks, which has strict timing constraints and dependability requirements. The performance and efficiency of TSN depend on a reliable scheduling mechanism for real-time communications. Traditionally, the TSN scheduler is analyzed using simulations and testing, which are error-prone and inaccurate. In this article, we employ a timed model checker UPPAAL to formally model and analyze the TSN scheduler with a consideration of its transmission latency and time utilization. We first use the build-in assertion in UPPAAL to verify the deadlock-free property, safety property, and starvation-free property of our model. Then, we calculate the time utilization and the transmission delay of audio video bridging data frame under two scheduling mechanisms according to the simulation process. Then, we compared the time performance of this two scheduling mechanisms and found that each of them has their own advantages and disadvantages. This article provides a formal analysis framework for investigating scheduling strategies in TSN, which facilitates the designers to have a better understanding and development of TSN schedulers in the future. [ABSTRACT FROM AUTHOR]

For a formal language L , the problem of language enumeration asks to compute the length-lexicographically smallest word in L larger than a given input w ∈ Σ ∗ (henceforth called the L -successor of w). We investigate this problem for regular languages from a computational complexity and state complexity perspective. We first show that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are (in general) necessary and sufficient for an unambiguous finite-state transducer to compute L -successors. As a byproduct, we obtain that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are sufficient for a DFA to recognize the subset S (L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S (L) is represented as an NFA. It has been known that L -successors can be computed in polynomial time, even if the regular language is given as part of the input (assuming a suitable representation of the language, such as a DFA). In this paper, we refine this result in multiple directions. We show that if the regular language is given as part of the input and encoded as a DFA, the problem is in N L. If the regular language L is fixed, we prove that the enumeration problem of the language is reducible to deciding membership to the Myhill-Nerode equivalence classes of L under D L O G T I M E -uniform A C 0 reductions. In particular, this implies that fixed star-free languages can be enumerated in A C 0 , arbitrary fixed regular languages can be enumerated in N C 1 and that there exist regular languages for which the problem is N C 1 -complete. [ABSTRACT FROM AUTHOR]

Unmanned aircraft systems (UAS) collaborate with humans to operate in diverse, safety-critical applications. However, assurance technologies need to be integrated into the design process in order to guarantee safe behavior, thereby enabling UAS operations in the National Airspace System (NAS). In this paper, formal methods are integrated with learning-enabled systems representations. The generation and representation of knowledge are captured via monadic second-order logic rules in the cognitive architecture Soar. These rules are translated into timed automata, and a proof of correctness for the translation is provided so that safety and liveness properties can be checked in the formal verification environment Uppaal. This approach is agnostic to the learning mechanism used to generate the learned rules (e.g., chunking, etc.). An example of a fault-tolerant, learning-enabled UAS deciding which of four contingency procedures to execute under a lost link scenario while overflying an urban area is used to illustrate the approach. [ABSTRACT FROM AUTHOR]

Opacity, as an important security property, has been well investigated in crisp discrete event systems. However, in some practical systems, the general behaviors, secret and nonsecret behaviors obtained by the intruder need to be expressed as fuzzy sets rather than crisp sets. Under this situation, the intruder makes inferences by fuzzy logic rather than classic logic, thus the notions of the fuzzy opacity measures are desired to be established. First, by means of the basic laws of fuzzy logic, a general fuzzy opacity measure, as a template, is presented, in this article, for the given generalized characterizations of secret and nonsecret behaviors. Moreover, a specific measure, called as fuzzy initial-final opacity (FIFO) measure, is investigated under the assumption that the secrets and nonsecrets can be coded into the initial-final state-pairs. In addition, two variants of FIFO measure are also proposed under the assumptions that the secrets and nonsecrets are only related to the initial-states or final-states. With these fuzzy opacity measures, the system designers can evaluate the opacity degree of the systems to be designed. To show the applicability of the fuzzy opacity measures to practical systems, we finally present an illustrative example of evaluating the location privacy protection systems in location-based services by means of the fuzzy opacity measures. [ABSTRACT FROM AUTHOR]

The three large images that adorn folios 4v, 19v and 25v of the 12th-century cartulary have already been extensively studied and commented upon and continue to raise numerous problems of interpretation. On the assumption that these drawings are partly based on texts independent of the cartulary, the present study aims to try to identify these sources. In the case of the illustration on folio 4v, the investigation carried out through a series of historical and literary texts leads to the conclusion that the palace of Saint Aubert is probably inspired by the description of a hydraulic clock in the image of the celestial city. The illustration on folio 19v, dedicated to the Montois reform of Richard I, is based on the Introductio monachorum. The illustration on folio 25v, depicting two miracles that occurred on the Mount, seems to have two main sources: a life of William the Long Sword and the late eleventh-century book of Miracula. One of the two miracles is not associated with any of the charters in the cartulary, which raises the question of why the image was included in this collection.

(Ar) اسهامات الهندسة الميكانيكية الإسلامية في تطوير الآلات ذاتية الحركة (في ضوء كتاب الحيل للجزري) دراسة وصفية تحليلية هل كان للعرب المسلمين قديما باع في علم الهندسة الميكانيكية؟ وهل كان لهم السبق على الغرب في هذا المجال؟ من الملاحظ حاليا أن العرب والمسلمين في شتى دول العالم -تقريباً- أصبحوا مجرد مستهلكون لما ينتجه الغرب في شتى المجالات، نتيجة لما وصل اليه الغرب من تقدم وتطور تكنولوجي مستمر ومتنامي بسرعة فائقة. وهنا كان لابد لنا ان نتساءل هل كان العرب المسلمين على هذا الحال قديما؟ يقوم هذا البحث على اثبات فرضية أن العلماء المسلمين قد حققوا تقدماً كبيرا في مجال الهندسة الميكانيكية، واستطاعوا ابتكار آلات ذاتية الحركة، والمعروفة حديثاً بـ »الأتمته«. ووفقاً لذلك، كان الهدف الأساسي لهذا البحث هو إثبات صحة هذه الفرضية. يتناول هذا البحث بعض نماذج من الآلات ذاتية الحركة؛ وذلك من خلال كتاب »الجامع بين العلم والعمل النافع في معرفة الحيل الهندسية« لمؤلفه العالم المسلم الجزري. تضمن الكتاب - في الأصل مخطوط - وصف تفصيلي لهذه الآلات الميكانيكية ذاتية الحركة، وكيفية تنفيذها مشفوعا بالتصاوير الملونة المعروفة اصطلاحاً بـ »المنمنمات«. تتكون خطة البحث من تمهيد يتناول التعريف بما يصطلح عليه التكنولوجيا الدقيقة والأتمته » الآلات ذاتية الحركة«، ويلي ذلك تاريخ الأتمته بدءا من العصور القديمة وحتى العصور الوسطى. كما سيتناول البحث إسهامات علماء المسلمين في مجال الهندسة الميكانيكية بشكل عام، وفي مجال انتاج الآلات ذاتية الحركة بشكل خاص، مدعوما باستعراض نماذج للآلات ذاتية الحركة تم شرحها ضمن »كتاب الحيل«. ويلي ذلك السيرة الذاتية للعالم المسلم اسماعيل بن الرزاز الملقب بـ »الجزري «، بالإضافة إلى تحليل تاريخي وفني موجز عن المخطوط محل الدراسة. وفي النهاية سيتم عمل دراسة تحليلية للنماذج المختارة من الآلات ذاتية الحركة وعلاقتهم بالآلات الحديثة والصناعات التكنولوجية المتطورة. وفي المجمل واستنادا على »كتاب الحيل«، والذي يعود تاريخه للقرن ٧هـ/ ١٣م تمكن هذا البحث من التدليل على أن الآلات ذاتية الحركة ليست اختراعاً غربياً؛ بل هي نتاج الحضارة الإسلامية، ودليل ملموس على مدى تفوقهم في مجال الهندسة الميكانيكية منذ العصور الوسطى. (En) Were the Muslims in ancient times highly proficient in mechanical engineering? Did they have a head start over the West in this field? Unfortunately, it is noticeable nowadays that Arabs and Muslims all over the world became just consumers; exploiting all technological developments of the West that are rapidly growing. Here we had to wonder whether the Arab Muslims, long ago, was in this manner. This research hypothesizes that Muslims had attained an advanced level of mechanical engineering and were the inventors of the self-moving artifacts; recently known as automata. Accordingly, this research has undertaken the mission to prove that assumption. This paper focuses on automata machines, in light of «kitāb al-Ḥiyal» of the Muslim engineer al- Ǧazarī. This book -initially a manuscript- included a detailed description of these machines accompanied by painted illustrations known as «miniatures». The paper begins with a preface dealing with the meaning of fine technology and automata, followed by the story of automata since the antique ages and until the medieval epochs. The latter element is an indication of Muslims’ contributions to mechanical engineering in general, and automata in particular. This is supported by previewing samples on automata «self-moving» machines according to the miniatures of «kitāb al-Ḥiyal ». This is followed by briefed biography of the book’s author al- Ǧazarī and a historical and artistic analysis of the book itself. Finally, there is a concise scientific analysis of the chosen samples of automata and their relevance to modern machines and advanced technology industries. Conclusively, concerning the value of «kitāb al-Ḥiyal» which is dated back to the 7th century AH/ 13th century AD, this research accentuated that automata machines are not a Western invention, they are an outcome of the Golden Age of the Islamic civilization, proving their supremacy in mechanical engineering since the medieval epochs.