Log in

Relevant bibliographies by topics / Deterministic Finite Automata / Journal articles

To see the other types of publications on this topic, follow the link: Deterministic Finite Automata.

Journal articles on the topic 'Deterministic Finite Automata'

Author: Grafiati

Published: 4 June 2021

Last updated: 6 September 2023

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

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Deterministic Finite Automata.'

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

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

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

de Castro, Amaury Antonio, Joao Jose Neto, and Hemerson Pistori. "Deterministic Adaptive Finite Automata." IEEE Latin America Transactions 5, no. 7 (2007): 515–21. http://dx.doi.org/10.1109/t-la.2007.4445750.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

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

3

HUYNH, DUNG T. "THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS." International Journal of Algebra and Computation 02, no. 01 (1992): 39–55. http://dx.doi.org/10.1142/s0218196792000050.

Full text

Abstract:

In this paper, we study the complexity of deciding code and monoid properties for regular sets specified by deterministic or nondeterministic finite automata. The results are as follows. The code problem for regular sets specified by deterministic or nondeterministic finite automata is NL-complete under NC(1) reducibilities. The problems of determining whether a regular set given by a deterministic finite automaton is a monoid or a free monoid or a finitely generated monoid are all NL-complete under NC(1) reducibilities. These monoid problems become PSPACE-complete if the regular sets are specified by nondeterministic finite automata instead. The maximal code problem for deterministic finite automata is shown to be in DET and NL-hard, while a PSPACE upper bound and NP-hardness lower bound hold for the case of nondeterministic finite automata.

APA, Harvard, Vancouver, ISO, and other styles

4

Kutrib, Martin, Andreas Malcher, and Matthias Wendlandt. "Set Automata." International Journal of Foundations of Computer Science 27, no. 02 (2016): 187–214. http://dx.doi.org/10.1142/s0129054116400062.

Full text

Abstract:

We consider the model of deterministic set automata which are basically deterministic finite automata equipped with a set as an additional storage medium. The basic operations on the set are the insertion of elements, the removing of elements, and the test whether an element is in the set. We investigate the computational power of deterministic set automata and compare the language class accepted with the context-free languages and classes of languages accepted by queue automata. As result the incomparability to all classes considered is obtained. Furthermore, we examine the closure properties under several operations. Then we show that deterministic set automata may be an interesting model from a practical point of view by proving that their regularity problem as well as the problems of emptiness, finiteness, infiniteness, and universality are decidable. Finally, the descriptional complexity of deterministic and nondeterministic set automata is investigated. A conversion procedure that turns a deterministic set automaton accepting a regular language into a deterministic finite automaton is developed which leads to a double exponential upper bound. This bound is proved to be tight in the order of magnitude by presenting also a double exponential lower bound. In contrast to these recursive bounds we obtain non-recursive trade-offs when nondeterministic set automata are considered.

APA, Harvard, Vancouver, ISO, and other styles

5

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

6

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

7

Campeanu, Cezar. "Non-Deterministic Finite Cover Automata." Scientific Annals of Computer Science 25, no. 1 (2015): 3–28. http://dx.doi.org/10.7561/sacs.2015.1.3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Ron, Dana, and Ronitt Rubinfeld. "Learning fallible Deterministic Finite Automata." Machine Learning 18, no. 2-3 (1995): 149–85. http://dx.doi.org/10.1007/bf00993409.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

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

11

Ďuriš, Pavol. "On Computational Power of Partially Blind Automata." Journal of Applied Mathematics, Statistics and Informatics 8, no. 1 (2012): 33–41. http://dx.doi.org/10.2478/v10294-012-0003-5.

Full text

Abstract:

On Computational Power of Partially Blind Automata In this paper we deal with 1-way multihead finite automata, in which the symbol under only one head (called read head) controls its move and other heads cannot distinguish the input symbols, they can only distinguish the end-marker from the other input symbols and they are called the blind head. We call such automaton a partially blind multihead automaton. We prove that partially blind k + 1-head finite automata are more powerful than such k-head finite automata. We show also that nondeterministic partially blind k-head finite automata languages are not closed under iteration and intersection for any k ≥ 2, and moreover, deterministic partially blind k head finite automata languages are not closed under intersection, union, complementation and reversal for any k ≥ 2. Finally we prove that deterministic partially blind k-head finite automata with endmarker are more powerful that such automata without endmarker for each k ≥ 4.

APA, Harvard, Vancouver, ISO, and other styles

12

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Ganty, Pierre, Elena Gutiérrez, and Pedro Valero. "A Congruence-Based Perspective on Finite Tree Automata." Fundamenta Informaticae 184, no. 1 (2022): 1–47. http://dx.doi.org/10.3233/fi-2021-2091.

Full text

Abstract:

We provide new insights on the determinization and minimization of tree automata using congruences on trees. From this perspective, we study a Brzozowski’s style minimization algorithm for tree automata. First, we prove correct this method relying on the following fact: when the automata-based and the language-based congruences coincide, determinizing the automaton yields the minimal one. Such automata-based congruences, in the case of word automata, are defined using pre and post operators. Now we extend these operators to tree automata, a task that is particularly challenging due to the reduced expressive power of deterministic top-down (or equivalently co-deterministic bottom-up) automata. We leverage further our framework to offer an extension of the original result by Brzozowski for word automata.

APA, Harvard, Vancouver, ISO, and other styles

14

KAMINSKI, MICHAEL, and DANIEL ZEITLIN. "FINITE-MEMORY AUTOMATA WITH NON-DETERMINISTIC REASSIGNMENT." International Journal of Foundations of Computer Science 21, no. 05 (2010): 741–60. http://dx.doi.org/10.1142/s0129054110007532.

Full text

Abstract:

In this paper we extend finite-memory automata with non-deterministic reassignment that allows an automaton to "guess" the future content of its registers, and introduce the corresponding notion of a regular expression over an infinite alphabet.

APA, Harvard, Vancouver, ISO, and other styles

15

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

16

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

17

Vayadande, Kuldeep, Krisha Patel, Nikita Punde, Shreyash Patil, Srushti Nikam, and Sudhanshu Pathrabe. "Non-Deterministic Finite Automata to Deterministic Finite Automata Conversion by Subset Construction Method using Python." International Journal of Computer Sciences and Engineering 10, no. 1 (2022): 1–5. http://dx.doi.org/10.26438/ijcse/v10i1.15.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Bordihn, Henning, and György Vaszil. "Reversible parallel communicating finite automata systems." Acta Informatica 58, no. 4 (2021): 263–79. http://dx.doi.org/10.1007/s00236-021-00396-9.

Full text

Abstract:

AbstractWe study the concept of reversibility in connection with parallel communicating systems of finite automata (PCFA in short). We define the notion of reversibility in the case of PCFA (also covering the non-deterministic case) and discuss the relationship of the reversibility of the systems and the reversibility of its components. We show that a system can be reversible with non-reversible components, and the other way around, the reversibility of the components does not necessarily imply the reversibility of the system as a whole. We also investigate the computational power of deterministic centralized reversible PCFA. We show that these very simple types of PCFA (returning or non-returning) can recognize regular languages which cannot be accepted by reversible (deterministic) finite automata, and that they can even accept languages that are not context-free. We also separate the deterministic and non-deterministic variants in the case of systems with non-returning communication. We show that there are languages accepted by non-deterministic centralized PCFA, which cannot be recognized by any deterministic variant of the same type.

APA, Harvard, Vancouver, ISO, and other styles

19

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

20

Maryanto, Eddy. "AUTOMATA SEBAGAI MODEL PENGENAL BAHASA." Jurnal Ilmiah Matematika dan Pendidikan Matematika 1, no. 2 (2009): 53. http://dx.doi.org/10.20884/1.jmp.2009.1.2.2981.

Full text

Abstract:

A deterministic finite automaton as well a nondeterministic finite automaton can be used to model a language recognizer. In computer software technology, language recognizer usually be an integrated part of a compiler, that is a computer program that take responsibility to translate source code into machine code. Comparing with a deterministic finite automaton, a nondeterministic finite automaton is a better model for language recognizer because it might be simpler and less in size than a deterministic one.

APA, Harvard, Vancouver, ISO, and other styles

21

Zhang, Meng, Yi Zhang, Wei Lv, and Chen Hou. "Compacted Implementations of Deterministic Finite Automata." Journal of Computational and Theoretical Nanoscience 11, no. 3 (2014): 893–98. http://dx.doi.org/10.1166/jctn.2014.3443.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

Fleischer, Lukas, and Manfred Kufleitner. "Green’s Relations in Deterministic Finite Automata." Theory of Computing Systems 63, no. 4 (2018): 666–87. http://dx.doi.org/10.1007/s00224-018-9847-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Berlinkov, Mikhail V., Robert Ferens, and Marek Szykuła. "Preimage problems for deterministic finite automata." Journal of Computer and System Sciences 115 (February 2021): 214–34. http://dx.doi.org/10.1016/j.jcss.2020.08.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Chigahara, Hiroyuki, Szilárd Zsolt Fazekas, and Akihiro Yamamura. "One-Way Jumping Finite Automata." International Journal of Foundations of Computer Science 27, no. 03 (2016): 391–405. http://dx.doi.org/10.1142/s0129054116400165.

Full text

Abstract:

We propose the one-way jumping finite automaton model, restricting the jumping relation of the recently introduced jumping finite automaton so that the machine can only jump over symbols it cannot process in its current state. The reading head of a one-way jumping finite automaton moves deterministically in one direction within the input word, whereas movement of the reading head of jumping finite automaton is non-deterministic. The class of languages accepted by one-way jumping finite automata is different from that of jumping finite automata, in particular, it includes all regular languages, as opposed to the latter. We study one-way jumping finite automata and obtain closure properties, a pumping lemma, and separation results with respect to the classical language classes of the Chomsky hierarchy.

APA, Harvard, Vancouver, ISO, and other styles

25

Sapunov, Seregy. "Collectives of automata on infinite grid graph with deterministic vertex labeling." Proceedings of the Institute of Applied Mathematics and Mechanics NAS of Ukraine 33 (December 27, 2019): 170–87. http://dx.doi.org/10.37069/1683-4720-2019-33-14.

Full text

Abstract:

Automata walking on graphs are a mathematical formalization of autonomous mobile agents with limited memory operating in discrete environments. Under this model broad area of studies of the behaviour of automata in finite and infinite labyrinths (a labyrinth is an embedded directed graph of special form) arose and intensively developing. Research in this regard received a wide range of applications, for example, in the problems of image analysis and navigation of mobile robots. Automata operating in labyrinths can distinguish directions, that is, they have a compass. This paper examines vertex labellings of infinite square grid graph thanks to these labellings a finite automaton without a compass can walk along graph in any arbitrary direction. The automaton looking over neighbourhood of the current vertex and may move to some neighbouring vertex selected by its label. We propose a minimal deterministic traversable vertex labelling that satisfies the required property. A labelling is said to be deterministic if all vertices in closed neighbourhood of every vertex have different labels. It is shown that minimal deterministic traversable vertex labelling of square grid graph uses labels of five different types. Minimal deterministic traversable labelling of subgraphs of infinite square grid graph whose degrees are less than four are developed. The key problem for automata and labyrinths is the problem of constructing a finite automaton that traverse a given class of labyrinths. We say that automaton traverse infinite graph if it visits any randomly selected vertex of this graph in a finite time. It is proved that a collective of one automaton and three pebbles can traverse infinite square grid graph with deterministic labelling and any collective with fewer pebbles cannot. We consider pebbles as automata of the simplest form, whose positions are completely determined by the remaining automata of the collective. The results regarding to exploration of an infinite deterministic square grid graph coincide with the results of A.V. Andzhan (Andzans) regarding to traversal of an infinite mosaic labyrinth without holes. It follows from above that infinite grid graph after constructing a minimal traversable deterministic labelling on it and fixing two pairs of opposite directions on it becomes an analogue of an infinite mosaic labyrinth without holes.

APA, Harvard, Vancouver, ISO, and other styles

26

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

27

KÜÇÜK, UĞUR, A. C. CEM SAY, and ABUZER YAKARYILMAZ. "FINITE AUTOMATA WITH ADVICE TAPES." International Journal of Foundations of Computer Science 25, no. 08 (2014): 987–1000. http://dx.doi.org/10.1142/s012905411440019x.

Full text

Abstract:

We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.

APA, Harvard, Vancouver, ISO, and other styles

28

Paul, Erik. "Finite Sequentiality of Unambiguous Max-Plus Tree Automata." Theory of Computing Systems 65, no. 4 (2021): 736–76. http://dx.doi.org/10.1007/s00224-020-10021-w.

Full text

Abstract:

AbstractWe show the decidability of the finite sequentiality problem for unambiguous max-plus tree automata. A max-plus tree automaton is called unambiguous if there is at most one accepting run on every tree. The finite sequentiality problem asks whether for a given max-plus tree automaton, there exist finitely many deterministic max-plus tree automata whose pointwise maximum is equivalent to the given automaton.

APA, Harvard, Vancouver, ISO, and other styles

29

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

30

DASSOW, JÜRGEN, and VICTOR MITRANA. "FINITE AUTOMATA OVER FREE GROUPS." International Journal of Algebra and Computation 10, no. 06 (2000): 725–37. http://dx.doi.org/10.1142/s0218196700000315.

Full text

Abstract:

Finite automata are extended by adding an element of a given group to each of their configurations. An input string is accepted if and only if the neutral element of the group is associated to a final configuration reached by the automaton. We get a new characterization of the context-free languages as soon as the considered group is the binary free group. The result cannot be carried out in the deterministic case. Some remarks about finite automata over other groups are also presented.

APA, Harvard, Vancouver, ISO, and other styles

31

Axelsen, Holger Bock, Markus Holzer, and Martin Kutrib. "The Degree of Irreversibility in Deterministic Finite Automata." International Journal of Foundations of Computer Science 28, no. 05 (2017): 503–22. http://dx.doi.org/10.1142/s0129054117400044.

Full text

Abstract:

Recently, a method to decide the NL-complete problem of whether the language accepted by a given deterministic finite automaton (DFA) can also be accepted by some reversible deterministic finite automaton (REV-DFA) has been derived. Here, we show that the corresponding problem for nondeterministic finite automata (NFA) is PSPACE-complete. The recent DFA method essentially works by minimizing the DFA and inspecting it for a forbidden pattern. We here study the degree of irreversibility for a regular language, the minimal number of such forbidden patterns necessary in any DFA accepting the language, and show that the degree induces a strict infinite hierarchy of language families. We examine how the degree of irreversibility behaves under the usual language operations union, intersection, complement, concatenation, and Kleene star, showing tight bounds (some asymptotically) on the degree.

APA, Harvard, Vancouver, ISO, and other styles

32

Ouardi, Faissal, Zineb Lotfi, and Bilal Elghadyry. "Efficient Construction of the Equation Automaton." Algorithms 14, no. 8 (2021): 238. http://dx.doi.org/10.3390/a14080238.

Full text

Abstract:

This paper describes a fast algorithm for constructing directly the equation automaton from the well-known Thompson automaton associated with a regular expression. Allauzen and Mohri have presented a unified construction of small automata and gave a construction of the equation automaton with time and space complexity in O(mlogm+m2), where m denotes the number of Thompson automaton transitions. It is based on two classical automata operations, namely epsilon-removal and Hopcroft’s algorithm for deterministic Finite Automata (DFA) minimization. Using the notion of c-continuation, Ziadi et al. presented a fast computation of the equation automaton in O(m2) time complexity. In this paper, we design an output-sensitive algorithm combining advantages of the previous algorithms and show that its computational complexity can be reduced to O(m×|Q≡e|), where |Q≡e| denotes the number of states of the equation automaton, by an epsilon-removal and Bubenzer minimization algorithm of an Acyclic Deterministic Finite Automata (ADFA).

APA, Harvard, Vancouver, ISO, and other styles

33

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

34

Bruchertseifer, Jens, and Henning Fernau. "Synchronizing series-parallel deterministic finite automata with loops and related problems." RAIRO - Theoretical Informatics and Applications 55 (2021): 7. http://dx.doi.org/10.1051/ita/2021005.

Full text

Abstract:

We study the problem DFA-SW of determining if a given deterministic finite automaton A possesses a synchronizing word of length at most k for automata whose (multi-)graphs are TTSPL, i.e., series-parallel, plus allowing some self-loops. While DFA-SW remains NP-complete on TTSPL automata, we also find (further) restrictions with efficient (parameterized) algorithms. We also study the (parameterized) complexity of related problems, for instance, extension variants of the synchronizing word problem, or the problem of finding smallest alphabet-induced synchronizable sub-automata.

APA, Harvard, Vancouver, ISO, and other styles

35

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

36

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

37

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

38

Sarkar, Pratima, and Chinmoy Kar. "Adaptive E-learning using Deterministic Finite Automata." International Journal of Computer Applications 97, no. 21 (2014): 14–17. http://dx.doi.org/10.5120/17130-7712.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

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

40

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

41

Mateescu, Alexandru, and Gheorghe P[acaron]un. "On States Observability in Deterministic Finite Automata." International Journal of Computer Mathematics 21, no. 1 (1987): 17–30. http://dx.doi.org/10.1080/00207168708803554.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Grachev, Petr, Igor Lobanov, Ivan Smetannikov, and Andrey Filchenkov. "Neural network for synthesizing deterministic finite automata." Procedia Computer Science 119 (2017): 73–82. http://dx.doi.org/10.1016/j.procs.2017.11.162.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Melnikov, B. F., and A. A. Melnikova. "Edge-minimization of non-deterministic finite automata." Korean Journal of Computational & Applied Mathematics 8, no. 3 (2001): 469–79. http://dx.doi.org/10.1007/bf02941980.

Full text

APA, Harvard, Vancouver, ISO, and other styles

44

Freivalds, Rūsiņš. "Amount of nonconstructivity in deterministic finite automata." Theoretical Computer Science 411, no. 38-39 (2010): 3436–43. http://dx.doi.org/10.1016/j.tcs.2010.05.038.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Birkendorf, Andreas, Andreas Böker, and Hans Ulrich Simon. "Learning Deterministic Finite Automata from Smallest Counterexamples." SIAM Journal on Discrete Mathematics 13, no. 4 (2000): 465–91. http://dx.doi.org/10.1137/s0895480198340943.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Bhatia, Amandeep Singh, and Ajay Kumar. "On the power of two-way multihead quantum finite automata." RAIRO - Theoretical Informatics and Applications 53, no. 1-2 (2019): 19–35. http://dx.doi.org/10.1051/ita/2018020.

Full text

Abstract:

This paper introduces a variant of two-way quantum finite automata named two-way multihead quantum finite automata. A two-way quantum finite automaton is more powerful than classical two-way finite automata. However, the generalizations of two-way quantum finite automata have not been defined so far as compared to one-way quantum finite automata model. We have investigated the newly introduced automata from two aspects: the language recognition capability and its comparison with classical and quantum counterparts. It has been proved that a language which cannot be recognized by any one-way and multi-letter quantum finite automata can be recognized by two-way quantum finite automata. Further, it has been shown that a language which cannot be recognized by two-way quantum finite automata can be recognized by two-way multihead quantum finite automata with two heads. Furthermore, it has been investigated that quantum variant of two-way deterministic multihead finite automata takes less number of heads to recognize a language containing of all words whose length is a prime number.

APA, Harvard, Vancouver, ISO, and other styles

47

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

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

FREIVALDS, RŪSIŅŠ. "NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA." International Journal of Foundations of Computer Science 19, no. 03 (2008): 565–80. http://dx.doi.org/10.1142/s0129054108005826.

Full text

Abstract:

Size (the number of states) of finite probabilistic automata with an isolated cut-point can be exponentially smaller than the size of any equivalent finite deterministic automaton. However, the proof is non-constructive. The result is presented in two versions. The first version depends on Artin's Conjecture (1927) in Number Theory. The second version does not depend on conjectures not proved but the numerical estimates are worse. In both versions the method of the proof does not allow an explicit description of the languages used. Since our finite probabilistic automata are reversible, these results imply a similar result for quantum finite automata.

APA, Harvard, Vancouver, ISO, and other styles

50

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

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!