This paper introduces a variant of two-way quantum finite automata named two-way multihead quantum finite automata. A two-way quantum finite automaton is more powerful than classical two-way finite ...automata. However, the generalizations of two-way quantum finite automata have not been defined so far as compared to one-way quantum finite automata model. We have investigated the newly introduced automata from two aspects: the language recognition capability and its comparison with classical and quantum counterparts. It has been proved that a language which cannot be recognized by any one-way and multi-letter quantum finite automata can be recognized by two-way quantum finite automata. Further, it has been shown that a language which cannot be recognized by two-way quantum finite automata can be recognized by two-way multihead quantum finite automata with two heads. Furthermore, it has been investigated that quantum variant of two-way deterministic multihead finite automata takes less number of heads to recognize a language containing of all words whose length is a prime number.
We study the class of languages that have membership proofs which can be verified by real-time finite-state machines using only a constant number of random bits, regardless of the size of their ...inputs. Since any further restriction on the verifiers would preclude the verification of nonregular languages, this is the tightest computational budget which allows the checking of externally provided proofs to have meaningful use. We provide a full characterization of this class of languages in terms of a restricted version of the one-way nondeterministic multihead finite automaton model. For any k>0, there exist languages that cannot be recognized by any k-head one-way nondeterministic finite automaton, but that are nonetheless real-time verifiable in this sense. The set of nonpalindromes, which cannot be recognized by any one-way multihead deterministic finite automaton, is also demonstrated to be verifiable within these restrictions.
Linear temporal logic is a widely used method for verification of model checking and expressing the system specifications. The relationship between theory of automata and logic had a great influence ...in the computer science. Investigation of the relationship between quantum finite automata and linear temporal logic is a natural goal. In this paper, we present a construction of quantum finite automata on finite words from linear-time temporal logic formulas. Further, the relation between quantum finite automata and linear temporal logic is explored in terms of language recognition and acceptance probability. We have shown that the class of languages accepted by quantum finite automata are definable in linear temporal logic, except for measure-once one-way quantum finite automata.
We study the capabilities of probabilistic finite-state machines that act as verifiers for certificates of language membership for input strings, in the regime where the verifiers are restricted to ...toss some fixed nonzero number of coins regardless of the input size. Say and Yakaryılmaz showed that the class of languages that could be verified by these machines within an error bound strictly less than 12 is precisely NL, but their construction yields verifiers with error bounds that are very close to 12 for most languages in that class when the definition of “error” is strengthened to include looping forever without giving a response. We characterize a subset of NL for which verification with arbitrarily low error is possible by these extremely weak machines. It turns out that, for any ε>0, one can construct a constant-coin, constant-space verifier operating within error ε for every language that is recognizable by a linear-time multi-head nondeterministic finite automaton (2nfa(k)). We discuss why it is difficult to generalize this method to all of NL, and give a reasonably tight way to relate the power of linear-time 2nfa(k)'s to simultaneous time-space complexity classes defined in terms of Turing machines.
This article is a continuation of the authors' previous work devoted to the development of the algebra of finite automata of the special type DTA (Digital Twin Algebra), designed for mathematical ...modeling of the behavior of digital twins of production. In this work, the mathematical modeling of the functions of twins uses the DTA algebra apparatus in the form of systems of event-matched finite automata or event matched machines ‒ abbreviated ‒ EMM-systems, while automata (quasi-automata) of such systems are considered as having a specialized multi-sorted structure and an appropriate interpretation of behavior. The multi-sorted structure of automata is realized by dividing the states of quasi-automatic machines of EMM systems into non-intersecting classes, namely, the sets of their states are divided into two classes ‒ A (states of the modes of operation of an object modeled using FSA) and B (states of the production activity of an object). Such FSAs are called bipartite FSAs or abbreviated as BPA (Bipartite Automaton). Using a graphical view of such bipartite automata in the form of Moore diagrams, an example of describing the functioning of equipment and facilities of some imaginary mine of a mining enterprise is considered. This example demonstrates the clarity and adequacy of the means of the proposed apparatus for modelling the behavior of similar production facilities.
•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.
Regular expression matching is one of the key techniques for Deep packet inspection(DPI). Generally, the Deterministic finite automata(DFA) can process regular expression matching at a very high rate ...but memory inefficient. By contrast, the Non-deterministic finite automata(NFA) improves the memory efficiency significantly, at the cost of low speed. To meet the increasing demands on both throughput and memory scalability, we propose a novel schema to achieve fast regular expression with reasonable and controllable memory consumption. According to observations on matching real traffic, we design a Multi-Stride Indexing(MSI) table and divide each matching into two steps, toward the MSI table and the NFA respectively. the MSI table consumes a small fixed amount of on-chip memories(it is about 20 KB for 2 stride level MSI table). After the most of unnecessary matching was eliminated via MSI table, we implement the fast-speed regular expression matching with NFA.
The state complexity of a finite(-state) automaton intuitively measures the size of the description of the automaton. Sakoda and Sipser STOC 1972, pp. 275–286 were concerned with nonuniform families ...of finite automata and they discussed the behaviors of the nonuniform complexity classes defined by such families of finite automata having polynomial-size state complexity. In a similar fashion, we introduce state complexity classes using nonuniform families of quantum finite automata empowered by the flexible use of garbage tapes. We first present general inclusion and separation relationships among state complexity classes of nonuniform families of various one-way finite automata, including deterministic, nondeterministic, probabilistic, and quantum finite automata having polynomially many inner states. For two-way quantum finite automata equipped with flexible garbage tapes, we show a close relationship between the state complexity of the nonuniform family of such polynomial-size quantum finite automata and the parameterized complexity class induced by logarithmic-space quantum computation assisted by polynomial-size advice. We further establish a direct connection between space-bounded quantum computation with quantum advice and quantum finite automata whose transitions are dictated by superpositions of transition tables.
PDF
