To see the other types of publications on this topic, follow the link: Minimal Acyclic Deterministic Finite Automaton.
Journal articles on the topic 'Minimal Acyclic Deterministic Finite Automaton'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 30 journal articles for your research 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.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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 algorithm is faster than the algorithm for addition of strings presented in Carrasco and Forcada's article, as it handles each state only once.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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).
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 textAbstract:
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.
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 textAbstract:
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.
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 textAbstract:
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.
11
Bhargava, Sanjay, and G. N. Purohit. "Construction of a Minimal Deterministic Finite Automaton from a Regular Expression." International Journal of Computer Applications 15, no. 4 (2011): 16–27. http://dx.doi.org/10.5120/1938-2589.
Full text
12
Bonfante, Guillaume, and Florian L. Deloup. "Decidability of regular language genus computation." Mathematical Structures in Computer Science 29, no. 9 (2019): 1428–43. http://dx.doi.org/10.1017/s0960129519000057.
Full textAbstract:
AbstractThis article continues the study of the genus of regular languages that the authors introduced in a 2013 paper (published in 2018). In order to understand further the genus g(L) of a regular language L, we introduce the genus size of |L|gen to be the minimal size of all finite deterministic automata of genus g(L) computing L.We show that the minimal finite deterministic automaton of a regular language can be arbitrarily far away from a finite deterministic automaton realizing the minimal genus and computing the same language, in terms of both the difference of genera and the difference in size. In particular, we show that the genus size |L|gen can grow at least exponentially in size |L|. We conjecture, however, the genus of every regular language to be computable. This conjecture implies in particular that the planarity of a regular language is decidable, a question asked in 1976 by R. V. Book and A. K. Chandra. We prove here the conjecture for a fairly generic class of regular languages having no short cycles. The methods developed for the proof are used to produce new genus-based hierarchies of regular languages and in particular, we show a new family of regular languages on a two-letter alphabet having arbitrary high genus.
13
Sapunov, Serhii. "Minimal Deterministic Traversable Vertex Labelling of Infinite Square Grid Graph." Proceedings of the Institute of Applied Mathematics and Mechanics NAS of Ukraine 34 (April 24, 2021): 118–33. http://dx.doi.org/10.37069/1683-4720-2020-34-12.
Full textAbstract:
Automata walking on graphs are a mathematical formalization of autonomous mobile agents with limited memory operating in discrete environments. Under this model a broad area of studies of the behaviour of automata in labyrinths arose and intensively developing last decades (a labyrinth is an embedded directed graph of special form). 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 deals with the problem of constructing square grid graph vertex labelling thanks to which a finite automaton without a compass can walk on graph in any arbitrary direction. The automaton looking over neighbourhood of the current vertex and may travel to some neighbouring vertex selected by its label. In this paper, 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. In previous works we have proved that minimal deterministic traversable vertex labelling of square grid graph uses labels of five different types. In this paper we prove that a collective of one automaton and three pebbles can construct this labelling on initially unlabelled infinite square grid graph. We consider pebbles as automata of the simplest form, whose positions are completely determined by the remaining automata of the collective.
14
JIANG, TAO, EDWARD McDOWELL, and B. RAVIKUMAR. "THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET." International Journal of Foundations of Computer Science 02, no. 02 (1991): 163–82. http://dx.doi.org/10.1142/s012905419100011x.
Full textAbstract:
Many difficult open problems in theoretical computer science center around non-determinism. We study the fundamental problem of converting a given deterministic finite automaton (DFA) to a minimal nondeterministic finite automaton (NFA). Despite extensive work on finite automata, this fundamental problem has remained open. Recently, we studied this problem and showed that this (and related) problems are computationally hard.11 Herewe study the restriction of this problem to the case when the input DFA is over a one-letter alphabet. Even in this restricted case the problem is computationally hard even though our evidence of hardness is different from (and is weaker than) the standard ones such as NP-hardness. Let A → B denote the problem of converting a finite automaton of type A to a minimal finite automaton of type B. Our main result is that DFA → NFA , when the input is a unary cyclic DFA (a DFA whose graph is a simple cycle), is in NP but not in P unless NP ⊆ DTIME (nO( log n)). Our work was also motivated by the problem of finding structurally simple “normal forms” of NFA’s over a unary alphabet. We present some normal forms for minimal NFA’s over a unary alphabet and present an application to lower bounds on the size complexity of an NFA. In fact, the normal form result is used in a nontrivial manner to show the NP membership result stated above.
15
HOLZER, MARKUS, SEBASTIAN JAKOBI, and MARTIN KUTRIB. "THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES." International Journal of Foundations of Computer Science 23, no. 01 (2012): 115–31. http://dx.doi.org/10.1142/s0129054112400084.
Full textAbstract:
We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DFA) has α states, for all n and α satisfying n ≤ α ≤ 2n. A number α not satisfying this condition is called a magic number (for n). It was shown that no magic numbers exist for general regular languages, whereas trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, star-free languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic.
16
CAMPEANU, CEZAR, ANDREI PAUN, and SHENG YU. "AN EFFICIENT ALGORITHM FOR CONSTRUCTING MINIMAL COVER AUTOMATA FOR FINITE LANGUAGES." International Journal of Foundations of Computer Science 13, no. 01 (2002): 83–97. http://dx.doi.org/10.1142/s0129054102000960.
Full textAbstract:
The concept of cover automata for finite languages was formally introduced in [3]. Cover automata have been studied as an efficient representation of finite languages. In [3], an algorithm was given to transform a DFA that accepts a finite language to a minimal deterministic finite cover automaton (DFCA) with the time complexity O(n4), where n is the number of states of the given DFA. In this paper, we review the basic concept of cover automata and describe a new efficient transformation algorithm with the time complexity O(n2), which is a significant improvement from the previous algorithm.
17
Dvorkin, M. E., and I. R. Akishev. "ON CONSTRUCTING MINIMAL DETERMINISTIC FINITE AUTOMATON RECOGNIZING A PREFIX-CODE OF A GIVEN CARDINALITY." Prikladnaya diskretnaya matematika, no. 8 (June 1, 2010): 104–16. http://dx.doi.org/10.17223/20710410/8/11.
Full text
18
KÖRNER, HEIKO. "A TIME AND SPACE EFFICIENT ALGORITHM FOR MINIMIZING COVER AUTOMATA FOR FINITE LANGUAGES." International Journal of Foundations of Computer Science 14, no. 06 (2003): 1071–86. http://dx.doi.org/10.1142/s0129054103002187.
Full textAbstract:
A deterministic finite automaton (DFA) [Formula: see text] is called a cover automaton (DFCA) for a finite language L over some alphabet Σ if [Formula: see text], with l being the length of some longest word in L. Thus a word w ∈ Σ* is in L if and only if |w| ≤ l and [Formula: see text]. The DFCA [Formula: see text] is minimal if no DFCA for L has fewer states. In this paper, we present an algorithm which converts an n–state DFA for some finite language L into a corresponding minimal DFCA, using only O(n log n) time and O(n) space. The best previously known algorithm requires O(n2) time and space. Furthermore, the new algorithm can also be used to minimize any DFCA, where the best previous method takes O(n4) time and space. Since the required data structure is rather complex, an implementation in the common programming language C/C++ is also provided.
19
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 textAbstract:
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.
20
Geffert, Viliam, and Zuzana Bednárová. "Minimal Size of Counters for (Real-Time) Multicounter Automata." Fundamenta Informaticae 181, no. 2-3 (2021): 99–127. http://dx.doi.org/10.3233/fi-2021-2053.
Full textAbstract:
We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n)ɛ. This is required for weak space bounds on the size of their counters, for real-time and one-way, and for nondeterministic and alternating versions of these automata. The same holds for two-way automata, independent of whether they work with strong or weak space bounds, and of whether they are deterministic, nondeterministic, or alternating. (Here ɛ denotes an arbitrarily small—but fixed—constant; the “space” refers to the values stored in the counters, rather than to the lengths of their binary representation.) On the other hand, we show that the minimal space required for accepting a nonregular language is nɛ for multicounter automata with strong space bounds, both for real-time and one-way versions, independent of whether they are deterministic, nondeterministic, or alternating, and also for real-time and one-way deterministic multicounter automata with weak space bounds. All these bounds are optimal both for unary and general nonregular languages. However, for automata equipped with only one counter, it was known that one-way nondeterministic automata cannot recognize any unary nonregular languages at all, even if the size of the counter is not restricted, while, with weak space bound log n, we present a real-time nondeterministic automaton recognizing a binary nonregular language here.
21
Löding, Christof. "Simplification Problems for Deterministic Pushdown Automata on Infinite Words." International Journal of Foundations of Computer Science 26, no. 08 (2015): 1041–68. http://dx.doi.org/10.1142/s0129054115400122.
Full textAbstract:
The article surveys some decidability results concerning simplification problems for DPDAs on infinite words (ω-DPDAs). We summarize some recent results on the regularity problem, which asks for a given ω-DPDA, whether its language can also be accepted by a finite automaton. The results also give some insights on the equivalence problem for a subclass of ω-DPDA. Furthermore, we present some new results on the parity index problem for ω-DPDAs. For the specification of a parity condition, the states of the ω-DPDA are assigned priorities (natural numbers), and a run is accepting if the highest priority that appears infinitely often during a run is even. The basic simplification question asks whether one can determine the minimal number of priorities that are needed to accept the language of a given ω-DPDA. We provide some decidability results on variations of this question for some classes of ω-DPDAs.
22
Dassow, Jürgen, and Bianca Truthe. "Accepting networks of evolutionary processors with resources restricted and structure limited filters." RAIRO - Theoretical Informatics and Applications 55 (2021): 8. http://dx.doi.org/10.1051/ita/2021004.
Full textAbstract:
In this paper, we continue the research on accepting networks of evolutionary processors where the filters belong to several special families of regular languages. We consider families of codes or ideals and subregular families which are defined by restricting the resources needed for generating or accepting them (the number of states of the minimal deterministic finite automaton accepting a language of the family as well as the number of non-terminal symbols or the number of production rules of a right-linear grammar generating such a language). We insert the newly defined language families into the hierachy of language families obtained by using as filters languages of other subregular families (such as ordered, non-counting, power-separating, circular, suffix-closed regular, union-free, definite, combinational, finite, monoidal, nilpotent, or commutative languages).
23
Samaniego, Franklin, Javier Sanchis, Sergio García-Nieto, and Raúl Simarro. "Recursive Rewarding Modified Adaptive Cell Decomposition (RR-MACD): A Dynamic Path Planning Algorithm for UAVs." Electronics 8, no. 3 (2019): 306. http://dx.doi.org/10.3390/electronics8030306.
Full textAbstract:
A relevant task in unmanned aerial vehicles (UAV) flight is path planning in 3 D environments. This task must be completed using the least possible computing time. The aim of this article is to combine methodologies to optimise the task in time and offer a complete 3 D trajectory. The flight environment will be considered as a 3 D adaptive discrete mesh, where grids are created with minimal refinement in the search for collision-free spaces. The proposed path planning algorithm for UAV saves computational time and memory resources compared with classical techniques. With the construction of the discrete meshing, a cost response methodology is applied as a discrete deterministic finite automaton (DDFA). A set of optimal partial responses, calculated recursively, indicates the collision-free spaces in the final path for the UAV flight.
24
Grachev, Petr, Sergey Muravyov, Andrey Filchenkov, and Anatoly Shalyto. "Automata generation based on recurrent neural networks and automated cauterization selection." Information and Control Systems, no. 1 (February 19, 2020): 34–43. http://dx.doi.org/10.31799/1684-8853-2020-1-34-43.
Full textAbstract:
Intoduction: The regular inference problem is to synthesize deterministic finite-state automata by a list of words which are examplesand counterexamples of some unknown regular language. This problem is one of the main in the theory of formal languages and relatedfields. One of the most successful solutions to this problem is training a recurrent neural network on word classification and clusteringthe vectors in the space of RNN inner weights. However, it is not guaranteed that a consistent automaton can be constructed based onthe clustering results. More complex models require more memory, training time and training samples. Purpose: Creating a brand newgrammar inference algorithm which would use modern machine learning methods. Methods: A recurrent neural network with an errorfunction proposed by the authors was used for classification. For clustering, the method of joint selection and tuning of hyperparameterwas used. Results: Ten different datasets were used for testing the models, corresponding to ten different regular grammars and tenautomata. According to the test results, the developed model successfully synthesize automata with no more than five input charactersand states. For four grammars, out of the seven successfully inferred ones, the constructed automaton was minimal. For three datasets,an automaton could not be built, either because of an insufficient number of clusters in the proposed partition, or because of the inabilityto build a consistent automaton for this partition. Discussion: Applying the algorithm of search for maximum likelihood between theclusters of vector and the corresponding states in order to resolve structural conflicts may expand the scope of the model.
25
CZYZOWICZ, JUREK, WOJCIECH FRACZAK, ANDRZEJ PELC, and WOJCIECH RYTTER. "LINEAR-TIME PRIME DECOMPOSITION OF REGULAR PREFIX CODES." International Journal of Foundations of Computer Science 14, no. 06 (2003): 1019–31. http://dx.doi.org/10.1142/s0129054103002151.
Full textAbstract:
One of the new approaches to data classification uses prefix codes and finite state automata as representations of prefix codes. A prefix code is a (possibly infinite) set of strings such that no string is a prefix of another one. An important task driven by the need for the efficient storage of such automata in memory is the decomposition (in the sense of formal languages concatenation) of prefix codes into prime factors. We investigate properties of such prefix code decompositions. A prime decomposition is a decomposition of a prefix code into a concatenation of nontrivial prime prefix codes. A prefix code is prime if it cannot be decomposed into at least two nontrivial prefix codes. In the paper a linear time algorithm is designed which finds the prime decomposition F1F2…Fk of a regular prefix code F given by its minimal deterministic automaton. Our results are especially interesting for infinite regular prefix codes.
26
An, Jie, Bohua Zhan, Naijun Zhan, and Miaomiao Zhang. "Learning Nondeterministic Real-Time Automata." ACM Transactions on Embedded Computing Systems 20, no. 5s (2021): 1–26. http://dx.doi.org/10.1145/3477030.
Full textAbstract:
We present an active learning algorithm named NRTALearning for nondeterministic real-time automata (NRTAs). Real-time automata (RTAs) are a subclass of timed automata with only one clock which resets at each transition. First, we prove the corresponding Myhill-Nerode theorem for real-time languages. Then we show that there exists a unique minimal deterministic real-time automaton (DRTA) recognizing a given real-time language, but the same does not hold for NRTAs. We thus define a special kind of NRTAs, named residual real-time automata (RRTAs), and prove that there exists a minimal RRTA to recognize any given real-time language. This transforms the learning problem of NRTAs to the learning problem of RRTAs. After describing the learning algorithm in detail, we prove its correctness and polynomial complexity. In addition, based on the corresponding Myhill-Nerode theorem, we extend the existing active learning algorithm NL* for nondeterministic finite automata to learn RRTAs. We evaluate and compare the two algorithms on two benchmarks consisting of randomly generated NRTAs and rational regular expressions. The results show that NRTALearning generally performs fewer membership queries and more equivalence queries than the extended NL* algorithm, and the learnt NRTAs have much fewer locations than the corresponding minimal DRTAs. We also conduct a case study using a model of scheduling of final testing of integrated circuits.
27
Tappler, Martin, Bernhard K. Aichernig, Giovanni Bacci, Maria Eichlseder, and Kim G. Larsen. "$$L^*$$-based learning of Markov decision processes (extended version)." Formal Aspects of Computing 33, no. 4-5 (2021): 575–615. http://dx.doi.org/10.1007/s00165-021-00536-5.
Full textAbstract:
AbstractAutomata learning techniques automatically generate systemmodels fromtest observations. Typically, these techniques fall into two categories: passive and active. On the one hand, passive learning assumes no interaction with the system under learning and uses a predetermined training set, e.g., system logs. On the other hand, active learning techniques collect training data by actively querying the system under learning, allowing one to steer the discovery ofmeaningful information about the systemunder learning leading to effective learning strategies. A notable example of active learning technique for regular languages is Angluin’s $$L^*$$ L ∗ -algorithm. The $$L^*$$ L ∗ -algorithm describes the strategy of a student who learns the minimal deterministic finite automaton of an unknown regular language $$L$$ L by asking a succinct number of queries to a teacher who knows $$L$$ L .In this work, we study $$L^*$$ L ∗ -based learning of deterministic Markov decision processes, a class of Markov decision processes where an observation following an action uniquely determines a successor state. For this purpose, we first assume an ideal setting with a teacher who provides perfect information to the student. Then, we relax this assumption and present a novel learning algorithm that collects information by sampling execution traces of the system via testing.Experiments performed on an implementation of our sampling-based algorithm suggest that our method achieves better accuracy than state-of-the-art passive learning techniques using the same amount of test obser vations. In contrast to existing learning algorithms which assume a predefined number of states, our algorithm learns the complete model structure including the state space.
28
Brzozowski, Janusz A., and Sylvie Davies. "Most Complex Non-Returning Regular Languages." International Journal of Foundations of Computer Science 30, no. 06n07 (2019): 921–57. http://dx.doi.org/10.1142/s0129054119400239.
Full textAbstract:
A regular language [Formula: see text] is non-returning if in the minimal deterministic finite automaton accepting it there are no transitions into the initial state. Eom, Han and Jirásková derived upper bounds on the state complexity of boolean operations and Kleene star, and proved that these bounds are tight using two different binary witnesses. They derived tight upper bounds for concatenation and reversal using three different ternary witnesses. These five witnesses use a total of six different transformations. We show that for each [Formula: see text], there exists a ternary witness of state complexity [Formula: see text] that meets the bound for reversal, and restrictions of this witness to binary alphabets meet the bounds for star, product, and boolean operations. Hence all of these operations can be handled simultaneously with a single witness, using only three different transformations. We also derive tight upper bounds on the state complexity of binary operations that take arguments with different alphabets. We prove that the maximal syntactic semigroup of a non-returning language has [Formula: see text] elements and requires at least [Formula: see text] generators. We find the maximal state complexities of atoms of non-returning languages. We show that there exists a most complex sequence of non-returning languages that meet the bounds for all of these complexity measures. Furthermore, we prove there is a most complex sequence that meets all the bounds using alphabets of minimal size.
29
Priez, Jean-Baptiste. "Enumeration of minimal acyclic automata via generalized parking functions." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings, 27th..., Proceedings (2015). http://dx.doi.org/10.46298/dmtcs.2471.
Full textAbstract:
International audience We give an exact enumerative formula for the minimal acyclic deterministic finite automata. This formula is obtained from a bijection between a family of generalized parking functions and the transitions functions of acyclic automata. On donne une formule d’énumération exacte des automates finites déterministes acycliques minimaux. Cetteformule s’obtient à partir d’une bijection entre une famille fonctions de parking généralisées et les fonctions detransitions des automates acycliques.
30
Brzozowski, Janusz A., Lila Kari, Bai Li, and Marek Szykuła. "State Complexity of Overlap Assembly." International Journal of Foundations of Computer Science, December 15, 2020, 1–20. http://dx.doi.org/10.1142/s012905412042006x.
Full textAbstract:
The state complexity of a regular language [Formula: see text] is the number [Formula: see text] of states in a minimal deterministic finite automaton (DFA) accepting [Formula: see text]. The state complexity of a regularity-preserving binary operation on regular languages is defined as the maximal state complexity of the result of the operation where the two operands range over all languages of state complexities [Formula: see text] and [Formula: see text], respectively. We determine, for [Formula: see text], [Formula: see text], the exact value of the state complexity of the binary operation overlap assembly on regular languages. This operation was introduced by Csuhaj-Varjú, Petre, and Vaszil to model the process of self-assembly of two linear DNA strands into a longer DNA strand, provided that their ends “overlap”. We prove that the state complexity of the overlap assembly of languages [Formula: see text] and [Formula: see text], where [Formula: see text] and [Formula: see text], is at most [Formula: see text]. Moreover, for [Formula: see text] and [Formula: see text] there exist languages [Formula: see text] and [Formula: see text] over an alphabet of size [Formula: see text] whose overlap assembly meets the upper bound and this bound cannot be met with smaller alphabets. Finally, we prove that [Formula: see text] is the state complexity of the overlap assembly in the case of unary languages and that there are binary languages whose overlap assembly has exponential state complexity at least [Formula: see text].