Search

A weighted finite automaton has the finite-image property if the image of the weighted language associated with it is finite. We show two undecidability results concerning the finite-image property of weighted finite automata over semirings, respectively strong bimonoids. Firstly, we give a computable idempotent commutative past-finite ordered semiring such that it is undecidable, for an arbitrary deterministic weighted finite automaton over that semiring, whether has the finite-image property. Secondly, we give a computable commutative past-finite monotonic ordered strong bimonoid such that it is undecidable, for an arbitrary weighted finite automaton over that strong bimonoid, whether has the finite-image property. This shows that recent decidability results for suitable weighted finite automata over past-finite monotonic strong bimonoids cannot be extended to natural classes of ordered semirings and ordered strong bimonoids without further assumptions. [ABSTRACT FROM AUTHOR]

The early detection of cyber threats with cyber-attacks adapted to the nature of information systems is a crucial cybersecurity problem. This problem and the task of recognizing normal and abnormal states and behavior of various processes in information systems are closely related. An additional condition is often the absence of templates, signatures, or rules of normal behavior that would allow using existing statistical or other known methods of data analysis. We analyze the existing and propose a new method for detecting abnormal behavior without the use of signatures based on the finite state machine(FSM) model and the Security Information and Events Management (SIEM) system. [ABSTRACT FROM AUTHOR]

Information in non-standard address texts in Chinese is usually presented with rough content, complex and diverse presentation forms, and inconsistent hierarchical granularity, causing low accuracy in Chinese address parsing. Therefore, we propose a method for parsing non-standard address text in Chinese that integrates the Chinese Toponym Named Entity Recognition (CHTopoNER) model and a dynamic finite state machine (FSM). First, named entity recognition is performed by the CHTopoNER model. Sets of dynamic FSMs are then constructed based on the address hierarchical characteristics to sort and combine the Chinese address elements, thereby achieving address parsing on the Chinese internet. This method showed excellent accuracy in parsing both standard and non-standard placename addresses. In particular, this method performed better in address parsing for disordered or missing hierarchical elements than traditional methods using an FSM. Specifically, this method achieved accuracies of 96.6% and 96.8% for standard and non-standard placenames, respectively. These accuracies increased by 8.0% and 57.1%, respectively, compared with the integrated CHTopoNER model and traditional FSM, and by 7.4% and 19.8%, respectively, compared with the integrated CHTopoNER model and bidirectional FSM. After analysis, the address-parsing method showed good scalability and adaptability, which could be applied to various types of address-parsing tasks. [ABSTRACT FROM AUTHOR]

The early detection of arrhythmia can effectively reduce the risk of serious heart diseases and save time for treatment. Many healthcare devices have been widely used for electrocardiogram (ECG) monitoring. However, most of them can only complete simple two-classes detection and have unacceptable hardware overhead and energy consumption. For achieving accurate and low-power arrhythmia detection, a novel ECG processor application specific integrated circuit (ASIC) is proposed in this paper, which can perform the prediction of five types of cardiac arrhythmias and heart rate monitoring. To realize hardware-efficient R-peak detection, an ECG pre-processing engine based on a first derivative and moving average comparison method is proposed. Efficient arrhythmia detection is realized by the proposed low-power classification engine, which is based on a carefully designed lightweight artificial neural network (ANN) with good prediction accuracy. The hardware reuse strategy is used to implement the hardware logic of ANN, where computations are executed by only one processing unit (PU), which is controlled by a flexible finite state machine (FSM). Also, the weights of ANN are configurable to facilitate model updates. We validate the functionality of the design using real-world ECG data. The proposed ECG processor is implemented using 55 nm CMOS technology, occupying an area of 0.33 mm2. This design consumes 12.88 μW at a 100 kHz clock frequency, achieving a classification accuracy of 96.69%. The comparison results with previous work indicate that our design has advantages in detection performance and power consumption, providing a good solution for low-power and low-cost ECG monitoring. [ABSTRACT FROM AUTHOR]

