Relevant bibliographies by topics / Deterministic finite state automata

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Deterministic finite state automata'

Author: Grafiati
Published: 3 June 2025
Last updated: 22 June 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Deterministic finite state automata.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Deterministic finite state automata"

1

Alawida, Moatsum, Azman Samsudin, Je Sen Teh, and Wafa’ Hamdan Alshoura. "Deterministic chaotic finite-state automata." Nonlinear Dynamics 98, no. 3 (2019): 2403–21. http://dx.doi.org/10.1007/s11071-019-05311-z.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Holzer, Markus, Sebastian Jakobi, and Martin Kutrib. "Minimal Reversible Deterministic Finite Automata." International Journal of Foundations of Computer Science 29, no. 02 (2018): 251–70. http://dx.doi.org/10.1142/s0129054118400063.

Full text
Abstract:
We study reversible deterministic finite automata (REV-DFAs), that are partial deterministic finite automata whose transition function induces an injective mapping on the state set for every letter of the input alphabet. We give a structural characterization of regular languages that can be accepted by REV-DFAs. This characterization is based on the absence of a forbidden pattern in the (minimal) deterministic state graph. Again with a forbidden pattern approach, we also show that the minimality of REV-DFAs among all equivalent REV-DFAs can be decided. Both forbidden pattern characterizations give rise to [Formula: see text]-complete decision algorithms. In fact, our techniques allow us to construct the minimal REV-DFA for a given minimal DFA. These considerations lead to asymptotic upper and lower bounds on the conversion from DFAs to REV-DFAs. Thus, almost all problems that concern uniqueness and the size of minimal REV-DFAs are solved.
APA, Harvard, Vancouver, ISO, and other styles
3

Câmpeanu, Cezar. "Two Extensions of Cover Automata." Axioms 10, no. 4 (2021): 338. http://dx.doi.org/10.3390/axioms10040338.

Full text
Abstract:
Deterministic Finite Cover Automata (DFCA) are compact representations of finite languages. Deterministic Finite Automata with “do not care” symbols and Multiple Entry Deterministic Finite Automata are both compact representations of regular languages. This paper studies the benefits of combining these representations to get even more compact representations of finite languages. DFCAs are extended by accepting either “do not care” symbols or considering multiple entry DFCAs. We study for each of the two models the existence of the minimization or simplification algorithms and their computational complexity, the state complexity of these representations compared with other representations of the same language, and the bounds for state complexity in case we perform a representation transformation. Minimization for both models proves to be NP-hard. A method is presented to transform minimization algorithms for deterministic automata into simplification algorithms applicable to these extended models. DFCAs with “do not care” symbols prove to have comparable state complexity as Nondeterministic Finite Cover Automata. Furthermore, for multiple entry DFCAs, we can have a tight estimate of the state complexity of the transformation into equivalent DFCA.
APA, Harvard, Vancouver, ISO, and other styles
4

Badr, Andrew, Viliam Geffert, and Ian Shipman. "Hyper-minimizing minimized deterministic finite state automata." RAIRO - Theoretical Informatics and Applications 43, no. 1 (2007): 69–94. http://dx.doi.org/10.1051/ita:2007061.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Reger, Johann. "CYCLE ANALYSIS FOR DETERMINISTIC FINITE STATE AUTOMATA." IFAC Proceedings Volumes 35, no. 1 (2002): 247–52. http://dx.doi.org/10.3182/20020721-6-es-1901.00529.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Nagy, Benedek. "A Class of 2-Head Finite Automata for Linear Languages." Triangle, no. 8 (June 29, 2018): 89. http://dx.doi.org/10.17345/triangle8.89-99.

Full text
Abstract:
Both deterministic and non-deterministic nite state machines (automata) recognize regular languages exactly. Now we extend these machines using two heads to characterize even-linear and linear languages. The heads move in opposite directions in these automata. For even-linear languages, deterministic automata have the same eciency as non-deterministic ones, but for the general case (linear languages) only the non-deterministic version is sucient. We compare our automata to other two-head automata as well.
APA, Harvard, Vancouver, ISO, and other styles
7

