Search

This paper addresses fault pattern diagnosis of discrete event systems, involving fault pattern detection and diagnosability. A fault pattern is modelled as a finite automaton whose accepted language is the objective to be diagnosed, representing the occurrence of complex or composite faults. A verifier for fault pattern detection based on the synchronous product of a system and a fault pattern is proposed. By removing all silent events, a silent closure is calculated based on the synchronous product, which offers computational advantages for systems that have a large number of silent events. An NSC/FSC pair verifier is then computed by taking the product of a normal silent closure and an accepted silent closure. By studying indeterminate cycles of the NSC/FSC pair verifier, necessary and sufficient verification conditions are established, asserting that a system is diagnosable with respect to a fault pattern if and only if there is no indeterminate cycle in the NSC/FSC pair verifier. It is shown that the proposed method requires polynomial time at most. Finally, a case study to illustrate the results is provided. [ABSTRACT FROM AUTHOR]

Abstract With the emergence of powerful and low‐energy Internet of Things devices, deep learning computing is increasingly applied to resource‐constrained edge devices. However, the mismatch between hardware devices with low computing capacity and the increasing complexity of Deep Neural Network models, as well as the growing real‐time requirements, bring challenges to the design and deployment of deep learning models. For example, autonomous driving technologies rely on real‐time object detection of the environment, which cannot tolerate the extra latency of sending data to the cloud, processing and then sending the results back to edge devices. Many studies aim to find innovative ways to reduce the size of deep learning models, the number of Floating‐point Operations per Second, and the time overhead of inference. Neural Architecture Search (NAS) makes it possible to automatically generate efficient neural network models. The authors summarise the existing NAS methods on resource‐constrained devices and categorise them according to single‐objective or multi‐objective optimisation. We review the search space, the search algorithm and the constraints of NAS on hardware devices. We also explore the challenges and open problems of hardware NAS.

High-performance computers are used for computation-intensive tasks. It is essential for these systems to simultaneously execute several computation-intensive tasks for efficient and timely system utilization. Since typical tasks have a longer runtime, it is essential to determine the runtime of each task prior to execution and schedule them accordingly. We propose a method for predicting the runtime of MPI-based software. Initially, we analyze the source code of the software by translating the code to finite automata and measuring the state complexity. Next, the runtime of software is trained using a deep neural network (DNN) along with its state complexity. Herein, we propose three models based on DNN, statistics and their hybrid. DNN model is superior in comparison. Additionally, the adaptability of our method is demonstrated by showing that our method can adapt on new environment with 90% accuracy on various software. [ABSTRACT FROM AUTHOR]

We introduce an n-state Game of Life (GoL) on a cellular array (cells indexed by (i, j)), where each state σ = 0, ..., n − 1 has a nominal values vσ ≥ 0. The game involves computing the sum of the state values of the eight cells that surround cell (i, j) and using this sum to determine whether cell (i, j) stays in state σ, progress to state σ + 1, or reverts at state 0. We illustrate examples of this game, identifying still-life, oscillator, glider, and replicator patterns, as well as the long term behavior arising from random and regular starting configurations. Importantly, we provide two freely downloadable application programs that can be used to explore the behavior of the three and four state GoLs discussed in this paper [ABSTRACT FROM AUTHOR]

The Declare process modeling language has been established within the research community for modeling so-called flexible processes. Declare follows the declarative modeling paradigm and therefore guarantees flexible process execution. For several reasons, declarative process models turned out to be hard to read and comprehend. Thus, it is also hard to decide whether two process models are equal with respect to their semantic meaning, whether one model is completely contained in another one or how far two models overlap. In this paper, we follow an automaton-based approach by transforming Declare process models into finite state automatons and applying automata theory for solving this issue. [ABSTRACT FROM AUTHOR]

String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the past few years given the massive use of strings in different application domains like formal analysis, automated testing, database query processing, and cybersecurity. This article reports a comprehensive survey on string constraint solving by exploring the large number of approaches that have been proposed over the past few decades to solve string constraints. [ABSTRACT FROM AUTHOR]

