Journal articles: '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

11

HAN, YO-SUB, and KAI SALOMAA. "STATE COMPLEXITY OF UNION AND INTERSECTION OF FINITE LANGUAGES." International Journal of Foundations of Computer Science 19, no. 03 (2008): 581–95. http://dx.doi.org/10.1142/s0129054108005838.

Full text

Abstract:

We investigate the state complexity of union and intersection for finite languages. Note that the problem of obtaining the tight bounds for both operations was open. First we compute upper bounds using structural properties of minimal deterministic finite-state automata for finite languages. Then, we show that the upper bounds are tight if we have a variable sized alphabet that can depend on the size of input deterministic finite-state automata. In addition, we prove that the upper bounds are unreachable for any fixed sized alphabet.

APA, Harvard, Vancouver, ISO, and other styles

12

HINES, PETER. "A categorical framework for finite state machines." Mathematical Structures in Computer Science 13, no. 3 (2003): 451–80. http://dx.doi.org/10.1017/s0960129503003931.

Full text

Abstract:

We provide a consistent way of looking at a range of finite state machines and their algebraic models. Our claim is that the natural representation of transitions of finite state machines is in terms of monoid homomorphisms, and distinct generalisation processes that can be applied to finite state machines correspond to distinct categorical generalisation processes at the level of the algebraic models.The generalisations we consider are those from deterministic to non-deterministic machines, from one-way to two-way machines, and from read-only machines to read/write machines. Hence the finite state machines we consider, and provide algebraic models for, are (deterministic and non-deterministic) finite state automata, two-way automata, Mealy machines, and bounded Turing machines.The categorical constructions corresponding to these generalisation processes are, respectively: altering the base category from functions to relations, applying the Geometry of Interaction, or Int construction, and a categorical process, which we refer to as the Comp construction, that uses the tensor on monoidal categories to construct graded categories.

APA, Harvard, Vancouver, ISO, and other styles

13

Krithivasan, Kamala, K. Sharda та Sandeep V. Varma. "Distributed ω-Automata". International Journal of Foundations of Computer Science 14, № 04 (2003): 681–98. http://dx.doi.org/10.1142/s0129054103001959.

Full text

Abstract:

In this paper, we introduce the notion of distributed ω-automata. Distributed ω-automata are a group of automata working in unison to accept an ω-language. We build the theory of distributed ω-automata for finite state automata and pushdown automata in different modes of cooperation like the t-mode, *-mode, = k-mode, ≤ k-mode and ≥ k-mode along with different acceptance criteria i.e. Büchi-, Muller-, Rabin- and Streett- acceptance criteria. We then analyze the acceptance power of such automata in all the above modes of cooperation and acceptance criteria. We present proofs that distributed ω-finite state automata do not have any additional power over ω-finite state automata in any of the modes of cooperation or acceptance criteria, while distributed ω-pushdown automata can accept languages not in CFLω. We give proofs for the equivalence of all modes of cooperation and acceptance criteria in the case of distributed ω-pushdown automata. We show that the power of distributed ω-pushdown automata is equal to that of ω-Turing Machines. We also study the deterministic version of distributed ω-pushdown automata. Deterministic ω-pushdown automata accept only languages contained in CFLω but distributed deterministic ω-pushdown automata can accept languages not in CFLω and have the same power as their nondeterministic counterparts. We also define distributed completely deterministic ω-pushdown automata and analyze their power.

APA, Harvard, Vancouver, ISO, and other styles

14

S.KOM., SUGIYANTO, Hamdan, Eni Heni Hermaliani, Tuti Haryanti, and Windu Gata. "PENERAPAN FINITE STATE AUTOMATA PADA VENDING MACHINE SISTEM PARKIR KENDARAAN MOTOR." Jurnal Ilmiah Betrik 12, no. 2 (2021): 146–53. http://dx.doi.org/10.36050/betrik.v12i2.324.

Full text

Abstract:

Kebutuhan akan tempat parkir menjadi suatu hal yang penting bilamana area untuk parkir tidak ada atau lahan yang semakin sempit. Tentu perlu dipikirkan alternatif yang modern dan kekinian untuk menciptakan sebuah kondisi tempat parkir yang nyaman. Penciptaan sebuah tempat parkir yang nyaman dengan menggunakan kombinasi teknologi akan sangat membantu bilamana hal ini bisa di aplikasikan. Tujuan penelitian ini membahas penerapan Finite State Automata (FSA) pada vending machine sistem parkir kendaraan motor. Metode penelitian dengan melakukan penggambaran Finite State Automata menggunakan Non-deterministic Finite Automata, perancangan Diagram State tentang fitur-fitur dan desain antarmuka saat Vending Machine diimplementasikan. Hasil penelitian menunjukkan penggunaan Non-deterministic Finite Automata pada desain Vending Machine sistem parkir kendaraan motor didapatkan teknologi parkir masa depan yang modern nyaman dan efektif.

APA, Harvard, Vancouver, ISO, and other styles

15

