Search

Symbolic execution is one of the most important testing techniques to ensure the quality of software systems that need to be dependable and reliable. This technique systematically explores the program of the subject system which is represented by an Inter-procedural Control Flow Graph (ICFG). An ICFG is a graph that combines Control Flow Graphs (CFGs) of the program procedures by connecting each CFG with its call nodes. The existence of unreachable CFGs and infinite loops increases the complexity and runtime of a program, while they have no effect on testing the program. In this paper, we present an approach to convert the ICFG of a program to the corresponding finite automaton, called ICFG-automaton. Then, we construct a quasi-ordering hypergroup on the set of states of the ICFG-automaton and prove that the inner irreducibility in hypergroups is equivalent to the connectivity in CFGs. Moreover, we show that if every sub-automaton of an ICFG-automaton is a sub-hypergroup, then the program has an infinite loop. These results identify the parts of a program that should be modified to decrease the complexity of the testing activity. [ABSTRACT FROM AUTHOR]

In this modern era, the detection of plant disease plays a vital role in the sustainability of agricultural ecosystem. Today, India being second in farming, well-timed information related to crop is still questioning. Indian Government's farmer portal is available for pesticides, fertilisers, and farm machinery. To alleviate this problem, the paper describes a model to validate the leaf image, predicting leaf disease and notifying the farmer in an effective way on the harvest failure to stabilise farming income. For specific consideration on the validation, a data set library with predefined, uniformly scaled, regular image patterns of leaf disease, is maintained. The research suggests that farmers utilising the model can predict the breakout of leaf disease predominantly acquiring 100% yield. [ABSTRACT FROM AUTHOR]

In this paper we characterize normal sequences and finite-state dimension in terms of the automatic Kolmogorov complexity and finite-state a priori probability. We show that many known results about normal sequences and finite-state dimension, including the equivalence between aligned and non-aligned normality, Wall's theorem, Piatetski–Shapiro's theorem, Champernowne's example of normal number and its modifications, equivalences between different definitions of finite-state dimension, Agafonov's and Schnorr's results about finite-state selection rules, become easy corollaries of this characterization. For that we use notions of automatic (finite-state) complexity and finite-state a priori probability that are the natural counterparts of the notions of Kolmogorov complexity and Solomonoff–Levin a priori probability in the algorithmic information theory. We also give a machine-independent characterization of normality and finite-state dimension in terms of superadditive calibrated functions. We compare our approach with previous results and notions relating finite automata and complexity. [ABSTRACT FROM AUTHOR]

We present a minimization algorithm for non-deterministic finite state automata that finds and merges bisimulation-equivalent states. The bisimulation relation is computed through partition aggregation, in contrast to existing algorithms that use partition refinement. The algorithm simultaneously generalises and simplifies an earlier one by Watson and Daciuk for deterministic devices. We show the algorithm to be correct and run in time O n 2 r 2 Σ , where n is the number of states of the input automaton M , r is the maximal out-degree in the transition graph for any combination of state and input symbol, and Σ is the size of the input alphabet. The algorithm has a higher time complexity than derivatives of Hopcroft's partition-refinement algorithm, but represents a promising new solution approach that preserves language equivalence throughout the computation process. Furthermore, since the algorithm essentially computes the maximal model of a logical formula derived from M , optimisation techniques from the field of model checking become applicable. [ABSTRACT FROM AUTHOR]

One-way quantum finite automata are reversible in nature, which greatly reduces its accepting property. In fact, the set of languages accepted by one-way quantum finite automata is a proper subset of regular languages. In this paper, we replace the tape head of one-way quantum finite automata with DNA double strand and name the model Watson–Crick quantum finite automata. The non-injective complementarity relation of Watson–Crick automata introduces non-determinism in the quantum model. We show that this introduction of non-determinism increases the computational power of one-way quantum finite automata significantly. Watson–Crick quantum finite automata can accept all regular languages and also accepts some languages which are not accepted by any multi-head deterministic finite automata. Exploiting the superposition property of quantum finite automata, we show that Watson–Crick quantum finite automata accept the language L = {ww|w ∈ {a, b}*}. [ABSTRACT FROM AUTHOR]

Watson–Crick (abbreviated as WK) finite automata are working on double stranded DNA molecule that is also called Watson–Crick tape. Subsequently, these automata have two reading heads, one for each strand. While in traditional WK automata both heads read the whole input in the same physical direction, in 5 ′ → 3 ′ WK automata the heads start from the two extremes (say 5 ′ end of the strands) and read the input in opposite direction. In sensing 5 ′ → 3 ′ WK automata the process on the input is finished when the heads meet. Since the heads of a WK automaton may read longer strings in a transition, in previous models a so-called sensing parameter took care for the proper meeting of the heads (not allowing to read the same positions of the input in the last step). Recently a new model is investigated, which works without the sensing parameter. In this paper, the deterministic counterpart is studied and is proven to accept the language class 2detLIN defined by the deterministic variant of the earlier version. However, using some of the restricted variants, e.g, all-final automata, the classes of the accepted languages are changed showing a finer hierarchy inside the class of linear context-free languages. [ABSTRACT FROM AUTHOR]

