Search results for "Finite-state machine"
showing 10 items of 97 documents
Quantum Finite State Transducers
2001
We introduce quantum finite state transducers (qfst), and study the class of relations which they compute. It turns out that they share many features with probabilistic finite state transducers, especially regarding undecidability of emptiness (at least for low probability of success). However, like their 'little brothers', the quantum finite automata, the power of qfst is incomparable to that of their probabilistic counterpart. This we show by discussing a number of characteristic examples.
Improved constructions of quantum automata
2008
We present a simple construction of quantum automata which achieve an exponential advantage over classical finite automata. Our automata use \frac{4}{\epsilon} \log 2p + O(1) states to recognize a language that requires p states classically. The construction is both substantially simpler and achieves a better constant in the front of \log p than the previously known construction of Ambainis and Freivalds (quant-ph/9802062). Similarly to Ambainis and Freivalds, our construction is by a probabilistic argument. We consider the possibility to derandomize it and present some results in this direction.
Probabilities to Accept Languages by Quantum Finite Automata
1999
We construct a hierarchy of regular languages such that the current language in the hierarchy can be accepted by 1-way quantum finite automata with a probability smaller than the corresponding probability for the preceding language in the hierarchy. These probabilities converge to 1/2.
Standard Sturmian words and automata minimization algorithms
2015
The study of some close connections between the combinatorial properties of words and the performance of the automata minimization process constitutes the main focus of this paper. These relationships have been, in fact, the basis of the study of the tightness and the extremal cases of Hopcroft's algorithm, that is, up to now, the most efficient minimization method for deterministic finite state automata. Recently, increasing attention has been paid to another minimization method that, unlike the approach proposed by Hopcroft, is not based on refinement of the set of states of the automaton, but on automata operations such as determinization and reverse, and is also applicable to non-determ…
Group Input Machine
2009
We introduce a new type of internal memory for finite automata and real-time automata. Instead of using tapes with a prescribed Euclidean structure (one-dimensional or two-dimensional tapes) we allow arbitrary group structure of the internal memory of the automata.
The monadic quantifier alternation hierarchy over grids and pictures
1998
The subject of this paper is the expressive power of monadic second-order logic over two-dimensional grids. We give a new, self-contained game-theoretical proof of the nonexpressibility results of Matz and Thomas. As we show, this implies the strictness of the monadic second-order quantifier alternation hierarchy over grids.
MAC-Engine
2011
In this demo, we prove that the flexibility supported by off-the-shelf IEEE 802.11 hardware can be significantly extended if we move the control of the MAC programming interface from the driver to the firmware, i.e. from the host CPU to the card CPU. To this purpose, we introduce the concept of MAC--Engine, that is an executor of Programmable Finite State Machines (PFSM) implemented at the firmware level: we show how the card itself can support different protocol logics thanks to PFSM bytecode representations that can be dynamically injected inside the card memory at run-time without incurring in down time issues or network disconnect events. We provide different PFSM examples in order to t…
CNC Milling Machine Simulation in Engineering Education
2012
In this work an effective simulator for a CNC milling machine is presented. It has been developed in EMC2, a free Opens Source NC software running in Linux environment, developed by an international community. It can be installed on a common PC and is able to: control a CNC machine; read part programs; display the tool path; send instructions to the CNC machine for the cutting process. In this work a new feature has been implemented, which can both display a 3D model of the machine and simulate all the motions of the movable parts of a real 3 axis end milling machine. This simulator lets the users not only verify the toolpath but also detect any possible collision by using the very computer…
Testing of cooperative tasks for Unmanned Aerial and ground platforms
2014
In the last years the Model Based Design for Unmanned Systems aided the safe and rational release of applications running on unmanned systems. In particular in this paper we focus on a hybrid methodology that merges Software in the Loop (SIL) and Model in the Loop (MIL) strategies for cooperative tasks performed by aerial and ground autonomous vehicles. The proposed work flow covers the design and testing of Ground Control Station (GCS) modelled by a finite state machine, the design and testing of navigation code running on UAV and UGV and the testing of cooperative missions. The work-flow is based on a realistic 3D physical simulator interfaced with Matlab-Simulink-Stafeflow. The proposed …
Application of latent nestling method using Coloured Petri Nets for the Fault Diagnosis in the wind turbine subsets
2008
This paper presents an application example using the lating nestling method for the fault diagnosis based in the use of coloured Petri nets, to a lubrication and cooling system in the wind turbinepsilas gearbox with a critical subsystem as far as failure probability. It demonstrate the synthesis capacity of the method for any model of diagnosis and isolation, giving as opposed to know the contributed advantages other methodologies, as those based in finite state machine.