Paramitha, I. Gusti Bagus Arya Pradnja, Windu Gata, Laela Kurniawati, Eni Heni Hermaliani, and Jordy Lasmana Putra. "Penerapan Finite State Automata Pada Desain Vending Machine Batu Permata Sapphire Alami." J-SISKO TECH (Jurnal Teknologi Sistem Informasi dan Sistem Komputer TGD) 5, no. 2 (2022): 144. http://dx.doi.org/10.53513/jsk.v5i2.5677.

Full text

Abstract:

Batu Sapphire adalah salah satu jenis batu permata yang ada di dunia, yang paling di cari serta di minati oleh para penggemarnya adalah batu permata Sapphire berwarna biru. Untuk memudahkan penjualan batu permata Sapphire alami adalah dengan menggunakan Vending machine. Metode penelitian dengan melakukan penggambaran Finite State Automata menggunakan Deterministic Finite Automata, perancangan Diagram State tentang fitur-fitur dan desain antarmuka saat Vending machine diimplementasikan. Hasil penelitian menunjukkan penggunaan Deterministic Finite Automata pada desain Vending machine Batu Permata Sapphire Alami sehingga didapatkan sistem penjualan batu permata pada masa depan secara efektif dan nyaman. Dalam Vending machine Batu Permata Sapphire Alami menggunakan Finite State Automata dilengkapi dengan satu metode pembayaran yaitu menggunakan uang tunai. Perancangan Vending machine Batu Permata Sapphire Alami menggunakan Finite State Automata diharapkan dapat diterapkan dan dikembangkan di sentra – sentra penjualan oleh – oleh yang menjual batu – batu permata sehingga dapat dinikmati oleh masyarakat luas.

APA, Harvard, Vancouver, ISO, and other styles

16

Bernadotte, A. "Structural Modification of the Finite State Machine to Solve the Exponential Explosion Problem." Programmnaya Ingeneria 13, no. 9 (2022): 449–61. http://dx.doi.org/10.17587/prin.13.449-461.

Full text

Abstract:

In many modern applications, such as intrusion detection and prevention systems, expert knowledge can be formalized in the form of regular expressions. After this formalization, a finite automaton checks whether a word belongs to a regular language. Deterministic finite automata have an optimal time complexity, but the number of automaton states (space complexity) can grow exponentially with the length of the regular expression. At the same time, the time complexity is the main disadvantage of non-deterministic finite automata. Therefore, reducing spatial complexity while maintaining low time complexity is highly relevant. In applied problems of regular language recognition, a significant problem is the problem of the exponentially growing number of states of the recognizing deterministic finite automaton depending on the length of regular expressions of the recognized language — the exponential explosion problem. There are the following three main approaches to solving this problem using finite automata: 1) restriction on signatures given by experts; 2) regular language modification — this approach assumes the appearance in the solution of a practical problem of recognizing errors of the first and second kind; 3) finite automata modification without recognizing regular language changing. The third approach can be implemented as a finite automata modification through compression algorithms and particular structural elements. The paper presents a review of modern solutions, the main idea of which is the transition from an abstract finite automaton, represented by a table-specified function, to a structural automaton that combines the abstract part stored in the memory and various structural elements such as bit arrays and counters. Some ideas and algorithms have become especially successful when solving the exponential explosion problem by adding special structural elements. First, such successful solutions include the use of counters. Second, the idea of storing additional information about the state machine. Third, the combination of non-deterministic and deterministic finite automata. Fourth, the economic attitude to the state machine regarding its location to fast and slow memory allows us to consider the empirical experience of accumulated malicious traffic in intrusion detection systems.

APA, Harvard, Vancouver, ISO, and other styles

17

SALOMAA, KAI, and PAUL SCHOFIELD. "STATE COMPLEXITY OF ADDITIVE WEIGHTED FINITE AUTOMATA." International Journal of Foundations of Computer Science 18, no. 06 (2007): 1407–16. http://dx.doi.org/10.1142/s0129054107005443.

Full text

Abstract:

It is known that the neighborhood of a regular language with respect to an additive distance is regular. We introduce an additive weighted finite automaton model that provides a conceptually simple way to reprove this result. We consider the state complexity of converting additive weighted finite automata to deterministic finite automata. As our main result we establish a tight upper bound for the state complexity of the conversion.

APA, Harvard, Vancouver, ISO, and other styles

18

Manolios, Peter, and Robert Fanelli. "First-Order Recurrent Neural Networks and Deterministic Finite State Automata." Neural Computation 6, no. 6 (1994): 1155–73. http://dx.doi.org/10.1162/neco.1994.6.6.1155.

Full text

Abstract:

We examine the correspondence between first-order recurrent neural networks and deterministic finite state automata. We begin with the problem of inducing deterministic finite state automata from finite training sets, that include both positive and negative examples, an NP-hard problem (Angluin and Smith 1983). We use a neural network architecture with two recurrent layers, which we argue can approximate any discrete-time, time-invariant dynamic system, with computation of the full gradient during learning. The networks are trained to classify strings as belonging or not belonging to the grammar. The training sets used contain only short strings, and the sets are constructed in a way that does not require a priori knowledge of the grammar. After training, the networks are tested using various test sets with strings of length up to 1000, and are often able to correctly classify all the test strings. These results are comparable to those obtained with second-order networks (Giles et al. 1992; Watrous and Kuhn 1992a; Zeng et al. 1993). We observe that the networks emulate finite state automata, confirming the results of other authors, and we use a vector quantization algorithm to extract deterministic finite state automata after training and during testing of the networks, obtaining a table listing the start state, accept states, reject states, all transitions from the states, as well as some useful statistics. We examine the correspondence between finite state automata and neural networks in detail, showing two major stages in the learning process. To this end, we use a graphics module, which graphically depicts the states of the network during the learning and testing phases. We examine the networks' performance when tested on strings much longer than those in the training set, noting a measure based on clustering that is correlated to the stability of the networks. Finally, we observe that with sufficiently long training times, neural networks can become true finite state automata, due to the attractor structure of their dynamics.