By investigating the methods for filtering the sensitive word in the text and the related technologies, this paper proposed a sensitive word filtering algorithm based on the improved Trie tree and DF A to solve the key problems of the sensitive word filtration, including artificial interference, participle obstacles and so on. The algorithm improved the accuracy and validity of sensitive word filtering in text. It consisted of three major steps. Firstly, based on the mathematical theory of permutation and combination, it constructed an algorithm for extending Chinese word to Chinese-phonetic mixed word. Secondly, it employed the improved Trie tree structure to store all the status of DF A to build the sensitive word tree. Finally, it could search and filter the sensitive words in the text content on the basis of the construction of the sensitive word tree structure and the minimum matching rule. Through analysis, the time complexity of constructing sensitive word tree algorithm is 0 ( n x Zen), and detecting and filtering sensitive word algorithm is 0 ( L) . The experimental results show that the precision rate of the algorithm is 100%, and the recall rate is about 87% - 100% . [ABSTRACT FROM AUTHOR]

We consider the problem of A-completeness in the class of linear automata such that the sets of inputs, outputs and states are Cartesian products of dyadic rationals; systems checked for completeness are comprised of a variable finite set and a fixed additional set. We obtain conditions of A-completeness in terms of maximal subclasses in the cases when the additional set is the set of all unary automata and when the additional set consists of the adder. [ABSTRACT FROM AUTHOR]

When designing of Shared Memory Multiprocessor systems Cache Coherence becomes the great challenge to deal because incoherence may occur when the processors are working on the same data without any coordination. This coherence can be brought by using cache coherence protocols which are finite state machines which manages the cache and memory. This Paper aims at introducing cache coherence in details and providing a performance analysis of some of the cache coherence protocols. Thus this work is majorly focusing on implementation of MSI, MESI and MOESI cache coherence protocols using Xilinx ISE on FPGA and the way coherence protocols are designed are analysed perfectly. [ABSTRACT FROM AUTHOR]

In a cut-in scenario, traditional adaptive cruise control usually cannot effectively identify the cut-in vehicle and respond to it in advance. This paper proposes an adaptive cruise control (ACC) strategy based on the MPC algorithm for cut-in scenarios. A finite state machine (FSM) is designed to manage vehicle control in different cut-in scenarios. For a cut-in scenario, a method to identify and quantify the possibility of cut-in of a vehicle is proposed. At the same time, a safety distance model of the cut-in vehicle is established as the basis for the state transition of the finite state machine. Taking the quantified cut-in possibility of a vehicle as a reference, the model predictive control (MPC) algorithm, which considers the constraints of driving safety and comfort, is used to realize coordinated control of the host vehicle and the cut-in vehicle. Simulink–Carsim simulation studies show that the ACC strategy for a cut-in scenario can effectively identify a cut-in vehicle and quantify the possibility of cut-in of the vehicle. Faced with a cut-in vehicle, the host vehicle using the ACC strategy can brake several seconds early and switch the following target to the cut-in vehicle. Meanwhile, the acceleration and jerk of the host vehicle changes within a reasonable range, which ensures driving safety and comfort. [ABSTRACT FROM AUTHOR]

The maximal existential (respectively, universal) width of an alternating finite automaton (AFA) on a string w is the maximal number of existential choices encountered in one branch (respectively, the maximal number of universal parallel branches) of a computation of A on w. We give upper bounds for the size of a nondeterministic finite automaton simulating an AFA of finite maximal universal width and for the size of a universal finite automaton simulating an AFA of finite maximal existential width. We give lower bounds for the transformations that are tight within a multiplicative factor that depends only on the universal (respectively, existential) width of the AFA. • We consider alternating finite automata (AFA) making a limited number of existential or universal choices in a computation. • We provide upper and lower bounds for converting an AFA with limited universal width to a nondeterministic finite automaton. • We provide upper and lower bounds for converting an AFA with limited existential width to a universal finite automaton. [ABSTRACT FROM AUTHOR]

Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language L such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is Ω ˜ (n 2) , while of exact two-way quantum finite automata with classical states (2QCFA) is O ˜ (n 5 / 3) , that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing. [ABSTRACT FROM AUTHOR]

We define the jump complexity of a finite automaton with translucent letters as a function that computes the smallest upper bound on the number of jumps needed by the automaton in order to accept each word of length n , for any positive integer n. We prove that a sufficient condition for a finite automaton with translucent letters to accept a regular language is to have a jump complexity bounded by a constant. Along the same lines, we show that there are languages which require a jump complexity in Ω (n) of any finite automaton with translucent letters accepting one of these languages. We also show that there exist nondeterministic finite automata with translucent letters of jump complexity in O (log ⁡ n) and O (n) that accept non-regular languages. Several open problems and directions for further developments are finally discussed. • We have defined a new complexity measure for automata with translucent letters. • We prove that a sufficient condition for a finite automaton with translucent letters to accept a regular language is to have a jump complexity bounded by a constant. • We show that there are languages which require a jump complexity in Ω (n) of any finite automaton with translucent letter accepting one of these languages. • We show that there exist nondeterministic finite automata with translucent letters of jump complexity in O (log ⁡ n) and O (n). • We have proposed several open problems and two conjectures. [ABSTRACT FROM AUTHOR]