Rauch, Christian, and Markus Holzer. "On the accepting state complexity of operations on permutation automata." RAIRO - Theoretical Informatics and Applications 57 (2023): 9. http://dx.doi.org/10.1051/ita/2023010.

Full text
Abstract:
We investigate the accepting state complexity of deterministic finite automata for regular languages obtained by applying one of the following operations on languages accepted by permutation automata: union, quotient, complement, difference, intersection, Kleene star, Kleene plus, and reversal. The paper thus joins the study of the accepting state complexity of regularity preserving language operations which was initiated in [J. Dassow, J. Autom., Lang. Comb. 21 (2016) 55–67]. We show that for almost all of the above-mentioned operations, except for reversal and quotient, there is no difference in the accepting state complexity for permutation automata compared to deterministic finite automata in general. For both reversal and quotient we prove that certain accepting state complexities cannot be obtained; these numbers are called “magic” in the literature. Moreover, we solve the left open accepting state complexity problem for the intersection of unary languages accepted by permutation automata and deterministic finite automata in general.
APA, Harvard, Vancouver, ISO, and other styles
8

PIGHIZZINI, GIOVANNI. "DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES." International Journal of Foundations of Computer Science 20, no. 04 (2009): 629–45. http://dx.doi.org/10.1142/s0129054109006784.

Full text
Abstract:
The simulation of deterministic pushdown automata defined over a one-letter alphabet by finite state automata is investigated from a descriptional complexity point of view. We show that each unary deterministic pushdown automaton of size s can be simulated by a deterministic finite automaton with a number of states that is exponential in s. We prove that this simulation is tight. Furthermore, its cost cannot be reduced even if it is performed by a two-way nondeterministic automaton. We also prove that there are unary languages for which deterministic pushdown automata cannot be exponentially more succinct than finite automata. In order to state this result, we investigate the conversion of deterministic pushdown automata into context-free grammars. We prove that in the unary case the number of variables in the resulting grammar is strictly smaller than the number of variables needed in the case of nonunary alphabets.
APA, Harvard, Vancouver, ISO, and other styles
9

PIGHIZZINI, GIOVANNI, and ANDREA PISONI. "LIMITED AUTOMATA AND REGULAR LANGUAGES." International Journal of Foundations of Computer Science 25, no. 07 (2014): 897–916. http://dx.doi.org/10.1142/s0129054114400140.

Full text
Abstract:
Limited automata are one-tape Turing machines that are allowed to rewrite the content of any tape cell only in the first d visits, for a fixed constant d. In the case d = 1, namely, when a rewriting is possible only during the first visit to a cell, these models have the same power of finite state automata. We prove state upper and lower bounds for the conversion of 1-limited automata into finite state automata. In particular, we prove a double exponential state gap between nondeterministic 1-limited automata and one-way deterministic finite automata. The gap reduces to a single exponential in the case of deterministic 1-limited automata. This also implies an exponential state gap between nondeterministic and deterministic 1-limited automata. Another consequence is that 1-limited automata can have less states than equivalent two-way nondeterministic finite automata. We show that this is true even if we restrict to the case of the one-letter input alphabet. For each d ≥ 2, d-limited automata are known to characterize the class of context-free languages. Using the Chomsky-Schützenberger representation for contextfree languages, we present a new conversion from context-free languages into 2-limited automata.
APA, Harvard, Vancouver, ISO, and other styles
10

Riduan Achmad, Refi, Fahmi Fadillah Septiana, Nur Syamsi, Bobby Suryo Prakoso, and Hafifah Bella Novitasari. "Penerapan Finite State Automata pada Vending Machine dalam Melakukan Transaksi Pengembalian Buku di Perpustakaan." METIK JURNAL 5, no. 1 (2021): 63–70. http://dx.doi.org/10.47002/metik.v5i1.219.