APA, Harvard, Vancouver, ISO, and other styles

19

van, Zijl Lynette, and Jaco Geldenhuys. "Descriptional Complexity of Ambiguity in Symmetric Difference NFAs." JUCS - Journal of Universal Computer Science 17, no. (6) (2011): 874–90. https://doi.org/10.3217/jucs-017-06-0874.

Full text

Abstract:

We investigate ambiguity for symmetric difference nondeterministic finite automata. We show the existence of unambiguous, finitely ambiguous, polynomially ambiguous and exponentially ambiguous symmetric difference nondeterministic finite automata. We show that, for each of these classes, there is a family of n-state nondeterministic finite automata such that the smallest equivalent deterministic finite automata have O(2n) states.

APA, Harvard, Vancouver, ISO, and other styles

20

Jirásková, Galina, and Ivana Krajňáková. "Square on Deterministic, Alternating, and Boolean Finite Automata." International Journal of Foundations of Computer Science 30, no. 06n07 (2019): 1117–34. http://dx.doi.org/10.1142/s0129054119400318.

Full text

Abstract:

We investigate the state complexity of the square operation on languages represented by deterministic, alternating, and Boolean automata. For each [Formula: see text] such that [Formula: see text], we describe a binary language accepted by an [Formula: see text]-state deterministic finite automaton with [Formula: see text] final states meeting the upper bound [Formula: see text] on the state complexity of its square. We show that in the case of [Formula: see text], the corresponding upper bound cannot be met. Using the binary deterministic witness for square with [Formula: see text] states where half of them are final, we get the tight upper bounds [Formula: see text] and [Formula: see text] on the complexity of the square operation on alternating and Boolean automata, respectively.

APA, Harvard, Vancouver, ISO, and other styles

21

Nagy, Benedek. "State-deterministic Finite Automata with Translucent Letters and Finite Automata with Nondeterministically Translucent Letters." Electronic Proceedings in Theoretical Computer Science 386 (September 3, 2023): 170–84. http://dx.doi.org/10.4204/eptcs.386.14.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Sulaiman, Maulana Muhamad, Romi Andrianto, and Muhamad Arief Yulianto. "Mobile Learning Application for Language and Automata Theory using Android-based." Jurnal Online Informatika 5, no. 2 (2020): 176. http://dx.doi.org/10.15575/join.v5i2.630.

Full text

Abstract:

The language and automata theory are which required course must implemented by college student in informatic engineering study program. In this course, there are finite state automata (FSA) and deterministic finite automata (DFA) which are important materials in language and automata theory. This material requires more understanding of mathematical logic from students to determine an input which can be accepted or rejected in an abstract machine system. The assist students to understand the material, it is need to develop the learning media for mobile learning applications for language and automata theory on finite state automata (FSA) and deterministic finite automata (DFA) based on android as an evaluation of learning media for students. And the development of this learning media use the ADDIE development model (analysis, design, development, implementation, evaluation) to design language and automata theory applications learning so can be support the learning process for students and then assist lecturer to explain the material more dynamic and applicative.

APA, Harvard, Vancouver, ISO, and other styles

23

KUTRIB, MARTIN, ANDREAS MALCHER, and MATTHIAS WENDLANDT. "SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA." International Journal of Foundations of Computer Science 25, no. 07 (2014): 877–96. http://dx.doi.org/10.1142/s0129054114400139.

Full text

Abstract:

We investigate the descriptional complexity of deterministic one-way multi-head finite automata accepting unary languages. It is known that in this case the languages accepted are regular. Thus, we study the increase of the number of states when an n-state k-head finite automaton is simulated by a classical (one-head) deterministic or nondeterministic finite automaton. In the former case upper and lower bounds that are tight in the order of magnitude are shown. For the latter case we obtain an upper bound of O(n2k) and a lower bound of Ω(nk) states. We investigate also the costs for the conversion of one-head nondeterministic finite automata to deterministic k-head finite automata, that is, we trade nondeterminism for heads. In addition, we study how the conversion costs vary in the special case of finite and, in particular, of singleton unary lanuages. Finally, as an application of the simulation results, we show that decidability problems for unary deterministic k-head finite automata such as emptiness or equivalence are LOGSPACE-complete.

APA, Harvard, Vancouver, ISO, and other styles

24

Hospodár, Michal, and Galina Jirásková. "The complexity of concatenation on deterministic and alternating finite automata." RAIRO - Theoretical Informatics and Applications 52, no. 2-3-4 (2018): 153–68. http://dx.doi.org/10.1051/ita/2018011.