We present methods for testing and incremental testing of systems modeled as finite state machines with timeouts (TFSMs). For testing, we establish an appropriate fault model and show how a complete test suite can be derived for a given TFSM specification using traditional FSM-based test derivation approaches considering an untimed FSM abstraction of the given specification. In addition, we consider reducing the cost of testing a modified or an evolving TFSM specification by the selection of appropriate incremental test suites that can verify whether the modified parts of a modified specification are correctly implemented in a corresponding implementation under test. In particular, we define the incremental testing problem for TFSMs and investigate appropriate fault models that can be used for incremental test derivation and accordingly propose related test selection algorithms. According to conducted experiments length and run time (sum of time delays) of obtained test suites are much lower than their theoretic upper bounds; in some cases, these bounds are linear. In addition, for incremental testing, when the modified part is up to 20% of the whole specification, length and run time of incremental test suites are at least twice as less than those obtained using the whole modified specification. • For testing, we propose a fault model and show how test derivation with complete fault coverage can be carried out using traditional FSM based testing methods from an FSM abstraction of a given TFSM specification. • We defined the incremental testing problem which deals with the derivation of incremental tests for verifying whether the modified parts of a modified TFSM specification are correctly implemented in a corresponding implementation under test. • To this end, we investigate three special cases with relate fault models and propose related incremental test derivation algorithms. • We conduct experiments to assess the presented work. • According to these experiments: (a) Length and run time (sum of time delays) of obtained test suites are much lower than their theoretic upper bounds; in some cases, these bounds are linear. (b) When the modified part is up to 20% of the whole specification, length and run time of incremental test suites are at least twice less than those obtained using the whole modified specification. [ABSTRACT FROM AUTHOR]

This document is a corrigendum to a paper titled "Quantum algorithms for unate and binate covering problems with application to finite state machine minimization." The authors clarify that Figure 13 in their paper uses a variant of the Grover diffusion circuit that is not the standard Grover diffusion operator for the Boolean oracles and phase oracles of L. K. Grover. They explain that this variant of the Grover diffusion circuit is the same as the quantum diffuser proposed by A. A-Bayaty and M. Perkowski, known as the "Grover controlled-diffusion operator." The authors request to publish this clarification as a corrigendum in the Journal of Applied Logics. [Extracted from the article]

Semi-tensor product of matrices (STP of matrices) is a new matrix product and has been successfully applied to many fields, especially to logical dynamic systems. This paper considers how to represent a Boolean matrix as an exponentiation of another one in the framework of the STP of matrices. To this end, Boolean matrices (BMs) are classified into three types, single block, full block and non-full block BMs. For each kind of BMs, a sufficient and necessary condition for the exponentiation-representability is proposed, and an algebraic algorithm of finding all the exponentiation representations of a Boolean matrix is designed. As potential applications, a discussion of how to use the obtained results to analyze and synthesize logical systems mathematically, especially to finite state machines, is finally presented. The results of this paper may provide a theory basis for studying finite-valued systems, logical systems, logical networks and networked evolutionary games, etc.

Different strategies for the combination of merging and splitting transformation procedures for incompletely specified finite state machines implemented on field-programmable logic devices are offered. In these methods, such optimization criteria as the speed of operation, power consumption and implementation cost are considered already in the early phase of finite state machine synthesis. The methods also take into account the technological features of programmable logic devices and the state assignment method. The transformation quality ratio is calculated on the base of estimations of consumed power, critical path delay and number of utilized logic cells. The user is also able to choose the order of merging and splitting procedures and the direction of the optimization by setting weights for each criterion. The methods of the estimation of optimization criteria values are described, and the experimental results are also discussed.

System-on-chip (SoC) is the main processor for most recent applications such as the Internet of things (IoT). SoCs are composed of multiple blocks that communicate with each other through an integrated router. Data routing from a block to another poses many challenges. The network-on-chip (NoC) was used for the transmission of data from a source to a destination with high reliability, high speed, low power consumption, and low hardware occupation. An NoC is composed of a router, network links (NL), and network interface (NI). The main component of the NoC, the NI, is composed of an input/output FIFO, a finite state machine (FSM), pack, and depack modules. Data transmission from a block to another poses a security problem such as secret information extraction. In this paper, we proposed a data encryption framework for NoC based on a light encryption device (LED) algorithm. The main advantages of the proposed algorithm are to reduce the implementation area and to achieve high speed while reducing the power consumption. The proposed encryption framework was simulated Verilog/VHDL on the Xilinx ISE and implemented on the Xilinx Virtex 5 XC5VFX200T. The obtained results have shown that the proposed framework has a smaller area and higher speed compared to existing works. The proposed algorithm has reduced the NI implementation area and enhanced the network performance in terms of speed and security. [ABSTRACT FROM AUTHOR]