Serious game is one of the pedagogical media capable of transferring knowledge to its players. This game genre requires a support system that adaptively selects the appropriate scenario for players to increase their interest and comfort. Therefore, this study proposed an adaptive scenario selection (ASS) system using a finite state machine based on an artificial neural network (ANN). The game scenario is selected by ASS based on five player preferences, including work, hobbies/interests, origin, group members, and repetition. Furthermore, the multi-layer perceptron (MLP) architecture was used in the scenario selection process for the proposed ANN method. The experimental stage was carried out using the theme of travel in several tourism destinations in Batu City, East Java, Indonesia. The experimental results show that ASS succeeded in generating adaptive game scenario choices for players based on their preference data with an accuracy of 67.25%. [ABSTRACT FROM AUTHOR]

The paper presents a comprehensive exploration of a novel image encryption and decryption methodology, leveraging finite state machines (FSM) for the secure transformation of visual data. The study meticulously evaluates the effectiveness of the proposed encryption algorithm using a diverse image dataset. The encryption algorithm demonstrates high proficiency in obfuscating the original content of images, producing cipher images that resemble noise, thereby substantiating the encryption’s effectiveness. The robustness of the proposed methodology is further evidenced by its performance in the National Institute of Standards and Technology Statistical Test Suite (NIST STS). Such achievements highlight the algorithm’s capability to maintain the stochastic integrity of encrypted data, a critical aspect of data security and confidentiality. Histogram analysis revealed that the encryption process achieves a uniform distribution of pixel values across the encrypted images, masking any identifiable patterns and enhancing the security level. Correlation analysis corroborated the success of the encryption technique, showing a substantial reduction in the correlation among adjacent pixel values, thereby disrupting spatial relationships essential for deterring unauthorized data analysis. This improvement indicates the algorithm’s efficiency in altering pixel patterns to secure image data. Additionally, a comparative analysis of correlation coefficients using various encryption methods on the Lenna image offered insights into the relative effectiveness of different techniques, emphasizing the importance of method selection based on specific security requirements and data characteristics.

A measure of the "goodness" or efficiency of the test suite is used to determine the proficiency of a test suite. The appropriateness of the test suite is determined through mutation analysis. Several Finite State Machine (FSM) mutants are produced in mutation analysis by injecting errors against hypotheses. These mutants serve as test subjects for the test suite (TS). The effectiveness of the test suite is proportional to the number of eliminated mutants. The most effective test suite is the one that removes the most significant number of mutants at the optimal time. It is difficult to determine the fault detection ratio of the system. Because it is difficult to identify the system's potential flaws precisely. In mutation testing, the Fault Detection Ratio (FDR) metric is currently used to express the adequacy of a test suite. However, there are some issues with this metric. If both test suites have the same defect detection rate, the smaller of the two tests is preferred. The test case (TC) is affected by the same issue. The smaller two test cases with identical performance are assumed to have superior performance. Another difficulty involves time. The performance of numerous vehicles claiming to have a perfect mutant capture time is problematic. Our study developed three metrics to address these issues: FDR/|TS|, FDR/|TC|, and FDR/|Time| generation tools were examined and tested using the developed metrics. Thanks to the metrics we have developed, the research contributes to eliminating the problems related to performance measurement by integrating the missing parameters into the system. [ABSTRACT FROM AUTHOR]

Most real-world dynamical systems are often involving continuous behaviors and discrete events, in this case, they are called hybrid dynamical systems (HDSs). To properly model this kind of systems, it is necessary to consider both the continuous and the discrete aspects of its dynamics. In this paper, a modeling framework based on the hybrid automata (HA) approach is proposed. This hybrid modeling framework allows combining the multi-state models of the system, described by nonlinear differential equations, with the system's discrete dynamics described by finite state machines. To attest to the efficiency of the proposed modeling framework, its application to a two-tank hybrid system (TTHS) is presented. The TTHS studied is a typical benchmark for HDSs with four operating modes. The MATLAB Simulink and Stateflow tools are used to implement and simulate the hybrid model of the TTHS. Different simulations results demonstrate the efficiency of the proposed modeling framework, which allows us to appropriately have a complete model of an HDS. [ABSTRACT FROM AUTHOR]