Full text

Abstract:

We study the state complexity of the concatenation operation on regular languages represented by deterministic and alternating finite automata. For deterministic automata, we show that the upper bound m2n − k2n−1 on the state complexity of concatenation can be met by ternary languages, the first of which is accepted by an m-state DFA with k final states, and the second one by an n-state DFA with ℓ final states for arbitrary integers m, n, k, ℓ with 1 ≤ k ≤ m − 1 and 1 ≤ ℓ ≤ n − 1. In the case of k ≤ m − 2, we are able to provide appropriate binary witnesses. In the case of k = m − 1 and ℓ ≥ 2, we provide a lower bound which is smaller than the upper bound just by one. We use our binary witnesses for concatenation on deterministic automata to describe binary languages meeting the upper bound 2m + n + 1 for the concatenation on alternating finite automata. This solves an open problem stated by Fellah et al. [Int. J. Comput. Math. 35 (1990) 117–132].

APA, Harvard, Vancouver, ISO, and other styles

25

Hospodár, Michal, Galina Jirásková, and Peter Mlynárčik. "Descriptional Complexity of the Forever Operator." International Journal of Foundations of Computer Science 30, no. 01 (2019): 115–34. http://dx.doi.org/10.1142/s0129054119400069.

Full text

Abstract:

We examine the descriptional complexity of the forever operator, which assigns the language [Formula: see text] to a regular language [Formula: see text], and we investigate the trade-offs between various models of finite automata. We consider complete and partial deterministic finite automata, nondeterministic finite automata with single or multiple initial states, alternating, and Boolean finite automata. We assume that the argument and the result of this operation are accepted by automata belonging to one of these six models. We investigate all possible trade-offs and provide a tight upper bound for 32 of 36 of them. The most interesting result is the trade-off from nondeterministic to deterministic automata given by the Dedekind number [Formula: see text]. We also prove that the nondeterministic state complexity of [Formula: see text] is [Formula: see text] which solves an open problem stated by Birget [The state complexity of [Formula: see text] and its connection with temporal logic, Inform. Process. Lett. 58 (1996) 185–188].

APA, Harvard, Vancouver, ISO, and other styles

26

Abe, Naoki. "Learning commutative deterministic finite state automata in polynomial time." New Generation Computing 8, no. 4 (1991): 319–35. http://dx.doi.org/10.1007/bf03037090.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Omlin, Christian W., and C. Lee Giles. "Constructing deterministic finite-state automata in recurrent neural networks." Journal of the ACM 43, no. 6 (1996): 937–72. http://dx.doi.org/10.1145/235809.235811.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Bubenzer, Johannes. "Cycle-aware minimization of acyclic deterministic finite-state automata." Discrete Applied Mathematics 163 (January 2014): 238–46. http://dx.doi.org/10.1016/j.dam.2013.08.003.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Lapin, Eduard S., and Marat I. Abdrakhmanov. "Functional approach to deterministic finite-state automata systems dynamic modeling." Izvestiya vysshikh uchebnykh zavedenii. Gornyi zhurnal 1 (March 30, 2021): 113–22. http://dx.doi.org/10.21440/0536-1028-2021-2-113-122.

Full text

Abstract:

Research aim is to study the functional approach to modeling the deterministic finite-state automata system which is not confined to the elements communication topology and the heterogeneity of the algorithm types. Relevance. The substantial part of engineering systems applied in the mining industry may be described through the finite-state automaton model. They include the mine conveyor systems, shaft signal systems, processing facilities control systems, etc. Such model makes it possible to shorten the time spent on control software development and carry out algorithm analysis, debug, and testing effectively. There are a lot of effective approaches and tools to solve the problem of finite-state automata dynamic modeling, each of which has its own advantages and disadvantages. Methodology. In this article, the methodology of finite-state automata systems modeling is considered as applied to mine conveyor systems. Results. Final-state automata (FSA) models have been developed together with the conditions for FSA systems dynamic modeling as applied to mine conveyor systems. Conclusions. The considered approach to modeling, which involves functors and applicative functors 122 "Izvestiya vysshikh uchebnykh zavedenii. Gornyi zhurnal". No. 2. 2021 ISSN 0536-1028 for structure composition and its operational dynamics study, as well as the possibility to mathematically prove the model’s properties, makes the approach a good alternative when choosing tools for systems models development.

APA, Harvard, Vancouver, ISO, and other styles

30

JEŻ, ARTUR, and ANDREAS MALETTI. "HYPER-MINIMIZATION FOR DETERMINISTIC TREE AUTOMATA." International Journal of Foundations of Computer Science 24, no. 06 (2013): 815–30. http://dx.doi.org/10.1142/s0129054113400200.

Full text

Abstract:

Hyper-minimization is a recent automaton compression technique that can reduce the size of an automaton beyond the limits imposed by classical minimization. The additional compression power is enabled by allowing a finite difference in the represented language. The necessary theory for hyper-minimization is developed for (bottom-up) deterministic tree automata. The hyper-minimization problem for deterministic tree automata is reduced to the hyper-minimization problem for deterministic finite-state string automata, for which fast algorithms exist. The fastest algorithm obtained in this way runs in time [Formula: see text], where m is the size of the transition table and n is the number of states of the input tree automaton.