Sofic shifts are symbolic dynamical systems defined by the set of bi-infinite sequences on an edge-labeled directed graph, called a presentation. We study the computational complexity of an array of natural decision problems about presentations of sofic shifts, such as whether a given graph presents a shift of finite type, or an irreducible shift; whether one graph presents a subshift of another; and whether a given presentation is minimal, or has a synchronizing word. Leveraging connections to automata theory, we first observe that these problems are all decidable in polynomial time when the given presentation is irreducible (strongly connected), via algorithms both known and novel to this work. For the general (reducible) case, however, we show they are all PSPACE -complete. All but one of these problems (subshift) remain polynomial-time solvable when restricting to synchronizing deterministic presentations. We also study the size of synchronizing words and synchronizing deterministic presentations. [ABSTRACT FROM AUTHOR]

Nominal automata are models for recognising languages over infinite alphabets, based on the algebraic notion of nominal set. Motivated by their use in automata theory, we show how to compute efficiently with nominal sets over the so-called total order symmetry , a variant which allows to compare alphabet letters for equality as well as their respective order. We develop an explicit finite representation of such nominal sets and basic constructions thereon. The approach is implemented as the library Ons (Ordered Nominal Sets), enabling programming with infinite sets. Returning to our motivation of nominal automata, we evaluate Ons in two applications: minimisation of automata and active automata learning. In both cases, Ons is competitive compared to existing implementations and outperforms them for certain classes of inputs. [ABSTRACT FROM AUTHOR]

The Nottingham group at 2 is the group of (formal) power series t + a 2 t 2 + a 3 t 3 + ⋯ in the variable t with coefficients a i from the field with two elements, where the group operation is given by composition of power series. The depth of such a series is the largest d ⩾ 1 for which a 2 = ... = a d = 0. Only a handful of power series of finite order (forcedly a power of 2) are explicitly known through a formula for their coefficients. We argue in this paper that it is advantageous to describe such series in closed computational form through automata, based on effective versions of proofs of Christol's theorem identifying algebraic and automatic series. Up to conjugation, there are only finitely many series σ of order 2 n with fixed break sequence (i.e. the sequence of depths of σ ∘ 2 i ). Starting from Witt vector or Carlitz module constructions, we give an explicit automaton-theoretic description of: (a) representatives up to conjugation for all series of order 4 with break sequence (1 , m) for m < 10 ; (b) representatives up to conjugation for all series of order 8 with minimal break sequence (1 , 3 , 11) ; and (c) an embedding of the Klein four-group into the Nottingham group at 2. We study the complexity of the new examples from the algebro-geometric properties of the equations they satisfy. For this, we generalise the theory of sparseness of power series to a four-step hierarchy of complexity, for which we give both Galois-theoretic and combinatorial descriptions. We identify where our different series fit into this hierarchy. We construct sparse representatives for the conjugacy class of elements of order two and depth 2 μ ± 1 (μ ⩾ 1). Series with small state complexity can end up high in the hierarchy. This is true, for example, for a new automaton we found, representing a series of order 4 with 5 states (the minimal possible number for such a series). [ABSTRACT FROM AUTHOR]

Venkatachala on the one hand, and Avdispahić & Zejnulahi on the other, both studied integer sequences with an unusual sum property defined in a greedy way, and proved many results about them. However, their proofs were rather lengthy and required numerous cases. In this paper, I provide a different approach, via finite automata, that can prove the same results (and more) in a simple, unified way. Instead of case analysis, we use a decision procedure implemented in the free software Walnut. Using these ideas, we can prove a conjecture of Quet and find connections between Quet's sequence and the "married" functions of Hofstadter. • Uses a new technique, automata theory, to prove properties of some greedily-defined integer sequences. • Finds much simpler proofs of some known results in the literature. • Finds a new connection between Quet's sequence and the Hofstadter married functions. [ABSTRACT FROM AUTHOR]

Abstract Visual simultaneous localization and mapping (vSLAM), one of the most important applications in autonomous vehicles and robots to estimate the position and pose using inexpensive visual sensors, suffers from error accumulation for long‐term navigation without loop closure detection. Recently, deep neural networks (DNNs) are leveraged to achieve high accuracy for loop closure detection, however the execution time is much slower than those employing handcrafted visual features. In this paper, a parallel loop searching and verifying method for loop closure detection with both high accuracy and high speed, which combines two parallel tasks using handcrafted and DNN features, respectively, is proposed. A fast loop searching is proposed to link the bag‐of‐words features and histogram for higher accuracy, and it splits the images into multiple grids for high parallelism; meanwhile, a DNN feature extractor is utilized for further verification. A loop state control method based on a finite state machine to control these tasks is designed, wherein the loop closure detection is described as a context‐related procedure. The framework is implemented on a real machine, and the top‐2 best accuracy and fastest execution time of 80‐543 frames per second (min: 1.84ms, and max: 12.45ms) are achieved on several public benchmarks compared with some existing algorithms.