Trajectory generation for biped robots is very complex due to the challenge posed by real-world uneven terrain. To address this complexity, this paper proposes a data-driven Gait model that can handle continuously changing conditions. Data-driven approaches are used to incorporate the joint relationships. Therefore, the deep learning methods are employed to develop seven different data-driven models, namely DNN, LSTM, GRU, BiLSTM, BiGRU, LSTM+GRU, and BiLSTM+BiGRU. The dataset used for training the Gait model consists of walking data from 10 able subjects on continuously changing inclines and speeds. The objective function incorporates the standard error from the inter-subject mean trajectory to guide the Gait model to not accurately follow the high variance points in the gait cycle, which helps in providing a smooth and continuous gait cycle. The results show that the proposed Gait models outperform the traditional finite state machine (FSM) and Basis models in terms of mean and maximum error summary statistics. In particular, the LSTM+GRU-based Gait model provides the best performance compared to other data-driven models. [ABSTRACT FROM AUTHOR]

The subject matter of this article is a control system for unmanned aerial vehicles (UAVs) whose mathematical model is a finite state machine (FSM). The goal is to develop FSM structural models that enable (1) detection of multiple faults of FSM elements caused by an electromagnetic pulse or laser beam, and (2) prevent negative impacts on the controlled object. The tasks to be solved are as follows: to develop FSM structural models to detect invalid input vector X for the whole FSM and in each state, to detect invalid output vector Y for the whole FSM, at each transition and in each state, invalid code of the present (current) state, invalid code of the next state, and invalid transition between states; to determine the possible causes of the faults, which can be the failure in the logic Φ of forming the code of the next state, the invalid input vector X, the failure in the feedback circuit, the failure in the logic Ψ of forming the output vector, the failure in the state register R, the failure in the wire between the FSM input and the input of the logic Ψ; development of a combined structural model for the detection of all listed faults with a minimum number of additional combinational circuits, as well as a structural model that combines all additional combinational circuits. The methods used are: the theory of finite state machines, structural models of FSMs, state encoding methods of FSMs, representation methods of FSMs, and Verilog hardware description language. The following results were obtained: (1) the Mealy FSM structural models were developed to detect all the above mentioned faults, (2) the combined FSM structural models were developed, and (3) the possible causes of faults detected by each FSM structural model were identified. Experimental studies have shown that for the presented FSM structural models, the area overhead averages 3-23%, for onehot encoding of FSM states, and 2-8%, for binary encoding of FSM states. Conclusions. The scientific novelty of the obtained results consists in the following for the first time FSM faults that are not caused by radiation and cosmic rays but by an electromagnetic pulse affecting the control device are considered; the number of faults is not limited for the state codes as well as for the input and output vectors; the faults can be detected not only in the state register R but also in the input vector X, in the logic Φ of generating the next state code, in the logic Ψ of generating the output signals, and in the feedback circuit; the invalid transitions of FSMs and the transitions to invalid states are also detected; the proposed structural models not only detect FSM failures but also prevent their negative impact on the controlled object; combined structural models allow simultaneous detection of faults in all elements of the FSM. Future research will focus on developing structural models for correcting FSM failures. [ABSTRACT FROM AUTHOR]

Reforestation is performed after the final felling as an important and often law-mandated step to ensure that wood production is sustainable. In Sweden alone, over 400 millions seedlings are planted annually. This work is physically demanding and the quality is uneven. Therefore, automatic production systems are under research and development. A necessary effort in this endeavor is presented in this paper: the development and evaluation of a mission supervisor utilized to control the mission and behavior of a full-scale autonomous forest regeneration machine tested in realistic environments. The mission supervisor is implemented in the Robot Operating System framework using a finite state machine package called SMACH. A terrain machine built as a research platform with an added full-scale forwarder crane is used as a base machine. First, we describe the scenario in which planting is conducted, whereupon we develop the composite tasks required as states. A simplified simulator then enables an intermediate step before field experiments. The system is implemented and operated in real time on a full-scale machine. Results show that the developed SMACH mission supervisor can be used as a sound basis for an autonomous forest regeneration machine and the chosen communication solution between different systems works well. The simulations show good agreement with the experiments. The results also show that crane movements take 70% of the machine time, emphasizing the importance of limiting crane movement, improving the actuator movement speed and integrating the composite solutions. Further development with a holistic approach is required before the concept can reach the prototype level. [ABSTRACT FROM AUTHOR]