Full text
Abstract:
Revolusi Industri 4.0 dan Society 5.0 menuntut untuk terus mengembangkan bidang teknologi dan sumber daya manusia dalam seluruh ranah kehidupan. Penelitian ini bertujuan untuk memadukan antara teknologi dan upaya peningkatan literasi, dalam hal ini membahas tentang penerapan finite automata pada vending machine untuk mempermudah transaksi pengembalian buku di perpustakaan. Metode penelitian yakni melakukan penggambaran Finite State Automata menggunakan Non-deterministic Finite Automata, perancangan Diagram State mengenai fitur-fitur dan desain tampilan antarmuka saat Vending Machine diimplementasikan. Hasil penelitian menunjukkan bahwa penggunaan Non-deterministic Finite Automata pada desain Vending Machine pengembalian buku di perpustakaan dapat mempermudah transaksi pengembalian buku di perpustakaan.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Deterministic finite state automata"

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
APA, Harvard, Vancouver, ISO, and other styles
2

Kshatriya, Jagannath Rajini Singh. "Visualizing the minimization of a deterministic finite state automaton." Thesis, Montana State University, 2007. http://etd.lib.montana.edu/etd/2007/kshatriyajagannath/KshatriyaJagannathR1207.pdf.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Stanek, Timotej. "Automatické shlukování regulárních výrazů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2011. http://www.nusl.cz/ntk/nusl-235531.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

Neme, Alexis. "An arabic language resource for computational morphology based on the semitic model." Thesis, Paris Est, 2020. http://www.theses.fr/2020PESC2013.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
5

Watson, Bruce William. "Constructing minimal acyclic deterministic finite automata." Thesis, University of Pretoria, 2010. http://hdl.handle.net/2263/23648.

Full text
Abstract:
This thesis is submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Ph.D) in the FASTAR group of the Department of Computer Science, University of Pretoria, South Africa. I present a number of algorithms for constructing minimal acyclic deterministic finite automata (MADFAs), most of which I originally derived/designed or co-discovered. Being acyclic, such automata represent finite languages and have proven useful in applications such as spellchecking, virus-searching and text indexing. In many of those applications, the automata grow to billions of states, making them difficult to store without using various compression techniques — the most important of which is minimization. Results from the late 1950’s show that minimization yields a unique automaton (for a given language), and later results show that minimization of acyclic automata is possible in time linear in the number of states. These two results make for a rich area of algorithmics research; automata and algorithmics research are relatively old fields of computing science and the discovery/invention of new algorithms in the field is an exciting result. I present both incremental and nonincremental algorithms. With nonincremental techniques, the unminimized acyclic deterministic finite automaton (ADFA) is first constructed and then minimized. As mentioned above, the unminimized ADFA can be very large indeed — often even too large to fit within the virtual memory space of the computer. As a result, incremental techniques for minimization (i.e. the ADFA is minimized during its construction) become interesting. Incremental algorithms frequently have some overhead: if the unminimized ADFA fits easily within physical memory, it may still be faster to use nonincremental techniques. The presentation used in this thesis has a few unusual characteristics: <ul><li> Few other presentations follow a correctness-by-construction style for presenting and deriving algorithms. The presentations given here include correctness arguments or sketches thereof. </li><li> The presentation is taxonomic — emphasizing the similarities and differences between the algorithms at a fundamental level. </li><li> While it is possible to present these algorithms in a formal-language-theoretic setting, this thesis remains somewhat closer to the actual implementation issues. </li><li> In several chapters, new algorithms and interesting new variants of existing algorithms are presented. </li><li> It gives new presentations of many existing algorithms — all in a common format with common examples. </li><li> There are extensive links to the existing literature. </li></ul><br>Thesis (PhD)--University of Pretoria, 2011.<br>Computer Science<br>unrestricted
APA, Harvard, Vancouver, ISO, and other styles
6

VETTEL, LYNNE ANN. "LEARNING DETERMINISTIC FINITE AUTOMATA TO CAPTURE TEMPORAL PATTERNS." University of Cincinnati / OhioLINK, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1037999729.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bilal, Tahir. "Content Based Packet Filtering In Linux Kernel Using Deterministic Finite Automata." Master's thesis, METU, 2011. http://etd.lib.metu.edu.tr/upload/12613710/index.pdf.

