Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Efficient Construction of the Equation Automaton
View through CrossRef
This paper describes a fast algorithm for constructing directly the equation automaton from the well-known Thompson automaton associated with a regular expression. Allauzen and Mohri have presented a unified construction of small automata and gave a construction of the equation automaton with time and space complexity in O(mlogm+m2), where m denotes the number of Thompson automaton transitions. It is based on two classical automata operations, namely epsilon-removal and Hopcroft’s algorithm for deterministic Finite Automata (DFA) minimization. Using the notion of c-continuation, Ziadi et al. presented a fast computation of the equation automaton in O(m2) time complexity. In this paper, we design an output-sensitive algorithm combining advantages of the previous algorithms and show that its computational complexity can be reduced to O(m×|Q≡e|), where |Q≡e| denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA).
Title: Efficient Construction of the Equation Automaton
Description:
This paper describes a fast algorithm for constructing directly the equation automaton from the well-known Thompson automaton associated with a regular expression.
Allauzen and Mohri have presented a unified construction of small automata and gave a construction of the equation automaton with time and space complexity in O(mlogm+m2), where m denotes the number of Thompson automaton transitions.
It is based on two classical automata operations, namely epsilon-removal and Hopcroft’s algorithm for deterministic Finite Automata (DFA) minimization.
Using the notion of c-continuation, Ziadi et al.
presented a fast computation of the equation automaton in O(m2) time complexity.
In this paper, we design an output-sensitive algorithm combining advantages of the previous algorithms and show that its computational complexity can be reduced to O(m×|Q≡e|), where |Q≡e| denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA).
Related Results
A gearing forest automaton to automate a gearing system
A gearing forest automaton to automate a gearing system
Abstract
A gearing system design completely depends on the designer’s skills and experiences because there is no theory or method to standardize the design process. In this...
The waveform comparison of three common-used fractional viscous acoustic wave equations
The waveform comparison of three common-used fractional viscous acoustic wave equations
Abstract
The forward simulation of the viscous acoustic wave equation is an essential part of geophysics and energy resources exploration research. The viscous acoustic sei...
Long-range superharmonic Josephson current and spin-triplet pairing correlations in a junction with ferromagnetic bilayers
Long-range superharmonic Josephson current and spin-triplet pairing correlations in a junction with ferromagnetic bilayers
AbstractThe long-range spin-triplet supercurrent transport is an interesting phenomenon in the superconductor/ferromagnet ("Equation missing") heterostructure containing noncolline...
A New Method of Predicting the Productivity And Critical Production Rate Calculation of Horizontal Well
A New Method of Predicting the Productivity And Critical Production Rate Calculation of Horizontal Well
Abstract
The paper analyzes some productivity forecast equations and critical production rate calculation of horizontal wells especially Joshi's equation of predi...
Similarity Solutions for Shallow Hydraulic Fracture in Impermeable Rock
Similarity Solutions for Shallow Hydraulic Fracture in Impermeable Rock
ABSTRACT
The paper deals with the plane strain problem ofa shallow fluid-driven fracture propagating parallel to a free surface in an impermeable elastic rock. Fo...
Effects of Some Simpilfying Assumptions On Interpretation of Transient Data
Effects of Some Simpilfying Assumptions On Interpretation of Transient Data
Abstract
The fluid flows in porous medium is described by the diffusion type of partial differential equation. In deriving the flow equation for the constant comp...
Desa Pekerja Bangunan: Pemberdayaan Masyarakat Menuju Desa Penghasil Pekerja Bangunan Profesional Dan Bersertifikat Dengan Pemasaran Jasa Online Di Kelurahan Gunungpati
Desa Pekerja Bangunan: Pemberdayaan Masyarakat Menuju Desa Penghasil Pekerja Bangunan Profesional Dan Bersertifikat Dengan Pemasaran Jasa Online Di Kelurahan Gunungpati
The needs of construction workers play a very important role in society. However, based on the results of a survey of several construction workers from Gunungpati Village, problems...
An empirical study on the lead-lag relationship between individual share futures and spot markets: focused on NHN and GS Construction futures
An empirical study on the lead-lag relationship between individual share futures and spot markets: focused on NHN and GS Construction futures
This study tests the lead-lag relationship between spot and futures markets of NHN and GS construction company. We introduced the daily near by futures price and spot price of the ...