Log in

Relevant bibliographies by topics / NONDETERMINISTIC AUTOMATON

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'NONDETERMINISTIC 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 'NONDETERMINISTIC 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 "NONDETERMINISTIC AUTOMATON"

1

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

2

KUPFERMAN, ORNA, GILA MORGENSTERN та ANIELLO MURANO. "TYPENESS FOR ω-REGULAR AUTOMATA". International Journal of Foundations of Computer Science 17, № 04 (2006): 869–83. http://dx.doi.org/10.1142/s0129054106004157.

Full text

Abstract:

We introduce and study three notions of typeness for automata on infinite words. For an acceptance-condition class γ (that is, γ is weak, Büchi, co-Büchi, Rabin, or Streett), deterministic γ-typeness asks for the existence of an equivalent γ-automaton on the same deterministic structure, nondeterministic γ-typeness asks for the existence of an equivalent γ-automaton on the same structure, and γ-powerset-typeness asks for the existence of an equivalent γ-automaton on the (deterministic) powerset structure – one obtained by applying the subset construction. The notions are helpful in studying th

APA, Harvard, Vancouver, ISO, and other styles

3

Mráz, František, and Friedrich Otto. "On restarting automata with auxiliary symbols and small window size." RAIRO - Theoretical Informatics and Applications 55 (2021): 9. http://dx.doi.org/10.1051/ita/2021003.

Full text

Abstract:

Here we show that for monotone RWW- (and RRWW-) automata, window size two is sufficient, both in the nondeterministic as well as in the deterministic case. For the former case, this is done by proving that each context-free language is already accepted by a monotone RWW-automaton of window size two. In the deterministic case, we first prove that each deterministic pushdown automaton can be simulated by a deterministic monotone RWW-automaton of window size three, and then we present a construction that transforms a deterministic monotone RWW-automaton of window size three into an equivalent aut

APA, Harvard, Vancouver, ISO, and other styles

4

Fernau, Henning, Martin Kutrib, and Matthias Wendlandt. "Self-Verifying Pushdown and Queue Automata." Fundamenta Informaticae 180, no. 1-2 (2021): 1–28. http://dx.doi.org/10.3233/fi-2021-2032.

Full text

Abstract:

We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes, no, or do not know. For every input word, at least one computation path must give either the answer yes or no, and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free

APA, Harvard, Vancouver, ISO, and other styles

5

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 nonde

APA, Harvard, Vancouver, ISO, and other styles

6

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 si

APA, Harvard, Vancouver, ISO, and other styles

7

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

APA, Harvard, Vancouver, ISO, and other styles

8

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 spec

APA, Harvard, Vancouver, ISO, and other styles

9

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

10

CHAMPARNAUD, J. M., and F. COULON. "ENUMERATING NONDETERMINISTIC AUTOMATA FOR A GIVEN LANGUAGE WITHOUT CONSTRUCTING THE CANONICAL AUTOMATON." International Journal of Foundations of Computer Science 16, no. 06 (2005): 1253–66. http://dx.doi.org/10.1142/s0129054105003790.

Full text

Abstract:

Our aim is to enumerate all NFAs (nondeterministic finite automata) that recognize a given regular language [Formula: see text]. More precisely, we produce a set 𝔸 of automata such that each automaton A recognizing [Formula: see text] appears in 𝔸 up to the merging of some states and the addition of some transitions, that is, there is a surjective morphism that maps A onto an automaton of 𝔸. We provide a common theoretical framework, based on morphism properties, to previous works of Kameda and Weiner (1970), and of Sengoku (1992), whose issue is the minimization of NFAs. Our paper gives two i

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "NONDETERMINISTIC AUTOMATON"

1

Шабана, Х. М. Д. "Синхронизация частичных и недетерминированных автоматов: подход на основе sat-решателей : автореферат диссертации на соискание ученой степени кандидата физико-математических наук : 05.13.17". Thesis, б. и, 2020. http://hdl.handle.net/10995/84648.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Shabana, H. M. D. "Synchronization of partial and non-deterministic automata: a sat-based approach : dissertation for the degree of candidate of physical and mathematical sciences : 05.13.17." Thesis, б. и, 2020. http://hdl.handle.net/10995/83662.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Procházka, Lukáš. "Redukce nedeterministických konečných automatů." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2011. http://www.nusl.cz/ntk/nusl-237032.