We study the state complexity and nondeterministic state complexity of the k -th power, positive closure, right quotient, and left quotient on the classes of prefix-, suffix-, factor-, and subword-free, -closed, and -convex regular languages, and on the classes of right, left, two-sided, and all-sided ideal languages. We show that the nondeterministic state complexity of the k -th power is kn for closed and convex languages, and k (n − 1) + 1 in the remaining classes, while its state complexity is n + (k − 1) 2 n − 2 for right ideals, k (n − 1) + 1 for other ideals and factor- and subword-closed languages, and k (n − 2) + 2 for prefix-, factor-, and subword-free languages. We next prove that the nondeterministic state complexity of positive closure is 1 for factor- and subword-closed languages and n for all other classes, while its state complexity is 2 for factor- and subword-closed languages, 2 n − 2 + 1 for prefix-closed and suffix-free languages, and n for all other considered classes. We also study left and right quotients by a language from the considered class or by a regular language, and get tight upper bounds in all cases except for state complexity of left quotient of all-sided ideals and subword-closed languages by a regular language, and nondeterministic state complexity of left quotient on subword-convex languages. Assuming that both dividend K and divisor L belong to a given class, the upper bound m on the complexity of the right quotient is tight for free, closed, convex, and right ideal languages, while the complexity of the right quotient of two left ideals is one. The nondeterministic state complexity of the left quotient is m + 1 for left ideal, prefix-free, prefix-closed, and factor convex languages, it is m for suffix-free and suffix-closed languages and it is one for right ideals. If the divisor is an arbitrary regular language, then the upper bound m on the complexity of right quotient is always tight, and the upper bound m + 1 on the complexity of left quotient is tight unless the dividend is an all-sided ideal, suffix-free, or subword-closed language. In these cases, the complexity of the left quotient is at most m. In four cases, our witnesses are defined over a growing alphabet. All the remaining witnesses are described over a small fixed alphabet, and whenever the binary alphabet is used, it is optimal. [ABSTRACT FROM AUTHOR]

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we investigate how to find rectangular subarrays that belong to the picture language. Two-dimensional pattern matching problems can be formulated by interpreting subarrays as matches and picture languages as patterns. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving the problems for basic classes of picture languages, which include local picture languages and picture languages accepted by various types of deterministic two-dimensional finite automata such as four-way, three-way and two-way automata, on-line tessellation automata, and returning finite automata. We also prove that the pattern matching problems cannot be solved for the class of local picture languages in time linear in the input area unless the well known problem of triangle finding in a graph is solvable in quadratic time. This shows a fundamental difference between the complexity of one-dimensional and two-dimensional pattern matching. [ABSTRACT FROM AUTHOR]

The study of alternation in two-way finite automata (2 fa s) has been quite non-systematic. Since the 1970's, various authors with a variety of motivations have studied 2 fa s with various types of alternation and a variety of names, creating a fairly long list of sporadic contributions with little internal consistency. This article attempts to organize the subject into a single unifying framework. We start with a detailed account of all contributions to date, that reveals the large variety of approaches and the lack of consistency between them. We then identify and name four types of automata that these contributions have really studied over the years: general two-way Boolean finite automata (2 b fa s); monotone 2 b fa s; basic 2 b fa s; and (monotone basic, or) alternating 2 b fa s (2 a fa s). Next, we identify four different ways by which authors have described how such automata compute, each offering a distinct view onto their operation: the circuit view , where computation is modeled by a circuit of Boolean gates; the formula view , where computation is modeled by a Boolean formula over configuration-variables; the run view , where decisions are determined by the existence of appropriate trees of configuration-goal pairs, called "runs"; and the (most classic) tree view , where computation is modeled by a tree of configurations. After carefully defining each 2 b fa type and each view, we prove the following. First, that within each type, every two of the four views are equivalent to each other, in the strong sense that each of them closely mimics the other at every step of the computation. Second, that not all types of 2 b fa s are equivalent: although general 2 b fa s are as powerful as monotone 2 b fa s, and basic 2 b fa s are as powerful as 2 a fa s (up to polynomial differences in the number of states), general 2 b fa s may need exponentially fewer states than 2 a fa s. [ABSTRACT FROM AUTHOR]

In this paper, we propose an architecture of oritatami systems, a mathematical model of RNA cotranscriptional folding, with which one can simulate an arbitrary nondeterministic finite automaton (NFA) in a unified manner. The oritatami system is known to be Turing-universal but the simulation available so far requires 542 bead types and O (t 4 log 2 ⁡ t) steps in order to simulate t steps of a Turing machine. The architecture we propose employs only 337 bead types and requires just O (t | Q | 4 | Σ | 2) steps to simulate an NFA with a state set Q working on a word of length t over an alphabet Σ. [ABSTRACT FROM AUTHOR]

This study investigates the potential application of Stateflow (SF) to design an energy management strategy (EMS) for a renewable-based hybrid energy system (HES). The SF is an extended finite state machine; it provides a platform to design, model, and execute complex event-driven systems using an interactive graphical environment. The HES comprises photovoltaics (PV), energy storage units (ESU) and a diesel generator (Gen), integrated with the power grid that experiences a regular load shedding condition (scheduled power outages). The EMS optimizes the energy production and utilization during both modes of HES operation, i.e., grid-connected mode and the islanded mode. For islanded operation mode, a resilient power delivery is ensured when the system is subjected to intermittent renewable supply and grid vulnerability. The contributions of this paper are twofold: first is to propose an integrated framework of HES to address the problem of load shedding, and second is to design and implement a resilient EMS in the SF environment. The validation of the proposed EMS demonstrates its feasibility to serve the load for various operating scenarios. The latter include operations under seasonal variation, abnormal weather conditions, and different load shedding patterns. The simulation results reveal that the proposed EMS not only ensures uninterrupted power supply during load shedding but also reduces grid burden by maximizing the use of PV energy. In addition, the SF-based adopted methodology is envisaged to be a useful alternative to the popular design method using the conventional software tools, particularly for event-driven systems. [ABSTRACT FROM AUTHOR]