Full text
Abstract:
In this thesis, we present a content based packet filtering Architecture in Linux using Deterministic Finite Automata and iptables framework. New generation firewalls and intrusion detection systems not only filter or inspect network packets according to their header fields but also take into account the content of payload. These systems use a set of signatures in the form of regular expressions or plain strings to scan network packets. This scanning phase is a CPU intensive task which may degrade network performance. Currently, the Linux kernel firewall scans network packets separately for each signature in the signature set provided by the user. This approach constitutes a considerable bottleneck to network performance. We implement a content based packet filtering architecture and a multiple string matching extension for the Linux kernel firewall that matches all signatures at once, and show that we are able to filter network traffic by consuming constant bandwidth regardless of the number of signatures. Furthermore, we show that we can do packet filtering in multi-gigabit rates.
APA, Harvard, Vancouver, ISO, and other styles
8

FRANCH, Daniel Kudlowiez. "Dynamical system modeling with probabilistic finite state automata." Universidade Federal de Pernambuco, 2017. https://repositorio.ufpe.br/handle/123456789/25448.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
9

Khemuka, Atul Ravi. "Workflow Modeling Using Finite Automata." [Tampa, Fla.] : University of South Florida, 2003. http://purl.fcla.edu/fcla/etd/SFE0000172.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Bird, Philip. "Unifying programming paradigms : logic programming and finite state automata." Thesis, University of Sheffield, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.419609.

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Deterministic finite state automata"

1

Karttunen, Lauri. Finite-State Technology. Edited by Ruslan Mitkov. Oxford University Press, 2012. http://dx.doi.org/10.1093/oxfordhb/9780199276349.013.0018.

Full text
Abstract:
The article introduces the basic concepts of finite-state language processing: regular languages and relations, finite-state automata, and regular expressions. Many basic steps in language processing, ranging from tokenization, to phonological and morphological analysis, disambiguation, spelling correction, and shallow parsing, can be performed efficiently by means of finite-state transducers. The article discusses examples of finite-state languages and relations. Finite-state networks can represent only a subset of all possible languages and relations; that is, only some languages are finite-state languages. Furthermore, this article introduces two types of complex regular expressions that have many linguistic applications, restriction and replacement. Finally, the article discusses the properties of finite-state automata. The three important properties of networks are: that they are epsilon free, deterministic, and minimal. If a network encodes a regular language and if it is epsilon free, deterministic, and minimal, the network is guaranteed to be the best encoding for that language.
APA, Harvard, Vancouver, ISO, and other styles
2

Schulz, Klaus U., and Stoyan Mihov. Finite-State Techniques: Automata, Transducers and Bimachines. Cambridge University Press, 2019.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Schulz, Klaus U., and Stoyan Mihov. Finite-State Techniques: Automata, Transducers and Bimachines. Cambridge University Press, 2019.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Aubry, Jean François, and Nicolae Brinzei. Systems Dependability Assessment: Modeling with Graphs and Finite State Automata. Wiley & Sons, Incorporated, John, 2015.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

Aubry, Jean François, and Nicolae Brinzei. Systems Dependability Assessment: Modeling with Graphs and Finite State Automata. Wiley & Sons, Incorporated, John, 2015.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Aubry, Jean François, and Nicolae Brinzei. Systems Dependability Assessment: Modeling with Graphs and Finite State Automata. Wiley & Sons, Incorporated, John, 2015.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Aubry, Jean François, and Nicolae Brinzei. Systems Dependability Assessment: Modeling with Graphs and Finite State Automata. Wiley & Sons, Incorporated, John, 2015.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Shornikov, Yury V. Theory of Programming Languages: Design and Implementation. Novosibirsk State Technical University, 2022. http://dx.doi.org/10.17212/978-5-7782-4817-5.