Full text

Abstract:

Nondeterministic finite automaton is an important tool, which is used to process strings in many different areas of programming. It is important to try to reduce its size for increasing programs' effectiveness. However, this problem is computationally hard, so we need to search for new techniques. Basics of finite automata are described in this work. Some methods for their reduction are then introduced. Usable reduction algorithms are described in greater detail. Then they are implemented and tested. The test results are finally evaluated.

APA, Harvard, Vancouver, ISO, and other styles

4

Almeida, Ricardo Manuel de Oliveira. "Efficient algorithms for hard problems in nondeterministic tree automata." Thesis, University of Edinburgh, 2017. http://hdl.handle.net/1842/28794.

Full text

Abstract:

We present PTIME language-preserving techniques for the reduction of non-deterministic tree automata, both for the case of finite trees and for infinite trees. Our techniques are based on new transition removing and state merging results, which rely on binary relations that compare the downward and upward behaviours of states in the automaton. We use downward/upward simulation preorders and the more general but EXPTIME-complete trace inclusion relations, for which we introduce good under-approximations computable in polynomial time. We provide a complete picture of combinations of downward and

APA, Harvard, Vancouver, ISO, and other styles

5

Cazalis, Daniel S. "Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications." FIU Digital Commons, 2007. http://digitalcommons.fiu.edu/etd/8.

Full text

Abstract:

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which i

APA, Harvard, Vancouver, ISO, and other styles

6

Merryman, William Patrick. "Animating the conversion of nondeterministic finite state automata to deterministic finite state automata." Thesis, Montana State University, 2007. http://etd.lib.montana.edu/etd/2007/merryman/MerrymanW0507.pdf.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Donnoe, Joshua. "Compiling Java in linear nondeterministic space." Thesis, 2018. http://hdl.handle.net/2097/38879.

Full text

Abstract:

Master of Science<br>Department of Computer Science<br>Torben Amtoft<br>Shannon’s and Chomsky’s attempts to model natural language with Markov chains showed differing gauges of language complexity. These were codified with the Chomsky Hierarchy with four types of languages, each with an accepting type of grammar and au- tomaton. Though still foundationally important, this fails to identify remarkable proper subsets of the types including recursive languages among recursively enumerable languages. In general, with Rice’s theorem, it is undecidable whether a Turing machine’s language is re- curs

APA, Harvard, Vancouver, ISO, and other styles

8

Kern, Carsten [Verfasser]. "Learning communicating and nondeterministic automata / vorgelegt von Carsten Kern." 2009. http://d-nb.info/1000490483/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "NONDETERMINISTIC AUTOMATON"

1

Fredriksson, Kimmo. "From Nondeterministic Suffix Automaton to Lazy Suffix Tree." In Algorithms and Applications. Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-12476-1_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Szklarski, Jacek. "Nondeterministic Cellular Automaton for Modelling Urban Traffic with Self-organizing Control." In Parallel Processing and Applied Mathematics. Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-78054-2_42.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Myers, Robert S. R., Stefan Milius, and Henning Urbat. "Nondeterministic Syntactic Complexity." In Lecture Notes in Computer Science. Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-71995-1_23.

Full text

Abstract:

AbstractWe introduce a new measure on regular languages: their nondeterministic syntactic complexity. It is the least degree of any extension of the ‘canonical boolean representation’ of the syntactic monoid. Equivalently, it is the least number of states of any subatomic nondeterministic acceptor. It turns out that essentially all previous structural work on nondeterministic state-minimality computes this measure. Our approach rests on an algebraic interpretation of nondeterministic finite automata as deterministic finite automata endowed with semilattice structure. Crucially, the latter form a self-dual category.

APA, Harvard, Vancouver, ISO, and other styles

4