The emergence of new embedded system technologies, such as IoT, requires the design of new lightweight cryptosystems to meet different hardware restrictions. In this context, the concept of Finite State Machines (FSMs) can offer a robust solution when using cryptosystems based on finite automata, known as FAPKC (Finite Automaton Public Key Cryptosystems), introduced by Renji Tao. These cryptosystems have been proposed as alternatives to traditional public key cryptosystems, such as RSA. They are based on composing two private keys, which are two FSMs M 1 and M 2 with the property of invertibility with finite delay to obtain the composed FSM M = M 1 o M 2 , which is the public key. The invert process (factorizing) is hard to compute. Unfortunately, these cryptosystems have not really been adopted in real-world applications, and this is mainly due to the lack of profound studies on the FAPKC key space and a random generator program. In this paper, we first introduce an efficient algebraic method based on the notion of a testing table to compute the delay of invertibility of an FSM. Then, we carry out a statistical study on the number of invertible FSMs with finite delay by varying the number of states as well as the number of output symbols. This allows us to estimate the landscape of the space of invertible FSMs, which is considered a first step toward the design of a random generator. [ABSTRACT FROM AUTHOR]

In the mid-1930s, the English mathematician and logician Alan Turing invented an imaginary machine which could emulate the process of manipulating finite symbolic configurations by human computers. His machine launched the field of computer science and provided a foundation for the modern-day programmable computer. A decade later, building on Turing's machine, the American-Hungarian mathematician John von Neumann invented an imaginary self-reproducing machine capable of open-ended evolution. Through his machine, von Neumann answered one of the deepest questions in Biology: Why is it that all living organisms carry a self-description in the form of DNA? The story behind how two pioneers of computer science stumbled on the secret of life many years before the discovery of the DNA double helix is not well known, not even to biologists, and you will not find it in biology textbooks. Yet, the story is just as relevant today as it was eighty years ago: Turing and von Neumann left a blueprint for studying biological systems as if they were computing machines. This approach may hold the key to answering many remaining questions in Biology and could even lead to advances in computer science. [ABSTRACT FROM AUTHOR]

When realized on computational devices with finite quantities of memory, feedforward artificial neural networks and the functions they compute cease being abstract mathematical objects and turn into executable programs generating concrete computations. To differentiate between feedforward artificial neural networks and their functions as abstract mathematical objects and the realizations of these networks and functions on finite memory devices, we introduce the categories of general and actual computabilities and show that there exist correspondences, i.e., bijections, between functions computable by trained feedforward artificial neural networks on finite memory automata and classes of primitive recursive functions. [ABSTRACT FROM AUTHOR]

One essential component of security systems at public locations, such as airports, bus stops, train stations, marketplaces, etc., is the video surveillance. More powerful and efficient automated technical developments are needed for video surveillance. When an unattended object is left in the public places it will be considered as suspicious object as the terrorist assaults have escalated globally in recent years. The people in public areas must be protected from this attack by using safety precautions. Complex surveillance recordings make it difficult to identify abandoned or removed objects due to a number of factors, such as occlusion, abrupt changes in lighting, and so on. A novel approach is proposed in this article for the identification and classification of a static object in a public place. The main aim of this work is the automatic detection of abandoned objects. This method consists of two steps: static item detection using background subtraction and motion estimation; and (ii) abandoned luggage recognition using convolutional neural networks. (CNN). By applying the background subtraction method using fuzzy integral, the suggested method extracts foreground items. Afterwards the static object is detected using hierarchical Finite state machine (FSM). And finally, the object is classified using the CNN algorithm Yolo V5. In terms of accuracy, precision, and recall, the performance of the suggested algorithm is compared with that of traditional approaches. [ABSTRACT FROM AUTHOR]

Stochastic-computing-based artificial neural networks (SC-ANNs) can be used to perform hardware- and energy-efficient neuromorphic computing. We have been developing SC-ANNs using an energy-efficient superconductor logic family, namely, adiabatic quantum-flux-parametron (AQFP) logic. AQFP logic is suitable as a building block for SC-ANNs since it can perform stochastic operations with extremely small energy dissipation. In this Letter, we propose and demonstrate a sigmoid function generator (SFG) for AQFP SC-ANNs, which we refer to as the AQFP SFG. An SFG is an important circuit in neural networks that generates outputs from the sum of weighted inputs in accordance with the sigmoid function. The AQFP SFG performs the sigmoid function using a finite state machine based on an AQFP buffer coupled to a flux storage loop. We experimentally demonstrate that the AQFP SFG generates output signals from stochastic bitstreams in accordance with the sigmoid function and that the characteristics of the sigmoid function can be controlled by a bias current. Furthermore, we show that the AQFP SFG operates with small power dissipation due to its simple structure. [ABSTRACT FROM AUTHOR]