Full text
Abstract:
The textbook has been prepared in accordance with the State educational Standard in the fields of "Computer Science and Computer Engineering" (09.03.01), "Applied Computer Science" (09.03.03) for the cycle of disciplines of information specialties. The basis of the textbook was the material of lectures delivered by the author to students of the relevant specialties at the Novosibirsk State Technical University and the Kazakh-British Technical University in the courses "Theory of Formal Languages and Compilers", "System Software", and "Linguistic Support". The textbook discusses the theory of generating grammars, finite automata and regular expressions. All theoretical mechanisms of analysis and synthesis of language constructions are strictly formalized and constitute the theoretical foundations of the programming language design. The implementation of programming languages is represented by the development of language processors. The transition from formal languages to language processors is carried out through constructive analysis methods with strict modeling algorithms that can be implemented in high-level languages or with the help of modern programming automation tools. The manual discusses ANTLR and FLEX &amp; BIZON tools for automating parser and lexer programming. Despite the educational orientation, the manual can be useful to anyone who is engaged in the design and implementation of new languages, language processors and finite-automaton recognizers.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Deterministic finite state automata"

1

Davies, Sylvie. "State Complexity of Reversals of Deterministic Finite Automata with Output." In Implementation and Application of Automata. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94812-6_12.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Jirásková, Galina, and Alexander Okhotin. "State Complexity of Unambiguous Operations on Deterministic Finite Automata." In Descriptional Complexity of Formal Systems. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-94631-3_16.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Myers, Robert S. R., Stefan Milius, and Henning Urbat. "Nondeterministic Syntactic Complexity." In Lecture Notes in Computer Science. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-71995-1_23.

Full text
Abstract:
AbstractWe introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.
APA, Harvard, Vancouver, ISO, and other styles
4

Blondin, Michael, Michaël Cadilhac, Xin-Yi Cui, Philipp Czerner, Javier Esparza, and Jakob Schulz. "Weakly Acyclic Diagrams: A Data Structure for Infinite-State Symbolic Verification." In Lecture Notes in Computer Science. Springer Nature Switzerland, 2025. https://doi.org/10.1007/978-3-031-90660-2_2.

Full text
Abstract:
Abstract Ordered binary decision diagrams (OBDDs) are a fundamental data structure for the manipulation of Boolean functions, with strong applications to finite-state symbolic model checking. OBDDs allow for efficient algorithms using top-down dynamic programming. From an automata-theoretic perspective, OBDDs essentially are minimal deterministic finite automata recognizing languages whose words have a fixed length (the arity of the Boolean function). We introduce weakly acyclic diagrams (WADs), a generalization of OBDDs that maintains their algorithmic advantages, but can also represent infinite languages. We develop the theory of WADs and show that they can be used for symbolic model checking of various models of infinite-state systems.
APA, Harvard, Vancouver, ISO, and other styles
5

Daciuk, Jan. "Comparison of Construction Algorithms for Minimal, Acyclic, Deterministic, Finite-State Automata from Sets of Strings." In Implementation and Application of Automata. Springer Berlin Heidelberg, 2003. http://dx.doi.org/10.1007/3-540-44977-9_26.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Bordihn, Henning, and Markus Holzer. "On the Number of Active States in Deterministic and Nondeterministic Finite Automata." In Implementation and Application of Automata. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-60134-2_4.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Chocholatý, David, Tomáš Fiedor, Vojtěch Havlena, et al. "Mata: A Fast and Simple Finite Automata Library." In Tools and Algorithms for the Construction and Analysis of Systems. Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-57249-4_7.

Full text
Abstract:
AbstractMata is a well-engineered automata library written in C++ that offers a unique combination of speed and simplicity. It is meant to serve in applications such as string constraint solving and reasoning about regular expressions, and as a reference implementation of automata algorithms. Besides basic algorithms for (non)deterministic automata, it implements a fast simulation reduction and antichain-based language inclusion checking. The simplicity allows a straightforward access to the low-level structures, making it relatively easy to extend and modify. Besides the C++ API, the library also implements a Python binding.The library comes with a large benchmark of automata problems collected from relevant applications such as string constraint solving, regular model checking, and reasoning about regular expressions. We show that Mata is on this benchmark significantly faster than all libraries from a wide range of automata libraries we collected. Its usefulness in string constraint solving is demonstrated by the string solver Z3-Noodler, which is based on Mata and outperforms the state of the art in string constraint solving on many standard benchmarks.
APA, Harvard, Vancouver, ISO, and other styles
8

