Log in

Relevant bibliographies by topics / Nondeterministic finite automata / Journal articles

To see the other types of publications on this topic, follow the link: Nondeterministic finite automata.

Journal articles on the topic 'Nondeterministic finite automata'

Author: Grafiati

Published: 3 June 2025

Last updated: 6 July 2025

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 'Nondeterministic 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

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

2

Melnikov, Boris. "Extended Nondeterministic Finite Automata." Fundamenta Informaticae 104, no. 3 (2010): 255–65. http://dx.doi.org/10.3233/fi-2010-348.

Full text

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

Câmpeanu, Cezar. "Simplifying Nondeterministic Finite Cover Automata." Electronic Proceedings in Theoretical Computer Science 151 (May 21, 2014): 162–73. http://dx.doi.org/10.4204/eptcs.151.11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

HOLZER, MARKUS, and SEBASTIAN JAKOBI. "NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY." International Journal of Foundations of Computer Science 25, no. 07 (2014): 837–55. http://dx.doi.org/10.1142/s0129054114400115.

Full text

Abstract:

We investigate the descriptional complexity of nondeterministic biautomata, which are a generalization of biautomata [O. KLÍMA, L. POLÁK: On biautomata. RAIRO — Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages.

APA, Harvard, Vancouver, ISO, and other styles

6

Holzer, Markus, and Martin Kutrib. "One-Time Nondeterministic Computations." International Journal of Foundations of Computer Science 30, no. 06n07 (2019): 1069–89. http://dx.doi.org/10.1142/s012905411940029x.

Full text

Abstract:

We introduce the concept of one-time nondeterminism as a new kind of limited nondeterminism for finite state machines and pushdown automata. Roughly speaking, one-time nondeterminism means that at the outset the computation is nondeterministic, but whenever it performs a guess, this guess is fixed for the rest of the computation. We characterize the computational power of one-time nondeterministic finite automata (OTNFAs) and one-time nondeterministic pushdown devices. Moreover, we study the descriptional complexity of these machines. For instance, we show that for an [Formula: see text]-state OTNFA with a sole nondeterministic state, that is nondeterministic for only one input symbol, [Formula: see text] states are sufficient and necessary in the worst case for an equivalent deterministic finite automaton. In case of pushdown automata, the conversion of a nondeterministic to a one-time nondeterministic as well as the conversion of a one-time nondeterministic to a deterministic one turn out to be non-recursive, that is, the trade-offs in size cannot be bounded by any recursive function.

APA, Harvard, Vancouver, ISO, and other styles

7

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

8

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

9

MARTYUGIN, PAVEL. "THE LENGTH OF SUBSET REACHABILITY IN NONDETERMINISTIC AUTOMATA." International Journal of Foundations of Computer Science 20, no. 05 (2009): 887–900. http://dx.doi.org/10.1142/s0129054109006942.

Full text

Abstract:

We study subset reachability in nondeterministic finite automata and look for bounds of the length of the shortest reaching words for automata with a fixed number of states. We obtain such bounds for nondeterministic automata over 2-letter, 3-letter and arbitrary alphabets.a

APA, Harvard, Vancouver, ISO, and other styles

10

Calude, Cristian S., Elena Calude, and Bakhadyr Khoussainov. "Finite nondeterministic automata: Simulation and minimality." Theoretical Computer Science 242, no. 1-2 (2000): 219–35. http://dx.doi.org/10.1016/s0304-3975(98)00221-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

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

12

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

13

HOLZER, MARKUS, and MARTIN KUTRIB. "NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY." International Journal of Foundations of Computer Science 20, no. 04 (2009): 563–80. http://dx.doi.org/10.1142/s0129054109006747.

Full text

Abstract:

Nondeterministic finite automata (NFAs) were introduced in [68], where their equivalence to deterministic finite automata was shown. Over the last 50 years, a vast literature documenting the importance of finite automata as an enormously valuable concept has been developed. In the present paper, we tour a fragment of this literature. Mostly, we discuss recent developments relevant to NFAs related problems like, for example, (i) simulation of and by several types of finite automata, (ii) minimization and approximation, (iii) size estimation of minimal NFAs, and (iv) state complexity of language operations. We thus come across descriptional and computational complexity issues of nondeterministic finite automata. We do not prove these results but we merely draw attention to the big picture and some of the main ideas involved.

APA, Harvard, Vancouver, ISO, and other styles

14

Kwee, Kent, and Friedrich Otto. "Nondeterministic Ordered Restarting Automata." International Journal of Foundations of Computer Science 29, no. 04 (2018): 663–85. http://dx.doi.org/10.1142/s0129054118410101.

Full text

Abstract:

While (stateless) deterministic ordered restarting automata accept exactly the regular languages, it has been observed that nondeterministic ordered restarting automata (ORWW-automata for short) are more expressive. Here we show that the class of languages accepted by the latter automata is an abstract family of languages that is incomparable to the linear, the context-free, and the growing context-sensitive languages with respect to inclusion, and that the emptiness problem is decidable for these languages. In addition, we give a construction that turns a stateless ORWW-automaton into a nondeterministic finite-state acceptor for the same language.

APA, Harvard, Vancouver, ISO, and other styles

15

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

16

Yakaryilmaz, Abuzer, and A. C. Cem Say. "Languages recognized by nondeterministic quantum finite automata." Quantum Information and Computation 10, no. 9&10 (2010): 747–70. http://dx.doi.org/10.26421/qic10.9-10-3.

Full text

Abstract:

The nondeterministic quantum finite automaton (NQFA) is the only known case where a one-way quantum finite automaton (QFA) model has been shown to be strictly superior in terms of language recognition power to its probabilistic counterpart. We give a characterization of the class of languages recognized by NQFAs, demonstrating that it is equal to the class of exclusive stochastic languages. We also characterize the class of languages that are recognized necessarily by two-sided error by QFAs. It is shown that these classes remain the same when the QFAs used in their definitions are replaced by several different model variants that have appeared in the literature. We prove several closure properties of the related classes. The ramifications of these results about classical and quantum sublogarithmic space complexity classes are examined.

APA, Harvard, Vancouver, ISO, and other styles

17

Kutrib, Martin, Andreas Malcher, and Matthias Wendlandt. "Complexity of Unary Exclusive Nondeterministic Finite Automata." Electronic Proceedings in Theoretical Computer Science 407 (September 11, 2024): 136–49. http://dx.doi.org/10.4204/eptcs.407.10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Jastrzab, Tomasz. "On Parallel Induction of Nondeterministic Finite Automata." Procedia Computer Science 80 (2016): 257–68. http://dx.doi.org/10.1016/j.procs.2016.05.318.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Melnikov, Boris. "On an expansion of nondeterministic finite automata." Journal of Applied Mathematics and Computing 24, no. 1-2 (2007): 155–65. http://dx.doi.org/10.1007/bf02832307.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Wen-Guey, Tzeng. "On path equivalence of nondeterministic finite automata." Information Processing Letters 58, no. 1 (1996): 43–46. http://dx.doi.org/10.1016/0020-0190(96)00039-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Gorrieri, Roberto. "An algebraic theory of nondeterministic finite automata." Journal of Logical and Algebraic Methods in Programming 145 (May 2025): 101055. https://doi.org/10.1016/j.jlamp.2025.101055.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

MACARIE, IOAN I. "A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA." International Journal of Foundations of Computer Science 07, no. 04 (1996): 329–37. http://dx.doi.org/10.1142/s0129054196000233.

Full text

Abstract:

We present connections among nondeterministic and one-sided-error probabilistic multihead finite-state automata. Several properties of logarithmic-space Turing machines follow from the more refined results that we prove in the setting of the corresponding multihead finite-state automata.

APA, Harvard, Vancouver, ISO, and other styles

23

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

24

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

25

Madejski, Grzegorz, and Andrzej Szepietowski. "Membership Problem for Two-Dimensional General Row Jumping Finite Automata." International Journal of Foundations of Computer Science 31, no. 04 (2020): 527–38. http://dx.doi.org/10.1142/s0129054120500239.

Full text

Abstract:

Two-dimensional general row jumping finite automata were recently introduced as an interesting computational model for accepting two-dimensional languages. These automata are nondeterministic. They guess an order in which rows of the input array are read and they jump to the next row only after reading all symbols in the previous row. In each row, they choose, also nondeterministically, an order in which segments of the row are read. In this paper, we study the membership problem for these automata. We show that each general row jumping finite automaton can be simulated by a nondeterministic Turing machine with space bounded by the logarithm. This means that the fixed membership problems for such automata are in NL, and so in P. On the other hand, we show that the uniform membership problem is NP-complete.

APA, Harvard, Vancouver, ISO, and other styles

26

CANTONE, DOMENICO, and SIMONE FARO. "A SPACE EFFICIENT BIT-PARALLEL ALGORITHM FOR THE MULTIPLE STRING MATCHING PROBLEM." International Journal of Foundations of Computer Science 17, no. 06 (2006): 1235–51. http://dx.doi.org/10.1142/s0129054106004388.

Full text

Abstract:

Finite (nondeterministic) automata are very useful building blocks in the field of string matching. This is particularly true in the case of multiple pattern matching, where the use of factor-based automata can reduce substantially the number of computational steps when the patterns have large common factors. Direct simulation of nondeterministic automata can be performed very efficiently using the bit-parallelism technique, though this is not necessarily true for factor-based automata. In this paper we present an algorithm for the multiple string matching problem, based on the bit-parallel simulation of nondeterministic factor-based automata which satisfy a particular ordering condition. We also show how to enforce such condition by suitably modifying a minimal initial automaton, through equivalence preserving transformations. The resulting automaton turns out to be smaller than the corresponding maximal automata used by existing bit-parallel algorithms, as they do not take any advantage of common factors in patterns.

APA, Harvard, Vancouver, ISO, and other styles

27

Jastrzab, Tomasz, Zbigniew J. Czech, and Wojciech Wieczorek. "Parallel Algorithms for Minimal Nondeterministic Finite Automata Inference." Fundamenta Informaticae 178, no. 3 (2021): 203–27. http://dx.doi.org/10.3233/fi-2021-2004.

Full text

Abstract:

The goal of this paper is to develop the parallel algorithms that, on input of a learning sample, identify a regular language by means of a nondeterministic finite automaton (NFA). A sample is a pair of finite sets containing positive and negative examples. Given a sample, a minimal NFA that represents the target regular language is sought. We define the task of finding an NFA, which accepts all positive examples and rejects all negative ones, as a constraint satisfaction problem, and then propose the parallel algorithms to solve the problem. The results of comprehensive computational experiments on the variety of inference tasks are reported. The question of minimizing an NFA consistent with a learning sample is computationally hard.

APA, Harvard, Vancouver, ISO, and other styles

28

Hanneforth, Thomas, Andreas Maletti, and Daniel Quernheim. "Random Generation of Nondeterministic Finite-State Tree Automata." Electronic Proceedings in Theoretical Computer Science 134 (November 20, 2013): 11–16. http://dx.doi.org/10.4204/eptcs.134.2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Gruber, Hermann, Markus Holzer, and Sebastian Jakobi. "More on deterministic and nondeterministic finite cover automata." Theoretical Computer Science 679 (May 2017): 18–30. http://dx.doi.org/10.1016/j.tcs.2016.10.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Bensch, Suna, Henning Bordihn, Markus Holzer, and Martin Kutrib. "On input-revolving deterministic and nondeterministic finite automata." Information and Computation 207, no. 11 (2009): 1140–55. http://dx.doi.org/10.1016/j.ic.2009.03.002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Potechin, Aaron, and Jeffrey Shallit. "Lengths of words accepted by nondeterministic finite automata." Information Processing Letters 162 (October 2020): 105993. http://dx.doi.org/10.1016/j.ipl.2020.105993.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Borsotti, Angelo, and Ulya Trofimovich. "Efficient POSIX submatch extraction on nondeterministic finite automata." Software: Practice and Experience 51, no. 2 (2020): 159–92. http://dx.doi.org/10.1002/spe.2881.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Jastrzab, Tomasz, Frédéric Lardeux, and Eric Monfroy. "Robust models to infer flexible nondeterministic finite automata." Journal of Computational Science 79 (July 2024): 102309. http://dx.doi.org/10.1016/j.jocs.2024.102309.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

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

35

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

36

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 text

Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles

37

K, Chitra. "Some Properties of Fuzzy Finite Tree Automata." International Journal for Research in Applied Science and Engineering Technology 13, no. 4 (2025): 1341–47. https://doi.org/10.22214/ijraset.2025.68487.

Full text

Abstract:

Abstract: This paper examines fuzzy tree automata's deterministic, reduced, and homomorphic properties. It is demonstrated through an example that there is a deterministic fuzzy tree automaton for the nondeterministic one. For every given fuzzy tree automaton, an equivalent reduced fuzzy tree automaton is displayed. A theorem that fuzzy tree languages are preserved by tree homomorphism is derived

APA, Harvard, Vancouver, ISO, and other styles

38

Denis, François, Aurélien Lemay, and Alain Terlutte. "Residual Finite State Automata." Fundamenta Informaticae 51, no. 4 (2002): 339–68. https://doi.org/10.3233/fun-2002-51402.

Full text

Abstract:

We define a new variety of Nondeterministic Finite Automata (NFA): a Residual Finite State Automaton (RFSA) is an NFA all the states of which define residual languages of the language L that it recognizes; a residual language according to a word u is the set of words v such that uv is in L. We prove that every regular language is recognized by a unique (canonical) RFSA which has a minimal number of states and a maximal number of transitions. Canonical RFSAs are based on the notion of prime residual languages, i.e. that are not the union of other residual languages. We provide an algorithmic construction of the canonical RFSA similar to the subset construction used to build the minimal DFA from a given NFA. We study the size of canonical RFSAs and the complexity of our constructions.

APA, Harvard, Vancouver, ISO, and other styles

39

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

40

Waters, L. K., and J. K. Grieshop. "ON THE REGULARITY OF SETS OF MULTI-ACCEPTED STRINGS OF A NON-DETERMINISTIC FINITE AUTOMATON." Asian-European Journal of Mathematics 02, no. 04 (2009): 717–26. http://dx.doi.org/10.1142/s1793557109000595.

Full text

Abstract:

In this paper we establish the regularity of various sets of multi-accepted strings of nondeterministic finite automata. Regularity follows from the existence of accepting automata constructed by introducing a vector labeling method which generalizes the subset labeling approach. In each set the acceptance levels of the strings correspond to finite sets of additive equivalence classes of non-negative integers.

APA, Harvard, Vancouver, ISO, and other styles

41

Holzer, Markus, and Sebastian Jakobi. "More on Minimizing Finite Automata with Errors — Nondeterministic Machines." International Journal of Foundations of Computer Science 28, no. 03 (2017): 229–45. http://dx.doi.org/10.1142/s0129054117500150.

Full text

Abstract:

We continue our research on minimization problems and related problems for automata w.r.t. to different error profiles, now considering nondeterministic finite automata (NFAs) as inputs. Here the error profiles are almost-equivalence and E-equivalence. We show that the minimization problems and their underlying equivalence problems become PSPACE-complete in most cases. The obtained results nicely fit to the known ones on ordinary NFA minimization, and show a significant difference to the previously obtained results on deterministic finite state machines.

APA, Harvard, Vancouver, ISO, and other styles

42

BORDIHN, HENNING, MARTIN KUTRIB, and ANDREAS MALCHER. "ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA." International Journal of Foundations of Computer Science 23, no. 03 (2012): 713–32. http://dx.doi.org/10.1142/s0129054112500062.

Full text

Abstract:

Systems of parallel finite automata communicating by states are investigated. We consider deterministic and nondeterministic devices and distinguish four working modes. It is known that systems in the most general mode are as powerful as one-way multi-head finite automata. Here we solve some open problems on the computational capacity of systems working in the remaining modes. In particular, it is shown that deterministic returning and non-returning devices are equivalent, and that there are languages which are accepted by deterministic returning and centralized systems but cannot be accepted by deterministic non-returning centralized systems. Furthermore, we show that nondeterministic systems are strictly more powerful than their deterministic variants in all the four working modes. Finally, incomparability with the classes of (deterministic) (linear) context-free languages as well as the Church-Rosser languages is derived.

APA, Harvard, Vancouver, ISO, and other styles

43

HOLZER, MARKUS, and MARTIN KUTRIB. "NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES." International Journal of Foundations of Computer Science 14, no. 06 (2003): 1087–102. http://dx.doi.org/10.1142/s0129054103002199.

Full text

Abstract:

We investigate the descriptional complexity of operations on finite and infinite regular languages over unary and arbitrary alphabets. The languages are represented by nondeterministic finite automata (NFA). In particular, we consider Boolean operations, catenation operations – concatenation, iteration, λ-free iteration – and the reversal. Most of the shown bounds are tight in the exact number of states, i.e. the number is sufficient and necessary in the worst case. Otherwise tight bounds in the order of magnitude are shown.

APA, Harvard, Vancouver, ISO, and other styles

44

Miller, Hannah, and David E. Narváez. "Toward Determining NFA Equivalence via QBFs (Student Abstract)." Proceedings of the AAAI Conference on Artificial Intelligence 35, no. 18 (2021): 15849–50. http://dx.doi.org/10.1609/aaai.v35i18.17921.

Full text

Abstract:

Equivalence of deterministic finite automata (DFAs) has been researched for several decades, but equivalence of nondeterministic finite automata (NFAs) is not as studied. Equivalence of two NFAs is a PSPACE-complete problem. NFA equivalence is a challenging theoretical problem with practical applications such as lexical analysis. Quantified boolean formulas (QBFs) naturally encode PSPACE-complete problems, and we share our preliminary work towards determining NFA equivalence via QBFs.

APA, Harvard, Vancouver, ISO, and other styles

45

Jirásek, Jozef, Galina Jirásková, and Juraj Šebej. "Operations on Unambiguous Finite Automata." International Journal of Foundations of Computer Science 29, no. 05 (2018): 861–76. http://dx.doi.org/10.1142/s012905411842008x.

Full text

Abstract:

A nondeterministic finite automaton is unambiguous if it has at most one accepting computation on every input string. We investigate the state complexity of basic regular operations on languages represented by unambiguous finite automata. We get tight upper bounds for reversal ([Formula: see text]), intersection ([Formula: see text]), left and right quotients ([Formula: see text]), positive closure ([Formula: see text]), star ([Formula: see text]), shuffle ([Formula: see text]), and concatenation ([Formula: see text]). To prove tightness, we use a binary alphabet for intersection and left and right quotients, a ternary alphabet for star and positive closure, a five-letter alphabet for shuffle, and a seven-letter alphabet for concatenation. For complementation, we reduce the trivial upper bound [Formula: see text] to [Formula: see text]. We also get some partial results for union and square.

APA, Harvard, Vancouver, ISO, and other styles

46

Palioudakis, Alexandros, Kai Salomaa, and Selim G. Akl. "Worst Case Branching and Other Measures of Nondeterminism." International Journal of Foundations of Computer Science 28, no. 03 (2017): 195–210. http://dx.doi.org/10.1142/s0129054117500137.

Full text

Abstract:

Many nondeterminism measures for finite automata have been studied in the literature. The tree width of an NFA (nondeterministic finite automaton) counts the number of leaves of computation trees as a function of input length. The trace of an NFA is defined in terms of the largest product of the degrees of nondeterministic choices in computations on inputs of given length. Branching is the corresponding best case measure based on the product of nondeterministic choices in the computation that minimizes this value. We establish upper and lower bounds for the trace of an NFA in terms of its tree width. We give a tight bound for the size blow-up of determinizing an NFA with finite trace. Also we show that the trace of any NFA either is bounded by a constant or grows exponentially.

APA, Harvard, Vancouver, ISO, and other styles

47

Burdonov, Igor Borisovich, Nina Vladimirovna Yevtushenko, and Alexander Sergeevich Kossachev. "Separating Input/Output Automata With Nondeterministic Behavior." Russian Digital Libraries Journal 23, no. 4 (2020): 634–55. http://dx.doi.org/10.26907/1562-5419-2020-23-4-634-655.

Full text

Abstract:

When deriving tests for checking functional and nonfunctional requirements for components of control systems, the notion of separablity becomes very important that is used for distinguishing the fault-free component from a faulty one. In order to do this, proper separating sequences are utilized. Such sequences are well studied for complete and deterministic Finite State Machines but components of control systems can be only partially described and their behavior can be nondeterministic. In this paper, we consider the formal model of Input/Output automata, introduce the notion of a separating sequence for two such automata and propose an approach for deriving such a separating sequence.

APA, Harvard, Vancouver, ISO, and other styles

48

Mel’nikov, B. F., and M. R. Saifullina. "Some algorithms for equivalent transformation of nondeterministic finite automata." Russian Mathematics 53, no. 4 (2009): 54–57. http://dx.doi.org/10.3103/s1066369x09040100.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

RAMASUBRAMANIAN, S. V., and KAMALA KRITHIVASAN. "FINITE AUTOMATA AND DIGITAL IMAGES." International Journal of Pattern Recognition and Artificial Intelligence 14, no. 04 (2000): 501–24. http://dx.doi.org/10.1142/s0218001400000325.

Full text

Abstract:

In this paper, we initially consider representation of 2D black–white images and 3D objects using finite state automata. We describe transformation of scaling on the 2D image by an operation on the FSA. We also give constructions for getting the projections of a 3D object on to coordinate planes and for reconstructing the 3D object from its projections. We define minimization of nondeterministic FSAs and give an O(e2) (e is the number of edges in the FSA) algorithm for minimization of NFAs. Later, we define a WFA and describe various properties of WFA. We define four normal forms of WFA and show how a WFA can be normalized into any of these forms. We show the equivalence of WFAs with ∊ edges and ∊-free WFAs. Then, we define minimization of WFAs and present an algorithm to minimize a WFA.

APA, Harvard, Vancouver, ISO, and other styles

50

Ď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

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!