International Telemetering Conference Proceedings / October 30-November 02, 1995 / Riviera Hotel, Las Vegas, Nevada / In its simplest form an automaton can be considered a set of inputs, a process, and a set of outputs. Certainly telemetry can be thought of in this way as well. Automata theory is a cross between mathematics and computer science which considers how to precisely define the inputs, the outputs, and the process of translating the one into the other. The input to an automaton can be described using a formal grammar. Two standard bit stream encodings, PCM matrices and MIL-STD-1553, are described using grammars. An example of how a grammar can be used to decode a bit stream is given. Further, ambiguity and complexity of bit stream encodings are discussed in the context of grammars. It is thus illustrated how grammars can be used to cleanly define and decode telemetry bit streams.

published_or_final_version / Physics / Master / Master of Philosophy

New tools are available for reconstructing the attractor basins of discrete dynamical networks where state-space is linked according the network's dynamics. In this thesis the computer software "Discrete Dynamics Lab" is applied to examine simple networks ranging from cellular automata (CA) to random Boolean networks (RBN), that have been widely applied as idealised models of physical and biological systems, to search for general principles underlying their dynamics. The algorithms and methods for generating pre-images for both CA and RBN, and reconstructing and representing attractor basins are described, and also considered in the mathematical context of random directed graphs. RBN and CA provide contrasting notions of self-organisation. RBN provide models of hierarchical categorisation in biology, for example memory in neural and genomic networks. CA provide models at the lower level of emergent complex pattern. New measures and results are presented on CA attractor basins and how they relate to measures on local dynamics and the Z parameter, characterising ordered to "complex" to chaotic behaviour. A method is described for classifying CA rules by an entropy-variance measure which allows glider rules and related complex rules to be found automatically giving a virtually unlimited sample for further study. The dynamics of RBN and intermediate network architectures are examined in the context of memory, where categorisation occurs at the roots of subtrees as well as at attractors. Learning algorithms are proposed for "sculpting" the basin of attraction field. RBN are proposed as a possible neural network model, and also discussed as a model of genomic regulatory networks, where cell types have been explained as attractors