Kari, Jarkko, and Cristopher Moore. "New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata." In STACS 2001. Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/3-540-44693-1_35.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Palmer, Nick, and Paul W. Goldberg. "PAC-Learnability of Probabilistic Deterministic Finite State Automata in Terms of Variation Distance." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11564089_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Dell’Erba, Daniele, Yong Li, and Sven Schewe. "DFAMiner: Mining Minimal Separating DFAs from Labelled Samples." In Lecture Notes in Computer Science. Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-71177-0_4.

Full text
Abstract:
AbstractWe propose , a passive learning tool for learning minimal separating deterministic finite automata (DFA) from a set of labelled samples. Separating automata are an interesting class of automata that occurs generally in regular model checking and has raised interest in foundational questions of parity game solving. We first propose a simple and linear-time algorithm that incrementally constructs a three-valued DFA (3DFA) from a set of labelled samples given in the usual lexicographical order. This 3DFA has accepting and rejecting states as well as don’t-care states, so that it can exactly recognise the labelled examples. We then apply our tool to mining a minimal separating DFA for the labelled samples by minimising the constructed automata via a reduction to SAT solving. Empirical evaluation shows that our tool outperforms current state-of-the-art tools significantly on standard benchmarks for learning minimal separating DFAs from samples. Progress in the efficient construction of separating DFAs can also lead to finding the lower bound of parity game solving, where we show that can create optimal separating automata for simple languages with up to 7 colours. Future improvements might offer inroads to better data structures.
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Deterministic finite state automata"

1

J Y, Dharshan, Arjun R. Amarnath, Valupadasu Srujan, and Radha D. "Validation of ARM Processor Instructions using Deterministic Finite Automata." In 2024 IEEE North Karnataka Subsection Flagship International Conference (NKCon). IEEE, 2024. https://doi.org/10.1109/nkcon62728.2024.10774677.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Mathew, Joel, Nishit Kumar, Sreeharsha Sadhu, and Niharika Panda. "Converting Regular Expressions to Non-Deterministic Finite Automata through an Automated Framework." In 2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT). IEEE, 2024. http://dx.doi.org/10.1109/icccnt61001.2024.10724734.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Madhuja, C., Shreya Bhanot, Srinidhi M, and D. Radha. "Design of an Automatic Washing Machine Control System using Deterministic Finite Automata." In 2024 5th IEEE Global Conference for Advancement in Technology (GCAT). IEEE, 2024. https://doi.org/10.1109/gcat62922.2024.10923861.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Heksaputra, Dadang, Rahmat Gernowo, and R. Rizal Isnanto. "Model for Bahasa Text Cleaning Based Regular Expression Non-Deterministic Finite Automata Approach." In 2024 International Conference on Informatics, Multimedia, Cyber and Information System (ICIMCIS). IEEE, 2024. https://doi.org/10.1109/icimcis63449.2024.10956223.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Chen, Keru, Shaowen Miao, Aiwen Lai, Ji Ma, and Sihan Chen. "Decidability of Probabilistic Current-State Opacity for Probabilistic Finite Automata." In 2024 43rd Chinese Control Conference (CCC). IEEE, 2024. http://dx.doi.org/10.23919/ccc63176.2024.10661575.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Pisal, Tulashiram B., Arjun P. Ghatule, and Pandurang M. Lawate. "Simple algorithm to construct deterministic finite automata from non-deterministic finite automata using initial state transitions successor." In THE 2ND UNIVERSITAS LAMPUNG INTERNATIONAL CONFERENCE ON SCIENCE, TECHNOLOGY, AND ENVIRONMENT (ULICoSTE) 2021. AIP Publishing, 2022. http://dx.doi.org/10.1063/5.0106219.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

"Non-Deterministic Finite State Automata as Termites Swarm Agent Model." In 2017 the 7th International Workshop on Computer Science and Engineering. WCSE, 2017. http://dx.doi.org/10.18178/wcse.2017.06.055.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