Aiming at the challenging problem of the traditional warp knitting machine electronic jacquard control system with complex structure of multiple circuit boards layered cascade, such as large physical space occupation, high power consumption, and independent high-voltage power supply voltage, we proposed an embedded circuit and control strategy design for the piezoelectric jacquard needle (PJN) with adaptive boost and energy recovery functions. Firstly, the electromechanical dynamics model of PJN was established. Secondly, the fuzzy PI double closed-loop control algorithm driven by a finite state machine is proposed. Thirdly, with the help of a Metal-Oxide-Semiconductor Field-Effect Transistor (MOSFET), the PJN is integrated with the drive circuit. The drive circuit of PJN uses an energy storage inductor to replace the current limiting resistor of the traditional drive circuit, which can not only limit the forward charging current of the PJN and reduce energy loss but also can use the energy absorbed from the low-voltage power supply to adaptively boost the power supply of the PJN to the high voltage required for working conditions. The simulation results show that the new PJN drive circuit has an adaptive self-boost function. The PWM signal modulated by the fuzzy PI double closed-loop control algorithm can efficiently and accurately control the adaptive boost power supply and the voltage across the PJN. The mode of the circuit can be correctly switched through the sequential logic of the finite state machine and realize the energy recovery function. [ABSTRACT FROM AUTHOR]

The theory of finite automata and rational semiring elements is reconsidered in the setting of summation semirings, traditionally known as Σ-semirings. These generalise complete semirings by allowing infinite sums to be defined just for selected families of elements. A relation of the presented approach to the theory of finite automata over partial Conway semirings is discussed. Equivalence of finite automata over summation semirings to rational expressions and right-linear systems is proved under suitable semantics. Moreover, MSO logics over summation semirings are introduced and proved to be equivalent to finite automata. [ABSTRACT FROM AUTHOR]

In real life, the increased data accessing speed and data storage ability is required by most of the machinery fields. However, the real-world problems can be studied effectively with the combination of scientific computational techniques with the mathematical models. Automata theory is known to be the popular mathematical model. Towards most of the software and hardware related applications, the computational methods are analyzed and designed using significant automata theory concepts (likely, pushdown automata (PDA), Turing machines (TMs) and finite automata (FA)). Hence, the conventional lecture-driven style has attracted the reflective preferences of learners using these abstract natured concepts. But the lecture-driven teaching style has less motivated the computer engineering learners. In order to learn automata theory and computational models, we introduce the PDA and TM in a virtual platform. However, this work has motivated the improvement of longitudinal experimental validation and learning using the modern technology. Java Formal Languages and Automata Package (JFLAP) tool is used to write our simulators in JAVA language and the results are obtained from each machine through simulating the input strings. [ABSTRACT FROM AUTHOR]

In the last few decades, much effort has been made for the production of squeezed vacuum states in order to reduce quantum noise in the audio-frequency band. This technique has been implemented in all running gravitational-wave interferometric detectors and helped to improve their sensitivity. While the detectors are acquiring data for astrophysical observations, they must be kept in the operating condition, also called "science mode," that is, a state that requires the highest possible duty-cycle for all the instrumental parts and controls. We report the development of a highly automated setup for the generation of optical squeezed states, where all the required control loops are supervised by a software based on finite state machines; we took special care to grant ease of use, stability of operation, and possibility of auto-recovery. Moreover, the setup has been designed to be compatible with the existing software and hardware infrastructure of the Virgo detector. In this paper, we discuss the optical properties of this squeezing setup, the locking techniques, and the automation algorithms. [ABSTRACT FROM AUTHOR]

The quantum-resistant attribute is a new design criterion for cryptography algorithms in the era of quantum supremacy. Lattice-based cryptography is proved to be secure against quantum computing. CRYSTALS-Kyber is a lattice-based promising candidate in the post-quantum cryptography standardization process. This paper proposes a high-performance polynomial ring processor for the CRYSTALS-Kyber algorithm. The processor executes optimized polynomial ring arithmetic, which cuts off over 20%/50% on the times of modular multiplication/addition compared with the straightforward implementations. Besides, the forward and inverse Number Theoretic Transform (NTT) reuse the control logic with the help of an efficient configurable butterfly unit to minimize the area of the finite state machine. Further, the underlying dual-column sequential storage scheme breaks the bottleneck of memory accessing. To evaluate the performance, a fully pipelined architecture is implemented on a low-cost FPGA platform. Benefiting from these optimizations, the Kyber1024processor can perform NTT operation for a 4-dimensional polynomial vector in 17.1 μ s, and it achieves speedup by a factor of 2.1 compared with the state-of-the-art implementation. • Kyber1024 processor can perform NTT operation for a 4-dimensional polynomial vector in 17.1 μ s on a low-cost FPGA. • Saving more than 20% on the times of modular multiplication operations in polynomial ring arithmetic. • Optimized NTT signal flow reuses the loop control logic to save nearly 50% of the resource. • Dual-column sequential storage improves memory bandwidth. • Configurable butterfly unit supports Cooley–Tukey butterfly-based forward NTT, Gentlemen–Sande butterfly-based inverse NTT, and other meta operations. [ABSTRACT FROM AUTHOR]