Kozen, Dexter C. "Collapsing Nondeterministic Automata." In Automata and Computability. Springer New York, 1997. http://dx.doi.org/10.1007/978-1-4612-1844-9_18.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kozen, Dexter C. "Nondeterministic Finite Automata." In Automata and Computability. Springer New York, 1997. http://dx.doi.org/10.1007/978-1-4612-1844-9_5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Rosenberg, Arnold L. "Nondeterministic Online Automata." In The Pillars of Computation Theory. Springer New York, 2009. http://dx.doi.org/10.1007/978-0-387-09639-1_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Myers, Robert S. R., Jiří Adámek, Stefan Milius, and Henning Urbat. "Canonical Nondeterministic Automata." In Advanced Information Systems Engineering. Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44124-4_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Nießner, Frank. "Nondeterministic Tree Automata." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2002. http://dx.doi.org/10.1007/3-540-36387-4_8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Holzer, Markus, and Martin Kutrib. "Reversible Nondeterministic Finite Automata." In Reversible Computation. Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-59936-6_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Alur, Rajeev, and Jyotirmoy V. Deshmukh. "Nondeterministic Streaming String Transducers." In Automata, Languages and Programming. Springer Berlin Heidelberg, 2011. http://dx.doi.org/10.1007/978-3-642-22012-8_1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "NONDETERMINISTIC AUTOMATON"

1

Szpak, Rodrigo, and Max Hering de Queiroz. "Design and Implementation of Supervisory Control for an Electropneumatic Station Subject to Faults in Material Flow." In 9th FPNI Ph.D. Symposium on Fluid Power. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/fpni2016-1542.

Full text

Abstract:

Human intervention in automated manufacturing systems may result in faults in material flow leading to incoherent behavior of the control system. Particularly when multiple workpieces can be operated concurrently, the design of a programmable logic controller (PLC) that can handle such nondeterministic events is a complex task that justifies the use of formal methods such as the Supervisory Control Theory (SCT). The main objective of this work is the use of SCT for the systematic design of the automation system of an electro-pneumatic station of a Modular Production System prone to faults in t

APA, Harvard, Vancouver, ISO, and other styles

2

Ito, Masami. "Deterministic and Nondeterministic Directable Automata." In Proceedings of the Conference. WORLD SCIENTIFIC, 2005. http://dx.doi.org/10.1142/9789812703118_0008.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

CALUDE, CRISTIAN S., and ELENA CALUDE. "BISIMULATIONS AND BEHAVIOUR OF NONDETERMINISTIC AUTOMATA." In Proceedings of the 4th International Conference. WORLD SCIENTIFIC, 2000. http://dx.doi.org/10.1142/9789812792464_0006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Schuh, Melanie, and Jan Lunze. "Feedback control of nondeterministic input/output automata." In 2014 IEEE 53rd Annual Conference on Decision and Control (CDC). IEEE, 2014. http://dx.doi.org/10.1109/cdc.2014.7040447.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Jiang Kunpeng, Guo Huifang, Zhu Shengping, and Lan Julong. "Nondeterministic finite automata for high-speed network." In International Conference on Automatic Control and Artificial Intelligence (ACAI 2012). Institution of Engineering and Technology, 2012. http://dx.doi.org/10.1049/cp.2012.1244.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

"Controllability for Nondeterministic Finite Automata with Variables." In International Conference on Software Paradigm Trends. SciTePress - Science and and Technology Publications, 2013. http://dx.doi.org/10.5220/0004430604380446.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Jastrzab, Tomasz. "Parallel induction of nondeterministic finite automata revisited." In PROCEEDINGS OF THE INTERNATIONAL CONFERENCE OF COMPUTATIONAL METHODS IN SCIENCES AND ENGINEERING 2017 (ICCMSE-2017). Author(s), 2017. http://dx.doi.org/10.1063/1.5012490.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Su, Rong, Jan H. van Schuppen, and Jacobus E. Rooda. "Supervisor synthesis based on abstractions of nondeterministic automata." In 2008 9th International Workshop on Discrete Event Systems. IEEE, 2008. http://dx.doi.org/10.1109/wodes.2008.4605981.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Kim, Mi-Sook, Wook-jae Jo, and Hong Seong Park. "A nondeterministic flowchart-based script editor." In 2017 17th International Conference on Control, Automation and Systems (ICCAS). IEEE, 2017. http://dx.doi.org/10.23919/iccas.2017.8204271.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Abdulghafour, Muhamad, and Mongi A. Abidi. "Data fusion through nondeterministic approaches: a comparison." In Optical Tools for Manufacturing and Advanced Automation, edited by Paul S. Schenker. SPIE, 1993. http://dx.doi.org/10.1117/12.150253.

Full text

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!