Non-Playable Characters (NPCs) are essential for creating a fully immersive video game experience. However, their behaviours are typically programmed using rigid methods such as Finite State Machines and Behaviour Trees. These methods are hard to maintain, struggle with implementing intricate cooperative behaviours, and patterns in NPC behaviour can easily be exploited by human players. Machine Learning and Reinforcement Learning (RL) methods in particular, offer a solution to these challenges by allowing dynamic and real-time NPC responses to human player actions and other characters in the game. This work describes and extends upon a Curriculum-based RL approach to train a single model for multiple agents representing vehicles to respect traffic regulations. These vehicles learn to navigate a road network which includes a traffic lights crossroad intersection and a roundabout junction. A comparison of our simulated data against datasets obtained from real world data is conducted; results demonstrate that the learned models have similar trends to the real-world data. • Multi-agent simulation for game characters navigating a road network. • Reinforcement Learning in game design can generate compelling agent behaviours. • Curricula can help reinforcement learning process to learn complex behaviours. • Macroscopic behaviour of agents matches real world data. [ABSTRACT FROM AUTHOR]

The paper is devoted to the problem of deriving synchronizing and homing experiments for nondeterministic Input/Output automata; corresponding input sequences are widely used in testing (non-initialized) discrete event systems. In active testing, there is an opportunity to set a system under test into a known initial state; in passive testing, a known current state allows to reduce the number of properties to be checked. In the paper, we note that such experiments for Input/Output automata are different from so-called "gedanken" experiments with classical Finite State Machines; the existence check conditions of such experiments are established for a predefined discipline of applying inputs and a method for its derivation is proposed when such an experiment exists. The obtained results allow to reduce the problem of deriving synchronizing and homing experiments for Input/Output automata to the well developed problem of deriving such experiments for appropriate classes of Finite State Machines. [ABSTRACT FROM AUTHOR]

The notion of bipolar neutrosophic finite switchboard state machines (BNFSSTMs), homomorphisms and strong homomorphisms of bipolar neutrosophic finite state machines (BNFSSTMs) are introduced and some related results are studied. [ABSTRACT FROM AUTHOR]

Aiming at shortcomings of domestic air-jet looms in terms of width and weft insertion rate, a highspeed air-jet loom control system based on ARM + FPGA was designed and developed. The FMC (Flexible Memory Controller) parallel bus was used to complete the data transmission between the two. According to the function of air-jet loom control system, the whole hardware control system was divided into main control subsystem, weft insertion control subsystem, clutch and brake subsystem, input and output subsystem, human-computer interaction subsystem and power supply subsystem by using the modular idea. According to the timing weaving process of air-jet loom weft insertion movement, FPGA internal hardware circuit with weft insertion control register and internal storage module as the core was designed. Based on FreeRTOS real-time operating system, high-speed weaving software framework was designed by using the Mealy finite state machine model and the spindle timing control strategy. Finally, the system was tested on the hardware control system simulation experimental platform. The results showed that the control system had the characteristics of stronger stability, faster running speed and stronger anti-interference ability, which can meet high-speed production demand of 540 cm nominal reed width of air-jet loom. [ABSTRACT FROM AUTHOR]

In recent times, enterprise environments such as E-banking, E-commerce, etc., are greatly affected by the evolution of web services and their associated attacks. The process of web service composition gives rise to security issues due to the incompatibility standards of the Simple Object Access Protocol (SOAP) and representational state transfer (REST) features and the compromising service-level agreement (SLA) between the end parties which has not been considered yet. Also, the security assessment process needs to cooperate with good security standards and web services. In case of heterogeneous web services, assessment done using machine learning technologies makes use of pattern analysis where this does not work with the evolving trend behind the web service environment. Hence, there is a need for a security assessment model which will incorporate finite state machine (FSM) in its assessment process to keep track of the various WS-attacks that arise in the web application via web services in heterogeneous environments. The proposed model does the web service composition by compromising all the security conflicts that arise due to the usage of dissimilar web services. We experimented the concept by testing several web services and observed that the performance of the proposed framework in attack detection is accurate and automatic thereby achieving traceability and computability metrics. [ABSTRACT FROM AUTHOR]

