To see the other types of publications on this topic, follow the link: Finite state automata.
Dissertations / Theses on the topic '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 '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
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.
3
Khemuka, Atul Ravi. "Workflow Modeling Using Finite Automata." [Tampa, Fla.] : University of South Florida, 2003. http://purl.fcla.edu/fcla/etd/SFE0000172.
Full text
4
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
5
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.
6
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.
7
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
8
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.
9
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
10
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.
11
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.
12
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).
13
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>
14
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.
15
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.
16
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.
17
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).
18
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.
19
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.
20
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.
21
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.
22
Coetser, Rayner Johannes Lodewikus. "Finite state automaton construction through regular expression hashing." Diss., University of Pretoria, 2009. http://hdl.handle.net/2263/27536.
Full textAbstract:
In this study, the regular expressions forming abstract states in Brzozowski’s algorithm are not remapped to sequential state transition table addresses as would be the case in the classical approach, but are hashed to integers. Two regular expressions that are hashed to the same hash code are assigned the same integer address in the state transition table, reducing the number of states in the automaton. This reduction does not necessarily lead to the construction of a minimal automaton: no restrictions are placed on the hash function hashing two regular expressions to the same code. Depending on the quality of the hash function, a super-automaton, previously referred to as an approximate automaton, or an exact automaton can be constructed. When two regular expressions are hashed to the same state, and they do not represent the same regular language, a super-automaton is constructed. A super-automaton accepts the regular language of the input regular expression, in addition to some extra strings. If the hash function is bad, many regular expressions that do not represent the same regular language will be hashed together, resulting in a smaller automaton that accepts extra strings. In the ideal case, two regular expressions will only be hashed together when they represent the same regular language. In this case, an exact minimal automaton will be constructed. It is shown that, using the hashing approach, an exact or super-automaton is always constructed. Another outcome of the hashing approach is that a non-deterministic automaton may be constructed. A new version of the hashing version of Brzozowski’s algorithm is put forward which constructs a deterministic automaton. A method is also put forward for measuring the difference between an exact and a super-automaton: this takes the form of the k-equivalence measure: the k-equivalence measure measures the number of characters up to which the strings of two regular expressions are equal. The better the hash function, the higher the value of k, up to the point where the hash function results in regular expressions being hashed together if and only if they have the same regular language. Using the k-equivalence measure, eight generated hash functions and one hand coded hash function are evaluated for a large number of short regular expressions, which are generated using G¨odel numbers. The k-equivalence concept is extended to the average k-equivalence value in order to evaluate the hash functions for longer regular expressions. The hand coded hash function is found to produce good results. Copyright<br>Dissertation (MEng)--University of Pretoria, 2009.<br>Computer Science<br>unrestricted
23
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
24
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
25
Maťas, Marek. "Metody analýzy stavových automatů pro vestavné aplikace." Master's thesis, Vysoké učení technické v Brně. Fakulta elektrotechniky a komunikačních technologií, 2011. http://www.nusl.cz/ntk/nusl-218940.
Full textAbstract:
This master’s thesis deals with analysis of state machines for embedded applications. The issue of finite-state machine is described theoretically. The document also contains a proposal for funding for modeling finite state machines in Matlab/Simulink. It is designed data representation of finite automaton. Over this data representation algorithm of minimization is applied. Finally, the algorithm is implemented to generate code in C language.
26
Derderian, Karnig Agop. "Automated test sequence generation for finite state machines using genetic algorithms." Thesis, Brunel University, 2006. http://bura.brunel.ac.uk/handle/2438/3062.
Full textAbstract:
Testing software implementations, formally specified using finite state automata (FSA) has been of interest. Such systems include communication protocols and control sections of safety critical systems. There is extensive literature regarding how to formally validate an FSM based specification, but testing that an implementation conforms to the specification is still an open problem. Two aspects of FSA based testing, both NP-hard problems, are discussed in this thesis and then combined. These are the generation of state verification sequences (UIOs) and the generation of sequences of conditional transitions that are easy to trigger. In order to facilitate test sequence generation a novel representation of the transition conditions and a number of fitness function algorithms are defined. An empirical study of the effectiveness on real FSA based systems and example FSAs provides some interesting positive results. The use of genetic algorithms (GAs) makes these problems scalable for large FSAs. The experiments used a software tool that was developed in Java.
27
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.
28
Müller, Frank Henrik. "A finite-state approach to shallow parsing and grammatical functions annotation of German." [S.l. : s.n.], 2005.
Find full text
29
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.
30
Risler, Max. "Behavior control for single and multiple autonomous agents based on hierarchical finite state machines /." Düsseldorf : VDI-Verl, 2009. http://d-nb.info/998464244/04.
Full text
31
Seward, Alexander. "Efficient Methods for Automatic Speech Recognition." Doctoral thesis, KTH, Tal, musik och hörsel, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3675.
Full textAbstract:
This thesis presents work in the area of automatic speech recognition (ASR). The thesis focuses on methods for increasing the efficiency of speech recognition systems and on techniques for efficient representation of different types of knowledge in the decoding process. In this work, several decoding algorithms and recognition systems have been developed, aimed at various recognition tasks. The thesis presents the KTH large vocabulary speech recognition system. The system was developed for online (live) recognition with large vocabularies and complex language models. The system utilizes weighted transducer theory for efficient representation of different knowledge sources, with the purpose of optimizing the recognition process. A search algorithm for efficient processing of hidden Markov models (HMMs) is presented. The algorithm is an alternative to the classical Viterbi algorithm for fast computation of shortest paths in HMMs. It is part of a larger decoding strategy aimed at reducing the overall computational complexity in ASR. In this approach, all HMM computations are completely decoupled from the rest of the decoding process. This enables the use of larger vocabularies and more complex language models without an increase of HMM-related computations. Ace is another speech recognition system developed within this work. It is a platform aimed at facilitating the development of speech recognizers and new decoding methods. A real-time system for low-latency online speech transcription is also presented. The system was developed within a project with the goal of improving the possibilities for hard-of-hearing people to use conventional telephony by providing speech-synchronized multimodal feedback. This work addresses several additional requirements implied by this special recognition task.<br>QC 20100811
32
Lundberg, Edvin. "Collaboration in Multi-agent Games : Synthesis of Finite-state Strategies in Games of Imperfect Information." Thesis, KTH, Skolan för datavetenskap och kommunikation (CSC), 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-209917.
Full textAbstract:
We study games where a team of agents needs to collaborate against an adversary to achieve a common goal. The agents make their moves simultaneously, and they have different perceptions about the system state after each move, due to different sensing capabilities. Each agent can only act based on its own experiences, since no communication is assumed during the game. However, before the game begins, the agents can agree on some strategy. A strategy is winning if it guarantees that the agents achieve their goal regardless of how the opponent acts. Identifying a winning strategy, or determining that none exists, is known as the strategy synthesis problem. In this thesis, we only consider a simple objective where the agents must force the game into a given state. Much of the literature is focused on strategies that either rely on that the agents (a) can remember everything that they have perceived or (b) can only remember the last thing that they have perceived. The strategy synthesis problem is (in the general case) undecidable in (a) and has exponential running time in (b). We are interested in the middle, where agents can have finite memory. Specifically, they should be able to keep a finite-state machine, which they update when they make new observations. In our case, the internal state of each agent represents its knowledge about the state of affairs. In other words, an agent is able to update its knowledge, and act based on it. We propose an algorithm for constructing the finite-state machine for each agent, and assigning actions to the internal states before the game begins. Not every winning strategy can be found by the algorithm, but we are convinced that the ones found are valid ones. An important building block for the algorithm is the knowledge-based subset construction (KBSC) used in the literature, which we generalise to games with multiple agents. With our construction, the game can be reduced to another game, still with uncertain state information, but with less or equal uncertainty. The construction can be applied arbitrarily many times, but it appears as if it stabilises (so that no new knowledge is gained) after only a few steps. We discuss this and other interesting properties of our algorithm in the final chapters of this thesis.<br>Vi studerar spel där ett lag agenter behöver samarbeta mot en motståndare för att uppnå ett mål. Agenterna agerar samtidigt, och vid varje steg av spelet så har de olika uppfattning om spelets tillstånd. De antas inte kunna kommunicera under spelets gång, så agenterna kan bara agera utifrån sina egna erfarenheter. Innan spelet börjar kan agenterna dock komma överrens om en strategi. En sådan strategi är vinnande om den garanterar att agenterna når sitt mål oavsett hur motståndaren beter sig. Att hitta en vinnande strategi är känt som syntesproblemet. I den här avhandlingen behandlar vi endast ett enkelt mål där agenterna måste tvinga in spelet i ett givet tillstånd. Mycket av litteraturen handlar om strategier där agenterna antingen antas (a) kunna minnas allt som de upplevt eller (b) bara kunna minnas det senaste de upplevt. Syntesproblemet är (i det generella fallet) oavgörbart i (a) och tar exponentiell tid i (b). Vi är intressede av fallet där agenter kan ha ändligt minne. De ska kunna ha en ändlig automat, som de kan uppdatera när de får nya observationer. I vårt fall så representerar det interna tillståndet agentens kunskap om spelets tillstånd. En agent kan då uppdatera sin kunskap och agera utifrån den. Vi föreslår en algoritm som konstruerar en ändlig automat åt varje agent, samt instruktioner för vad agenten ska göra i varje internt tillstånd. Varje vinnande strategi kan inte hittas av algoritmen, men vi är övertygade om att de som hittas är giltiga. En viktig byggsten är den kunskapsbaserade delmängskonstruktionen (KBSC), som vi generaliserar till spel med flera agenter. Med vår konstruktion kan spelet reduceras till ett annat spel som har mindre eller lika mycket osäkerhet. Detta kan göras godtyckligt många gånger, men det verkar som om att ingen ny kunskap tillkommer efter bara några gånger. Vi diskuterar detta vidare tillsammans med andra intressanta egenskaper hos algoritmen i de sista kapitlen i avhandlingen.
33
Nojoumian, Peyman. "Towards the Development of an Automatic Diacritizer for the Persian Orthography based on the Xerox Finite State Transducer." Thèse, Université d'Ottawa / University of Ottawa, 2011. http://hdl.handle.net/10393/20158.
Full textAbstract:
Due to the lack of short vowels or diacritics in Persian orthography, many Natural Language Processing applications for this language, including information retrieval, machine translation, text-to-speech, and automatic speech recognition systems need to disambiguate the input first, in order to be able to do further processing. In machine translation, for example, the whole text should be correctly diacritized first so that the correct words, parts of speech and meanings are matched and retrieved from the lexicon. This is primarily because of Persian’s ambiguous orthography. In fact, the core engine of any Persian language processor should utilize a diacritizer and a lexical disambiguator. This dissertation describes the design and implementation of an automatic diacritizer for Persian based on the state-of-the-art Finite State Transducer technology developed at Xerox by Beesley & Karttunen (2003). The result of morphological analysis and generation on a test corpus is shown, including the insertion of diacritics.
This study will also look at issues that are raised by phonological and semantic ambiguities as a result of short vowels in Persian being absent in the writing system. It suggests a hybrid model (rule-based & inductive) that is inspired by psycholinguistic experiments on the human mental lexicon for the disambiguation of heterophonic homographs in Persian using frequency and collocation information. A syntactic parser can be developed based on the proposed model to discover Ezafe (the linking short vowel /e/ within a noun phrase) or disambiguate homographs, but its implementation is left for future work.
34
Angrand, Pierre-Yves. "Contributions à l'étude de la dérivation des expressions rationnelles et à l'étude des systèmes de numération abstraits." Phd thesis, Télécom ParisTech, 2012. http://pastel.archives-ouvertes.fr/pastel-00850633.
Full textAbstract:
Les travaux de cette thèse s'inscrivent dans la théorie des automates et des langages formels. ils peuvent se diviser en deux parties qui donnent également deux visions différentes de manipuler les langages dans la théorie des automates. La première partie s'intéresse à la notion de dérivation des expressions qui permet de faire passer le formalisme des quotients de langages au niveau des expressions rationnelles. en particulier cette thèse étudie les termes dérivés cassés d'une expression rationnelle. ces termes dérivés cassés permettent, sous certaines circonstances, et à l'aide d'autres opérations, une réversibilité de la transformation d'un automate en une expression rationnelle. Dans la seconde partie, la théorie des automates est utilisée pour traiter des problèmes sur les systèmes de numération. les systèmes de numération représentent des nombres par des mots. il est possible d'utiliser des automates et des transducteurs afin d'être capable de 'compter' sur un langage rationnel représentant les entiers. plus précisément ces automates sont étudiés pour le cas des systèmes de numération abstraits qui associent à chaque entier un mot d'un langage rationnel, ordonné par l'ordre radiciel. dans un tel système, la fonction qui permet de calculer le mot suivant est une fonction co-séquentielle par morceaux, c'est-à-dire qu'il suffit de lire deux fois le mot d'entrée de la droite vers la gauche pour qu'une machine calcule son image.
35
Wallerö, Emma. "Automatic morphological analysis of L-verbs in Palula." Thesis, Stockholms universitet, Institutionen för lingvistik, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:su:diva-182528.
Full textAbstract:
This study is exploring the possibilities of automatic morphological analysis of L-verbs in the Palula language by the help from Finite-state technology and two-level morphology along with supervised machine learning. The type of machine learning used are neural Sequence to Sequence models. A morphological transducer is made with the Helsinki Finite-State Transducer Technology, HFST, toolkit covering the L-verbs of the Palula Language. Several Sequence to Sequence models are trained on sets of L-verbs along with morphological tagging annotation. One model is trained with a small amount of manually annotated data and four models are trained with different amounts of training examples generated by the Finite-State Transducer. The efficiency and accuracy of these methods are investigated. The Sequence to Sequence model trained on solely manually annotated data did not perform as well as the other models. A Sequence to Sequence model trained with training examples generated by the transducer performed the best recall, accuracy and F1-score, while the Finite-State Transducer performed the best precision score.<br>Denna studie undersöker möjligheterna för en automatisk morfologisk analys av L-verb i språket Palula med hjälp av finit tillståndsteknik och två-nivå-morfologi samt övervakad maskininlärning. Den typ av maskininlärning som används i studien är neurala Sekvens till Sekvens-modeller. En morfologisk transduktor är skapad med verktyget Helsinki Finite-State Transducer Technology, HFST, som täcker L-verben i Palula. Flera Sekvens till Sekvens-modeller tränas på set av L-verb med morfologisk taggningsannotation. En modell tränas på ett litet set av manuellt annoterade data och fyra modeller tränas på olika mängder träningsdata som genererats av den finita tillstånds-transduktorn. Effektiviteten och noggrannheten för dessa modeller undersöks. Sekvens till Sekvens-modellen som tränats med bara manuellt annoterade data presterade inte lika bra som de andra modellerna i studien. En Sekvens till Sekvens-modell tränad med träningsdata bestående av genereringar producerade av transduktorn gav bästa svarsfrekvens, noggrannhet och F1-poäng, medan den finita tillstånds-transduktorn gav bästa precision.
36
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
37
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
38
Saers, Markus. "Translation as Linear Transduction : Models and Algorithms for Efficient Learning in Statistical Machine Translation." Doctoral thesis, Uppsala universitet, Institutionen för lingvistik och filologi, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-135704.
Full textAbstract:
Automatic translation has seen tremendous progress in recent years, mainly thanks to statistical methods applied to large parallel corpora. Transductions represent a principled approach to modeling translation, but existing transduction classes are either not expressive enough to capture structural regularities between natural languages or too complex to support efficient statistical induction on a large scale. A common approach is to severely prune search over a relatively unrestricted space of transduction grammars. These restrictions are often applied at different stages in a pipeline, with the obvious drawback of committing to irrevocable decisions that should not have been made. In this thesis we will instead restrict the space of transduction grammars to a space that is less expressive, but can be efficiently searched. First, the class of linear transductions is defined and characterized. They are generated by linear transduction grammars, which represent the natural bilingual case of linear grammars, as well as the natural linear case of inversion transduction grammars (and higher order syntax-directed transduction grammars). They are recognized by zipper finite-state transducers, which are equivalent to finite-state automata with four tapes. By allowing this extra dimensionality, linear transductions can represent alignments that finite-state transductions cannot, and by keeping the mechanism free of auxiliary storage, they become much more efficient than inversion transductions. Secondly, we present an algorithm for parsing with linear transduction grammars that allows pruning. The pruning scheme imposes no restrictions a priori, but guides the search to potentially interesting parts of the search space in an informed and dynamic way. Being able to parse efficiently allows learning of stochastic linear transduction grammars through expectation maximization. All the above work would be for naught if linear transductions were too poor a reflection of the actual transduction between natural languages. We test this empirically by building systems based on the alignments imposed by the learned grammars. The conclusion is that stochastic linear inversion transduction grammars learned from observed data stand up well to the state of the art.
39
Costa, Ednardo Luiz da. "A formaÃÃo de palavras no portuguÃs do brasil: um estudo dos sufixos -eir e -ud numa abordagem computacional." Universidade Federal do CearÃ, 2010. http://www.teses.ufc.br/tde_busca/arquivo.php?codArquivo=4963.
Full textAbstract:
CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior<br>Este estudo investiga a formaÃÃo de palavras na LÃngua Portuguesa contemporÃnea do Brasil. Dentro da perspectiva da morfologia derivacional, esta pesquisa teve por objetivo desenvolver um estudo das regras de formaÃÃo de palavras atravÃs dos sufixos -eir e -ud na LÃngua Portuguesa. Essas regras foram desenvolvidas para melhor investigar a produtividade do processo morfolÃgico da sufixaÃÃo sob a perspectiva da Teoria Gerativa, centramos nosso trabalho principalmente nas idÃias sobre a formaÃÃo de palavras desenvolvidas por Anderson (1992) e Rocha (1998). Realizamos uma pesquisa empÃrica para podermos alcanÃar os objetivos de nosso trabalho. Compilamos um corpus contendo exemplos dos seguintes corpora brasileiros: NILC- SÃo Carlos, ConDivport e Chave. AlÃm dessas fontes, coletamos tambÃm diversos textos de jornais e revistas on-line, de forma assistemÃtica, com o intuito de melhor descrever o fenÃmeno da derivaÃÃo sufixal no portuguÃs brasileiro contemporÃneo. O nosso trabalho tambÃm possui uma implementaÃÃo computacional, uma vez que desenvolvemos a construÃÃo de um analisador automÃtico de palavras derivadas. Utilizamos para isso o FSA Utilities (que atualmente à um dos mais usados pacotes de ferramentas computacionais para construÃÃo e manipulaÃÃo de autÃmatos e transdutores de estados finitos) na modelaÃÃo computacional deste fragmento da morfologia flexional e derivacional do portuguÃs.
40
Gabriel, Naveen. "Automatic Speech Recognition in Somali." Thesis, Linköpings universitet, Statistik och maskininlärning, 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-166216.
Full textAbstract:
The field of speech recognition during the last decade has left the research stage and found its way into the public market, and today, speech recognition software is ubiquitous around us. An automatic speech recognizer understands human speech and represents it as text. Most of the current speech recognition software employs variants of deep neural networks. Before the deep learning era, the hybrid of hidden Markov model and Gaussian mixture model (HMM-GMM) was a popular statistical model to solve speech recognition. In this thesis, automatic speech recognition using HMM-GMM was trained on Somali data which consisted of voice recording and its transcription. HMM-GMM is a hybrid system in which the framework is composed of an acoustic model and a language model. The acoustic model represents the time-variant aspect of the speech signal, and the language model determines how probable is the observed sequence of words. This thesis begins with background about speech recognition. Literature survey covers some of the work that has been done in this field. This thesis evaluates how different language models and discounting methods affect the performance of speech recognition systems. Also, log scores were calculated for the top 5 predicted sentences and confidence measures of pre-dicted sentences. The model was trained on 4.5 hrs of voiced data and its corresponding transcription. It was evaluated on 3 mins of testing data. The performance of the trained model on the test set was good, given that the data was devoid of any background noise and lack of variability. The performance of the model is measured using word error rate(WER) and sentence error rate (SER). The performance of the implemented model is also compared with the results of other research work. This thesis also discusses why log and confidence score of the sentence might not be a good way to measure the performance of the resulting model. It also discusses the shortcoming of the HMM-GMM model, how the existing model can be improved, and different alternatives to solve the problem.
41
Angrand, Pierre-Yves. "Contributions à l'étude de la dérivation des expressions rationnelles et à l'étude des systèmes de numération abstraits." Electronic Thesis or Diss., Paris, ENST, 2012. http://www.theses.fr/2012ENST0009.
Full textAbstract:
Les travaux de cette thèse s'inscrivent dans la théorie des automates et des langages formels. ils peuvent se diviser en deux parties qui donnent également deux visions différentes de manipuler les langages dans la théorie des automates. La première partie s'intéresse à la notion de dérivation des expressions qui permet de faire passer le formalisme des quotients de langages au niveau des expressions rationnelles. en particulier cette thèse étudie les termes dérivés cassés d'une expression rationnelle. ces termes dérivés cassés permettent, sous certaines circonstances, et à l'aide d'autres opérations, une réversibilité de la transformation d'un automate en une expression rationnelle. Dans la seconde partie, la théorie des automates est utilisée pour traiter des problèmes sur les systèmes de numération. les systèmes de numération représentent des nombres par des mots. il est possible d'utiliser des automates et des transducteurs afin d'être capable de 'compter' sur un langage rationnel représentant les entiers. plus précisément ces automates sont étudiés pour le cas des systèmes de numération abstraits qui associent à chaque entier un mot d'un langage rationnel, ordonné par l'ordre radiciel. dans un tel système, la fonction qui permet de calculer le mot suivant est une fonction co-séquentielle par morceaux, c'est-à-dire qu'il suffit de lire deux fois le mot d'entrée de la droite vers la gauche pour qu'une machine calcule son image<br>The works in this thesis lies in the automata and formal languages theory. in the first part, the notion of derivation of rational expressions is studied. more precisely the broken derived terms of a rational expressions. Theses broken derived terms allow, under certain circumstances, with some other operations on automata, to have the reversibility of the transformation of an automaton into a rational expression. In the second part, automata and tranducers allow to 'count' on a numeration system, where integers are represented by words on a rational language. more precisely, this part adress the problem of counting in an abstract numeration systems, which maps to any word of a rational language, ordored by radix order, the integer corresponding to the order of the word. in such a numeration system, the function which computes the successor of a word is a piecewise co-sequential function: it can be realised by a machine which reads the input two times to give the output
42
Hannemann, Mirko. "Rozpoznávácí sítě založené na konečných stavových převodnících pro dopředné a zpětné dekódování v rozpoznávání řeči." Doctoral thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2016. http://www.nusl.cz/ntk/nusl-412550.
Full textAbstract:
Pomocí matematického formalismu váhovaných konečných stavových převodníků (weighted finite state transducers WFST) může být formulována řada úloh včetně automatického rozpoznávání řeči (automatic speech recognition ASR). Dnešní ASR systémy široce využívají složených pravděpodobnostních modelů nazývaných dekódovací grafy nebo rozpoznávací sítě. Ty jsou z jednotlivých komponent konstruovány pomocí WFST operací, např. kompozice. Každá komponenta je zde zdrojem znalostí a omezuje vyhledávání nejlepší cesty ve složeném grafu v operaci zvané dekódování. Využití koherentního teoretického rámce garantuje, že výsledná struktura bude optimální podle definovaného kritéria. WFST mohou být v rámci daného polookruhu (semi-ring) optimalizovány pomocí determinizace a minimalizace. Aplikací těchto algoritmů získáme optimální strukturu pro prohledávání, optimální distribuce vah je pak získána aplikací "weight pushing" algoritmu. Cílem této práce je zdokonalit postupy a algoritmy pro konstrukci optimálních rozpoznávacích sítí. Zavádíme alternativní weight pushing algoritmus, který je vhodný pro důležitou třídu modelů -- převodníky jazykového modelu (language model transducers) a obecně pro všechny cyklické WFST a WFST se záložními (back-off) přechody. Představujeme také způsob konstrukce rozpoznávací sítě vhodné pro dekódování zpětně v čase, které prokazatelně produkuje ty samé pravděpodobnosti jako dopředná síť. K tomuto účelu jsme vyvinuli algoritmus pro exaktní reverzi back-off jazykových modelů a převodníků, které je reprezentují. Pomocí zpětných rozpoznávacích sítí optimalizujeme dekódování: ve statickém dekodéru je využíváme pro dvoustupňové dekódování (dopředné a zpětné vyhledávání). Tento přístup --- "sledovací" dekódování (tracked decoding) --- umožnuje zahrnout výsledky vyhledávání z prvního stupně do druhého stupně tak, že se sledují hypotézy obsažené v rozpoznávacím grafu (lattice) prvního stupně. Výsledkem je podstatné zrychlení dekódování, protože tato technika umožnuje prohledávat s variabilním prohledávacím paprskem (search beam) -- ten je povětšinou mnohem užší než u základního přístupu. Ukazujeme rovněž, že uvedenou techniku je možné využít v dynamickém dekodéru tím, že postupně zjemňujeme rozpoznávání. To navíc vede i k částečné paralelizaci dekódování.
43
Svoboda, Ondřej. "Poloautomatická diagnostika síťových protokolů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2018. http://www.nusl.cz/ntk/nusl-385884.
Full textAbstract:
This thesis is about semiautomatic network protocol diagnostics and creating protocol description from eavesdropped communication. Several network eavesdropping techniques and some common programs for network analysis are introduced. Well-known network protocols are described, with focus on their communication messages. Some already existing methods for creating models from examples are mentioned and their characteristics defined. Next we design architecture of developed tool and some methods, that create protocol description. After that we explain implementation of this tool and finally the tool is tested and experimented with.
44
Wang, Yihan. "Automatic Speech Recognition Model for Swedish using Kaldi." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-285538.
Full textAbstract:
With the development of intelligent era, speech recognition has been a hottopic. Although many automatic speech recognition(ASR) tools have beenput into the market, a considerable number of them do not support Swedishbecause of its small number. In this project, a Swedish ASR model basedon Hidden Markov Model and Gaussian Mixture Models is established usingKaldi which aims to help ICA Banken complete the classification of aftersalesvoice calls. A variety of model patterns have been explored, whichhave different phoneme combination methods and eigenvalue extraction andprocessing methods. Word Error Rate and Real Time Factor are selectedas evaluation criteria to compare the recognition accuracy and speed ofthe models. As far as large vocabulary continuous speech recognition isconcerned, triphone is much better than monophone. Adding feature transformationwill further improve the speed of accuracy. The combination oflinear discriminant analysis, maximum likelihood linear transformand speakeradaptive training obtains the best performance in this implementation. Fordifferent feature extraction methods, mel-frequency cepstral coefficient ismore conducive to obtain higher accuracy, while perceptual linear predictivetends to improve the overall speed.<br>Det existerar flera lösningar för automatisk transkribering på marknaden, menen stor del av dem stödjer inte svenska på grund utav det relativt få antalettalare. I det här projektet så skapades automatisk transkribering för svenskamed Hidden Markov models och Gaussian mixture models genom att användaKaldi. Detta för att kunna möjliggöra för ICABanken att klassificera samtal tillsin kundtjänst. En mängd av modellvariationer med olika fonemkombinationsmetoder,egenvärdesberäkning och databearbetningsmetoder har utforskats.Word error rate och real time factor är valda som utvärderingskriterier föratt jämföra precisionen och hastigheten mellan modellerna. När det kommertill kontinuerlig transkribering för ett stort ordförråd så resulterar triphonei mycket bättre prestanda än monophone. Med hjälp utav transformationerså förbättras både precisionen och hastigheten. Kombinationen av lineardiscriminatn analysis, maximum likelihood linear transformering och speakeradaptive träning resulterar i den bästa prestandan i denna implementation.För olika egenskapsextraktioner så bidrar mel-frequency cepstral koefficiententill en bättre precision medan perceptual linear predictive tenderar att ökahastigheten.
45
Mai, Daniel Xuan Hien. "Modèles et outils de conception de techniques d'interaction pour applications d'apprentissage en vidéo panoramique." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASG047.
Full textAbstract:
Cette thèse explore le développement de modèles et d'outils pour la conception de techniques d'interaction dans les applications d'apprentissage utilisant des vidéos panoramiques. Elle aborde les défis uniques posés par l'intégration de la réalité virtuelle et des vidéos panoramiques dans les environnements éducatifs, soulignant la nécessité de techniques d'interaction innovantes qui répondent aux objectifs éducatifs des formateurs. Au travers d'une revue exhaustive de l'état de l'art et des études empiriques, ce travail propose une nouvelle architecture pour les environnements virtuels d'apprentissage humain, ainsi qu'un outil auteur immersif qui simplifie la création de contenu interactif en limitant les exigences techniques pour les formateurs. Cette recherche contribue à la fois à la théorie de l'interaction homme-machine et à la pratique de la création de contenu éducatif immersif, offrant des perspectives pour des applications futures dans des domaines variés<br>This doctoral thesis investigates the development of models and tools for designing interaction techniques in learning applications utilizing 360-degree videos. It addresses the unique challenges of integrating virtual reality and 360-degree videos into educational settings, highlighting the need for innovative interaction techniques that meet the educational goals of trainers. Through a comprehensive literature review and empirical studies, this work proposes a new architecture for virtual human learning environments, as well as an immersive authoring tool that facilitates the creation of interactive and engaging content in limiting technical requirements for trainers. This research contributes to both the theory of human-computer interaction and the practice of immersive educational content creation, offering insights for future applications across diverse fields
46
Yazdani, Aminabadi Reza. "Ultra low-power, high-performance accelerator for speech recognition." Doctoral thesis, Universitat Politècnica de Catalunya, 2019. http://hdl.handle.net/10803/667429.
Full textAbstract:
Automatic Speech Recognition (ASR) is undoubtedly one of the most important and interesting applications in the cutting-edge era of Deep-learning deployment, especially in the mobile segment. Fast and accurate ASR comes at a high energy cost, requiring huge memory storage and computational power, which is not affordable for the tiny power budget of mobile devices.
Hardware acceleration can reduce power consumption of ASR systems as well as reducing its memory pressure, while delivering high-performance.
In this thesis, we present a customized accelerator for large-vocabulary, speaker-independent, continuous speech recognition. A state-of-the-art ASR system consists of two major components: acoustic-scoring using DNN and speech-graph decoding using Viterbi search. As the first step, we focus on the Viterbi search algorithm, that represents the main bottleneck in the ASR system.
The accelerator includes some innovative techniques to improve the memory subsystem, which is the main bottleneck for performance and power, such as a prefetching scheme and a novel bandwidth saving technique tailored to the needs of ASR.
Furthermore, as the speech graph is vast taking more than 1-Gigabyte memory space, we propose to change its representation by partitioning it into several sub-graphs and perform an on-the-fly composition during the Viterbi run-time. This approach together with some simple yet efficient compression techniques result in 31x memory footprint reduction, providing 155x real-time speedup and orders of magnitude power and energy saving compared to CPUs and GPUs.
In the next step, we propose a novel hardware-based ASR system that effectively integrates a DNN accelerator for the pruned/quantized models with the Viterbi accelerator. We show that, when either pruning or quantizing the DNN model used for acoustic scoring, ASR accuracy is maintained but the execution time of the ASR system is increased by 33%. Although pruning and quantization improves the efficiency of the DNN, they result in a huge increase of activity in the Viterbi search since the output scores of the pruned model are less reliable. In order to avoid the aforementioned increase in Viterbi search workload, our system loosely selects the N-best hypotheses at every time step, exploring only the N most likely paths. Our final solution manages to efficiently combine both DNN and Viterbi accelerators using all their optimizations, delivering 222x real-time ASR with a small power budget of 1.26 Watt, small memory footprint of 41 MB, and a peak memory bandwidth of 381 MB/s, being amenable for low-power mobile platforms.<br>Los sistemas de reconocimiento automático del habla (ASR por sus siglas en inglés, Automatic Speech Recognition) son sin lugar a dudas una de las aplicaciones más relevantes en el área emergente de aprendizaje profundo (Deep Learning), specialmente en el segmento de los dispositivos móviles. Realizar el reconocimiento del habla de forma rápida y precisa tiene un elevado coste en energía, requiere de gran capacidad de memoria y de cómputo, lo cual no es deseable en sistemas móviles que tienen severas restricciones de consumo energético y disipación de potencia. El uso de arquitecturas específicas en forma de aceleradores hardware permite reducir el consumo energético de los sistemas de reconocimiento del habla, al tiempo que mejora el rendimiento y reduce la presión en el sistema de memoria. En esta tesis presentamos un acelerador específicamente diseñado para sistemas de reconocimiento del habla de gran vocabulario, independientes del orador y que funcionan en tiempo real. Un sistema de reconocimiento del habla estado del arte consiste principalmente en dos componentes: el modelo acústico basado en una red neuronal profunda (DNN, Deep Neural Network) y la búsqueda de Viterbi basada en un grafo que representa el lenguaje. Como primer objetivo nos centramos en la búsqueda de Viterbi, ya que representa el principal cuello de botella en los sistemas ASR. El acelerador para el algoritmo de Viterbi incluye técnicas innovadoras para mejorar el sistema de memoria, que es el mayor cuello de botella en rendimiento y energía, incluyendo técnicas de pre-búsqueda y una nueva técnica de ahorro de ancho de banda a memoria principal específicamente diseñada para sistemas ASR. Además, como el grafo que representa el lenguaje requiere de gran capacidad de almacenamiento en memoria (más de 1 GB), proponemos cambiar su representación y dividirlo en distintos grafos que se componen en tiempo de ejecución durante la búsqueda de Viterbi. De esta forma conseguimos reducir el almacenamiento en memoria principal en un factor de 31x, alcanzar un rendimiento 155 veces superior a tiempo real y reducir el consumo energético y la disipación de potencia en varios órdenes de magnitud comparado con las CPUs y las GPUs. En el siguiente paso, proponemos un novedoso sistema hardware para reconocimiento del habla que integra de forma efectiva un acelerador para DNNs podadas y cuantizadas con el acelerador de Viterbi. Nuestros resultados muestran que podar y/o cuantizar el DNN para el modelo acústico permite mantener la precisión pero causa un incremento en el tiempo de ejecución del sistema completo de hasta el 33%. Aunque podar/cuantizar mejora la eficiencia del DNN, éstas técnicas producen un gran incremento en la carga de trabajo de la búsqueda de Viterbi ya que las probabilidades calculadas por el DNN son menos fiables, es decir, se reduce la confianza en las predicciones del modelo acústico. Con el fin de evitar un incremento inaceptable en la carga de trabajo de la búsqueda de Viterbi, nuestro sistema restringe la búsqueda a las N hipótesis más probables en cada paso de la búsqueda. Nuestra solución permite combinar de forma efectiva un acelerador de DNNs con un acelerador de Viterbi incluyendo todas las optimizaciones de poda/cuantización. Nuestro resultados experimentales muestran que dicho sistema alcanza un rendimiento 222 veces superior a tiempo real con una disipación de potencia de 1.26 vatios, unos requisitos de memoria modestos de 41 MB y un uso de ancho de banda a memoria principal de, como máximo, 381 MB/s, ofreciendo una solución adecuada para dispositivos móviles.
47
Маслова, Зоя Іванівна, Зоя Ивановна Маслова, Zoia Ivanivna Maslova, Тетяна Володимирівна Лаврик, Татьяна Владимировна Лаврик, and Tetiana Volodymyrivna Lavryk. "Software implementation of calculating the value of a logical expression in compilers." Thesis, Sumy State University, 2016. http://essuir.sumdu.edu.ua/handle/123456789/46996.
Full textAbstract:
This paper describes an algorithm to optimize a process of determining the value of a logical expression. This algorithm is based on the principles of the algebra of logic, graphs and automata theory. Fast calculation of a logical expression is achieved by a reduction in the number of operations. The program is a multi-functional simulator.
48
Fortin, Marie. "Expressivité de la logique du premier ordre, de la logique dynamique propositionnelle sans étoile et des automates communicants." Electronic Thesis or Diss., université Paris-Saclay, 2020. http://www.theses.fr/2020UPASG046.
Full textAbstract:
Cette thèse porte sur l’expressivité de la logique du premier ordre et d’autres formalismes sur différentes classes de structures ordonnées, parmi lesquelles les MSC (Message Sequence Charts), un modèle standard pour les exécutions de systèmes concurrents avec échange de messages. Cette étude est motivée par deux questions classiques : celle de l’équivalence, pour certaines classes de structures, entre la logique du premier ordre et son fragment avec k variables, et celle de la comparaison entre automates et logique, dans l’esprit du théorème de Büchi-Elgot-Trakhtenbrot. Notre approche repose sur la logique dynamique propositionnelle sans étoile (PDL sans étoile), une variante de PDL équivalente à la logique du premier ordre avec 3 variables. On étudie d’abord l’expressivité de PDL sans étoile sur des structures linéairement ordonnées avec des prédicats unaires et binaires. On montre que sous certaines conditions de monotonie, PDL sans étoile devient aussi expressive que la logique du premier ordre. Cela implique que toute formule de la logique du premier ordre peut alors être réécrite en une formule équivalente qui utilise au plus 3 variables. Ce résultat s’applique, directement ou indirectement, à un certain nombre de classes naturelles, généralisant des résultats connus et répondant à des questions ouvertes.On se concentre ensuite sur les MSC, auxquels ce premier résultat s’applique également. PDL sans étoile nous permet d’aborder un autre problème important: celui de la synthèse d’automates communicants à partir de spécifications écrites en logique du premier ordre. Les automates communicants sont un modèle de systèmes concurrents dans lequel un nombre fixé d’automates finis échangent des messages via des canaux FIFO. Ils définissent des langages de MSC. Bien que des caractérisations de l’expressivité des automates communicants aient déjà été établies pour certaines restrictions (borne sur la taille des canaux de communications, ou omission de la relation “arrivé-avant” au niveau de la logique), la question suivante restait ouverte dans le cas général : toute formule du premier ordre sur les MSC peut-elle être traduite en un automate communicant équivalent ? On montre que c’est le cas, en utilisant PDL sans étoile comme langage intermédiaire<br>This thesis is concerned with the expressive power of first-order logic and other formalisms over different classes of ordered structures, among which MSCs (Message Sequence Charts), a standard model for executions of message-passing systems. This study is motivated by two classic problems: the k-variable property, that is, the equivalence of first-order logic and its k-variable fragment over certain classes of structures, and the study of logic-automata connections, in the spirit of Büchi-Elgot-Trakhtenbrot theorem. Our approach relies on star-free propositional dynamic logic (star-free PDL), a variant of PDL with the same expressive power as the 3-variable fragment of first-order logic. We start by studying the expressive power of star-free PDL over linearly ordered structures with unary and binary predicates. We show that under certain monotonicity conditions, star-free PDL becomes as expressive as first-order logic. This implies that any first-order formula can then be rewritten into an equivalent formula with at most 3 variables. This result applies to various natural classes of structures, generalizing several known results and answering some open questions.We then focus on MSCs, to which this first result also applies. We use star-free PDL to address another important problem: the synthesis of communicating finite-state machines (CFMs) from first-order specifications. CFMs are a model of concurrent systems in which a fixed number of finite-state automata communicate through unbounded FIFO channels. They accept languages of MSCs. While logical characterizations of the expressive power of CFMs have been established under different restrictions (bounding the size of the communication channels, or removing the “happened-before” relation from the logic), the following question had remained open in the general case: can every first-order formula over MSCs be translated into an equivalent CFM? We prove that this is the case, using star-free PDL as an intermediate language
49
Dokulil, Marek. "Laserový řezací plotr ocelových plátů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2019. http://www.nusl.cz/ntk/nusl-399193.
Full textAbstract:
This diploma thesis is divided into two main parts. The first section is dedicated to the history and development of the laser technology. The second part describes all individual types of laser technology which are used in the industry nowadays. The next section follows with the research of various laser devices which serve mainly as a cutting tool. This knowledge gathered in the previous part was used to create the next part including the own conception of the machine. The second half of this diploma thesis deals with a research of software available at the market today. Eventually, after summarizing the characteristics of each software, the new concept and implementation of own software are made. In the final section, there are mentioned the possible extension and available upgrades. The reader should be able to create his/her own conception of the laser device and software after reading and understanding this paper.
50
Dokulil, Marek. "Laserový řezací plotr ocelových plátů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2018. http://www.nusl.cz/ntk/nusl-413352.
Full textAbstract:
This diploma thesis is divided into two main parts. The first section is dedicated to the history and development of the laser technology. The second part describes all individual types of laser technology which are used in the industry nowadays. The next section follows with the research of various laser devices which serve mainly as a cutting tool. This knowledge gathered in the previous part was used to create the next part including the own conception of the machine. The second half of this diploma thesis deals with a research of software available at the market today. Eventually, after summarizing the characteristics of each software, the new concept and implementation of own software are made. In the final section, there are mentioned the possible extension and available upgrades. The reader should be able to create his/her own conception of the laser device and software after reading and understanding this paper.