We compare two methods for software specification: <em>algebraic specifications</em> and automata. While algebraic specifications have been around since the 1970s and have been studied extensively, specification by automata is relatively new. Its origins are in another veteran method called <em>trace assertions</em>, which considers a software module as a set of traces, that is, a sequences of function executions. A module is specified by a set of canonical traces and an equivalence relation matching one of the canonical traces to each non-canonical trace. It has been recently shown that trace assertions is an equivalent method to specification by automata. In continuation of this work on trace assertions and automata, we study how automata compare with algebraic specifications. We prove that every specification using an automaton can be converted into an algebraic specification describing the same abstract data type. This conversion utilises a set of canonical words, representing states in the automaton. We next consider varieties of monoids as a heuristic for obtaining more concise algebraic specifications from automata. Finally, we discuss the opposite conversion of algebraic specifications into automata. We show that, while an automaton always exists for every abstract data type described by an algebraic specification, this automaton may not be finitely describable and therefore may not be considered as a viable method for software specification.

Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. This connection goes back to a much longer history in the 1960s, through the fundamental work of Büchi-Elgot-Trakhtenbrot, which shows the expressive equivalence of automata and logical systems such as monadic second-order logic on finite and infinite words. This allowed the handling of specifications (where global system properties are stated), and implementations (which involve the definition of the local steps in order to satisfy the global goals laid out in the specifications) in a single framework. This connection has been extended to and well-investigated for many other structures such as trees, finite pictures, timed words and data words. For many computer science applications, however, quantitative phenomena need to be modelled, as well. Examples are vagueness and uncertainty of a statement, length of time periods, spatial information, and resource consumption. Weighted automata, introduced by Schützenberger, are prominent models for quantitative aspects of systems. The framework of weighted monadic second-order logic over words was first introduced by Droste and Gastin. They gave a characterization of quantitative behavior of weighted finite automata, as semantics of monadic second-order sentences within their logic. Meanwhile, the idea of weighted logics was also applied to devices recognizing more general structures such as weighted tree automata, weighted automata on infinite words or traces. The main goal of this thesis is to give logical characterizations for weighted automata models on pictures and data words as well as for Büchi-tiling systems in the spirit of the classical Büchi-Elgot theorem. As the second goal, we deal with synchronizing problem for data words. Below, we briefly summarize the contents of this thesis. Informally, a two-dimensional string is called a picture and is defined as a rectangular array of symbols taken from a finite alphabet. A two-dimensional language (or picture language) is a set of pictures. Picture languages have been intensively investigated by several research groups. In Chapter 1, we define weighted two-dimensional on-line tessellation automata (W2OTA) taking weights from a new weight structure called picture valuation monoid. This new weighted picture automaton model can be used to model several applications, e.g. the average density of a picture. Such aspects could not be modelled by semiring weighted picture automaton model. The behavior of this automaton model is a picture series mapping pictures over an alphabet to elements of a picture valuation monoid. As one of our main results, we prove a Nivat theorem for W2OTA. It shows that recognizable picture series can be obtained precisely as projections of particularly simple unambiguously recognizable series restricted to unambiguous recognizable picture languages. In addition, we introduce a weighted monadic second-order logic (WMSO) which can model average density of pictures. As the other main result, we show that W2OTA and a suitable fragment of our weighted MSO logic are expressively equivalent. In Chapter 2, we generalize the notion of finite pictures to +ω-pictures, i.e., pictures which have finite number of rows and infinite number of columns. We extend conventional tiling systems with a Büchi acceptance condition in order to define the class of Büchi-tiling recognizable +ω-picture languages. The class of recognizable +ω-picture languages is indeed, a natural generalization of ω-regular languages. We show that the class of all Büchi-tiling recognizable +ω-picture languages has the similar closure properties as the class of tiling recognizable languages of finite pictures: it is closed under projection, union, and intersection, but not under complementation. While for languages of finite pictures, tiling recognizability and EMSO-definability coincide, the situation is quite different for languages of +ω-pictures. In this setting, the notion of tiling recognizability does not even cover the language of all +ω -pictures over Σ = {a, b} in which the letter a occurs at least once – a picture language that can easily be defined in first-order logic. As a consequence, EMSO is too strong for being captured by the class of tiling recognizable +ω-picture languages. On the other hand, EMSO is too weak for being captured by the class of all Büchi-tiling recognizable +ω-picture languages. To obtain a logical characterization of this class, we introduce the logic EMSO∞, which extends EMSO with existential quantification of infinite sets. Additionally, using combinatorial arguments, we show that the Büchi characterization theorem for ω-regular languges does not carry over to the Büchi-tiling recognizable +ω-picture languages. In Chapter 3, we consider the connection between weighted register automata and weighted logic on data words. Data words are sequences of pairs where the first element is taken from a finite alphabet (as in classical words) and the second element is taken from an infinite data domain. Register automata, introduced by Francez and Kaminski, provide a widely studied model for reasoning on data words. These automata can be considered as classical nondeterministic finite automata equipped with a finite set of registers which are used to store data in order to compare them with some data in the future. In this chapter, for quantitative reasoning on data words, we introduce weighted register automata over commutative data semirings equipped with a collection of binary data functions in the spirit of the classical theory of weighted automata. Whereas in the models of register automata known from the literature data are usually compared with respect to equality or a linear order, here we allow data comparison by means of an arbitrary collection of binary data relations. This approach permits easily to incorporate timed automata and weighted timed automata into our framework. Motivated by the seminal Büchi-Elgot-Trakhtenbrot theorem about the expressive equivalence of finite automata and monadic second-order (MSO) logic and by the weighted MSO logic of Droste and Gastin, we introduce weighted MSO logic on data words and give a logical characterization of weighted register automata. In Chapter 4, we study the concept of synchronizing data words in register automata. The synchronizing problem for data words asks whether there exists a data word that sends all states of the register automaton to a single state. The class of register automata that we consider here has a decidable non-emptiness problem, and the subclass of nondeterministic register automata with a single register has a decidable non-universality problem. We provide the complexity bounds of the synchronizing problem in the family of deterministic register automata with k registers (k-DRA), and in the family of nondeterministic register automata with single register (1-NRA), and in general undecidability of the problem in the family of k-NRA. To this end, we prove that, for k-DRA, inputting data words with only 2k + 1 distinct data values, from the infinite data domain, is sufficient to synchronize. Then, we show that the synchronizing problem for k-DRA is in general PSPACE-complete, and it is in NLOGSPACE for 1-DRA. For nondeterministic register automata (NRA), we show that Ackermann(n) distinct data, where n is the number of states of the register automaton, might be necessary to synchronize. Then, by means of a construction, proving that the synchronizing problem and the non-universality problem in 1-NRA are interreducible, we show the Ackermann-completeness of the problem for 1-NRA. However, for k-NRA, in general, we prove that this problem is undecidable due to the unbounded length of synchronizing data words.