APA, Harvard, Vancouver, ISO, and other styles

31

GRUBER, HERMANN, and MARKUS HOLZER. "PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA." International Journal of Foundations of Computer Science 24, no. 08 (2013): 1255–79. http://dx.doi.org/10.1142/s0129054113500330.

Full text

Abstract:

Based on recent results from extremal graph theory, we prove that every n-state binary deterministic finite automaton can be converted into an equivalent regular expression of size O(1.742n) using state elimination. Furthermore, we give improved upper bounds on the language operations intersection and interleaving on regular expressions.

APA, Harvard, Vancouver, ISO, and other styles

32

Asrun, Budyanita, and Irmayani Irmayani. "Klasifikasi Stadium Kanker Serviks Menggunakan Non-Deterministic Finite State Automata." Dewantara Journal of Technology 2, no. 2 (2021): 75–78. http://dx.doi.org/10.59563/djtech.v2i2.135.

Full text

Abstract:

Kanker serviks atau kanker leher rahim adalah suatu penyakit yang menyerang sistem reproduksi pada wanita.Kanker ini adalah kanker yang terjadi pada area leher rahim yaitu bagian rahim yang menghubungkan rahim bagian atas dengan vagina. Kanker serviks disebabkan infeksi virus HPV(Human Papilloma Virus) atau virus papiloma manusia. HPV menimbulkan kutil pada pria maupun wanita, termasuk kutil pada kelamin yang disebut kondiloma akuminatum. Hanya beberapa saja dari ratusan varian HPV yang dapat menyebabkan kanker.Kanker serviks atau kanker leher rahim bisa terjadi jika terjadi infeksi yang tidak sembuh-sembuh untuk waktu lama. Sebaliknya, kebanyakan infeksi HPV akan hilang sendiri, teratasi oleh sistem kekebalan tubuh. Konsep Automata dapat diterapkan dalam membantu memprediksi diagnosa awal tingkat stadium kanker serviks yang diderita oleh pasien berdasarkan keluhan yang diderita oleh pasien. Penelitian ini akan menghasilkan output tingkat klasifikasi stadium kanker. Penerapan automata digunakan untuk mengenal dan menangkap pola. Adapun dalam merancang dan mendesain digunakan model Non-Deterministic Finite State Automata (NFA).

APA, Harvard, Vancouver, ISO, and other styles

33

Camacho, Alberto, Jorge Baier, Christian Muise, and Sheila McIlraith. "Finite LTL Synthesis as Planning." Proceedings of the International Conference on Automated Planning and Scheduling 28 (June 15, 2018): 29–38. http://dx.doi.org/10.1609/icaps.v28i1.13908.

Full text

Abstract:

LTL synthesis is the task of generating a strategy that satisfies a Linear Temporal Logic (LTL) specification interpreted over infinite traces. In this paper we examine the problem of LTLf synthesis, a variant of LTL synthesis where the specification of the behaviour of the strategy we generate is interpreted over finite traces -- similar to the assumption we make in many planning problems, and important for the synthesis of business processes and other system interactions of finite duration. Existing approaches to LTLf synthesis transform LTLf into deterministic finite-state automata (DFA) and reduce the synthesis problem to a DFA game. Unfortunately, the DFA transformation is worst-case double-exponential in the size of the formula, presenting a computational bottleneck. In contrast, our approach exploits non-deterministic automata, and we reduce the synthesis problem to a non-deterministic planning problem. We leverage our approach not only for strategy generation but also to generate certificates of unrealizability -- the first such method for LTLf. We employ a battery of techniques that exploit the structure of the LTLf specification to improve the efficiency of our transformation to automata. We combine these techniques with lazy determinization of automata and on-the-fly state abstraction. We illustrate the effectiveness of our approach on a set of established LTL synthesis benchmarks adapted to finite LTL.

APA, Harvard, Vancouver, ISO, and other styles

34

G., Mutyalamma, Komali K., and Pushpa G. "A Novel Algorithm for Reduction of Non Deterministic Finite Automata." International Journal of Trend in Scientific Research and Development 2, no. 1 (2017): 1341–46. https://doi.org/10.31142/ijtsrd8233.

Full text

Abstract:

In automata theory a minimization is the task of transforming a given finite state machine into an equivalent automation that has a minimum number of states. Here, the reduction of Deterministic Finite Automata DFA is very simple whereas Nondeterministic Finite Automata NFA is complex because which has maximium number of possible paths to reach new states. So a minimal NFA is a primal problem in automata theory. We consider the problem of approximating a minimal NFA or a minimal regular expression. There are several approaches to NFA minimization either without approximation guarantees or running in at least exponential time. Here this paper introducing the new NFA reduction algorithm for the minimization of NFA. This algorithm will reduce number of state transitions of Nondeterministic Finite Automata. NFA reduction algorithm also resolves the complexity of Kameda Weiner algorithm. This paper shown empirically that this algorithm is effective in largely reducing the memory requirement of NFA minimization algorithm. Reducing the size of NFA by using NFA Reduction Algorithm has been shown to reduce importantly the search time. G. Mutyalamma | K. Komali | G. Pushpa "A Novel Algorithm for Reduction of Non-Deterministic Finite Automata" Published in International Journal of Trend in Scientific Research and Development (ijtsrd), ISSN: 2456-6470, Volume-2 | Issue-1 , December 2017, URL: https://www.ijtsrd.com/papers/ijtsrd8233.pdf