We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n)ɛ. This is required for weak space bounds on the size of their counters, for real-time and one-way, and for nondeterministic and alternating versions of these automata. The same holds for two-way automata, independent of whether they work with strong or weak space bounds, and of whether they are deterministic, nondeterministic, or alternating. (Here ɛ denotes an arbitrarily small—but fixed—constant; the "space" refers to the values stored in the counters, rather than to the lengths of their binary representation.) On the other hand, we show that the minimal space required for accepting a nonregular language is nɛ for multicounter automata with strong space bounds, both for real-time and one-way versions, independent of whether they are deterministic, nondeterministic, or alternating, and also for real-time and one-way deterministic multicounter automata with weak space bounds. All these bounds are optimal both for unary and general nonregular languages. However, for automata equipped with only one counter, it was known that one-way nondeterministic automata cannot recognize any unary nonregular languages at all, even if the size of the counter is not restricted, while, with weak space bound log n, we present a real-time nondeterministic automaton recognizing a binary nonregular language here. [ABSTRACT FROM AUTHOR]

• We extended the deterministic one-way jumping mode to two directions. • The model is storage-less, but strictly stronger than classical finite automata. • Two-way jumping is also strictly stronger than one-way. • We showed how to simulate one-way jumping machines with always halting counterparts. The recently introduced one-way jumping automata are strictly more powerful than classical finite automata (FA) while maintaining decidability in most of the important cases. We investigate the extension of the new processing mode to two-way deterministic finite automata (2DFA), resulting in deterministic finite automata which can jump to the nearest letter which they can read, with jumps allowed in either direction. We show that two-way jumping automata are strictly more powerful than one-way jumping ones and that alternative extensions of 2DFA with this jumping mode lead to equivalent machines. We also prove that the class of languages accepted by the new model is not closed under the usual language operations. Finally we show how one could change the model to terminate on every input by using non-erasable end markers. [ABSTRACT FROM AUTHOR]

In the implementation of robot motion control, it often requires complex forward and inverse kinematics calculation. However, this algorithm requires more CPU time in the software realization and apparently affects the response of robot movement. To solve this problem, the work is aimed at the development of the forward and inverse kinematics IP (intellectual property) based on FPGA (field programmable gate array) implementation and hoped to complete the overall computation less than ten microseconds for the purpose of enhancing the performance of the robot movement. In this paper, firstly, the forward and inverse kinematics for SCARA robot is derived. Secondly the circuit behavior using VHDL (Very-High-Speed-IC Hardware Description Language) is described. The design of VHDL code will apply the parameterized function to increase the code flexible and the FSM (Finite state machine) strategy is used to reduce the hardware resource usage. To verify the correctness of the proposed forward and inverse kinematics IP, a co-simulation work is constructed by ModelSim and Simulink. The forward and inverse kinematics IP is run by ModelSim and the Simulink models is taken as a test bench that generates stimulus to ModelSim and displays the output response. Finally, the developed forward and inverse kinematics IP will be downloaded to FPGA to further confirm its effectiveness. [ABSTRACT FROM AUTHOR]

Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority opinion when each agent has one of two opinions. Agents communicate in pairwise interactions with randomly assigned communication partners. Quality is measured in two ways: the number of interactions to complete the task and the number of states per agent. We present protocols for the majority problem that allow for a trade-off between these two measures. Compared to the only other trade-off result (Alistarh et al. in Proceedings of the 2015 ACM symposium on principles of distributed computing, Donostia-San Sebastián, 2015), we improve the number of interactions by almost a linear factor. Furthermore, our protocols can be made uniform (working correctly without any information on the population size n), yielding the first uniform majority protocols that stabilize in a subquadratic number of interactions. [ABSTRACT FROM AUTHOR]

Weighted finite automata (WFAs) are often used to represent probabilistic models, such as n-gram language models, because among other things, they are efficient for recognition tasks in time and space. The probabilistic source to be represented as a WFA, however, may come in many forms. Given a generic probabilistic model over sequences, we propose an algorithm to approximate it as a WFA such that the Kullback-Leibler divergence between the source model and the WFA target model is minimized. The proposed algorithm involves a counting step and a difference of convex optimization step, both of which can be performed efficiently. We demonstrate the usefulness of our approach on various tasks, including distilling n-gram models from neural models, building compact language models, and building open-vocabulary character models. The algorithms used for these experiments are available in an open-source software library. [ABSTRACT FROM AUTHOR]

We study the relationship between session types and behavioural contracts, representing Communicating Finite State Machines (CFSMs), under the assumption that processes communicate asynchronously. Session types represent a syntax-based approach for the description of communication protocols, while behavioural contracts, formally expressing CFSMs, follow an operational approach. We show the existence of a fully abstract interpretation of session types into a fragment of contracts that maps session subtyping into binary compliance-preserving CFSMs/behavioural contract refinement. In this way, on the one hand, we enrich the theory of session types with an operational characterization and, on the other hand, we use recent undecidability results for asynchronous session subtyping to obtain an original undecidability result for asynchronous CFSMs/behavioural contract refinement. [ABSTRACT FROM AUTHOR]

Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than ( 2 n n + 1 ) , with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e (1 + o (1)) m n (log n − log m) . [ABSTRACT FROM AUTHOR]