A key component of blockchain technology is the ledger, viz., a database that, unlike standard databases, keeps in memory the complete history of past transactions as in a notarial archive for the benefit of any future test. In second-generation blockchains such as Ethereum, the ledger is coupled with smart contracts, which enable the automation of transactions associated with agreements between the parties of a financial or commercial nature. The coupling of smart contracts and ledgers provides the technological background for very innovative application areas, such as Decentralized Autonomous Organizations (DAOs), Initial Coin Offerings (ICOs), and Decentralized Finance (DeFi), which propelled blockchains beyond cryptocurrencies that were the only focus of first generation blockchains, such as Bitcoin. However, the currently used implementation of smart contracts as arbitrary programming constructs has made them susceptible to dangerous bugs that can be exploited maliciously and has moved their semantics away from that of legal contracts. We propose here to recompose the split and recover the reliability of databases by formalizing a notion of contract modeled as a finite-state automaton with well-defined computational characteristics derived from encoding in terms of allocations of resources to actors, as an alternative to the approach based on programming. To complete the work, we use temporal logic as the basis for an abstract query language that is effectively suited to the historical nature of the information kept in the ledger.

We address the following decision problem. Given a numeration system U and a U-recognizable set X ⊆ ℕ , i.e. the set of its greedy U-representations is recognized by a finite automaton, decide whether or not X is ultimately periodic. We prove that this problem is decidable for a large class of numeration systems built on linear recurrence sequences. Based on arithmetical considerations about the recurrence equation and on p-adic methods, the DFA given as input provides a bound on the admissible periods to test. [ABSTRACT FROM AUTHOR]

The idea behind the neutrosophic set is we can connect the concept by dynamics of opposite interacts and its neutral that are uncertain and get common parts. Automata theory is beneficial to solve computational complexity problem and also it is an influential mathematical modeling tool in computer science. Inspired by the concepts of neutrosophic sets and automata theory, here, we are introducing and discussing the algebraic concept of neutrosophic finite automata based on the paper [10]. Generally, composite machines can be achieved by the output of the one machine that will be used as input for another machines. This paper introduced the concept of composite automata under the environment of the neutrosophic set and also examined the box function between the composite neutrosophic finite automata.

String constraint solving refers to solving combinatorial problems involving constraints over string variables. String solving approaches have become popular over the past few years given the massive use of strings in different application domains like formal analysis, automated testing, database query processing, and cybersecurity. This article reports a comprehensive survey on string constraint solving by exploring the large number of approaches that have been proposed over the past few decades to solve string constraints. [ABSTRACT FROM AUTHOR]

Simulation‐based learning tools have become commonly used at all levels of education. They are recognized as an effective means of studying complex and abstract systems. In traditional teaching of compiler concepts, students are incapable of visualizing theoretical constructions, while the use of simulation systems represents an excellent blend of theoretical and practical experience. This paper describes a software system for visualization and simulation of basic compiler concepts and algorithms. The simulation tool enables students to visualize the operation of finite automata, convert a regular expression into deterministic finite automata (DFA) or nondeterministic finite automata, and simulate Thompson's construction algorithm. The process of constructing the LL(0) and LR(1) parsing tables is represented as a step‐by‐step simulation, with the user receives feedback on the correctness of each step before moving on to the next. The system is capable of calculating the FIRST and FOLLOW sets, graphically representing DFA, and constructing the corresponding parsing table. This tool provides a module for visualizing the process of machine code generation. [ABSTRACT FROM AUTHOR]

There are many cases in which our understanding of a system may be limited due to its complexity or lack of access into the entire system, leaving us with only partial system knowledge. This paper proposes a novel systematic active-learning method for realizing a partially-known Discrete Event System (DES). The proposed technique takes the available information about the system into account by tabularly capturing the known data from the system, and then, discovers the unknown part of the system via an active-learning procedure. For this purpose, a series of tables will be constructed to first infer the information about the system from the available data, and if unavailable, the developed algorithm collects the information through basic queries made to an oracle. It is proven that the developed technique returns a language-equivalent finite-state automaton model for the system under identification after a finite number of iterations. A real-world illustrative example is provided to explain the details of the proposed method.