State machine is a concept originally proposed for computational numerical systems and used for modeling systems with applications in several fields. Governed by its own logic, an input produces a change of state and an output on the machine. The routing by FSM technique uses this dynamic to generate numerical sequences that represent the network nodes and the routes through which data transmission is allowed. With this, the number of transmissions is reduced and, consequently, the energy consumption. Due to its low complexity, the technique is particularly interesting in the context of networks with limited resources, such as wireless sensor networks and nanodevice networks. In this work, we show that for several scenarios the technique becomes inefficient due to the large number of routes produced and we propose a new implementation whereby the packet size remains reduced for a wide range of routing parameters. [ABSTRACT FROM AUTHOR]

The morphological analyzer is a computational process that combines lemmas with other linguistic features to produce new lexical word forms. This paper investigates the processing of a nominal system in the Urdu language. It focuses on the inflections of noun forms and studies number, gender, person, and case representations, using a Finite State Machine (FSM) to analyze and create all the possible forms of the standardized registers. The application of the analysis using this tool provides and displays all the possible structures and their declensions. This study adds all the necessary features and values to the lexical concatenating nouns according to their patterns. The accuracy score of the output is 92.7, where the actual output depends on the detailed design of the FSM and the specific morphological processes provided to the finite state tools. [ABSTRACT FROM AUTHOR]

Copyright of Informacije MIDEM: Journal of Microelectronics, Electronic Components & Materials is the property of MIDEM Society and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Abstract In recent years, research on sleep monitoring and analysis has attracted many scholars. Among them, the polysomnography (PSG) is performed more accurately. However, PSG is not suitable to be used at home due to its complicated operation and expensive cost. On the other hand, although the Pittsburgh sleep quality index (PSQI) is a standardized form for sleep quality assessment, the subjective and backward evaluation may lead to intuitive results. Therefore, this paper is intended to develop a sleep stage estimation system for home health care services. In the proposed platform, the sleep conditions, including the heart rate (HR) and body movement, are collected by an HR monitor and a force sensor array, respectively. Also, the fuzzy inference system is applied to the sleep depth evaluation, and then, the finite state machine is utilised to estimate the sleep stage. Experimental results show that the developed platform not only reduces the burden of PSG measurements, but also provides more convincible and reasonable results, presenting as an assistive tool of the conventional PSQI tests.

This paper proposes the conceptual design method for a hybrid-actuated lower limb exoskeleton based on energy consumption simulation. Firstly, the human-machine coupling model is established in OpenSim based on the proposed three passive assistance schemes. On this basis, the method of simulating muscle driving is used to find out the scheme that can reduce the metabolic rate the most with 3 passive springs models. Then, an active-passive cooperative control strategy is designed based on the finite state machine to coordinate the operation of the power mechanism and the passive energy storage structure and improve the mobility of the wearer. In the end, a simulation experiment based on the human-machine coupled model with the addition of active actuation is proceeded to evaluate its assistance performance according to reducing metabolic rate. The results show that the average metabolic cost decreased by 7.2% with both spring and motor. The combination of passive energy storage structures with active actuators to help the wearer overcome the additional consumption of energy storage can further reduce the body's metabolic rate. The proposed conceptual design method can also be utilized to implement the rapid design of a hybrid-actuated lower limb exoskeleton. [ABSTRACT FROM AUTHOR]