APA, Harvard, Vancouver, ISO, and other styles

35

Dobronravov, Egor, Nikita Dobronravov, and Alexander Okhotin. "On the Length of Shortest Strings Accepted by Two-way Finite Automata." Fundamenta Informaticae 180, no. 4 (2021): 315–31. http://dx.doi.org/10.3233/fi-2021-2044.

Full text

Abstract:

Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10n/5) and less than (2nn+1), with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least e(1+o(1))mn(log n− log m).

APA, Harvard, Vancouver, ISO, and other styles

36

VAN ZIJL, LYNETTE. "MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS." International Journal of Foundations of Computer Science 16, no. 05 (2005): 1027–38. http://dx.doi.org/10.1142/s0129054105003455.

Full text

Abstract:

Iwama et al. showed that there exists an n-state binary nondeterministic finite automaton such that its equivalent minimal deterministic finite automaton has exactly 2n - α states, for all n ≥ 7 and 5 ≤ α ≤ 2n-2, subject to certain coprimality conditions. We investigate the same question for both unary and binary symmetric difference nondeterministic finite automata. In the binary case, we show that for any n ≥ 4, there is an n-state symmetric difference nondeterministic finite automaton for which the equivalent minimal deterministic finite automaton has 2n - 1 + 2k - 1 - 1 states, for 2 < k ≤ n - 1. In the unary case, we consider a large practical subclass of unary symmetric difference nondeterministic finite automata: for all n ≥ 2, we argue that there are many values of α such that there is no n-state unary symmetric difference nondeterministic finite automaton with an equivalent minimal deterministic finite automaton with 2n - α states, where 0 < α < 2n - 1. For each n ≥ 2, we quantify such values of α precisely.

APA, Harvard, Vancouver, ISO, and other styles

37

Marzen, Sarah E., and James P. Crutchfield. "Probabilistic Deterministic Finite Automata and Recurrent Networks, Revisited." Entropy 24, no. 1 (2022): 90. http://dx.doi.org/10.3390/e24010090.

Full text

Abstract:

Reservoir computers (RCs) and recurrent neural networks (RNNs) can mimic any finite-state automaton in theory, and some workers demonstrated that this can hold in practice. We test the capability of generalized linear models, RCs, and Long Short-Term Memory (LSTM) RNN architectures to predict the stochastic processes generated by a large suite of probabilistic deterministic finite-state automata (PDFA) in the small-data limit according to two metrics: predictive accuracy and distance to a predictive rate-distortion curve. The latter provides a sense of whether or not the RNN is a lossy predictive feature extractor in the information-theoretic sense. PDFAs provide an excellent performance benchmark in that they can be systematically enumerated, the randomness and correlation structure of their generated processes are exactly known, and their optimal memory-limited predictors are easily computed. With less data than is needed to make a good prediction, LSTMs surprisingly lose at predictive accuracy, but win at lossy predictive feature extraction. These results highlight the utility of causal states in understanding the capabilities of RNNs to predict.

APA, Harvard, Vancouver, ISO, and other styles

38

Nagy, Benedek, and Zita Kovács. "On deterministic 1-limited 5′ → 3′ sensing Watson–Crick finite-state transducers." RAIRO - Theoretical Informatics and Applications 55 (2021): 5. http://dx.doi.org/10.1051/ita/2021007.

Full text

Abstract:

Finite automata and finite state transducers belong to the bases of (theoretical) computer science with many applications. On the other hand, DNA computing and related bio-inspired paradigms are relatively new fields of computing. Watson–Crick automata are in the intersection of the above fields. These finite automata have two reading heads as they read the upper and lower strands of the input DNA molecule, respectively. In 5′ → 3′ Watson–Crick automata the two reading heads move in the same biochemical direction, that is, from the 5′ end of the strand to the direction of the 3′ end. However, in the double-stranded DNA, the DNA strands are directed in opposite way to each other, therefore 5′ → 3′ Watson–Crick automata read the input from the two extremes. In sensing 5′ → 3′ automata the automata sense if the two heads are at the same position, moreover, the computing process is finished at that time. Based on this class of automata, we define WK transducers such that, at each transition, exactly one input letter is being processed, and exactly one output letter is written on a normal output tape. Some special cases are defined and analyzed, e.g., when only one of the reading heads is being used and when the transducer has only one state. We also show that the minimal transducer is uniquely defined if the transducer is deterministic and it has marked output, i.e., the output letter written in a step identifies the reading head that is used in that transition. We have also used the functions ‘processing order’ and ‘reading heads’ to analyze these transducers.

APA, Harvard, Vancouver, ISO, and other styles

39