The creation and use of models is critical not only to the scientific process, but also to life in general. Selected features of a system are abstracted into a model that can then be used to gain knowledge of the workings of the observed system and even anticipate its future behaviour. A key feature of the modelling process is the identification of commonality. This allows previous experience of one model to be used in a new or unfamiliar situation. This recognition of commonality between models allows standards to be formed, especially in areas such as measurement. How everyday physical objects are measured is built on an ingrained acceptance of their underlying commonality. Complex systems, often with their layers of interwoven interactions, are harder to model and, therefore, to measure and predict. Indeed, the inability to compute and model a complex system, except at a localised and temporal level, can be seen as one of its defining attributes. The establishing of commonality between complex systems provides the opportunity to find common metrics. This work looks at two dimensional cellular automata, which are widely used as a simple modelling tool for a variety of systems. This has led to a very diverse range of systems using a common modelling environment based on a lattice of cells. This provides a possible common link between systems using cellular automata that could be exploited to find a common metric that provided information on a diverse range of systems. An enhancement of a categorisation of cellular automata model types used for biological studies is proposed and expanded to include other disciplines. The thesis outlines a new metric, the C-Value, created by the author. This metric, based on the connectedness of the active elements on the cellular automata grid, is then tested with three models built to represent three of the four categories of cellular automata model types. The results show that the new C-Value provides a good indicator of the gathering of active cells on a grid into a single, compact cluster and of indicating, when correlated with the mean density of active cells on the lattice, that their distribution is random. This provides a range to define the disordered and ordered state of a grid. The use of the C-Value in a localised context shows potential for identifying patterns of clusters on the grid.

by Siu Chi Sang Obadiah. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1999. / Includes bibliographical references (leaves 66-68). / Abstracts in English and Chinese. / Chapter 1 --- Pseudorandom Number Generator --- p.5 / Chapter 1.1 --- Introduction --- p.5 / Chapter 1.2 --- Statistical Indistingushible and Entropy --- p.7 / Chapter 1.3 --- Example of PNG --- p.9 / Chapter 2 --- Basic Knowledge of Cellular Automata --- p.12 / Chapter 2.1 --- Introduction --- p.12 / Chapter 2.2 --- Elementary and Totalistic Cellular Automata --- p.14 / Chapter 2.3 --- Four classes of Cellular Automata --- p.17 / Chapter 2.4 --- Entropy --- p.20 / Chapter 3 --- Theoretical analysis of the CA PNG --- p.26 / Chapter 3.1 --- The Generator --- p.26 / Chapter 3.2 --- Global Properties --- p.27 / Chapter 3.3 --- Stability Properties --- p.31 / Chapter 3.4 --- Particular Initial States --- p.33 / Chapter 3.5 --- Functional Properties --- p.38 / Chapter 3.6 --- Computational Theoretical Properties --- p.42 / Chapter 3.7 --- Finite Size Behaviour --- p.44 / Chapter 3.8 --- Statistical Properties --- p.51 / Chapter 3.8.1 --- statistical test used --- p.54 / Chapter 4 --- Practical Implementation of the CA PNG --- p.56 / Chapter 4.1 --- The implementation of the CA PNG --- p.56 / Chapter 4.2 --- Applied to the set of integers --- p.58 / Chapter 5 --- Application to Cryptography --- p.61 / Chapter 5.1 --- Stream Cipher --- p.61 / Chapter 5.2 --- One Time Pad --- p.62 / Chapter 5.3 --- Probabilistic Encryption --- p.63 / Chapter 5.4 --- Probabilistic Encryption with RSA --- p.64 / Chapter 5.5 --- Prove yourself --- p.65 / Bibliography

No description available.

In this thesis we summarize our recent work on the control of timed systems.

Specifying varying speeds and temporal relationships is necessary when programming graphical animations, but support for temporal programming has usually been done by adding new language features to a Visual Programming Language (VPL), and these features must be mastered over and above the other aspects of the VPL. However, some researchers have believed that time should be able to be treated like just another dimension. In this thesis, we explore whether temporal programming can indeed be done using exactly the same devices as in spatial programming in grid-oriented VPLs. Toward this end, we provide a continuum of models aimed at this goal and discuss their advantages and disadvantages. Also, we identify core issues that help illuminate the essence of the problem. / Graduation date: 2001