JIŘIČKA, PETR, and JAROSLAV KRÁL. "DETERMINISTIC FORGETTING PLANAR AUTOMATA ARE MORE POWERFUL THAN NONDETERMINISTIC FINITE-STATE PLANAR AUTOMATA." In Proceedings of the 4th International Conference. WORLD SCIENTIFIC, 2000. http://dx.doi.org/10.1142/9789812792464_0007.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Wombacher, A., P. Fankhauser, and E. Neuhold. "Transforming BPEL into annotated deterministic finite state automata for service discovery." In Proceedings. IEEE International Conference on Web Services, 2004. IEEE, 2004. http://dx.doi.org/10.1109/icws.2004.1314753.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Bistaffa, Filippo. "Faster Exact MPE and Constrained Optimization with Deterministic Finite State Automata." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/209.

Full text
Abstract:
We propose a concise function representation based on deterministic finite state automata for exact most probable explanation and constrained optimization tasks in graphical models. We then exploit our concise representation within Bucket Elimination (BE). We denote our version of BE as FABE. FABE significantly improves the performance of BE in terms of runtime and memory requirements by minimizing redundancy. Indeed, results on most probable explanation and weighted constraint satisfaction benchmarks show that FABE often outperforms the state of the art, leading to significant runtime improvements (up to 2 orders of magnitude in our tests).
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Deterministic finite state automata"

1

Anderson, William Erik. On the secure obfuscation of deterministic finite automata. Office of Scientific and Technical Information (OSTI), 2008. http://dx.doi.org/10.2172/974399.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Borgwardt, Stefan, and Rafael Peñaloza. Complementation and Inclusion of Weighted Automata on Infinite Trees: Revised Version. Technische Universität Dresden, 2011. http://dx.doi.org/10.25368/2022.180.

Full text
Abstract:
Weighted automata can be seen as a natural generalization of finite state automata to more complex algebraic structures. The standard reasoning tasks for unweighted automata can also be generalized to the weighted setting. In this report we study the problems of intersection, complementation, and inclusion for weighted automata on infinite trees and show that they are not harder complexity-wise than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.
APA, Harvard, Vancouver, ISO, and other styles
3

Borgwardt, Stefan, and Rafael Peñaloza. Complementation and Inclusion of Weighted Automata on Infinite Trees. Technische Universität Dresden, 2010. http://dx.doi.org/10.25368/2022.178.

Full text
Abstract:
Weighted automata can be seen as a natural generalization of finite state automata to more complex algebraic structures. The standard reasoning tasks for unweighted automata can also be generalized to the weighted setting. In this report we study the problems of intersection, complementation and inclusion for weighted automata on infinite trees and show that they are not harder than reasoning with unweighted automata. We also present explicit methods for solving these problems optimally.
APA, Harvard, Vancouver, ISO, and other styles
4

Baader, Franz, and Marcel Lippmann. Runtime Verification Using a Temporal Description Logic Revisited. Technische Universität Dresden, 2014. http://dx.doi.org/10.25368/2022.203.

Full text
Abstract:
Formulae of linear temporal logic (LTL) can be used to specify (wanted or unwanted) properties of a dynamical system. In model checking, the system’s behaviour is described by a transition system, and one needs to check whether all possible traces of this transition system satisfy the formula. In runtime verification, one observes the actual system behaviour, which at any point in time yields a finite prefix of a trace. The task is then to check whether all continuations of this prefix to a trace satisfy (violate) the formula. More precisely, one wants to construct a monitor, i.e., a finite automaton that receives the finite prefix as input and then gives the right answer based on the state currently reached. In this paper, we extend the known approaches to LTL runtime verification in two directions. First, instead of propositional LTL we use the more expressive temporal logic ALC-LTL, which can use axioms of the Description Logic (DL) ALC instead of propositional variables to describe properties of single states of the system. Second, instead of assuming that the observed system behaviour provides us with complete information about the states of the system, we assume that states are described in an incomplete way by ALC-knowledge bases. We show that also in this setting monitors can effectively be constructed. The (double-exponential) size of the constructed monitors is in fact optimal, and not higher than in the propositional case. As an auxiliary result, we show how to construct Büchi automata for ALC-LTL-formulae, which yields alternative proofs for the known upper bounds of deciding satisfiability in ALC-LTL.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Deterministic finite state automata' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography