Log in

Relevant bibliographies by topics / Minimal Acyclic Deterministic Finite Automaton

Contents

Journal articles

Academic literature on the topic 'Minimal Acyclic Deterministic Finite Automaton'

Author: Grafiati

Published: 4 June 2021

Last updated: 9 February 2022

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

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Minimal Acyclic Deterministic Finite Automaton.'

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

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

Journal articles on the topic "Minimal Acyclic Deterministic Finite Automaton"

1

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 ot

APA, Harvard, Vancouver, ISO, and other styles

2

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 remo

APA, Harvard, Vancouver, ISO, and other styles

3

Daciuk, Jan. "Comments on “Incremental Construction and Maintenance of Minimal Finite-State Automata,” by Rafael C. Carrasco and Mikel L. Forcada." Computational Linguistics 30, no. 2 (2004): 227–35. http://dx.doi.org/10.1162/089120104323093302.

Full text

Abstract:

In a recent article, Carrasco and Forcada (June 2002) presented two algorithms: one for incremental addition of strings to the language of a minimal, deterministic, cyclic automaton, and one for incremental removal of strings from the automaton. The first algorithm is a generalization of the “algorithm for unsorted data”—the second of the two incremental algorithms for construction of minimal, deterministic, acyclic automata presented in Daciuk et al. (2000). We show that the other algorithm in the older article—the “algorithm for sorted data”—can be generalized in a similar way. The new algor

APA, Harvard, Vancouver, ISO, and other styles

4

ALMEIDA, MARCO, NELMA MOREIRA, and ROGÉRIO REIS. "EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA." International Journal of Foundations of Computer Science 19, no. 04 (2008): 751–65. http://dx.doi.org/10.1142/s0129054108005930.

Full text

Abstract:

We give a canonical representation for minimal acyclic deterministic finite automata (MADFA) with n states over an alphabet of k symbols. Using this normal form, we present a method for the exact generation of MADFAs. This method avoids a rejection phase that would be needed if a generation algorithm for a larger class of objects that contains the MADFAs were used. We give upper and lower bounds for MADFAs enumeration and some exact formulas for small values of n.

APA, Harvard, Vancouver, ISO, and other styles

5

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 <

APA, Harvard, Vancouver, ISO, and other styles

6

JIRÁSKOVÁ, GALINA. "MAGIC NUMBERS AND TERNARY ALPHABET." International Journal of Foundations of Computer Science 22, no. 02 (2011): 331–44. http://dx.doi.org/10.1142/s0129054111008076.

Full text

Abstract:

A number α, in the range from n to 2n, is magic for n with respect to a given alphabet size s, if there is no minimal nondeterministic finite automaton of n states and s input symbols whose equivalent minimal deterministic finite automaton has α states. We show that in the case of a ternary alphabet, there are no magic numbers. For all n and α satisfying n ⩽ α ⩽ 2n, we define an n-state nondeterministic finite automaton with a three-letter input alphabet that requires exactly α deterministic states.

APA, Harvard, Vancouver, ISO, and other styles

7

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. p

APA, Harvard, Vancouver, ISO, and other styles

8

JIRÁSEK, JOZEF, GALINA JIRÁSKOVÁ, and ALEXANDER SZABARI. "DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET." International Journal of Foundations of Computer Science 19, no. 03 (2008): 617–31. http://dx.doi.org/10.1142/s0129054108005851.

Full text

Abstract:

We show that for all integers n and α such that n ⩽ α ⩽ 2n, there exists a minimal nondeterministic finite automaton of n states with a four-letter input alphabet whose equivalent minimal deterministic finite automaton has exactly α states. It follows that in the case of a four-letter alphabet, there are no "magic numbers", i.e., the holes in the hierarchy. This improves a similar result obtained by Geffert for a growing alphabet of size n + 2.

APA, Harvard, Vancouver, ISO, and other styles

9

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

APA, Harvard, Vancouver, ISO, and other styles

10

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 langu

APA, Harvard, Vancouver, ISO, and other styles

More sources

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!