Given an input tree and a tree pattern, the inexact tree pattern matching problem is about finding all subtrees in the input tree that match the tree pattern with up to k errors. To measure the number of errors between two labeled ordered trees, we use the 1-degree edit distance that uses operations node relabel, leaf insert, and leaf delete. The proposed solution is based on a finite automaton that reads a given input tree represented in linear, prefix bar, notation. First, we show its construction for a constrained variant of 1-degree edit distance where leaf insert/delete operations cannot be applied to the tree pattern recursively. Then, we extend this approach to both unit cost and non-unit cost 1-degree edit distance. The deterministic version of the proposed finite automaton finds all inexact occurrences of the tree pattern in time linear to the size of the input tree. However, since the size of such automaton can be exponential in the number of nodes of the tree pattern, it is practical only for small patterns. Therefore, we also consider the dynamic programming approach as a way of simulating the nondeterministic finite automaton. This approach comes with the space complexity O (m k) and time complexity O (k m n) where m is the number of nodes of the tree pattern, n is the number of nodes of the input tree, and k is the maximum number of errors allowed. [ABSTRACT FROM AUTHOR]

Riskful and aggressive driving are significant problems in road transportation. Numerous studies prove drivers' behavior is critical in most road accidents and contributes significantly to fuel consumption and emissions. In an attempt to improve road safety, it is important to be able to detect such unskilful and irresponsible drivers on a mass scale. Thus an automated onboard driving safety assessment system is required. Transmitting amounts of telemetric data required to assess driving style is unpractical and economically unjustified, thus some data processing must take place in an Onboard Unit (OBU). As a first step in driving safety assessment is detecting maneuvers, this is the task, that can be done in the OBU. In this paper, we propose a Finite State Machine based algorithm, which could run on OBU and allows marking of basic maneuvers in the telemetry datastream. This allows the calculation of additional features, aggregation, and transmission of data useful for classification the of driving safety, and thus a vast reduction in data volume sent over the air. Also, an example of detecting unsafe maneuver using such aggregated data is given. [ABSTRACT FROM AUTHOR]

How do humans learn the regularities of their complex noisy world in a robust manner? There is ample evidence that much of this learning and development occurs in an unsupervised fashion via interactions with the environment. Both the structure of the world as well as the brain appear hierarchical in a number of ways, and structured hierarchical representations offer potential benefits for efficient learning and organization of knowledge, such as concepts (patterns) sharing parts (subpatterns), and for providing a foundation for symbolic computation and language. A major question arises: what drives the processes behind acquiring such hierarchical spatiotemporal concepts? We posit that the goal of advancing one’s predictions is a major driver for learning such hierarchies and introduce an information-theoretic score that shows promise in guiding the processes, and, in particular, motivating the learner to build larger concepts. We have been exploring the challenges of building an integrated learning and developing system within the framework of prediction games, wherein concepts serve as (1) predictors, (2) targets of prediction, and (3) building blocks for future higher-level concepts. Our current implementation works on raw text: it begins at a low level, such as characters, which are the hardwired or primitive concepts, and grows its vocabulary of networked hierarchical concepts over time. Concepts are strings or n-grams in our current realization, but we hope to relax this limitation, e.g., to a larger subclass of finite automata. After an overview of the current system, we focus on the score, named CORE. CORE is based on comparing the prediction performance of the system with a simple baseline system that is limited to predicting with the primitives. CORE incorporates a tradeoff between how strongly a concept is predicted (or how well it fits its context, i.e., nearby predicted concepts) vs. how well it matches the (ground) “reality,” i.e., the lowest level observations (the characters in the input episode). CORE is applicable to generative models such as probabilistic finite state machines (beyond strings). We highlight a few properties of CORE with examples. The learning is scalable and open-ended. For instance, thousands of concepts are learned after hundreds of thousands of episodes. We give examples of what is learned, and we also empirically compare with transformer neural networks and n-gram language models to situate the current implementation with respect to state-of-the-art and to further illustrate the similarities and differences with existing techniques. We touch on a variety of challenges and promising future directions in advancing the approach, in particular, the challenge of learning concepts with a more sophisticated structure. [ABSTRACT FROM AUTHOR]

Tsetlin Machines (TM) use finite state machines for learning and propositional logic to represent patterns. The resulting pattern recognition approach captures information in the form of conjunctive clauses, thus facilitating human interpretation. In this work, we propose a TM‐based approach to three common natural language processing (NLP) tasks, namely, sentiment analysis, semantic relation categorization and identifying entities in multi‐turn dialogues. By performing frequent itemset mining on the TM‐produced patterns, we show that we can obtain a global and a local interpretation of the learning, one that mimics existing rule‐sets or lexicons. Further, we also establish that our TM based approach does not compromise on accuracy in the quest for interpretability, via comparison with some widely used machine learning techniques. Finally, we introduce the idea of a relational TM, which uses a logic‐based framework to further extend the interpretability. [ABSTRACT FROM AUTHOR]