This paper analyses simulation systems for teaching compilers, represents their technical characteristics and topics addressed, their benefits in the teaching process, and the advantages and disadvantages of each simulator analyzed. Based on this information, a reader can easily decide which simulator is the most suitable for his needs. The usage of simulators in education has been recognized as an effective tool for exploration of complex and dynamic systems. A simulator can illustrate a large number of abstract theoretical concepts from the various phases of program translation. Simulation systems in the field of compilers stand for a perfect combination of theory and practical experiences, and as such contribute to the improvement of the teaching process.

We develop a generic framework to extend the logics LTL, CTL+ and CTL⁎ by automata-based connectives from formal language classes and analyse this framework with regard to regular languages, visibly pushdown languages, deterministic and non-deterministic context-free languages. More precisely, we consider how the use of different automata classes changes the expressive power of the logics and provide algorithms for the satisfiability and model checking problems induced by the use of different classes of automata. For the model checking problem, we treat not only finite Kripke transition systems, but also visibly pushdown systems and pushdown systems. We provide completeness or undecidability results in all cases and show that the extensions we consider can formulate properties not expressible in classical temporal logics or regular extensions thereof. [ABSTRACT FROM AUTHOR]

In the constrained synchronization problem we want to know if a given input automaton admits a synchronizing word contained in a (fixed) regular constraint language. Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages and the computational complexity of the problem restricted to commutative input semi-automata. We give a full classification of the computational complexity of the constrained synchronization problem for commutative regular constraints. Depending on the constraint language, our problem becomes PSPACE -complete, NP -complete or polynomial time solvable. In addition, we derive a polynomial time decision procedure for the complexity of the constrained synchronization problem, given a constraint automaton accepting a commutative language as input. Furthermore, for commutative input semi-automata, the problem is decidable in polynomial time, regardless of the regular constraint language. [ABSTRACT FROM AUTHOR]

The linked governance set has presently been introduced as an attractive scheme to the region analysis in wireless sensor networks (WSNs). Therefore the key issue bothering the behavior of the prevailing Minimal sized Governing Set (MGS) based analysis standards is that they are focused on increasing the count of sleep nodes to safeguard the energy. It makes the lively sensors to feel immense loads for handling voluminous adjacencies. The quicker depletion of the lively sensors might detach the network standard and discards the region explored. Hence for offering an improved transmission of the network association analysis and lifespan, a precise count of sensors must be triggered. The intention is based on the angle restricted minimal load allowance of the MGS issues termed as Angle Restricted minimal load MGS (ARGS) to design the region analysis in WSNs. The precise decision of the angle restriction of ARGS equalizes the load within the network on the lively sensors enhances the network analysis and lifespan. The knowledge automation-based heuristics termed as Automata Theory-based Energy Efficient Area algorithm (ATEEA) is designed for locating a close optimal solution to the substitution identical ARGS issues in WSN. The analysis difficulties of the designed scheme to locate the optimal solution of the region analysis issue are estimated. Diverse experiments are performed to depict the supremacy of the designed analysis standards over the prevailing MGS-based schemes in terms of rate of coverage region, remaining energy, number of lively nodes and the lifetime of the networks. [ABSTRACT FROM AUTHOR]

Afflictions, or predispositions to have particular disorders in an animal are often caused by specific genes. However, some of these conditions could be avoided using genetic alterations during the breeding process. A good example is brachycephaly in dogs, which, in many cases, causes dyspnoea. In this research paper, we focused on using Finite Deterministic Automata for pattern recognition in dog genes in order to improve the breathing problems of French bulldogs, and other brachycephalic breeds. [ABSTRACT FROM AUTHOR]

In this paper, we study two important problems related to quasi-multiautomata: the complicated nature of verification of the GMAC condition for systems of quasi-multiautomata, and the fact that the nature of quasi-multiautomata has deviated from the original nature of automata as seen by the theory of formal languages. For the former problem, we include several new conditions that simplify the procedure. For the latter problem, we close this gap by presenting a construction of quasi-multiautomata, which corresponds to deterministic automata of the theory of formal languages and is based on the operation of concatenation.