We propose a new algorithm for checking language equivalence of non-deterministic Büchi automata. We start from a construction proposed by Calbrix, Nivat and Podelski, which makes it possible to reduce the problem to that of checking equivalence of automata on finite words. Although this construction generates large and highly non-deterministic automata, we show how to exploit their specific structure and apply state-of-the art techniques based on coinduction to reduce the state-space that has to be explored. Doing so, we obtain algorithms which do not require full determinisation or complementation. [ABSTRACT FROM AUTHOR]

Researches about semantic computing are usually evaluated by experiments, lacking support from the theory of computation. But traditional finite automata are defined on a fixed finite set of states. They will be invalid when a different application needs to change the states. However, semantic computing always asks for more robust automata that can modify itself according to the changes of states. Therefore, in this paper, we redefine traditional automata in more robust forms by semantic computing. The intuitive idea is when the state which an automaton is supposed to enter has changed, we drive automata into a state that is similar to the original one. We can find another similar state in the original state set to replace the changed state by semantic similarity. Based on the theories of semantic similarity, there always exists a similar state. Therefore, once a state has changed, we can always find a similar state to replace it, which means that we can empower automata to adapt to the changes of states. Our new automata bridge the gap between semantic computing and the theory of computation. Furthermore, we also redefine fuzzy finite automata and pushdown automata in more robust forms. Finally, we provide an application about the weather forecast, which indicates how to overcome the limitations of traditional automata. [ABSTRACT FROM AUTHOR]

This paper presents a framework for adapting game elements to the player's affective state and the integration of the framework in a virtual reality environment for moral development. These game elements include gestural and facial expressions of avatars during dialogues with the player, background music, the score, game mechanics, aesthetics and learning. The framework BARGAIN (Behavioral Affective Rule-based Games Adaptation Interface) is an authoring tool for affective game design providing a visual interface based on finite state machine (FSM) technique to represent the affective rules as state transitions graph dependent on the player emotional state assessed using facial expression recognition system based on electroencephalography (EEG) data. We conducted a user study (n = 29) examining the effects of the resulting affective virtual reality game on players' experience using the Game experience Questionnaire (GEQ) (IJsselsteijn et al. in The game experience questionnaire, Technische Universiteit Eindhoven, Eindhoven, 2013). The results show significant correlation between the GEQ dimensions and the player's facial expressions during his interaction with the Non-Player Characters (NPCs) within the VR game. These findings highlight that adapting games to user's emotions enhance the players' experience. [ABSTRACT FROM AUTHOR]

Partially ordered automata are automata where the transition relation induces a partial order on states. The expressive power of partially ordered automata is closely related to the expressivity of fragments of first-order logic on finite words or, equivalently, to the language classes of the levels of the Straubing-Thérien hierarchy. Several fragments (levels) have been intensively investigated under various names. For instance, the fragment of first-order formulae with a single existential block of quantifiers in prenex normal form is known as piecewise testable languages or J-trivial languages. These languages are characterized by conuent partially ordered DFAs or by complete, conuent, and self-loop-deterministic partially ordered NFAs (ptNFAs for short). In this paper, we study the complexity of basic questions for several types of partially ordered automata on finite words; namely, the questions of inclusion, equivalence, and (k-)piecewise testability. The lower-bound complexity boils down to the complexity of universality. The universality problem asks whether a system recognizes all words over its alphabet. For ptNFAs, the complexity of universality decreases if the alphabet is fixed, but it is open if the alphabet may grow with the number of states. We show that deciding universality for general ptNFAs is as hard as for general NFAs. Our proof is a novel and nontrivial extension of our recent construction for self-loop-deterministic partially ordered NFAs, a model strictly more expressive than ptNFAs. We provide a comprehensive picture of the complexities of the problems of inclusion, equivalence, and (k-)piecewise testability for the considered types of automata. [ABSTRACT FROM AUTHOR]

Almost 50 years ago, D. E. Bell and L. LaPadula published the first formal model of a secure system, known today as the Bell–LaPadula (BLP) model. BLP is described as a state machine by means of first-order logic and set theory. The authors also formalize two state invariants known as security condition and *-property. Bell and LaPadula prove that all the state transitions preserve these invariants. In this paper we present a fully automated proof of the security condition and the *-property for all the model operations. The model and the proofs are coded in the { l o g } tool. As far as we know this is the first time such proofs are automated. Besides, we show that the { l o g } model is also an executable prototype. Therefore we are providing an automatically verified executable prototype of BLP. [ABSTRACT FROM AUTHOR]

Event-sequence modeling is a thread-architectural style for event-driven software. It bases the set of threads in a multithreaded program on an event-sequence model of the problem domain. Each event sequence is a time-ordered set of event occurrences in the domain. (It is often defined by a state machine.) An event-sequence model is a set of event sequences that together cover all relevant event occurrences in the domain. Occurrences in one event sequence are generally concurrent with those in other sequences. The event-sequence modeling approach leads to architectures consisting of threads, each based on an event sequence, and shared objects. The threads can run concurrently on different cores/processors except when they must have exclusive access to some shared object. This paper defines these concepts and illustrates them with examples. [ABSTRACT FROM AUTHOR]