Lediwara, Nadiza, Aulia Khamas Heikmakhtiar, Sembada Denrineksa Bimorogo, Alfian Habib Ahmed, and Rizki Yulian Agusti. "Implementation of Finite State Automata to Simulation of Automatic Clothes-Folding." Jurnal Teknologi Sistem Informasi dan Aplikasi 6, no. 4 (2023): 783–87. http://dx.doi.org/10.32493/jtsi.v6i4.34226.

Full text

Abstract:

Inconsistencies and differences clothes-folding methods are often a major problem in the military. Everyone has thier method to fold and their method is still traditional. Besides, the neatness of the clothes in the military is emphasized. This method certainly took up their time and energy then the folding was different to each other. To solve this problem, a simulation machine is made to fold the clothes automatically. This system works using Finite State Automa type Non-Deterministic Finite Automata. Finite State Automata are used because they are simple and do not require storage space. The result of this research is a design of an automatic clothes-folding that can be implemented properly and correctly for UNHAN RI’s students. This automatic clothes-folding has succeeded to create consistent folds even though user tried with different clothes.

APA, Harvard, Vancouver, ISO, and other styles

40

Kuperberg, Denis, Laureline Pinault, and Damien Pous. "Coinductive Algorithms for Büchi Automata." Fundamenta Informaticae 180, no. 4 (2021): 351–73. http://dx.doi.org/10.3233/fi-2021-2046.

Full text

Abstract:

We propose a new algorithm for checking language equivalence of non-deterministic Büchi automata. We start from a construction proposed by Calbrix, Nivat and Podelski, which makes it possible to reduce the problem to that of checking equivalence of automata on finite words. Although this construction generates large and highly non-deterministic automata, we show how to exploit their specific structure and apply state-of-the art techniques based on coinduction to reduce the state-space that has to be explored. Doing so, we obtain algorithms which do not require full determinisation or complementation.

APA, Harvard, Vancouver, ISO, and other styles

41

Carrasco, Rafael C., and Mikel L. Forcada. "Incremental Construction and Maintenance of Minimal Finite-State Automata." Computational Linguistics 28, no. 2 (2002): 207–16. http://dx.doi.org/10.1162/089120102760173652.

Full text

Abstract:

Daciuk et al. [Computational Linguistics 26(1):3–16 (2000)] describe a method for constructing incrementally minimal, deterministic, acyclic finite-state automata (dictionaries) from sets of strings. But acyclic finite-state automata have limitations: For instance, if one wants a linguistic application to accept all possible integer numbers or Internet addresses, the corresponding finite-state automaton has to be cyclic. In this article, we describe a simple and equally efficient method for modifying any minimal finite-state automaton (be it acyclic or not) so that a string is added to or removed from the language it accepts; both operations are very important when dictionary maintenance is performed and solve the dictionary construction problem addressed by Daciuk et al. as a special case. The algorithms proposed here may be straightforwardly derived from the customary textbook constructions for the intersection and the complementation of finite-state automata; the algorithms exploit the special properties of the automata resulting from the intersection operation when one of the finite-state automata accepts a single string.

APA, Harvard, Vancouver, ISO, and other styles

42

Li, Zhi, Harm Derksen, Jonathan Gryak, et al. "Prediction of cardiac arrhythmia using deterministic probabilistic finite-state automata." Biomedical Signal Processing and Control 63 (January 2021): 102200. http://dx.doi.org/10.1016/j.bspc.2020.102200.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Tresoldi, Tiago. "DAFSA: a Python library for Deterministic Acyclic Finite State Automata." Journal of Open Source Software 5, no. 46 (2020): 1986. http://dx.doi.org/10.21105/joss.01986.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Daciuk, Jan, Stoyan Mihov, Bruce W. Watson, and Richard E. Watson. "Incremental Construction of Minimal Acyclic Finite-State Automata." Computational Linguistics 26, no. 1 (2000): 3–16. http://dx.doi.org/10.1162/089120100561601.

Full text

Abstract:

In this paper, we describe a new method for constructing minimal, deterministic, acyclic finite-state automata from a set of strings. Traditional methods consist of two phases: the first to construct a trie, the second one to minimize it. Our approach is to construct a minimal automaton in a single phase by adding new strings one by one and minimizing the resulting automaton on-the-fly. We present a general algorithm as well as a specialization that relies upon the lexicographical ordering of the input strings. Our method is fast and significantly lowers memory requirements in comparison to other methods.

APA, Harvard, Vancouver, ISO, and other styles

45

Singh, Rashandeep, and Dr Gulshan Goyal. "Algorithm Design for Deterministic Finite Automata for a Given Regular Language with Prefix Strings." Journal of Scientific Research 66, no. 02 (2022): 16–21. http://dx.doi.org/10.37398/jsr.2022.660203.

Full text

Abstract:

Computer Science and Engineering have given us the field of automata theory, one of the largest areas that is concerned with the efficiency of an algorithm in solving a problem on a computational model. Various classes of formal languages are represented using Chomsky hierarchy. These languages are described as a set of specific strings over a given alphabet and can be described using state or transition diagrams. The state/transition diagram for regular languages is called a finite automaton which is used in compiler design for recognition of tokens. Other applications of finite automata include pattern matching, speech and text processing, CPU machine operations, etc. The construction of finite automata is a complicated and challenging process as there is no fixed mathematical approach that exists for designing Deterministic Finite Automata (DFA) and handling the validations for acceptance or rejection of strings. Consequently, it is difficult to represent the DFA’s transition table and graph. Novel learners in the field of theoretical computer science often feel difficulty in designing of DFA The present paper proposes an algorithm for designing of deterministic finite automata (DFA) for a regular language with a given prefix. The proposed method further aims to simplify the lexical analysis process of compiler design.

