This paper states a new metaheuristic based on Deterministic Finite Automata （DFA） for the multi - objective optimization of combinatorial problems. First, a new DFA named Multi - Objective Deterministic Finite Auto...This paper states a new metaheuristic based on Deterministic Finite Automata （DFA） for the multi - objective optimization of combinatorial problems. First, a new DFA named Multi - Objective Deterministic Finite Automata （MDFA） is defined. MDFA allows the representation of the feasible solutions space of combinatorial problems. Second, it is defined and implemented a metaheuritic based on MDFA theory. It is named Metaheuristic of Deterministic Swapping （MODS）. MODS is a local search strategy that works using a MDFA. Due to this, MODS never take into account unfeasible solutions. Hence, it is not necessary to verify the problem constraints for a new solution found. Lastly, MODS is tested using well know instances of the Bi-Objective Traveling Salesman Problem （TSP） from TSPLIB. Its results were compared with eight Ant Colony inspired algorithms and two Genetic algorithms taken from the specialized literature. The comparison was made using metrics such as Spacing, Generational Distance, Inverse Generational Distance and No-Dominated Generation Vectors. In every case, the MODS results on the metrics were always better and in some of those cases, the superiority was 100%.展开更多
We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be ...We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .展开更多
A major issue while building web applications is proper input validation and sanitization.Attackers can quickly exploit errors and vulnerabilities that lead to malicious behavior in web application validation operatio...A major issue while building web applications is proper input validation and sanitization.Attackers can quickly exploit errors and vulnerabilities that lead to malicious behavior in web application validation operations.Attackers are rapidly improving their capabilities and technologies and now focus on exploiting vulnerabilities in web applications and compromising confidentiality.Cross-site scripting(XSS)and SQL injection attack(SQLIA)are attacks in which a hacker sends malicious inputs(cheat codes)to confuse a web application,to access or disable the application’s back-end without user awareness.In this paper,we explore the problem of detecting and removing bugs from both client-side and server-side code.A new idea that allows assault detection and prevention using the input validation mechanism is introduced.In addition,the project supports web security tests by providing easy-to-use and accurate models of vulnerability prediction and methods for validation.If these attributes imply a program statement that is vulnerable in an SQLIA,this can be evaluated and checked for a set of static code attributes.Additionally,we provide a script whitelisting interception layer built into the browser’s JavaScript engine,where the SQLIA is eventually detected and the XSS attack resolved using the method of input validation and script whitelisting under pushdown automatons.This framework was tested under a scenario of an SQL attack and XSS.It is demonstrated to offer an extensive improvement over the current framework.The framework’s main ability lies in the decrease of bogus positives.It has been demonstrated utilizing new methodologies,nevertheless giving unique access to sites dependent on the peculiarity score related to web demands.Our proposed input validation framework is shown to identify all anomalies and delivers better execution in contrast with the current program.展开更多
Huffman[Huffman(1952)]encoding is one of the most known compression algorithms.In its basic use,only one encoding is given for the same letter in text to compress.In this paper,a text compression algorithm that is bas...Huffman[Huffman(1952)]encoding is one of the most known compression algorithms.In its basic use,only one encoding is given for the same letter in text to compress.In this paper,a text compression algorithm that is based on Huffman encoding is proposed.Huffman encoding is used to give different encodings for the same letter depending on the prefix preceding it in the word.A deterministic finite automaton(DFA)that recognizes the words of the text is constructed.This DFA records the frequencies for letters that label the transitions.Every state will correspond to one of the prefixes of the words of the text.For every state,a different Huffman encoding is defined for the letters that label the transitions leaving that state.These Huffman encodings are then used to encode the letters of the words in the text.This algorithm was implemented and experimental study showed significant reduction in compression ratio over the basic Huffman encoding.However,more time is needed to construct these codes.展开更多
Nowadays, using Deterministic Finite Automata (DFA) or Non-deterministic Finite Automata (NFA) to parse regular expressions is the most popular way for Deep Packet Inspection (DPI), and the research about DPI focuses ...Nowadays, using Deterministic Finite Automata (DFA) or Non-deterministic Finite Automata (NFA) to parse regular expressions is the most popular way for Deep Packet Inspection (DPI), and the research about DPI focuses on the improvement of DFA to reduce memory. However, most of the existing literature ignores a special kind of "overlap-matching expression", which causes states explosion and takes quite a large part in the DPI rules. To solve this problem, in this paper a new mechanism is proposed based on bitmap. We start with a simple regular expression to describe "overlap-matching expressions" and state the problem. Then, after calculating the terrible number of exploded states for this kind of expressions, the procedure of Bitmap-based Soft Parallel Mechanism (BSPM) is described. Based on BSPM, we discuss all the different types of "overlap-matching ex- pressions" and give optimization suggestions of them separately. Finally, experiment results prove that BSPM can give an excellent performance on solving the problem stated above, and the optimization suggestions are also effective for the memory reduction on all types of "overlap-matching expressions".展开更多
A word w is called synchronizing （recurrent, reset, directable） word of deterministic finite automata （DFA） if w brings all states of the automaton to a unique state. According to the famous conjecture of Cerny fr...A word w is called synchronizing （recurrent, reset, directable） word of deterministic finite automata （DFA） if w brings all states of the automaton to a unique state. According to the famous conjecture of Cerny from 1964, every n-state synchronizing automaton possesses a synchronizing word of length at most （n - 1）2. The problem is still open. It will be proved that the Cerny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every n-state （n 〉 2） synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than （n - 1）2/2. The last important class of DFA involved and studied by Schutzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established.展开更多
文摘This paper states a new metaheuristic based on Deterministic Finite Automata （DFA） for the multi - objective optimization of combinatorial problems. First, a new DFA named Multi - Objective Deterministic Finite Automata （MDFA） is defined. MDFA allows the representation of the feasible solutions space of combinatorial problems. Second, it is defined and implemented a metaheuritic based on MDFA theory. It is named Metaheuristic of Deterministic Swapping （MODS）. MODS is a local search strategy that works using a MDFA. Due to this, MODS never take into account unfeasible solutions. Hence, it is not necessary to verify the problem constraints for a new solution found. Lastly, MODS is tested using well know instances of the Bi-Objective Traveling Salesman Problem （TSP） from TSPLIB. Its results were compared with eight Ant Colony inspired algorithms and two Genetic algorithms taken from the specialized literature. The comparison was made using metrics such as Spacing, Generational Distance, Inverse Generational Distance and No-Dominated Generation Vectors. In every case, the MODS results on the metrics were always better and in some of those cases, the superiority was 100%.
文摘We investigate decomposition of codes and finite languages. A prime decomposition is a decomposition of a code or languages into a concatenation of nontrivial prime codes or languages. A code is prime if it cannot be decomposed into at least two nontrivial codes as the same for the languages. In the paper, a linear time algorithm is designed, which finds the prime decomposition. If codes or finite languages are presented as given by its minimal deterministic automaton, then from the point of view of abstract algebra and graph theory, this automaton has special properties. The study was conducted using system for computational Discrete Algebra GAP. .
基金Taif University supported this study through Taif University Researcher Support Project(TURSP-2020/115).
文摘A major issue while building web applications is proper input validation and sanitization.Attackers can quickly exploit errors and vulnerabilities that lead to malicious behavior in web application validation operations.Attackers are rapidly improving their capabilities and technologies and now focus on exploiting vulnerabilities in web applications and compromising confidentiality.Cross-site scripting(XSS)and SQL injection attack(SQLIA)are attacks in which a hacker sends malicious inputs(cheat codes)to confuse a web application,to access or disable the application’s back-end without user awareness.In this paper,we explore the problem of detecting and removing bugs from both client-side and server-side code.A new idea that allows assault detection and prevention using the input validation mechanism is introduced.In addition,the project supports web security tests by providing easy-to-use and accurate models of vulnerability prediction and methods for validation.If these attributes imply a program statement that is vulnerable in an SQLIA,this can be evaluated and checked for a set of static code attributes.Additionally,we provide a script whitelisting interception layer built into the browser’s JavaScript engine,where the SQLIA is eventually detected and the XSS attack resolved using the method of input validation and script whitelisting under pushdown automatons.This framework was tested under a scenario of an SQL attack and XSS.It is demonstrated to offer an extensive improvement over the current framework.The framework’s main ability lies in the decrease of bogus positives.It has been demonstrated utilizing new methodologies,nevertheless giving unique access to sites dependent on the peculiarity score related to web demands.Our proposed input validation framework is shown to identify all anomalies and delivers better execution in contrast with the current program.
文摘Huffman[Huffman(1952)]encoding is one of the most known compression algorithms.In its basic use,only one encoding is given for the same letter in text to compress.In this paper,a text compression algorithm that is based on Huffman encoding is proposed.Huffman encoding is used to give different encodings for the same letter depending on the prefix preceding it in the word.A deterministic finite automaton(DFA)that recognizes the words of the text is constructed.This DFA records the frequencies for letters that label the transitions.Every state will correspond to one of the prefixes of the words of the text.For every state,a different Huffman encoding is defined for the letters that label the transitions leaving that state.These Huffman encodings are then used to encode the letters of the words in the text.This algorithm was implemented and experimental study showed significant reduction in compression ratio over the basic Huffman encoding.However,more time is needed to construct these codes.
基金Supported by the National High Technology Development 863 Program of China (No. 2008AA01Z117)
文摘Nowadays, using Deterministic Finite Automata (DFA) or Non-deterministic Finite Automata (NFA) to parse regular expressions is the most popular way for Deep Packet Inspection (DPI), and the research about DPI focuses on the improvement of DFA to reduce memory. However, most of the existing literature ignores a special kind of "overlap-matching expression", which causes states explosion and takes quite a large part in the DPI rules. To solve this problem, in this paper a new mechanism is proposed based on bitmap. We start with a simple regular expression to describe "overlap-matching expressions" and state the problem. Then, after calculating the terrible number of exploded states for this kind of expressions, the procedure of Bitmap-based Soft Parallel Mechanism (BSPM) is described. Based on BSPM, we discuss all the different types of "overlap-matching ex- pressions" and give optimization suggestions of them separately. Finally, experiment results prove that BSPM can give an excellent performance on solving the problem stated above, and the optimization suggestions are also effective for the memory reduction on all types of "overlap-matching expressions".
文摘A word w is called synchronizing （recurrent, reset, directable） word of deterministic finite automata （DFA） if w brings all states of the automaton to a unique state. According to the famous conjecture of Cerny from 1964, every n-state synchronizing automaton possesses a synchronizing word of length at most （n - 1）2. The problem is still open. It will be proved that the Cerny conjecture holds good for synchronizing DFA with transition monoid having no involutions and for every n-state （n 〉 2） synchronizing DFA with transition monoid having only trivial subgroups the minimal length of synchronizing word is not greater than （n - 1）2/2. The last important class of DFA involved and studied by Schutzenberger is called aperiodic; its automata accept precisely star-free languages. Some properties of an arbitrary synchronizing DFA were established.