Genome annotation conceptually consists of inferring and assigning biological information to gene products. Over the years, numerous pipelines and computational tools have been developed aiming to automate this task and assist researchers in gaining knowledge about target genes of study. However, even with these technological advances, manual annotation or manual curation is necessary, where the information attributed to the gene products is verified and enriched. Despite being called the gold standard process for depositing data in a biological database, the task of manual curation requires significant time and effort from researchers who sometimes have to parse through numerous products in various public databases. To assist with this problem, we present CODON, a tool for manual curation of genomic data, capable of performing the prediction and annotation process. This software makes use of a finite state machine in the prediction process and automatically annotates products based on information obtained from the Uniprot database. CODON is equipped with a simple and intuitive graphic interface that assists on manual curation, enabling the user to decide about the analysis based on information as to identity, length of the alignment, and name of the organism in which the product obtained a match. Further, visual analysis of all matches found in the database is possible, impacting significantly in the curation task considering that the user has at his disposal all the information available for a given product. An analysis performed on eleven organisms was used to test the efficiency of this tool by comparing the results of prediction and annotation through CODON to ones from the NCBI and RAST platforms. Author summary: The accuracy of genome annotation is directly impacted by the manual curation step since complementary information is added to gene products. However, this process takes time and requires specialized labor, since there is a need to consult external databases to check the information of the products inferred in the automated process. We present the CODON software, which allows this process to be dynamic and significantly reduce the total work, the user responsible for conducting manual curation will be able to check the annotation of each product directly on the screen of his computer, without the need to search for the similarity of each ORF in the external databases, it is possible to change the ORF annotation based on the information displayed on the screen, for example, percentage of identity and alignment length match. The results show that CODON is an efficient tool for manual curation, beyond prediction and annotation. In addition to providing the user with access to highly accurate database information, producing a result with more gene acronyms, metabolic pathway information, and Gene Ontology terms. [ABSTRACT FROM AUTHOR]

The growing complexity of modern digital design makes designers shift toward starting design exploration using high-level languages, and generating register transfer level (RTL) design from system level modeling (SLM) using high-level synthesis tools or manual transformation. Unfortunately, this translation process is very complex and error prone. The most important verification task is to check whether the RTL implementation is indeed equivalent to the system-level model. Equivalence checking is critical to ensure that the synthesized RTL conforms to its SLM specification. In this paper, we propose a novel path-based sequential equivalence checking method to validate the transformed RTL description against its corresponding SLM description. We represent the original SLM and the transformed RTL descriptions using Finite state machines with datapath (FSMD) and compare the path-pairs of the FSMD to obtain the equivalence of the designs. Then we recognize the corresponding path-pairs from all the generated paths of FSMD with Machine learning (ML) technique, and compare the recognized path-pairs by symbolic simulation and a satisfiability modulo theories (SMT) solver. Our method can handle designs without mapping information and improve the efficiency of the state-of-the-art path-based equivalence checking methods. The promising experiments on representative benchmarks indicate the efficiency and effectiveness of our method. [ABSTRACT FROM AUTHOR]

Today, field programmable gate array (FPGA) is becoming widely used as computational accelerators in many application domains such as image/video processing, machine learning, and data mining. The inherent tolerance to the imprecise computation in such domains potentially provides an opportunity to trade quality of the results for higher energy efficiency. Therefore, this paper proposes a systematic methodology aiming to find the optimal energy saving corresponding to different quality bound, by approximating register-transfer level (RTL) designs on FPGA. As a case study, first, we investigate imprecise design on two submodules — adders and multipliers. By integrating the two combinational submodules with finite state machines (FSMs), several designs on a sequential circuit — color-to-grayscale converter — are further presented to offer a diverse range of energy consumption related to different quality constrains. Through this, we are able to set energy–quality (E–Q) parameters of our proposed methodology and configure the approximation knobs, capable of maximizing energy savings within different application-based quality margins. Experimental result demonstrates that leveraging E–Q leads to an average 1. 3 7 – 2. 1 6 × savings in energy for modest loss in application output quality (< 3 %), and 2. 3 1 – 2. 5 0 × energy savings for impact on relaxed quality constraints (3–7.5%). [ABSTRACT FROM AUTHOR]

Regular language inference, initiated by Angluin, has many developments, including applications in software engineering and testing. However, the capability of finite automata to model the system data is quite limited and, in many cases, extended finite state machine formalisms, that combine the system control with data structures, are used instead. The application of Angluin-style inference algorithms to extended state machines would involve constructing a minimal deterministic extended finite state machine consistent with a deterministic 3-valued deterministic finite automaton. In addition to the usual, accepting and rejecting, states of finite automaton, a 3-valued deterministic finite automaton may have "don't care" states; the sequences of inputs that reach such states may be considered as accepted or rejected, as is convenient. The aforementioned construction reduces to finding a minimal deterministic finite automaton consistent with a 3-valued deterministic finite automaton, that preserves the deterministic nature of the extended model that also handles the data structure associated with it. This paper investigates fundamental properties of extended finite state machines in relation to Angluin's language inference problem and provides an inference algorithm for such models. [ABSTRACT FROM AUTHOR]