APA, Harvard, Vancouver, ISO, and other styles

46

BORDIHN, HENNING, MARTIN KUTRIB, and ANDREAS MALCHER. "UNDECIDABILITY AND HIERARCHY RESULTS FOR PARALLEL COMMUNICATING FINITE AUTOMATA." International Journal of Foundations of Computer Science 22, no. 07 (2011): 1577–92. http://dx.doi.org/10.1142/s0129054111008891.

Full text

Abstract:

Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes.

APA, Harvard, Vancouver, ISO, and other styles

47

Puram, Varun teja, K. M. George, and Johnson P. Thomas. "Quantum Representation for Deterministic Push-Down Automata." Electronics 13, no. 22 (2024): 4531. http://dx.doi.org/10.3390/electronics13224531.

Full text

Abstract:

There are many papers presenting quantum computing models. The definitions parallel the classical definitions of finite state automata, push-down automata, context-free grammars, etc. Classical computing model definitions define languages precisely. We can state that a string belongs to a language or does not belong to it with no room for error. Quantum definitions do not possess this certainty. Sacrificing the certainty and adopting a quantum definition of a computing model does not appear to provide any concrete power to the model. Therefore, the path of this paper is to begin from the classical definition and end in a quantum circuit. In this paper, we start from a deterministic push-down automaton (DPDA). We present circuits for state transition and stack operations. The circuits presented can be viewed as independent algorithms. As an example, the approach used to construct the circuit for state transition can be utilized to build the circuit for a function presented as a Boolean matrix.

APA, Harvard, Vancouver, ISO, and other styles

48

ÉSIK, ZOLTÁN. "ORDINAL AUTOMATA AND CANTOR NORMAL FORM." International Journal of Foundations of Computer Science 23, no. 01 (2012): 87–98. http://dx.doi.org/10.1142/s0129054112400060.

Full text

Abstract:

It is known that an ordinal is the order type of the lexicographic ordering of a regular language if and only if it is less than ωω. We design a polynomial time algorithm that constructs, for each well-ordered regular language L with respect to the lexicographic ordering, given by a deterministic finite automaton, the Cantor Normal Form of its order type. It follows that there is a polynomial time algorithm to decide whether two deterministic finite automata accepting well-ordered regular languages accept isomorphic languages. We also give estimates on the state complexity of the smallest "ordinal automaton" representing an ordinal less than ωω, together with an algorithm that translates each such ordinal to an automaton.

APA, Harvard, Vancouver, ISO, and other styles

49

Salomaa, Arto, Kai Salomaa, and Taylor J. Smith. "Descriptional Complexity of Finite Automata – Selected Highlights." Fundamenta Informaticae 191, no. 3-4 (2024): 231–37. http://dx.doi.org/10.3233/fi-242180.

Full text

Abstract:

The state complexity, respectively, nondeterministic state complexity of a regular language L is the number of states of the minimal deterministic, respectively, of a minimal nondeterministic finite automaton for L. Some of the most studied state complexity questions deal with size comparisons of nondeterministic finite automata of differing degree of ambiguity. More generally, if for a regular language we compare the size of description by a finite automaton and by a more powerful language definition mechanism, such as a context-free grammar, we encounter non-recursive trade-offs. Operational state complexity studies the state complexity of the language resulting from a regularity preserving operation as a function of the complexity of the argument languages. Determining the state complexity of combined operations is generally challenging and for general combinations of operations that include intersection and marked concatenation it is uncomputable.

APA, Harvard, Vancouver, ISO, and other styles

50

MALETTI, ANDREAS, and DANIEL QUERNHEIM. "OPTIMAL HYPER-MINIMIZATION." International Journal of Foundations of Computer Science 22, no. 08 (2011): 1877–91. http://dx.doi.org/10.1142/s0129054111009094.

Full text

Abstract:

Minimal deterministic finite automata (DFAs) can be reduced further at the expense of a finite number of errors. Recently, such minimization algorithms have been improved to run in time O(n log n), where n is the number of states of the input DFA, by [GAWRYCHOWSKI and JEŻ: Hyper-minimisation made efficient. Proc. MFCS, LNCS 5734, 2009] and [HOLZER and MALETTI: An n log n algorithm for hyper-minimizing a (minimized) deterministic automaton. Theor. Comput. Sci. 411, 2010]. Both algorithms return a DFA that is as small as possible, while only committing a finite number of errors. These algorithms are further improved to return a DFA that commits the least number of errors at the expense of an increased (quadratic) run-time. This solves an open problem of [BADR, GEFFERT, and SHIPMAN: Hyper-minimizing minimized deterministic finite state automata. RAIRO Theor. Inf. Appl. 43, 2009]. In addition, an experimental study on random automata is performed and the effects of the existing algorithms and the new algorithm are reported.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Deterministic finite state automata'

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