Watson-Crick automata are belonging to the natural computing paradigm as these finite automata are working on strings representing DNA molecules. Watson-Crick automata have two reading heads, and in the 5' → 3' models these two heads start from the two extremes of the input. This is well motivated by the fact that DNA strands have 5' and 3' ends based on the fact which carbon atoms of the sugar group is used in the covalent bonds to continue the strand. However, in the two stranded DNA, the directions of the strands are opposite, so that, if an enzyme would read the strand it may read each strand in its 5' to 3' direction, which means physically opposite directions starting from the two extremes of the molecule. On the other hand, enzymes may not have inner states, thus those Watson-Crick automata which are stateless (i.e. have exactly one state) are more realistic from this point of view. In this paper these stateless 5' → 3' Watson-Crick automata are studied and some properties of the language classes accepted by their variants are proven. We show hierarchy results, and also a "pumping", i.e., iteration result for these languages that can be used to prove that some languages may not be in the class accepted by the class of stateless 5' → 3' Watson-Crick automata. [ABSTRACT FROM AUTHOR]

In this paper, a linear attack model of SNOW 3G and SNOW-V based on automatic search technology is proposed. We first describe the linear approximation of Finite State Machine transformation, which allows a wider range of automatic search, then model it with the automatic search technology based on SAT/SMT program. Adopting this generic method, we seek out a binary linear approximation of SNOW 3G with correlation of |$2^{-21.92}$| which has been verified by test. Treating this binary approximation as a mask of an 8-bit distribution in a fixed field, we provide a method to obtain the 8-bit distribution. The binary approximation is used in a fast correlation attack with expected time and memory complexity |$2^{184.67}$|⁠ , given |$2^{173.96}$| key stream words. For the full version of SNOW-V, considering the linear relationship between Linear Feedback Shift Register parts at three successive moments, we search out a distinguisher with correlation of |$2^{-175.51}$|⁠ , which results in a distinguishing attack with an expected complexity of |$2^{351.02}$|⁠. [ABSTRACT FROM AUTHOR]

Non‐playable characters (NPCs) play a crucial role in enhancing immersion in video games. However, traditional NPC behaviors are often hard‐coded using methods such as Finite State Machines, Decision and Behavior trees. This has a few limitations; namely, it is quite difficult to implement complex cooperative behaviors and secondly this makes it easy for human players to identify and exploit patterns in behavior. To overcome these challenges, Reinforcement learning (RL) can be used to generate dynamic and real‐time NPC responses to human player actions. In this paper, we report on first results of applying RL techniques to a Non‐Zero Sum, adversarial asymmetric game, using a multi‐agent team. The game environment simulates a museum heist, where the objective of the successfully trained team of robbers with different skills (Locksmith, Technician) is to steal valuable items from the museum without being detected by the scripted security guards and cameras. Both agents were trained concurrently with separate policies and received both individual and group reward signals. Through this training process, the agents learned to cooperate effectively and use their skills to maximize both individual and team benefits. These results demonstrate the feasibility of realizing the full game where both robbers and security guards are trained at the same time to achieve their adversarial goals. [ABSTRACT FROM AUTHOR]

This article discusses an approach to the development of large-scale cognitive cyber-physical systems characterized by a high level of structural, functional and architectural dynamics. The main idea of the proposed approach is the use of several modern paradigms to build cyber-physical systems, such as continuous architecture, agile architecture, digital twins and digital threads. A three-level model of a cognitive cyber-physical system is proposed. In order to ensure the required level of flexibility of the system, such possibility should be laid at earlier stages of the life cycle, i.e., at the development stage. At the upper level, the system is described in terms of a continuous architecture; at the middle level, the system is represented as a system with agile architecture, which is described as a multi-level relatively finite automaton, and at the lower level, structural and functional models are used that illustrate the system in the process of functioning. This article provides examples of using the proposed approach. [ABSTRACT FROM AUTHOR]