To see the other types of publications on this topic, follow the link: Deterministic finite state automata.
Dissertations / Theses on the topic 'Deterministic finite state automata'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Deterministic finite state automata.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Merryman, William Patrick. "Animating the conversion of nondeterministic finite state automata to deterministic finite state automata." Thesis, Montana State University, 2007. http://etd.lib.montana.edu/etd/2007/merryman/MerrymanW0507.pdf.
Full text
2
Kshatriya, Jagannath Rajini Singh. "Visualizing the minimization of a deterministic finite state automaton." Thesis, Montana State University, 2007. http://etd.lib.montana.edu/etd/2007/kshatriyajagannath/KshatriyaJagannathR1207.pdf.
Full text
3
Stanek, Timotej. "Automatické shlukování regulárních výrazů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2011. http://www.nusl.cz/ntk/nusl-235531.
Full textAbstract:
This project is about security of computer networks using Intrusion Detection Systems. IDS contain rules for detection expressed with regular expressions, which are for detection represented by finite-state automata. The complexity of this detection with non-deterministic and deterministic finite-state automata is explained. This complexity can be reduced with help of regular expressions grouping. Grouping algorithm and approaches for speedup and improvement are introduced. One of the approches is Genetic algorithm, which can work real-time. Finally Random search algorithm for grouping of regular expressions is presented. Experiment results with these approches are shown and compared between each other.
4
Neme, Alexis. "An arabic language resource for computational morphology based on the semitic model." Thesis, Paris Est, 2020. http://www.theses.fr/2020PESC2013.
Full textAbstract:
La morphologie de la langue arabe est riche, complexe, et hautement flexionnelle. Nous avons développé une nouvelle approche pour la morphologie traditionnelle arabe destinés aux traitements automatiques de l’arabe écrit. Cette approche permet de formaliser plus simplement la morphologie sémitique en utilisant Unitex, une suite logicielle fondée sur des ressources lexicales pour l'analyse de corpus. Pour les verbes (Neme, 2011), j’ai proposé une taxonomie flexionnelle qui accroît la lisibilité du lexique et facilite l’encodage, la correction et la mise-à-jour par les locuteurs et linguistes arabes. La grammaire traditionnelle définit les classes verbales par des schèmes et des sous-classes par la nature des lettres de la racine. Dans ma taxonomie, les classes traditionnelles sont réutilisées, et les sous-classes sont redéfinies plus simplement. La couverture lexicale de cette ressource pour les verbes dans un corpus test est de 99 %. Pour les noms et les adjectifs (Neme, 2013) et leurs pluriels brisés, nous sommes allés plus loin dans l’adaptation de la morphologie traditionnelle. Tout d’abord, bien que cette tradition soit basée sur des règles dérivationnelles, nous nous sommes restreints aux règles exclusivement flexionnelles. Ensuite, nous avons gardé les concepts de racine et de schème, essentiels au modèle sémitique. Pourtant, notre innovation réside dans l’inversion du modèle traditionnel de racine-et-schème au modèle schème-et-racine, qui maintient concis et ordonné l’ensemble des classes de modèle et de sous-classes de racine. Ainsi, nous avons élaboré une taxonomie pour le pluriel brisé contenant 160 classes flexionnelles, ce qui simplifie dix fois l’encodage du pluriel brisé. Depuis, j’ai élaboré des ressources complètes pour l’arabe écrit. Ces ressources sont décrites dans Neme et Paumier (2019). Ainsi, nous avons complété ces taxonomies par des classes suffixées pour les pluriels réguliers, adverbes, et d’autres catégories grammaticales afin de couvrir l’ensemble du lexique. En tout, nous obtenons environ 1000 classes de flexion implémentées au moyen de transducteurs concatenatifs et non-concatenatifs. A partir de zéro, j’ai créé 76000 lemmes entièrement voyellisés, et chacun est associé à une classe flexionnelle. Ces lemmes sont fléchis en utilisant ces 1000 FST, produisant un lexique entièrement fléchi de plus 6 millions de formes. J’ai étendu cette ressource entièrement fléchie à l’aide de grammaires d’agglutination pour identifier les mots composés jusqu’à 5 segments, agglutinés autour d’un verbe, d’un nom, d’un adjectif ou d’une particule. Les grammaires d’agglutination étendent la reconnaissance à plus de 500 millions de formes de mots valides, partiellement ou entièrement voyelles. La taille de fichier texte généré est de 340 mégaoctets (UTF-16). Il est compressé en 11 mégaoctets avant d’être chargé en mémoire pour la recherche rapide (fast lookup). La génération, la compression et la minimisation du lexique prennent moins d’une minute sur un MacBook. Le taux de couverture lexical d’un corpus est supérieur à 99 %. La vitesse de tagger est de plus de 200 000 mots/s, si les ressources ont été pré-chargées en mémoire RAM. La précision et la rapidité de nos outils résultent de notre approche linguistique systématique et de l’adoption des meilleurs choix pratiques en matière de méthodes mathématiques et informatiques. La procédure de recherche est rapide parce que nous utilisons l’algorithme de minimisation d’automate déterministique acyclique (Revuz, 1992) pour comprimer le dictionnaire complet, et parce qu’il n’a que des chaînes constantes. La performance du tagger est le résultat des bons choix pratiques dans les technologies automates finis (FSA/FST) car toutes les formes fléchies calculées à l’avance pour une identification précise et pour tirer le meilleur parti de la compression et une recherche des mots déterministes et efficace<br>We developed an original approach to Arabic traditional morphology, involving new concepts in Semitic lexicology, morphology, and grammar for standard written Arabic. This new methodology for handling the rich and complex Semitic languages is based on good practices in Finite-State technologies (FSA/FST) by using Unitex, a lexicon-based corpus processing suite. For verbs (Neme, 2011), I proposed an inflectional taxonomy that increases the lexicon readability and makes it easier for Arabic speakers and linguists to encode, correct, and update it. Traditional grammar defines inflectional verbal classes by using verbal pattern-classes and root-classes. In our taxonomy, traditional pattern-classes are reused, and root-classes are redefined into a simpler system. The lexicon of verbs covered more than 99% of an evaluation corpus. For nouns and adjectives (Neme, 2013), we went one step further in the adaptation of traditional morphology. First, while this tradition is based on derivational rules, we found our description on inflectional ones. Next, we keep the concepts of root and pattern, which is the backbone of the traditional Semitic model. Still, our breakthrough lies in the reversal of the traditional root-and-pattern Semitic model into a pattern-and-root model, which keeps small and orderly the set of pattern classes and root sub-classes. I elaborated a taxonomy for broken plural containing 160 inflectional classes, which simplifies ten times the encoding of broken plural. Since then, I elaborated comprehensive resources for Arabic. These resources are described in Neme and Paumier (2019). To take into account all aspects of the rich morphology of Arabic, I have completed our taxonomy with suffixal inflexional classes for regular plurals, adverbs, and other parts of speech (POS) to cover all the lexicon. In all, I identified around 1000 Semitic and suffixal inflectional classes implemented with concatenative and non-concatenative FST devices.From scratch, I created 76000 fully vowelized lemmas, and each one is associated with an inflectional class. These lemmas are inflected by using these 1000 FSTs, producing a fully inflected lexicon with more than 6 million forms. I extended this fully inflected resource using agglutination grammars to identify words composed of up to 5 segments, agglutinated around a core inflected verb, noun, adjective, or particle. The agglutination grammars extend the recognition to more than 500 million valid delimited word forms, partially or fully vowelized. The flat file size of 6 million forms is 340 megabytes (UTF-16). It is compressed then into 11 Mbytes before loading to memory for fast retrieval. The generation, compression, and minimization of the full-form lexicon take less than one minute on a common Unix laptop. The lexical coverage rate is more than 99%. The tagger speed is 5000 words/second, and more than 200 000 words/s, if the resources are preloaded/resident in the RAM. The accuracy and speed of our tools result from our systematic linguistic approach and from our choice to embrace the best practices in mathematical and computational methods. The lookup procedure is fast because we use Minimal Acyclic Deterministic Finite Automaton (Revuz, 1992) to compress the full-form dictionary, and because it has only constant strings and no embedded rules. The breakthrough of our linguistic approach remains principally on the reversal of the traditional root-and-pattern Semitic model into a pattern-and-root model.Nonetheless, our computational approach is based on good practices in Finite-State technologies (FSA/FST) as all the full-forms were computed in advance for accurate identification and to get the best from the FSA compression for fast and efficient lookups
5
Watson, Bruce William. "Constructing minimal acyclic deterministic finite automata." Thesis, University of Pretoria, 2010. http://hdl.handle.net/2263/23648.
Full textAbstract:
This thesis is submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Ph.D) in the FASTAR group of the Department of Computer Science, University of Pretoria, South Africa. I present a number of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs), most of which I originally derived/designed or co-discovered. Being acyclic, such automata represent finite languages and have proven useful in applications such as spellchecking, virus-searching and text indexing. In many of those applications, the automata grow to billions of states, making them difficult to store without using various compression techniques — the most important of which is minimization. Results from the late 1950’s show that minimization yields a unique automaton (for a given language), and later results show that minimization of acyclic automata is possible in time linear in the number of states. These two results make for a rich area of algorithmics research; automata and algorithmics research are relatively old fields of computing science and the discovery/invention of new algorithms in the field is an exciting result. I present both incremental and nonincremental algorithms. With nonincremental techniques, the unminimized acyclic deterministic finite automaton (ADFA) is first constructed and then minimized. As mentioned above, the unminimized ADFA can be very large indeed — often even too large to fit within the virtual memory space of the computer. As a result, incremental techniques for minimization (i.e. the ADFA is minimized during its construction) become interesting. Incremental algorithms frequently have some overhead: if the unminimized ADFA fits easily within physical memory, it may still be faster to use nonincremental techniques. The presentation used in this thesis has a few unusual characteristics: <ul><li> Few other presentations follow a correctness-by-construction style for presenting and deriving algorithms. The presentations given here include correctness arguments or sketches thereof. </li><li> The presentation is taxonomic — emphasizing the similarities and differences between the algorithms at a fundamental level. </li><li> While it is possible to present these algorithms in a formal-language-theoretic setting, this thesis remains somewhat closer to the actual implementation issues. </li><li> In several chapters, new algorithms and interesting new variants of existing algorithms are presented. </li><li> It gives new presentations of many existing algorithms — all in a common format with common examples. </li><li> There are extensive links to the existing literature. </li></ul><br>Thesis (PhD)--University of Pretoria, 2011.<br>Computer Science<br>unrestricted
6
VETTEL, LYNNE ANN. "LEARNING DETERMINISTIC FINITE AUTOMATA TO CAPTURE TEMPORAL PATTERNS." University of Cincinnati / OhioLINK, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1037999729.
Full text
7
Bilal, Tahir. "Content Based Packet Filtering In Linux Kernel Using Deterministic Finite Automata." Master's thesis, METU, 2011. http://etd.lib.metu.edu.tr/upload/12613710/index.pdf.
Full textAbstract:
In this thesis, we present a content based packet filtering Architecture in Linux using Deterministic Finite Automata and iptables framework. New generation firewalls and intrusion detection systems not only filter or inspect network packets according to their header fields but also take into account the content of payload. These systems use a set of signatures in the form of regular expressions or plain strings to scan network packets. This scanning phase is a CPU intensive task which may degrade network performance. Currently, the Linux kernel firewall scans network packets separately for each signature in the signature set provided by the user. This approach constitutes a considerable bottleneck to network performance. We implement a content based packet filtering architecture and a multiple string matching extension for the Linux kernel firewall that matches all signatures at once, and show that we are able to filter network traffic by consuming constant bandwidth regardless of the number of signatures. Furthermore, we show that we can do packet filtering in multi-gigabit rates.
8
FRANCH, Daniel Kudlowiez. "Dynamical system modeling with probabilistic finite state automata." Universidade Federal de Pernambuco, 2017. https://repositorio.ufpe.br/handle/123456789/25448.
Full textAbstract:
Submitted by Fernanda Rodrigues de Lima (fernanda.rlima@ufpe.br) on 2018-08-02T22:51:47Z
No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Daniel Kudlowiez Franch.pdf: 1140156 bytes, checksum: c02b1b4ca33f8165be5960ba5a212730 (MD5)<br>Approved for entry into archive by Alice Araujo (alice.caraujo@ufpe.br) on 2018-08-07T21:11:31Z (GMT) No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Daniel Kudlowiez Franch.pdf: 1140156 bytes, checksum: c02b1b4ca33f8165be5960ba5a212730 (MD5)<br>Made available in DSpace on 2018-08-07T21:11:31Z (GMT). No. of bitstreams: 2
license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5)
DISSERTAÇÃO Daniel Kudlowiez Franch.pdf: 1140156 bytes, checksum: c02b1b4ca33f8165be5960ba5a212730 (MD5)
Previous issue date: 2017-03-10<br>FACEPE<br>Discrete dynamical systems are widely used in a variety of scientific and engineering applications, such as electrical circuits, machine learning, meteorology and neurobiology. Modeling these systems involves performing statistical analysis of the system output to estimate the parameters of a model so it can behave similarly to the original system. These models can be used for simulation, performance analysis, fault detection, among other applications. The current work presents two new algorithms to model discrete dynamical systems from two categories (synchronizable and non-synchronizable) using Probabilistic Finite State Automata (PFSA) by analyzing discrete symbolic sequences generated by the original system and applying statistical methods and inference, machine learning algorithms and graph minimization techniques to obtain compact, precise and efficient PFSA models. Their performance and time complexity are compared with other algorithms present in literature that aim to achieve the same goal by applying the algorithms to a series of common examples.<br>Sistemas dinâmicos discretos são amplamente usados em uma variedade de aplicações cientifícas e de engenharia, por exemplo, circuitos elétricos, aprendizado de máquina, meteorologia e neurobiologia. O modelamento destes sistemas envolve realizar uma análise estatística de sequências de saída do sistema para estimar parâmetros de um modelo para que este se comporte de maneira similar ao sistema original. Esses modelos podem ser usados para simulação, referência ou detecção de falhas. Este trabalho apresenta dois novos algoritmos para modelar sistemas dinâmicos discretos de duas categorias (sincronizáveis e não-sincronizáveis) por meio de Autômatos Finitos Probabilísticos (PFSA, Probabilistic Finite State Automata) analisando sequências geradas pelo sistema original e aplicando métodos estatísticos, algoritmos de aprendizado de máquina e técnicas de minimização de grafos para obter modelos PFSA compactos e eficientes. Sua performance e complexidade temporal são comparadas com algoritmos presentes na literatura que buscam atingir o mesmo objetivo aplicando os algoritmos a uma série de exemplos.
9
Khemuka, Atul Ravi. "Workflow Modeling Using Finite Automata." [Tampa, Fla.] : University of South Florida, 2003. http://purl.fcla.edu/fcla/etd/SFE0000172.
Full text
10
Bird, Philip. "Unifying programming paradigms : logic programming and finite state automata." Thesis, University of Sheffield, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.419609.
Full text
11
Egri-Nagy, Attila. "Algebraic hierarchical decomposition of finite state automata : a computational approach." Thesis, University of Hertfordshire, 2005. http://hdl.handle.net/2299/14267.
Full textAbstract:
The theory of algebraic hierarchical decomposition of finite state automata is an important and well developed branch of theoretical computer science (Krohn-Rhodes Theory). Beyond this it gives a general model for some important aspects of our cognitive capabilities and also provides possible means for constructing artificial cognitive systems: a Krohn-Rhodes decomposition may serve as a formal model of understanding since we comprehend the world around us in terms of hierarchical representations. In order to investigate formal models of understanding using this approach, we need efficient tools but despite the significance of the theory there has been no computational implementation until this work. Here the main aim was to open up the vast space of these decompositions by developing a computational toolkit and to make the initial steps of the exploration. Two different decomposition methods were implemented: the VuT and the holonomy decomposition. Since the holonomy method, unlike the VUT method, gives decompositions of reasonable lengths, it was chosen for a more detailed study. In studying the holonomy decomposition our main focus is to develop techniques which enable us to calculate the decompositions efficiently, since eventually we would like to apply the decompositions for real-world problems. As the most crucial part is finding the the group components we present several different ways for solving this problem. Then we investigate actual decompositions generated by the holonomy method: automata with some spatial structure illustrating the core structure of the holonomy decomposition, cases for showing interesting properties of the decomposition (length of the decomposition, number of states of a component), and the decomposition of finite residue class rings of integers modulo n. Finally we analyse the applicability of the holonomy decompositions as formal theories of understanding, and delineate the directions for further research.
12
Cazalis, Daniel S. "Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications." FIU Digital Commons, 2007. http://digitalcommons.fiu.edu/etd/8.
Full textAbstract:
Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.
13
Makarov, Alexander. "Application of finite state methods to shape coding and processing in object-based video." Thesis, Staffordshire University, 2002. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.368316.
Full text
14
Atchuta, Kaushik. "Slicing of extended finite state machines." Kansas State University, 2014. http://hdl.handle.net/2097/17640.
Full textAbstract:
Master of Science<br>Department of Computing and Information Sciences<br>Torben Amtoft<br>An EFSM (Extended Finite State Machine) is a tuple (S, T, E, V) where S is a finite set of states,
T is a finite set of transitions, E is a finite set of events, and V is a finite set of variables.
Every transition t in T has a source state and a target state, both in S.
There is a need to develop a GUI which aids in building such machines and simulating them so
that a slicing algorithm can be implemented on such graphs. This was the main idea of Dr.
Torben Amtoft, who has actually written the slicing algorithm and wanted this to be
implemented in code.
The project aims at implementing a GUI which is effective to simulate and build the graph with
minimum user effort. Poor design often fails to attract users. So, the initial effort is to build a
simple and effective GUI which serves the purpose of taking input from the user, building graphs
and simulating it.
The scope of this project is to build and implement an interface so that the users can do the
following in an effective way:
Input a specification of an EFSM
Store and later retrieve EFSMs
Displaying an EFSM in a graphical form
Simulating the EFSM
Modify an EFSM
Implement the slicing algorithm
All the above mentioned features must be integrated into the GUI and it should only fail if the
input specification is wrong.
15
Hulden, Mans. "Finite-state Machine Construction Methods and Algorithms for Phonology and Morphology." Diss., The University of Arizona, 2009. http://hdl.handle.net/10150/196112.
Full textAbstract:
This dissertation is concerned with finite state machine-based technology for modeling natural language. Finite-state machines have proven to be efficient computational devices in modeling natural language phenomena in morphology and phonology. Because of their mathematical closure properties, finite-state machines can be manipulated and combined in many flexible ways that closely resemble formalisms used in different areas of linguistics to describe natural language. The use of finite-state transducers in constructing natural language parsers and generators has proven to be a versatile approach to describing phonological alternation, morphological constraints and morphotactics, and syntactic phenomena on the phrase level.The main contributions of this dissertation are the development of a new model of multitape automata, the development of a new logic formalism that can substitute for regular expressions in constructing complex automata, and adaptations of these techniques to solving classical construction problems relating to finite-state transducers, such as modeling reduplication and complex phonological replacement rules.The multitape model presented here goes hand-in-hand with the logic formalism, the latter being a necessary step to constructing the former. These multitape automata can then be used to create entire morphological and phonological grammars, and can also serve as a neutral intermediate tool to ease the construction of automata for other purposes.The construction of large-scale finite-state models for natural language grammars is a very delicate process. Making any solution practicable requires great care in the efficient implementation of low-level tasks such as converting regular expressions, logical statements, sets of constraints, and replacement rules to automata or finite transducers. To support the overall endeavor of showing the practicability of the logical and multitape extensions proposed in this thesis, a detailed treatment of efficient implementation of finite-state construction algorithms for natural language purposes is also presented.
16
Wilson, Deborah Ann Stoffer. "A Study of the Behavior of Chaos Automata." Kent State University / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=kent1478955376070686.
Full text
17
Bianchi, M. P. "DESCRIPTIONAL COMPLEXITY OF CLASSICAL AND QUANTUM UNARY AUTOMATA." Doctoral thesis, Università degli Studi di Milano, 2013. http://hdl.handle.net/2434/217566.
Full textAbstract:
In this thesis, we study some problems on classical and quantum one-way finite state automata working on a unary input alphabet. The central issue of this work is the descriptional complexity of different models of automata on families of languages defined through periodicity conditions on the length of the input. However, along the way many other issues on automata, such as computational power and decidability, are taken into consideration.
The work is organised into two parts. In the first one, we focus on three types of classical one-way finite automata, namely deterministic (DFAs), nondeterministic (NFAs) and probabilistic (PFAs), which differ from each other for the way evolution is defined. We present a normal form for unary PFAs, which extends the Chrobak normal form for NFAs and guarantees minimality on periodic languages. We then use this probabilistic normal form to obtain descriptional complexity results: we analyze several families of unary languages, characterized by periodicity conditions. We show that, for some of those families, all classical models require the same number of states while, for some other families, PFAs can be smaller than NFAs (sometimes reaching the theoretical lower bound), which in turn can be smaller than DFAs.
In the second part of this thesis, we focus on the quantum paradigm, considering three variants of one-way quantum automata (QFAs): measure-once QFAs (MO-QFAs), measure-many QFAs (MM-QFAs), and the hybrid model of QFA with control language (QFC). The computational power of MM-QFAs, unlike the one of MO-QFAs and QFCs, is still not fully characterised. In this thesis, we provide an explicit construction for MM-QFAs to recognize any unary regular language.
We then focus on the descriptional complexity of QFAs: first, we present families of unary languages for which MM-QFAs require an exponentially smaller number of states with respect to their deterministic equivalent. Then, we prove that this is very close to the (asymptotically) biggest size gap we can achieve between the two models, by showing a more general conversion lower bound on the number of states required by a DFA to simulate a QFC working on an alphabet of arbitrary size. This bound carries over to the other two quantum models, since both MO-QFAs and MM-QFAs can be simulated by QFCs without increasing the number of quantum states. Finally, we discuss periodicity problems on the behavior of MM-QFAs, presenting polynomial algorithmic solutions.
18
Davis, Paul C. "Stone Soup Translation: The Linked Automata Model." Connect to this title online, 2002. http://rave.ohiolink.edu/etdc/view?acc%5Fnum=osu1023806593.
Full textAbstract:
Thesis (Ph. D.)--Ohio State University, 2002.<br>Title from first page of PDF file. Document formatted into pages; contains xvi, 306 p.; includes graphics. Includes abstract and vita. Advisor: Chris Brew, Dept. of Linguistics. Includes indexes. Includes bibliographical references (p. 284-293).
19
Totzke, Patrick. "Inclusion problems for one-counter systems." Thesis, University of Edinburgh, 2014. http://hdl.handle.net/1842/9646.
Full textAbstract:
We study the decidability and complexity of verification problems for infinite-state systems. A fundamental question in formal verification is if the behaviour of one process is reproducible by another. This inclusion problem can be studied for various models of computation and behavioural preorders. It is generally intractable or even undecidable already for very limited computational models. The aim of this work is to clarify the status of the decidability and complexity of some well-known inclusion problems for suitably restricted computational models. In particular, we address the problems of checking strong and weak simulation and trace inclusion for processes definable by one-counter automata (OCA), that consist of a finite control and a single counter ranging over the non-negative integers. We take special interest of the subclass of one-counter nets (OCNs), that cannot fully test the counter for zero and which is subsumed both by pushdown automata and Petri nets / vector addition systems. Our new results include the PSPACE-completeness of strong and weak simulation, and the undecidability of trace inclusion for OCNs. Moreover, we consider semantic preorders between OCA/OCN and finite systems and close some gaps regarding their complexity. Finally, we study deterministic processes, for which simulation and trace inclusion coincide.
20
Petrovic, Pavel. "Incremental Evolutionary Methods for Automatic Programming of Robot Controllers." Doctoral thesis, Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, 2007. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-1748.
Full textAbstract:
<p>The aim of the main work in the thesis is to investigate Incremental Evolution methods for designing a suitable behavior arbitration mechanism for behavior-based (BB) robot controllers for autonomous mobile robots performing tasks of higher complexity. The challenge of designing effective controllers for autonomous mobile robots has been intensely studied for few decades. Control Theory studies the fundamental control principles of robotic systems. However, the technological progress allows, and the needs of advanced manufacturing, service, entertainment, educational, and mission tasks require features beyond the scope of the standard functionality and basic control. Artificial Intelligence has traditionally looked upon the problem of designing robotics systems from the high-level and top-down perspective: given a working robotic device, how can it be equipped with an intelligent controller. Later approaches advocated for better robustness, modifiability, and control due to a bottom-up layered incremental controller and robot building (Behavior-Based Robotics, BBR). Still, the complexity of programming such system often requires manual work of engineers. Automatic methods might lead to systems that perform task on demand without the need of expert robot programmer. In addition, a robot programmer cannot predict all the possible situations in the robotic applications. Automatic programming methods may provide flexibility and adaptability of the robotic products with respect to the task performed. One possible approach to automatic design of robot controllers is Evolutionary Robotics (ER). Most of the experiments performed in the field of ER have achieved successful learning of target task, while the tasks were of limited complexity. This work is a marriage of incremental idea from the BBR and automatic programming of controllers using ER. Incremental Evolution allows automatic programming of robots for more complex tasks by providing a gentle and easy-to understand support by expertknowledge — division of the target task into sub-tasks. We analyze different types of incrementality, devise new controller architecture, implement an original simulator compatible with hardware, and test it with various incremental evolution tasks for real robots. We build up our experimental field through studies of experimental and educational robotics systems, evolutionary design, distributed computation that provides the required processing power, and robotics applications. University research is tightly coupled with education. Combining the robotics research with educational applications is both a useful consequence as well as a way of satisfying the necessary condition of the need of underlying application domain where the research work can both reflect and base itself.</p>
21
Lewandowski, Matthew. "A Novel Method For Watermarking Sequential Circuits." Scholar Commons, 2013. http://scholarcommons.usf.edu/etd/4528.
Full textAbstract:
We present an Intellectual Property (IP) protection technique for sequential circuits driven by embedding a decomposed signature into a Finite State Machine (FSM) through the manipulation of the arbitrary state encoding of the unprotected FSM. This technique is composed of three steps: (a) transforming the signature into a watermark graph, (b) embedding watermark graphs into the original FSM's State Transition Graph (STG) and (c) generating models for verification and extraction. In the watermark construction process watermark graphs are generated from signatures. The proposed methods for watermark construction are: (1) BSD, (2) FSD, and (3) HSD. The HSD method is shown to be advantageous for all signatures while providing sparse watermark FSMs with complexity O(n^2). The embedding process is related to the sub-graph matching problem. Due to the computational complexity of the matching problem, attempts to reverse engineer or remove the constructed watermark from the protected FSM, with only finite resources and time, are shown to be infeasible. The proposed embedding solutions are: (1) Brute Force and (2) Greedy Heuristic. The greedy heuristic has a computational complexity of O(n log n), where n is the number of states in the watermark graph. The greedy heuristic showed improvements for three of the six encoding schemes used in experimental results. Model generation and verification utilizes design automation techniques for generating multiple representations of the original, watermark, and watermarked FSMs. Analysis of the security provided by this method shows that a variety of attacks on the watermark and system including: (1) data-mining hidden functionality, (2) preimage, (3) secondary preimage, and (4) collision, can be shown to be computationally infeasible. Experimental results for the ten largest IWLS 93 benchmarks that the proposed watermarking technique is a secure, yet flexible, technique for protecting sequential circuit based IP cores.
22
Brits, Jeanetta Hendrina. "Outomatiese Setswana lemma-identifisering / Jeanetta Hendrina Brits." Thesis, North-West University, 2006. http://hdl.handle.net/10394/1160.
Full textAbstract:
Within the context of natural language processing, a lemmatiser is one of the
most important core technology modules that has to be developed for a particular
language. A lemmatiser reduces words in a corpus to the corresponding lemmas
of the words in the lexicon.
A lemma is defined as the meaningful base form from which other more complex
forms (i.e. variants) are derived. Before a lemmatiser can be developed for a
specific language, the concept "lemma" as it applies to that specific language
should first be defined clearly. This study concludes that, in Setswana, only
stems (and not roots) can act independently as words; therefore, only stems
should be accepted as lemmas in the context of automatic lemmatisation for
Setswana.
Five of the seven parts of speech in Setswana could be viewed as closed
classes, which means that these classes are not extended by means of regular
morphological processes. The two other parts of speech (nouns and verbs) require
the implementation of alternation rules to determine the lemma. Such alternation
rules were formalised in this study, for the purpose of development of a
Setswana lemmatiser. The existing Setswana grammars were used as basis for
these rules. Therewith the precision of the formalisation of these existing grammars
to lemmatise Setswana words could be determined.
The software developed by Van Noord (2002), FSA 6, is one of the best-known
applications available for the development of finite state automata and transducers.
Regular expressions based on the formalised morphological rules were
used in FSA 6 to create finite state transducers. The code subsequently generated
by FSA 6 was implemented in the lemmatiser.
The metric that applies to the evaluation of the lemmatiser is precision. On a test
corpus of 1 000 words, the lemmatiser obtained 70,92%. In another evaluation
on 500 complex nouns and 500 complex verbs separately, the lemmatiser obtained
70,96% and 70,52% respectively. Expressed in numbers the precision on
500 complex and simplex nouns was 78,45% and on complex and simplex verbs
79,59%. The quantitative achievement only gives an indication of the relative
precision of the grammars. Nevertheless, it did offer analysed data with which
the grammars were evaluated qualitatively. The study concludes with an overview
of how these results might be improved in the future.<br>Thesis (M.A. (African Languages))--North-West University, Potchefstroom Campus, 2006.
23
LEOGRANDE, MARCO. "High Speed and Flexible Network Processing." Doctoral thesis, Politecnico di Torino, 2014. http://hdl.handle.net/11583/2542314.
Full textAbstract:
Packet filter technologies are facing new issues every day, as we had to re-engineer our computer networks in order to accommodate many new use cases. For instance, low-level network protocols are growing in number: new solutions, arising in particular for the purpose of network virtualization (e.g., 802QinQ, VXLAN), are rapidly transforming the Ethernet frames. The middle layers of the protocol stack are facing a similar metamorphosis: examples include the widespread adoption of Virtual Private Networks, or the necessity to transport IPv6 traffic over IPv4 networks.
Packet filters are dramatically affected by those changes, as they become more complicated: it is important to be able to capture all the traffic we are interested in (e.g., web traffic), independently from the actual encapsulation used at lower layers.
For this reason, the scientific research should embrace these new issues by proposing improvements over the traditional technologies, with the goal of maintaining the standards of efficiency of flexibility that we are used to.
This dissertation addresses two specific issues:
1. How to preserve packet filter flexibility when specifying packet matching rules. We need a solution that allows a finer specification of matching rules, but that is also independent (if desired) on the specific encapsulation used at lower levels; moreover, the solution should support protocol definitions specified at run-time. Part I addresses the problem and describes in detail the proposed solution: NetPFL, a declarative language targeted to data-plane packet processing.
2. How to achieve efficiency when representing and combining multiple packet filters, even in case of bizarre and unusual network encapsulations. Part II outlines the issue and proposes two solutions: pFSA (described in Chapter 2) and its extension, xpFSA (delineated in Chapter 3).
24
Paulson, Jörgen, and Peter Huynh. "Menings- och dokumentklassficering för identifiering av meningar." Thesis, Högskolan i Skövde, Institutionen för informationsteknologi, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:his:diva-16373.
Full textAbstract:
Detta examensarbete undersöker hur väl tekniker inom meningsklassificering och dokumentklassificering fungerar för att välja ut meningar som innehåller de variabler som använts i experiment som beskrivs i medicinska dokument. För meningsklassificering används tillståndsmaskiner och nyckelord, för dokumentklassificering används linjär SVM och Random forest. De textegenskaper som har valts ut är LIX (läsbarhetsindex) och ordmängd (word count). Textegenskaperna hämtas från en färdig datamängd som skapades av Abrahamsson (T.B.D) från artiklar som samlas in för denna studie. Denna datamängd används sedan för dokumentklassificering. Det som undersöks hos dokumentklassificeringsteknikerna är förmågan att skilja dokument av typerna vetenskapliga artiklar med experiment, vetenskapliga artiklar utan experiment, vetenskapliga artiklar med metaanalyser och dokument som inte är vetenskapliga artiklar åt. Dessa dokument behandlas med meningsklassificering för att undersöka hur väl denna hittar meningar sominnehåller definitioner av variabler. Resultatet från experimentet tydde på att teknikerna för meningsklassificering inte var dugliga för detta ändamål på grund av låg precision. För dokumentklassificering var Randomforest bäst lämpad men hade problem att skilja olika typer av vetenskapliga artiklar åt.
25
Dolzhenko, Egor. "Transducer dynamics." Scholar Commons, 2007. https://scholarcommons.usf.edu/etd/217.
Full textAbstract:
Transducers are finite state automata with an output. In this thesis, we attempt to classify sequences that can be constructed by iteratively applying a transducer to a given word. We begin exploring this problem by considering sequences of words that can be produced by iterative application of a transducer to a given input word, i.e., identifying sequences of words of the form w, t(w), t²(w), . . . We call such sequences transducer recognizable. Also we introduce the notion of "recognition of a sequence in context", which captures the possibility of concatenating prefix and suffix words to each word in the sequence, so a given sequence of words becomes transducer recognizable. It turns out that all finite and periodic sequences of words of equal length are transducer recognizable. We also show how to construct a deterministic transducer with the least number of states recognizing a given sequence. To each transducer t we associate a two-dimensional language L²(t) consisting of blocks of symbols in the following way. The first row, w, of each block is in the input language of t, the second row is a word that t outputs on input w. Inductively, every subsequent row is a word outputted by the transducer when its preceding row is read as an input. We show a relationship of the entropy values of these two-dimensional languages to the entropy values of the one-dimensional languages that appear as input languages for finite state transducers.
26
Veselý, Lukáš. "Korektor diakritiky." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2007. http://www.nusl.cz/ntk/nusl-236816.
Full textAbstract:
The goal of this diploma work is the suggestion and the implementation of the application, which allows adding / removing of diacritics into / from Czech written text. Retrieval "trie" structure is described along with its relation to finite state automata. Further, algorithm for minimization of finite state automata is described and various methods for adding diacritics are discussed. In practical part the implementation in Java programming language with usage of object-oriented approach is given. Achieved results are evaluated and analysed in the conclusion.
27
Solár, Peter. "Syntaxí řízený překlad založený na hlubokých zásobníkových automatech." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2009. http://www.nusl.cz/ntk/nusl-236779.
Full textAbstract:
This thesis introduces syntax-directed translation based on deep pushdown automata. Necessary theoretical models are introduced in the theoretical part. The most important model, introduced in this thesis, is a deep pushdown transducer. The transducer should be used in syntax analysis, significant part of translation. Practical part consists of an implementation of simple-language interpret based on these models.
28
Angus, Simon Douglas Economics Australian School of Business UNSW. "Economic networks: communication, cooperation & complexity." Awarded by:University of New South Wales. Economics, 2007. http://handle.unsw.edu.au/1959.4/27005.
Full textAbstract:
This thesis is concerned with the analysis of economic network formation. There are three novel sections to this thesis (Chapters 5, 6 and 8). In the first, the non-cooperative communication network formation model of Bala and Goyal (2000) (BG) is re-assessed under conditions of no inertia. It is found that the Strict Nash circle (or wheel) structure is still the equilibrium outcome for n = 3 under no inertia. However, a counter-example for n = 4 shows that with no inertia infinite cycles are possible, and hence the system does not converge. In fact, cycles are found to quickly dominate outcomes for n > 4 and further numerical simulations of conditions approximating no inertia (probability of updating > 0.8 to 1) indicate that cycles account for a dramatic slowing of convergence times. These results, together with the experimental evidence of Falk and Kosfeld (2003) (FK) motivate the second contribution of this thesis. A novel artificial agent model is constructed that allows for a vast strategy space (including the Best Response) and permits agents to learn from each other as was indicated by the FK results. After calibration, this model replicates many of the FK experimental results and finds that an externality exploiting ratio of benefits and costs (rather than the difference) combined with a simple altruism score is a good proxy for the human objective function. Furthermore, the inequity aversion results of FK are found to arise as an emergent property of the system. The third novel section of this thesis turns to the nature of network formation in a trust-based context. A modified Iterated Prisoners' Dilemma (IPD) model is developed which enables agents to play an additional and costly network forming action. Initially, canonical analytical results are obtained despite this modification under uniform (non-local) interactions. However, as agent network decisions are 'turned on' persistent cooperation is observed. Furthermore, in contrast to the vast majority of non-local, or static network models in the literature, it is found that a-periodic, complex dynamics result for the system in the long-run. Subsequent analysis of this regime indicates that the network dynamics have fingerprints of self-organized criticality (SOC). Whilst evidence for SOC is found in many physical systems, such dynamics have been seldom, if ever, reported in the strategic interaction literature.
29
Joly, Jean-Luc. "Contributions à la génération aléatoire pour des classes d'automates finis." Thesis, Besançon, 2016. http://www.theses.fr/2016BESA2012/document.
Full textAbstract:
Le concept d’automate, central en théorie des langages, est l’outil d’appréhension naturel et efficace de nombreux problèmes concrets. L’usage intensif des automates finis dans un cadre algorithmique s ’illustre par de nombreux travaux de recherche. La correction et l’ évaluation sont les deux questions fondamentales de l’algorithmique. Une méthode classique d’ évaluation s’appuie sur la génération aléatoire contrôlée d’instances d’entrée. Les travaux d´écrits dans cette thèse s’inscrivent dans ce cadre et plus particulièrement dans le domaine de la génération aléatoire uniforme d’automates finis.L’exposé qui suit propose d’abord la construction d’un générateur aléatoire d’automates à pile déterministes, real time. Cette construction s’appuie sur la méthode symbolique. Des résultats théoriques et une étude expérimentale sont exposés.Un générateur aléatoire d’automates non-déterministes illustre ensuite la souplesse d’utilisation de la méthode de Monte-Carlo par Chaînes de Markov (MCMC) ainsi que la mise en œuvre de l’algorithme de Metropolis - Hastings pour l’ échantillonnage à isomorphisme près. Un résultat sur le temps de mélange est donné dans le cadre général .L’ échantillonnage par méthode MCMC pose le problème de l’évaluation du temps de mélange dans la chaîne. En s’inspirant de travaux antérieurs pour construire un générateur d’automates partiellement ordonnés, on montre comment différents outils statistiques permettent de s’attaquer à ce problème<br>The concept of automata, central to language theory, is the natural and efficient tool to apprehendvarious practical problems.The intensive use of finite automata in an algorithmic framework is illustrated by numerous researchworks.The correctness and the evaluation of performance are the two fundamental issues of algorithmics.A classic method to evaluate an algorithm is based on the controlled random generation of inputs.The work described in this thesis lies within this context and more specifically in the field of theuniform random generation of finite automata.The following presentation first proposes to design a deterministic, real time, pushdown automatagenerator. This design builds on the symbolic method. Theoretical results and an experimental studyare given.This design builds on the symbolic method. Theoretical results and an experimental study are given.A random generator of non deterministic automata then illustrates the flexibility of the Markov ChainMonte Carlo methods (MCMC) as well as the implementation of the Metropolis-Hastings algorithm tosample up to isomorphism. A result about the mixing time in the general framework is given.The MCMC sampling methods raise the problem of the mixing time in the chain. By drawing on worksalready completed to design a random generator of partially ordered automata, this work shows howvarious statistical tools can form a basis to address this issue
30
Pétréolle, Mathias. "Quelques développements combinatoires autour des groupes de Coxeter et des partitions d'entiers." Thesis, Lyon 1, 2015. http://www.theses.fr/2015LYO10237/document.
Full textAbstract:
Cette thèse porte sur l'étude de la combinatoire énumérative, plus particulièrement autour des partitions d'entiers et des groupes de Coxeter. Dans une première partie, à l'instar de Han et de Nekrasov-Okounkov, nous étudions des développements combinatoires des puissances de la fonction êta de Dedekind, en termes de longueurs d'équerres de partitions d'entiers. Notre approche, bijective, utilise notamment les identités de Macdonald en types affines (en particulier le type C), généralisant l'approche de Han en type A. Nous étendons ensuite avec de nouveaux paramètres ces développements, grâce à de nouvelles propriétés de la décomposition de Littlewood vis-à-vis des partitions et statistiques considérées. Cela nous permet de déduire des formules des équerres symplectiques, ainsi qu'une connexion avec la théorie des représentations. Dans une seconde partie, nous étudions les éléments cycliquement pleinement commutatifs dans les groupes de Coxeter introduits par Boothby et al., qui forment une sous famille des éléments pleinement commutatifs. Nous commençons par développer une construction, la clôture cylindrique, donnant un cadre théorique qui est aux éléments CPC ce que les empilements de Viennot sont aux éléments PC. Nous donnons une caractérisation des éléments CPC en terme de clôtures cylindriques pour n'importe quel système de Coxeter. Celle-ci nous permet de déterminer en termes d'expressions réduites les éléments CPC dans tous les groupes de Coxeter finis ou affines, et d'en déduire dans tous ces groupes l'énumération de ces éléments. En utilisant la théorie des automates finis, nous montrons aussi que la série génératrice de ces éléments est une fraction rationnelle<br>This thesis focuses on enumerative combinatorics, particularly on integer partitions and Coxeter groups. In the first part, like Han and Nekrasov-Okounkov, we study the combinatorial expansion of power of the Dedekind's eta function, in terms of hook lengths of integer partitions. Our approach, bijective, use the Macdonald identities in affine types, generalizing the study of Han in the case of type A. We extend with new parameters the expansions that we obtained through new properties of the Littlewood decomposition. This enables us to deduce symplectic hook length formulas and a connexion with representation theory. In the second part, we study the cyclically fully commutative elements in Coxeter groups, introduced by Boothby et al., which are a sub family of the fully commutative elements. We start by introducing a new construction, the cylindrical closure, which give a theoretical framework for the CPC elements analogous to the Viennot's heaps for fully commutative elements. We give a characterization of CPC elements in terms of cylindrical closures in any Coxeter groups. This allows to deduce a characterization of these elements in terms of reduced decompositions in all finite and affine Coxeter and their enumerations in those groups. By using the theory of finite state automata, we show that the generating function of these elements is always rational, in all Coxeter groups
31
Le, Pelleter Tugdual. "Méthode de discrétisation adaptée à une logique événementielle pour l'utra-faible consommation : application à la reconnaissance de signaux physiologiques." Thesis, Université Grenoble Alpes (ComUE), 2015. http://www.theses.fr/2015GREAT043/document.
Full textAbstract:
Les systèmes embarqués mobiles font partis intégrante de notre quotidien. Afin de les rendre plus adaptésaux usages, ils ont été miniaturisés et leur autonomie a été augmentée, parfois de façon très considérable.Toutefois, les propositions d’amélioration butent désormais sur les possibilités de la technologie des circuitsintégrés. Pour aller plus loin, il faut donc envisager de repenser la chaîne de traitement du signal afin deréduire la consommation de ces dispositifs. Cette thèse développe une approche originale pour exploiterefficacement l’échantillonnage par traversée de niveaux d’une part et, d’autre part, associe cet échantillonnageà une logique évènementielle afin de réduire drastiquement la consommation d’énergie des systèmesintégrés autonomes. Une méthode de discrétisation adaptée à une application de reconnaissance de signauxphysiologiques, utilisée comme exemple dans cette thèse, y est présentée. Un premier prototype en logiqueévènementielle (asynchrone) sur circuit FPGA a permis de valider cette stratégie et de démontrer les bénéficesde cet échantillonnage dédié en termes de réduction de l’activité par rapport à un échantillonnage uniforme.Un second prototype en logique asynchrone et conçu en technologie CMOS AMS 0.35 μm a permis de validerpar simulation électrique un gain extrêmement important sur la consommation électrique du dispositif<br>Our everyday life is highly dependent on mobile embedded systems. In order to make them suitable to differentapplications, they have underwent size reduction and lifetime extension. However, these improvementsare currently limited by the possibilities of the integrated circuits technologies. In order to push back theboundaries, it is necessary to reconsider the whole digital signal processing chain from scratch to sustain thepower consumption reduction in this kind of system. This work develops on the first hand a strategy thatsmartly uses the level-crossing sampling scheme and on the other combines this sampling method with eventlogicto highly reduce the power consumption in mobile embedded systems. A discretisation method adaptedto the recognition of physiological patterns application is described. A first event-logic (asynchronous) prototypeimplemented on FPGA proved the potential benefits that an adapted sampling scheme could offersto reduce activity compared to a uniform sampling scheme. Electrical simulations performed on a secondprototype, also designed in asynchronous logic, with CMOS AMS 0.35 μm technology, validated a high gainin power consumption
32
Beaucamps, Philippe. "Analyse de Programmes Malveillants par Abstraction de Comportements." Phd thesis, Institut National Polytechnique de Lorraine - INPL, 2011. http://tel.archives-ouvertes.fr/tel-00646395.
Full textAbstract:
L'analyse comportementale traditionnelle opère en général au niveau de l'implantation du comportement malveillant. Pourtant, elle s'intéresse surtout à l'identification d'un comportement donné, indépendamment de sa mise en œuvre technique, et elle se situe donc plus naturellement à un niveau fonctionnel. Dans cette thèse, nous définissons une forme d'analyse comportementale de programmes qui opère non pas sur les interactions élémentaires d'un programme avec le système mais sur la fonction que le programme réalise. Cette fonction est extraite des traces d'un programme, un procédé que nous appelons abstraction. Nous définissons de façon simple, intuitive et formelle les fonctionnalités de base à abstraire et les comportements à détecter, puis nous proposons un mécanisme d'abstraction applicable à un cadre d'analyse statique ou dynamique, avec des algorithmes pratiques à complexité raisonnable, enfin nous décrivons une technique d'analyse comportementale intégrant ce mécanisme d'abstraction. Notre méthode est particulièrement adaptée à l'analyse des programmes dans des langages de haut niveau ou dont le code source est connu, pour lesquels l'analyse statique est facilitée : les programmes conçus pour des machines virtuelles comme Java ou .NET, les scripts Web, les extensions de navigateurs, les composants off-the-shelf. Le formalisme d'analyse comportementale par abstraction que nous proposons repose sur la théorie de la réécriture de mots et de termes, les langages réguliers de mots et de termes et le model checking. Il permet d'identifier efficacement des fonctionnalités dans des traces et ainsi d'obtenir une représentation des traces à un niveau fonctionnel ; il définit les fonctionnalités et les comportements de façon naturelle, à l'aide de formules de logique temporelle, ce qui garantit leur simplicité et leur flexibilité et permet l'utilisation de techniques de model checking pour la détection de ces comportements ; il opère sur un ensemble quelconque de traces d'exécution ; il prend en compte le flux de données dans les traces d'exécution ; et il permet, sans perte d'efficacité, de tenir compte de l'incertitude dans l'identification des fonctionnalités. Nous validons nos résultats par un ensemble d'expériences, menées sur des codes malicieux existants, dont les traces sont obtenues soit par instrumentation binaire dynamique, soit par analyse statique.
33
Beaucamps, Philippe. "Analyse de programmes malveillants par abstraction de comportements." Electronic Thesis or Diss., Vandoeuvre-les-Nancy, INPL, 2011. http://www.theses.fr/2011INPL092N.
Full textAbstract:
L’analyse comportementale traditionnelle opère en général au niveau de l’implantation de comportements malveillants. Pourtant, elle s’intéresse surtout à l’identification de fonctionnalités données et elle se situe donc plus naturellement à un niveau fonctionnel. Dans cette thèse, nous définissons une forme d’analyse comportementale de programmes qui opère non pas sur les interactions élémentaires d’un programme avec le système mais sur la fonction que le programme réalise. Cette fonction est extraite des traces d’un pro- gramme, un procédé que nous appelons abstraction. Nous définissons de façon simple, intuitive et formelle les fonctionnalités de base à abstraire et les comportements à détecter, puis nous proposons un mécanisme d’abstraction applicable à un cadre d’analyse statique ou dynamique, avec des algorithmes pratiques à complexité raisonnable, enfin nous décrivons une technique d’analyse comportementale intégrant ce mécanisme d’abstraction. Notre méthode est particulièrement adaptée à l’analyse des programmes dans des langages de haut niveau ou dont le code source est connu, pour lesquels l’analyse statique est facilitée : applications mobiles en .NET ou Java, scripts, extensions de navigateurs, composants off-the-shelf.Le formalisme d’analyse comportementale par abstraction que nous proposons repose sur la théorie de la réécriture de mots et de termes, les langages réguliers de mots et de termes et le model checking. Il permet d’identifier efficacement des fonctionnalités dans des traces et ainsi d’obtenir une représentation des traces à un niveau fonctionnel; il définit les fonctionnalités et les comportements de façon naturelle, à l’aide de formules de logique temporelle, ce qui garantit leur simplicité et leur flexibilité et permet l’utilisation de techniques de model checking pour la détection de ces comportements ; il opère sur un ensemble quelconque de traces d’exécution ; il prend en compte le flux de données dans les traces d’exécution; et il permet, sans perte d’efficacité, de tenir compte de l’incertitude dans l’identification des fonctionnalités. Un cadre d’expérimentation a été mis en place dans un contexte d’analyse dynamique comme statique<br>Traditional behavior analysis usually operates at the implementation level of malicious behaviors. Yet, it is mostly concerned with the identification of given functionalities and is therefore more naturally defined at a functional level. In this thesis, we define a form of program behavior analysis which operates on the function realized by a program rather than on its elementary interactions with the system. This function is extracted from program traces, a process we call abstraction. We define in a simple, intuitive and formal way the basic functionalities to abstract and the behaviors to detect, then we propose an abstraction mechanism applicable both to a static or to a dynamic analysis setting, with practical algorithms of reasonable complexity, finally we describe a behavior analysis technique integrating this abstraction mechanism. Our method is particularly suited to the analysis of programs written in high level languages or with a known source code, for which static analysis is facilitated: mobile applications for .NET or Java, scripts, browser addons, off-the-shelf components.The formalism we propose for behavior analysis by abstraction relies on the theory of string and terms rewriting, word and tree languages and model checking. It allows an efficient identification of functionalities in traces and thus the construction of a represen- tation of traces at a functional level; it defines functionalities and behaviors in a natural way, using temporal logic formulas, which assure their simplicity and their flexibility and enables the use of model checking techniques for behavior detection; it operates on an unrestricted set of execution traces; it handles the data flow in execution traces; and it allows the consideration of uncertainty in the identification of functionalities, with no complexity overhead. Experiments have been conducted in a dynamic and static analysis setting
34
Ipate, F., Marian Gheorghe, and Raluca Lefticaru. "Fundamental results for learning deterministic extended finite state machines from queries." 2020. http://hdl.handle.net/10454/18046.
Full textAbstract:
Yes<br>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.<br>The full-text of this article will be released for public view at the end of the publisher embargo on 17 Sep 2021.
35
Wang, Yi-Hsiang, and 王奕翔. "Malware Analysis with 3-Valued Deterministic Finite Tree Automata." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/90167970473567852693.
Full textAbstract:
碩士<br>國立臺灣大學<br>資訊管理學研究所<br>100<br>There exist many security threats on the Internet, and the most notorious is malware.
Malware (malicious software) refers to programs that have malicious intention and per-
form some harmful actions. Typical malware includes viruses, worms, trojan horses, and
spyware. The rst line of defense to deter malware is malware detector. Each malware
detector has its own analysis method. The most basic and prevalent methods used in
commercial malware detectors are based on syntactic signature matching. It is widely
recognized that this detection mechanism cannot cope with advanced malware. Advanced
malware uses program obfuscation to alter program structures and therefore can evade
the detection easily. However, the semantics of a malware instance is usually preserved
after obfuscation. So, it is feasible to develop a malware detector that is based on pro-
gram semantics.
In this thesis, we propose a semantics-based approach to malware analysis. Observing
recently proposed methods for malware detection, we notice that string-based signatures
are still used widely. It is natural to extend from string to tree, which is more general and
can carry more semantics. Therefore, we use trees as signatures. Our malware detector
requires a set of malware instances and a set of benign programs. The semantics of each
input program is extracted and represented as a system call dependence graph. The
graph is then transformed into a tree. With the set of trees generated from malware and
benign programs, we use the method of grammatical inference to learn a 3-valued deter-
ministic nite tree automaton (3DFT). A 3DFT has three di erent nal states: accept,
reject, and unknown. If we take this 3DFT as the malware detector, it outputs three
di erent values. If an input program is a malware instance, the detector outputs true. If
an input program is a benign program, the detector outputs false. Otherwise, it outputs
unknown. According to our experiments, our detector exhibits very low false positives.
However, there is a tradeo that many programs are identi ed as unknown.
36
Nxumalo, Madoda. "An assessment of selected algorithms for generating failure deterministic finite automata." Diss., 2016. http://hdl.handle.net/2263/57216.
Full textAbstract:
A Failure Deterministic Finite Automaton (FDFA) o ers a deterministic
and a compact representation of an automaton that is used by various algorithms
to solve pattern matching problems e ciently. An abstract, concept
lattice based algorithm called the DFA - Homomorphic Algorithm (DHA) was
proposed to convert a deterministic nite automata (DFA) into an FDFA.
The abstract DHA has several nondeterministic choices. The DHA is tuned
into four decisive and specialized variants that may potentially remove the
optimal possible number of symbol transitions from the DFA while adding
failure transitions. The resulting specialized FDFA are: MaxIntent FDFA,
MinExtent FDFA, MaxIntent-MaxExtent FDFA and MaxArcReduncdancy
FDFA. Furthermore, two output based investigations are conducted whereby
two speci c types of DFA-to-FDFA algorithms are compared with DHA variants.
Firstly, the well-known Aho-Corasick algorithm, and its DFA is converted
into DHA FDFA variants. Empirical and comparative results show
that when heuristics for DHA variants are suitably chosen, the minimality
attained by the Aho-Corasick algorithm in its output FDFAs can be closely
approximated by DHA FDFAs. Secondly, testing DHA FDFAs in the general
case whereby random DFAs and language equivalent FDFAs are carefully
constructed. The random DFAs are converted into DHA FDFA types and
the random FDFAs are compared with DHA FDFAs. A published non concept
lattice based algorithm producing an FDFA called D2FA is also shown
to perform well in all experiments. In the general context DHA performed
well though not as good as the D2FA algorithm. As a by-product of general
case FDFA tests, an algorithm for generating random FDFAs and a language
equivalent DFAs was proposed.<br>Dissertation (MSc)--University of Pretoria, 2016.<br>tm2016<br>Computer Science<br>MSc<br>Unrestricted
37
Hsu, Jung-Hua, and 許榮華. "A Pattern Matching Algorithm Using Deterministic Finite Automata with Infixes Checking." Thesis, 2005. http://ndltd.ncl.edu.tw/handle/42273068520390912376.
Full textAbstract:
碩士<br>國立中興大學<br>資訊科學研究所<br>93<br>This thesis presents two string matching algorithms. The first algorithm
constructs a string matching finite automaton (called mc-DFA) for multi-class
of keystrings with infix checking and then applies this mc-DFA to process the
matching procedure for a given text in a single pass. This algorithm can output
the occurrences of multiple keystrings in a text concurrently. An algorithm
used to minimize mc-DFA is also given and studied. The second algorithm
applies the failure function to detect the occurrence of a prefix square when a
string is on-line inputted. Some properties concerning these two algorithms are
studied to show the time complexity of these two string matching algorithms.
38
Luo, Frank Jin Ye. "A diagnostic method for non-deterministic finite state machines." Thesis, 1996. http://spectrum.library.concordia.ca/4522/1/MM18413.pdf.
Full text
39
Leung, Samuel. "Pathway representation using finite state automata and comparison using the NCI thesaurus." Thesis, 2006. http://hdl.handle.net/1828/2200.
Full textAbstract:
Can one classify biochemical pathways based on their topology? What is the topology of a biochemical pathway? What are the fundamental principles underlying different biochemical pathways involved in similar functional areas? Will one be able to characterize pathway "motifs" similar to motifs in proteins - i.e. reoccurring patterns in pathways? This thesis describes an attempt to develop a quantitative framework for the general representation and comparison of biochemical pathways. This quantitative framework involves a mathematical model to represent biochemical pathways and a set of similarity criteria to compare these biochemical pathways. We anticipate that such a tool would allow biologists to answer important questions such as the ones mentioned above.
40
Lee, Gen-Cher, and 李政池. "Autonomous Dynamical Associative Memory with the Applications in Learning Finite State Automata." Thesis, 1999. http://ndltd.ncl.edu.tw/handle/27484301726063797537.
Full textAbstract:
碩士<br>國立臺灣大學<br>資訊工程學研究所<br>87<br>Learning the structure of finite state automata (FSA) from training strings is an interesting and important problem. [Giles, 1992] proposed an analog second-order single layer recurrent neural networks (SLRNN) and demonstrated how it is capable of extracting FSA. However, there is no concrete transition in the state space of such a model, and the abstract FSA is extracted by clustering analysis. We stand in a point of view enhancing the dynamic behavior of RNN, and propose two kinds of associative recurrent neural networks (ARNN). Moreover, We prove that both two ARNNs have the capability for simulating any FSA. We also derive the learning algorithm for ADAM. Afterward, applying the method for solving nonlinear equations that is the basis of ADAM, we derive a weight evolving method that converges to a weight that satisfied all input-output specification. This weight decision method can be used to speed up the convergent time of ARNN, and generally applied into both feed forward single layer networks and simple feedback networks.
41
Busse, Edgar [Verfasser]. "Finite-state genericity : on the diagonalization strength of finite automata / vorgelegt von Edgar Busse (geb. Damir Serikovich Muldagaliev)." 2006. http://d-nb.info/979601673/34.
Full text
42
Ransikarbum, Kasin Wysk Richard A. "A procedural validation for affordanced-based finite state automata in human-involved complex systems." 2009. http://etda.libraries.psu.edu/theses/approved/WorldWideIndex/ETD-3883/index.html.
Full text
43
"Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 Potsdam, Germany, september 14 - 16 ; revised papers." Universität Potsdam, 2008. http://opus.kobv.de/ubp/volltexte/2008/2381/.
Full textAbstract:
Proceedings with the revised papers of the FSMNLP (Finite-state Methods and Natural Language Processing) 2007 Workshop in Potsdam<br>Tagungsband mit den Beiträgen der FSMNLP (Finite-state Methods and Natural Language Processing) 2007 in Potsdam
44
"Modeling, Characterizing and Reconstructing Mesoscale Microstructural Evolution in Particulate Processing and Solid-State Sintering." Doctoral diss., 2018. http://hdl.handle.net/2286/R.I.49029.
Full textAbstract:
abstract: In material science, microstructure plays a key role in determining properties, which further determine utility of the material. However, effectively measuring microstructure evolution in real time remains an challenge. To date, a wide range of advanced experimental techniques have been developed and applied to characterize material microstructure and structural evolution on different length and time scales. Most of these methods can only resolve 2D structural features within a narrow range of length scale and for a single or a series of snapshots. The currently available 3D microstructure characterization techniques are usually destructive and require slicing and polishing the samples each time a picture is taken. Simulation methods, on the other hand, are cheap, sample-free and versatile without the special necessity of taking care of the physical limitations, such as extreme temperature or pressure, which are prominent
issues for experimental methods. Yet the majority of simulation methods are limited to specific circumstances, for example, first principle computation can only handle several thousands of atoms, molecular dynamics can only efficiently simulate a few seconds of evolution of a system with several millions particles, and finite element method can only be used in continuous medium, etc. Such limitations make these individual methods far from satisfaction to simulate macroscopic processes that a material sample undergoes up to experimental level accuracy. Therefore, it is highly desirable to develop a framework that integrate different simulation schemes from various scales
to model complicated microstructure evolution and corresponding properties. Guided by such an objective, we have made our efforts towards incorporating a collection of simulation methods, including finite element method (FEM), cellular automata (CA), kinetic Monte Carlo (kMC), stochastic reconstruction method, Discrete Element Method (DEM), etc, to generate an integrated computational material engineering platform (ICMEP), which could enable us to effectively model microstructure evolution and use the simulated microstructure to do subsequent performance analysis. In this thesis, we will introduce some cases of building coupled modeling schemes and present
the preliminary results in solid-state sintering. For example, we use coupled DEM and kinetic Monte Carlo method to simulate solid state sintering, and use coupled FEM and cellular automata method to model microstrucutre evolution during selective laser sintering of titanium alloy. Current results indicate that joining models from different length and time scales is fruitful in terms of understanding and describing microstructure evolution of a macroscopic physical process from various perspectives.<br>Dissertation/Thesis<br>Doctoral Dissertation Materials Science and Engineering 2018
45
Arthur, Kweku Kwakye. "Considerations towards the development of a forensic evidence management system." Diss., 2010. http://hdl.handle.net/2263/26567.
Full textAbstract:
The decentralized nature of the Internet forms its very foundation, yet it is this very nature that has opened networks and individual machines to a host of threats and attacks from malicious agents. Consequently, forensic specialists - tasked with the investigation of crimes commissioned through the use of computer systems, where evidence is digital in nature - are often unable to adequately reach convincing conclusions pertaining to their investigations. Some of the challenges within reliable forensic investigations include the lack of a global view of the investigation landscape and the complexity and obfuscated nature of the digital world. A perpetual challenge within the evidence analysis process is the reliability and integrity associated with digital evidence, particularly from disparate sources. Given the ease with which digital evidence (such as metadata) can be created, altered, or destroyed, the integrity attributed to digital evidence is of paramount importance. This dissertation focuses on the challenges relating to the integrity of digital evidence within reliable forensic investigations. These challenges are addressed through the proposal of a model for the construction of a Forensic Evidence Management System (FEMS) to preserve the integrity of digital evidence within forensic investigations. The Biba Integrity Model is utilized to maintain the integrity of digital evidence within the FEMS. Casey's Certainty Scale is then employed as the integrity classifcation scheme for assigning integrity labels to digital evidence within the system. The FEMS model consists of a client layer, a logic layer and a data layer, with eight system components distributed amongst these layers. In addition to describing the FEMS system components, a fnite state automata is utilized to describe the system component interactions. In so doing, we reason about the FEMS's behaviour and demonstrate how rules within the FEMS can be developed to recognize and pro le various cyber crimes. Furthermore, we design fundamental algorithms for processing of information by the FEMS's core system components; this provides further insight into the system component interdependencies and the input and output parameters for the system transitions and decision-points infuencing the value of inferences derived within the FEMS. Lastly, the completeness of the FEMS is assessed by comparing the constructs and operation of the FEMS against the published work of Brian D Carrier. This approach provides a mechanism for critically analyzing the FEMS model, to identify similarities or impactful considerations within the solution approach, and more importantly, to identify shortcomings within the model. Ultimately, the greatest value in the FEMS is in its ability to serve as a decision support or enhancement system for digital forensic investigators. Copyright<br>Dissertation (MSc)--University of Pretoria, 2010.<br>Computer Science<br>unrestricted
46
Arceri, Vincenzo. "Taming Strings in Dynamic Languages - An Abstract Interpretation-based Static Analysis Approach." Doctoral thesis, 2020. http://hdl.handle.net/11562/1016351.
Full textAbstract:
In the recent years, dynamic languages such as JavaScript, Python or PHP, have found several fields of applications, thanks to the multiple features provided, the agility of deploying software and the seeming facility of learning such languages. In particular, strings play a central role in dynamic languages, as they can be implicitly converted to other type values, used to access object properties or transformed at run-time into executable code. In particular, the possibility to dynamically generate code as strings transformation breaks the typical assumption in static program analysis that the code is an immutable object, indeed static. This happens because program’s essential data structures, such as the control-flow graph and the system of equation associated with the program to analyze, are themselves dynamically mutating objects. In a sentence: "You can’t check the code you don’t see". For all these reasons, dynamic languages still pone a big challenge for static program analysis, making it drastically hard and imprecise. The goal of this thesis is to tackle the problem of statically analyzing dynamic code by treating the code as any other data structure that can be statically analyzed, and by treating the static analyzer as any other function that can be recursively called. Since, in dynamically-generated code, the program code can be encoded as strings and then transformed into executable code, we first define a novel and suitable string abstraction, and the corresponding abstract semantics, able to both keep enough information to analyze string properties, in general, and keep enough information about the possible executable strings that may be converted to code. Such string abstraction will permits us to distill from a string abstract value the executable program expressed by it, allowing us to recursively call the static analyzer on the synthesized program. The final result of this thesis is an important first step towards a sound-by- construction abstract interpreter for real-world dynamic string manipulation languages, analyzing also string-to-code statements, that is the code that standard static analysis "can’t see".
47
Ang, Thomas. "Problems Related to Shortest Strings in Formal Languages." Thesis, 2010. http://hdl.handle.net/10012/5162.
Full textAbstract:
In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language.
In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid.
Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.
48
Ciddi, Sibel. "Zpracování turkických jazyků." Master's thesis, 2014. http://www.nusl.cz/ntk/nusl-323086.
Full textAbstract:
Title: Processing of Turkic Languages Author: Sibel Ciddi Department: Institute of Formal and Applied Linguistics, Faculty of Mathematics and Physics, Charles University in Prague Supervisor: RNDr. Daniel Zeman, Ph.D. Abstract: This thesis presents several methods for the morpholog- ical processing of Turkic languages, such as Turkish, which pose a specific set of challenges for natural language processing. In order to alleviate the problems with lack of large language resources, it makes the data sets used for morphological processing and expansion of lex- icons publicly available for further use by researchers. Data sparsity, caused by highly productive and agglutinative morphology in Turkish, imposes difficulties in processing of Turkish text, especially for meth- ods using purely statistical natural language processing. Therefore, we evaluated a publicly available rule-based morphological analyzer, TRmorph, based on finite state methods and technologies. In order to enhance the efficiency of this analyzer, we worked on expansion of lexicons, by employing heuristics-based methods for the extraction of named entities and multi-word expressions. Furthermore, as a prepro- cessing step, we introduced a dictionary-based recognition method for tokenization of multi-word expressions. This method complements...
49
Kumar, Pawan. "Memory Efficient Regular Expression Pattern Matching Architecture For Network Intrusion Detection Systems." Thesis, 2012. https://etd.iisc.ac.in/handle/2005/2321.
Full textAbstract:
The rampant growth of the Internet has been coupled with an equivalent growth in cyber crime over the Internet. With our increased reliance on the Internet for commerce, social networking, information acquisition, and information exchange, intruders have found financial, political, and military motives for their actions. Network Intrusion Detection Systems (NIDSs) intercept the traffic at an organization’s periphery and try to detect intrusion attempts. Signature-based NIDSs compare the packet to a signature database consisting of known attacks and malicious packet fingerprints. The signatures use regular expressions to model these intrusion activities.
This thesis presents a memory efficient pattern matching system for the class of regular expressions appearing frequently in the NIDS signatures. Proposed Cascaded Automata Architecture is based on two stage automata. The first stage recognizes the sub-strings and character classes present in the regular expression. The second stage consumes symbol generated by the first stage upon receiving input traffic symbols. The basic idea is to utilize the research done on string matching problem for regular expression pattern matching. We formally model the class of regular expressions mostly found in NIDS signatures. The challenges involved in using string matching algorithms for regular expression matching has been presented. We introduce length-bound transitions, counter-based states, and associated counter arrays in the second stage automata to address these challenges. The system uses length information along with counter arrays to keep track of overlapped sub-strings and character class based transition. We present efficient implementation techniques for counter arrays. The evaluation of the architecture on practical expressions from Snort rule set showed compression in number of states between 50% to 85%. Because of its smaller memory footprint, our solution is suitable for both software based implementations on network chips as well as FPGA based designs.
50
Kumar, Pawan. "Memory Efficient Regular Expression Pattern Matching Architecture For Network Intrusion Detection Systems." Thesis, 2012. http://etd.iisc.ernet.in/handle/2005/2321.
Full textAbstract:
The rampant growth of the Internet has been coupled with an equivalent growth in cyber crime over the Internet. With our increased reliance on the Internet for commerce, social networking, information acquisition, and information exchange, intruders have found financial, political, and military motives for their actions. Network Intrusion Detection Systems (NIDSs) intercept the traffic at an organization’s periphery and try to detect intrusion attempts. Signature-based NIDSs compare the packet to a signature database consisting of known attacks and malicious packet fingerprints. The signatures use regular expressions to model these intrusion activities.
This thesis presents a memory efficient pattern matching system for the class of regular expressions appearing frequently in the NIDS signatures. Proposed Cascaded Automata Architecture is based on two stage automata. The first stage recognizes the sub-strings and character classes present in the regular expression. The second stage consumes symbol generated by the first stage upon receiving input traffic symbols. The basic idea is to utilize the research done on string matching problem for regular expression pattern matching. We formally model the class of regular expressions mostly found in NIDS signatures. The challenges involved in using string matching algorithms for regular expression matching has been presented. We introduce length-bound transitions, counter-based states, and associated counter arrays in the second stage automata to address these challenges. The system uses length information along with counter arrays to keep track of overlapped sub-strings and character class based transition. We present efficient implementation techniques for counter arrays. The evaluation of the architecture on practical expressions from Snort rule set showed compression in number of states between 50% to 85%. Because of its smaller memory footprint, our solution is suitable for both software based implementations on network chips as well as FPGA based designs.