Log in

Relevant bibliographies by topics / Deterministic and nondeterministic algorithm

Contents

Journal articles
Dissertations / Theses
Books
Book chapters
Conference papers
Reports

Academic literature on the topic 'Deterministic and nondeterministic algorithm'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 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 'Deterministic and nondeterministic algorithm.'

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 "Deterministic and nondeterministic algorithm"

1

STEWART, IAIN A. "ON TWO APPROXIMATION ALGORITHMS FOR THE CLIQUE PROBLEM." International Journal of Foundations of Computer Science 04, no. 02 (June 1993): 117–33. http://dx.doi.org/10.1142/s0129054193000080.

Full text

Abstract:

We look at well-known polynomial-time approximation algorithms for the optimization problem MAX-CLIQUE (“find the size of the largest clique in a graph”) with regard to how easy it is to compute the actual cliques yielded by these approximation algorithms. We show that even for two “pretty useless” deterministic polynomial-time approximation algorithms, it is unlikely that the resulting clique can be computed efficiently in parallel. We also show that for each non-deterministic algorithm, it is unlikely that there is some deterministic polynomial-time algorithm that decides whether any given vertex appears in some clique yielded by that nondeterministic algorithm.

APA, Harvard, Vancouver, ISO, and other styles

2

An, Jie, Bohua Zhan, Naijun Zhan, and Miaomiao Zhang. "Learning Nondeterministic Real-Time Automata." ACM Transactions on Embedded Computing Systems 20, no. 5s (October 31, 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

3

Barszcz, Tomasz. "Decomposition of Vibration Signals into Deterministic and Nondeterministic Components and its Capabilities of Fault Detection and Identification." International Journal of Applied Mathematics and Computer Science 19, no. 2 (June 1, 2009): 327–35. http://dx.doi.org/10.2478/v10006-009-0028-0.

Full text

Abstract:

Decomposition of Vibration Signals into Deterministic and Nondeterministic Components and its Capabilities of Fault Detection and IdentificationThe paper investigates the possibility of decomposing vibration signals into deterministic and nondeterministic parts, based on the Wold theorem. A short description of the theory of adaptive filters is presented. When an adaptive filter uses the delayed version of the input signal as the reference signal, it is possible to divide the signal into a deterministic (gear and shaft related) part and a nondeterministic (noise and rolling bearings) part. The idea of the self-adaptive filter (in the literature referred to as SANC or ALE) is presented and its most important features are discussed. The flowchart of the Matlab-based SANC algorithm is also presented. In practice, bearing fault signals are in fact nondeterministic components, due to a little jitter in their fundamental period. This phenomenon is illustrated using a simple example. The paper proposes a simulation of a signal containing deterministic and nondeterministic components. The self-adaptive filter is then applied—first to the simulated data. Next, the filter is applied to a real vibration signal from a wind turbine with an outer race fault. The necessity of resampling the real signal is discussed. The signal from an actual source has a more complex structure and contains a significant noise component, which requires additional demodulation of the decomposed signal. For both types of signals the proposed SANC filter shows a very good ability to decompose the signal.

APA, Harvard, Vancouver, ISO, and other styles

4

CLEOPHAS, LOEK, KEES HEMERIK, and GERARD ZWAAN. "TWO RELATED ALGORITHMS FOR ROOT-TO-FRONTIER TREE PATTERN MATCHING." International Journal of Foundations of Computer Science 17, no. 06 (December 2006): 1253–72. http://dx.doi.org/10.1142/s012905410600439x.

Full text

Abstract:

Tree pattern matching (TPM) algorithms on ordered, ranked trees play an important role in applications such as compilers and term rewriting systems. Many TPM algorithms appearing in the literature are based on tree automata. For efficiency, these automata should be deterministic, yet deterministic root-to-frontier tree automata (DRFTAS) are less powerful than nondeterministic ones, and no root-to-frontier TPM algorithm using a DRFTA has appeared so far. Hoffmann & O'Donnell presented a root-to-frontier TPM algorithm based on an Aho-Corasick automaton recognizing tree stringpaths. No relationship between this algorithm and algorithms using tree automata has however been described. We show that a specific DRFTA can be used for stringpath matching in a root-to-frontier TPM algorithm. This new algorithm provides a missing link between TPM algorithms using stringpath automata and those using tree automata. We also investigate the correspondence between the automata used by the two algorithms.

APA, Harvard, Vancouver, ISO, and other styles

5

Jafarsalehi, A., HR Fazeley, and M. Mirshams. "Spacecraft mission design optimization under uncertainty." Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 230, no. 16 (August 8, 2016): 2872–87. http://dx.doi.org/10.1177/0954406215603416.

Full text

Abstract:

The design of space systems is a complex and multidisciplinary process. In this study, two deterministic and nondeterministic approaches are applied to the system design optimization of a spacecraft which is actually a small satellite in low Earth orbit with remote sensing mission. These approaches were then evaluated and compared. Different disciplines such as mission analysis, payload, electrical power supply, mass model, and launch manifest were properly combined for further use. Furthermore, genetic algorithm and sequential quadratic programming were employed as the system-level and local-level optimizers. The main optimization objective of this study is to minimize the resolution of the satellite imaging payload while there are several constraints. A probabilistic analysis was performed to compare the results of the deterministic and nondeterministic approaches. Analysis of the results showed that the deterministic approaches may lead to an unreliable design (because of leaving little or no room for uncertainties), while using the reliability-based multidisciplinary design optimization architecture, all probabilistic constraints were satisfied.

APA, Harvard, Vancouver, ISO, and other styles

6

Amoiralis, Eleftherios I., Marina A. Tsili, Dimitrios G. Paparigas, and Antonios G. Kladas. "Global Transformer Design Optimization Using Deterministic and Nondeterministic Algorithms." IEEE Transactions on Industry Applications 50, no. 1 (January 2014): 383–94. http://dx.doi.org/10.1109/tia.2013.2288417.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

JACK, JOHN, ALFONSO RODRÍGUEZ-PATÓN, OSCAR H. IBARRA, and ANDREI PĂUN. "DISCRETE NONDETERMINISTIC MODELING OF THE FAS PATHWAY." International Journal of Foundations of Computer Science 19, no. 05 (October 2008): 1147–62. http://dx.doi.org/10.1142/s0129054108006194.

Full text

Abstract:

Computer modeling of molecular signaling cascades can provide useful insight into the underlying complexities of biological systems. We present a refined approach for the discrete modeling of protein interactions within the environment of a single cell. The technique we offer utilizes the Membrane Systems paradigm which, due to its hierarchical structure, lends itself readily to mimic the behavior of cells. Since our approach is nondeterministic and discrete, it provides an interesting contrast to the standard deterministic ordinary differential equations techniques. We argue that our approach may outperform ordinary differential equations when modeling systems with relatively low numbers of molecules – a frequent occurrence in cellular signaling cascades. Refinements over our previous modeling efforts include the addition of nondeterminism for handling reaction competition over limited reactants, increased efficiency in the storing and sorting of reaction waiting times, and modifications of the model reactions. Results of our discrete simulation of the type I and type II Fas-mediated apoptotic signaling cascade are illustrated and compared with two approaches: one based on ordinary differential equations and another based on the well-known Gillespie algorithm.

APA, Harvard, Vancouver, ISO, and other styles

8

Börger, Egon, and Klaus-Dieter Schewe. "A Behavioural Theory of Recursive Algorithms." Fundamenta Informaticae 177, no. 1 (December 18, 2020): 1–37. http://dx.doi.org/10.3233/fi-2020-1978.

Full text

Abstract:

“What is an algorithm?” is a fundamental question of computer science. Gurevich’s behavioural theory of sequential algorithms (aka the sequential ASM thesis) gives a partial answer by defining (non-deterministic) sequential algorithms axiomatically, without referring to a particular machine model or programming language, and showing that they are captured by (nondeterministic) sequential Abstract State Machines (nd-seq ASMs). However, recursive algorithms such as mergesort are not covered by this theory, as has been pointed out by Moschovakis, who had independently developed a different framework to mathematically characterize the concept of (in particular recursive) algorithm. In this article we propose an axiomatic definition of the notion of sequential recursive algorithm which extends Gurevich’s axioms for sequential algorithms by a Recursion Postulate and allows us to prove that sequential recursive algorithms are captured by recursive Abstract State Machines, an extension of nd-seq ASMs by a CALL rule. Applying this recursive ASM thesis yields a characterization of sequential recursive algorithms as finitely composed concurrent algorithms all of whose concurrent runs are partial-order runs.

APA, Harvard, Vancouver, ISO, and other styles

9

He, Wei, Yun Fei Guo, and Hong Chao Hu. "Hybrid Finite Automata-Based Algorithm for Large Scale Regular Expression Matching." Applied Mechanics and Materials 263-266 (December 2012): 3108–13. http://dx.doi.org/10.4028/www.scientific.net/amm.263-266.3108.

Full text

Abstract:

Fast data transmission put forward high requirements on network content matching (NCM). Due to the high time complexity, Nondeterministic Finite Automata (NFA) was unable to meet the demand of regular expression matching (REM) which was the core of NCM; Transfer NFA to Deterministic Finite Automaton (DFA) could enhance the throughput, but led to state explosion, which increased demand for memory. To balance memory and throughput, state explosion in the transformation from NFA to DFA has been analyzed and a new method DC-DFA is presented for large scale REM. DC-DFA is based on hybrid automata structure which composed of NFA and DFA. DC-DFA introduces GradeOne classification to cut the memory usage and deep classification to improve throughput. The results show that for serious state explosion, DC-DFA could reduce 75% DFA states and improve memory utilization efficiently while maintain high system throughput.

APA, Harvard, Vancouver, ISO, and other styles

10

Niehren, Joachim, and Momar Sakho. "Determinization and Minimization of Automata for Nested Words Revisited." Algorithms 14, no. 3 (February 24, 2021): 68. http://dx.doi.org/10.3390/a14030068.

Full text

Abstract:

We consider the problem of determinizing and minimizing automata for nested words in practice. For this we compile the nested regular expressions (NREs) from the usual XPath benchmark to nested word automata (NWAs). The determinization of these NWAs, however, fails to produce reasonably small automata. In the best case, huge deterministic NWAs are produced after few hours, even for relatively small NREs of the benchmark. We propose a different approach to the determinization of automata for nested words. For this, we introduce stepwise hedge automata (SHAs) that generalize naturally on both (stepwise) tree automata and on finite word automata. We then show how to determinize SHAs, yielding reasonably small deterministic automata for the NREs from the XPath benchmark. The size of deterministic SHAs automata can be reduced further by a novel minimization algorithm for a subclass of SHAs. In order to understand why the new approach to determinization and minimization works so nicely, we investigate the relationship between NWAs and SHAs further. Clearly, deterministic SHAs can be compiled to deterministic NWAs in linear time, and conversely NWAs can be compiled to nondeterministic SHAs in polynomial time. Therefore, we can use SHAs as intermediates for determinizing NWAs, while avoiding the huge size increase with the usual determinization algorithm for NWAs. Notably, the NWAs obtained from the SHAs perform bottom-up and left-to-right computations only, but no top-down computations. This NWA behavior can be distinguished syntactically by the (weak) single-entry property, suggesting a close relationship between SHAs and single-entry NWAs. In particular, it turns out that the usual determinization algorithm for NWAs behaves well for single-entry NWAs, while it quickly explodes without the single-entry property. Furthermore, it is known that the class of deterministic multi-module single-entry NWAs enjoys unique minimization. The subclass of deterministic SHAs to which our novel minimization algorithm applies is different though, in that we do not impose multiple modules. As further optimizations for reducing the sizes of the constructed SHAs, we propose schema-based cleaning and symbolic representations based on apply-else rules that can be maintained by determinization. We implemented the optimizations and report the experimental results for the automata constructed for the XPathMark benchmark.

APA, Harvard, Vancouver, ISO, and other styles

More sources

Dissertations / Theses on the topic "Deterministic and nondeterministic algorithm"

1

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

2

D'Souza, Sammy Raymond. "Parallelizing a nondeterministic optimization algorithm." CSUSB ScholarWorks, 2007. https://scholarworks.lib.csusb.edu/etd-project/3084.

Full text

Abstract:

This research explores the idea that for certain optimization problems there is a way to parallelize the algorithm such that the parallel efficiency can exceed one hundred percent. Specifically, a parallel compiler, PC, is used to apply shortcutting techniquest to a metaheuristic Ant Colony Optimization (ACO), to solve the well-known Traveling Salesman Problem (TSP) on a cluster running Message Passing Interface (MPI). The results of both serial and parallel execution are compared using test datasets from the TSPLIB.

APA, Harvard, Vancouver, ISO, and other styles

3

Kopřiva, Jan. "Srovnání algoritmů při řešení problému obchodního cestujícího." Master's thesis, Vysoké učení technické v Brně. Fakulta podnikatelská, 2009. http://www.nusl.cz/ntk/nusl-222126.

Full text

Abstract:

The Master Thesis deals with logistic module innovation of information system ERP. The principle of innovation is based on implementation of heuristic algorithms which solve Travel Salesman Problems (TSP). The software MATLAB is used for analysis and tests of these algorithms. The goal of Master Thesis is the comparison of selections algorithm, which are suitable for economic purposes (accuracy of solution, speed of calculation and memory demands).

APA, Harvard, Vancouver, ISO, and other styles

4

Schardl, Tao Benjamin. "Design and analysis of a nondeterministic parallel breadth-first search algorithm." Thesis, Massachusetts Institute of Technology, 2010. http://hdl.handle.net/1721.1/61575.

Full text

Abstract:

Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2010.
Cataloged from PDF version of thesis.
Includes bibliographical references (p. 75-77).
I have developed a multithreaded implementation of breadth-first search (BFS) of a sparse graph using the Cilk++ extensions to C++. My PBFS program on a single processor runs as quickly as a standard C++ breadth-first search implementation. PBFS achieves high workefficiency by using a novel implementation of a multiset data structure, called a "bag," in place of the FIFO queue usually employed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are significantly smaller than the number of vertices - a condition met by many real-world graphs - PBFS demonstrates good speedup with the number of processing cores. Since PBFS employs a nonconstant-time "reducer" - a "hyperobject" feature of Cilk++ - the work inherent in a PBFS execution depends nondeterministically on how the underlying work-stealing scheduler load-balances the computation. I provide a general method for analyzing nondeteriministic programs that use reducers. PBFS also is nondeterministic in that it contains benign races which affect its performance but not its correctness. Fixing these races with mutual-exclusion locks slows down PBFS empirically, but it makes the algorithm amenable to analysis. In particular, I show that for a graph G = (V, E) with diameter D and bounded out-degree. this data-race-free version of PBFS algorithm runs in time O((V +E)/P+DIg[supercript 3] (V/D)) on P processors, which means that it attains near-perfect linear speedup if P < (V +E)/DIg[supercript 3] (V/D).
by Tao Benjamin Schardl.
M.Eng.

APA, Harvard, Vancouver, ISO, and other styles

5

Xu, Didi. "Bandwidth extension algorithm for multiple deterministic systems /." View abstract or full-text, 2006. http://library.ust.hk/cgi/db/thesis.pl?MECH%202006%20XU.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Zhang, Hao. "Nondeterministic Linear Static Finite Element Analysis: An Interval Approach." Diss., Available online, Georgia Institute of Technology, 2005, 2005. http://etd.gatech.edu/theses/available/etd-08232005-020145/.

Full text

Abstract:

Thesis (Ph. D.)--Civil and Environmental Engineering, Georgia Institute of Technology, 2006.
White, Donald, Committee Member ; Will, Kenneth, Committee Member ; Zureick, Abdul Hamid, Committee Member ; Hodges, Dewey, Committee Member ; Muhanna, Rafi, Committee Chair ; Haj-Ali, Rami, Committee Member.

APA, Harvard, Vancouver, ISO, and other styles

7

Domingues, Riaal. "A polynomial time algorithm for prime recognition." Diss., Pretoria : [s.n.], 2006. http://upetd.up.ac.za/thesis/available/etd-08212007-100529.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

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

9

Wang, Bo Yu. "Deterministic annealing EM algorithm for robust learning of Gaussian mixture models." Thesis, University of Macau, 2011. http://umaclib3.umac.mo/record=b2493309.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Moon, Kyoung-Sook. "Adaptive Algorithms for Deterministic and Stochastic Differential Equations." Doctoral thesis, KTH, Numerical Analysis and Computer Science, NADA, 2003. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-3586.

Full text

APA, Harvard, Vancouver, ISO, and other styles

More sources

Books on the topic "Deterministic and nondeterministic algorithm"

1

Moshkov, Mikhail. Comparative Analysis of Deterministic and Nondeterministic Decision Trees. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-41728-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Massuthe, P. An algorithm for matching nondeterministic services with operating guidelines. Berlin: Professoren des Institutes für Informatik, 2006.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

3

Agarwal, Pankaj K. Partitioning arrangements of lines: I. An efficient deterministic algorithm. New York: Courant Institute of Mathematical Sciences, New York University, 1989.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

4

Moshkov, Mikhail. Comparative Analysis of Deterministic and Nondeterministic Decision Trees. Springer, 2020.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

5

Sakas, William. Computational Approaches to Parameter Setting in Generative Linguistics. Edited by Jeffrey L. Lidz, William Snyder, and Joe Pater. Oxford University Press, 2016. http://dx.doi.org/10.1093/oxfordhb/9780199601264.013.29.

Full text

Abstract:

This article presents a non-exhaustive history of research that employs computational modeling of human language acquisition in Chomsky’s principles and parameters framework. The history underscores a tension that has evolved in the field between deterministic (triggering) and nondeterministic (search) approaches. Though it is now clear that the original and widely accepted conception of triggering was flawed, results from recent computational modeling efforts indicate that a modified deterministic triggering theory of human language acquisition may be viable after all.

APA, Harvard, Vancouver, ISO, and other styles

6

Laver, Michael, and Ernest Sergenti. Systematically Interrogating Agent-Based Models. Princeton University Press, 2017. http://dx.doi.org/10.23943/princeton/9780691139036.003.0004.

Full text

Abstract:

This chapter develops the methods for designing, executing, and analyzing large suites of computer simulations that generate stable and replicable results. It starts with a discussion of the different methods of experimental design, such as grid sweeping and Monte Carlo parameterization. Next, it demonstrates how to calculate mean estimates of output variables of interest. It does so by first discussing stochastic processes, Markov Chain representations, and model burn-in. It focuses on three stochastic process representations: nonergodic deterministic processes that converge on a single state; nondeterministic stochastic processes for which a time average provides a representative estimate of the output variables; and nondeterministic stochastic processes for which a time average does not provide a representative estimate of the output variables. The estimation strategy employed depends on which stochastic process the simulation follows. Lastly, the chapter presents a set of diagnostic checks used to establish an appropriate sample size for the estimation of the means.

APA, Harvard, Vancouver, ISO, and other styles

7

Allen, Michael P., and Dominic J. Tildesley. Molecular dynamics. Oxford University Press, 2017. http://dx.doi.org/10.1093/oso/9780198803195.003.0003.

Full text

Abstract:

This chapter introduces the classical equations of motion for a system of molecules, and describes their solution by stable, accurate, time-stepping algorithms. Simple atomic systems, rigid molecules, and flexible molecules with and without constraints, are treated, with examples of program code. Quaternions are introduced as useful parameters for solving the rigid-body equations of motion of molecules. A simple example of a multiple timestep algorithm is given, and there is a brief summary of event-driven (hard-particle) dynamics. Examples of constant-temperature molecular dynamics using stochastic and deterministic methods are presented, and the corresponding constant-pressure molecular dynamics methods for fixed and variable box-shape are described. The molecular dynamics method is extended to the treatment of polarizable systems, and dynamical simulation of the grand canonical ensemble is mentioned.

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Deterministic and nondeterministic algorithm"

1

Wu, Yu-Chieh, Yue-Shi Lee, Jie-Chi Yang, and Show-Jane Yen. "An Integrated Deterministic and Nondeterministic Inference Algorithm for Sequential Labeling." In Information Retrieval Technology, 221–30. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-17187-1_21.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Delimata, Paweł, Barbara Marszał-Paszek, Mikhail Moshkov, Piotr Paszek, Andrzej Skowron, and Zbigniew Suraj. "Comparison of Some Classification Algorithms Based on Deterministic and Nondeterministic Decision Rules." In Lecture Notes in Computer Science, 90–105. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010. http://dx.doi.org/10.1007/978-3-642-14467-7_5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Ponzio, Pablo, Ariel Godio, Nicolás Rosner, Marcelo Arroyo, Nazareno Aguirre, and Marcelo F. Frias. "Efficient Bounded Model Checking of Heap-Manipulating Programs using Tight Field Bounds." In Fundamental Approaches to Software Engineering, 218–39. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-71500-7_11.

Full text

Abstract:

AbstractSoftware model checkers are able to exhaustively explore different bounded program executions arising from various sources of non-determinism. These tools provide statements to produce non-deterministic values for certain variables, thus forcing the corresponding model checker to consider all possible values for these during verification. While these statements offer an effective way of verifying programs handling basic data types and simple structured types, they are inappropriate as a mechanism for nondeterministic generation of pointers, favoring the use of insertion routines to produce dynamic data structures when verifying, via model checking, programs handling such data types.We present a technique to improve model checking of programs handling heap-allocated data types, by taming the explosion of candidate structures that can be built when non-deterministically initializing heap object fields. The technique exploits precomputed relational bounds, that disregard values deemed invalid by the structure’s type invariant, thus reducing the state space to be explored by the model checker. Precomputing the relational bounds is a challenging costly task too, for which we also present an efficient algorithm, based on incremental SAT solving.We implement our approach on top of the bounded model checker, and show that, for a number of data structures implementations, we can handle significantly larger input structures and detect faults that is unable to detect.

APA, Harvard, Vancouver, ISO, and other styles

4

Daniel, Gómez González. "Deterministic and Nondeterministic Turing Machine." In Encyclopedia of Sciences and Religions, 624. Dordrecht: Springer Netherlands, 2013. http://dx.doi.org/10.1007/978-1-4020-8265-8_200983.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Klin, Bartek, Sławomir Lasota, and Szymon Toruńczyk. "Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages." In Lecture Notes in Computer Science, 365–84. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-71995-1_19.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Jain, Alok, Kyle Nelson, and Randal E. Bryant. "Verifying nondeterministic implementations of deterministic systems." In Formal Methods in Computer-Aided Design, 109–25. Berlin, Heidelberg: Springer Berlin Heidelberg, 1996. http://dx.doi.org/10.1007/bfb0031803.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Myers, Robert S. R., Stefan Milius, and Henning Urbat. "Nondeterministic Syntactic Complexity." In Lecture Notes in Computer Science, 448–68. Cham: 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

8

Petrenko, A., N. Yevtushenko, and G. Bochmann. "Testing deterministic implementations from nondeterministic FSM specifications." In Testing of Communicating Systems, 125–40. Boston, MA: Springer US, 1996. http://dx.doi.org/10.1007/978-0-387-35062-2_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Razborov, Alexander A. "Lower bounds for deterministic and nondeterministic branching programs." In Fundamentals of Computation Theory, 47–60. Berlin, Heidelberg: Springer Berlin Heidelberg, 1991. http://dx.doi.org/10.1007/3-540-54458-5_49.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Gruber, Hermann, Markus Holzer, and Sebastian Jakobi. "More on Deterministic and Nondeterministic Finite Cover Automata." In Implementation and Application of Automata, 114–26. Cham: Springer International Publishing, 2015. http://dx.doi.org/10.1007/978-3-319-22360-5_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Deterministic and nondeterministic algorithm"

1

Zafar, Nazir Ahmad, and Syed Hasnain Haider Shah. "Algorithmic Formal Proof of Equivalence of Nondeterministic and Deterministic Finite Automata." In 2009 International Conference on Electronic Computer Technology, ICECT. IEEE, 2009. http://dx.doi.org/10.1109/icect.2009.140.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Fasse, Ernest D., and Albert J. Wavering. "Configuration Estimation of Gough-Stewart Platforms Using Extended Kalman Filtering." In ASME 2000 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2000. http://dx.doi.org/10.1115/detc2000/mech-14067.

Full text

Abstract:

Abstract This paper develops extended Kalman filtering algorithms for a generic Gough-Stewart platform assuming realistically available sensors such as length sensors, rate gyroscopes, and accelerometers. The basic idea is to extend existing methods for satellite attitude estimation. The nondeterministic methods are meant to be a practical alternative to existing iterative, deterministic methods for real-time estimation of platform configuration.

APA, Harvard, Vancouver, ISO, and other styles

3

Andrade de Melo, Alexsander, and Mateus De Oliveira Oliveira. "Symbolic Solutions for Symbolic Constraint Satisfaction Problems." In 17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/kr.2020/6.

Full text

Abstract:

A fundamental drawback that arises when one is faced with the task of deterministically certifying solutions to computational problems in PSPACE is the fact that witnesses may have superpolynomial size, assuming that NP is not equal to PSPACE. Therefore, the complexity of such a deterministic verifier may already be super-polynomially lower-bounded by the size of a witness. In this work, we introduce a new symbolic framework to address this drawback. More precisely, we introduce a PSPACE-hard notion of symbolic constraint satisfaction problem where both instances and solutions for these instances are implicitly represented by ordered decision diagrams (i.e. read-once, oblivious, branching programs). Our main result states that given an ordered decision diagram D of length k and width w specifying a CSP instance, one can determine in time f(w,w')*k whether there is an ODD of width at most w' encoding a solution for this instance. Intuitively, while the parameter w quantifies the complexity of the instance, the parameter w' quantifies the complexity of a prospective solution. We show that CSPs of constant width can be used to formalize natural PSPACE hard problems, such as reachability of configurations for Turing machines working in nondeterministic linear space. For such problems, our main result immediately yields an algorithm that determines the existence of solutions of width w in time g(w)*n, where g:N->N is a suitable computable function, and n is the size of the input.

APA, Harvard, Vancouver, ISO, and other styles

4

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

5

Poursina, Mohammad. "An Efficient Application of Polynomial Chaos Expansion for the Dynamic Analysis of Multibody Systems With Uncertainty." In ASME 2014 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2014. http://dx.doi.org/10.1115/detc2014-35226.

Full text

Abstract:

In this paper the mathematical framework of an advanced algorithm is presented to efficiently form and solve the equations of motion of a multibody system involving uncertainty in the system parameters and/or the excitations. The uncertainty is introduced to the system through the application of the polynomial chaos expansion. In this scheme, states of the system, nondeterministic parameters, and the constraint loads are expanded using modal values as well as orthogonal basis functions. Computational complexity of the application of traditional methods to solve the stochastic equations of motion of a multibody system drastically grows as a cubic function of the number of the states of the system, uncertain parameters and the maximum degree of the polynomial chosen for the basis function. The presented method forms the equation of motion of the system without forming the entire mass and Jacobian matrices. In this strategy, the stochastic governing equations of motion of each individual body as well as the one associated with the kinematic constraint at the connecting joint are developed in terms of the basis functions and modal coordinates. Then sweeping the system in two passes assembly and disassembly, one can form and solve the stochastic equations of motion. In the assembly pass the non-deterministic equations of motion of the assemblies are obtained. In the disassembly process, these equations are then recursively solved for the modal values of the spatial accelerations and the constraints loads. In the serial and parallel implementations, computational complexity of the method increases as a linear and logarithmic functions of the number of the states of the system, uncertain variables, and the maximum degree of the basis functions used in the expansion.

APA, Harvard, Vancouver, ISO, and other styles

6

Karimadini, Mohammad, Hai Lin, and Tong Heng Lee. "Decentralized supervisory control: Nondeterministic transitions versus deterministic moves." In 2009 IEEE/ASME International Conference on Advanced Intelligent Mechatronics (AIM). IEEE, 2009. http://dx.doi.org/10.1109/aim.2009.5229834.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Grathwohl, Bjørn Bugge, Fritz Henglein, Ulrik Terp Rasmussen, Kristoffer Aalund Søholm, and Sebastian Paaske Tørholm. "Kleenex: compiling nondeterministic transducers to deterministic streaming transducers." In POPL '16: The 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York, NY, USA: ACM, 2016. http://dx.doi.org/10.1145/2837614.2837647.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Maheri, A., R. Bagali, C. Chilak, F. Scheller, and A. I. Mustafa. "Deterministic versus nondeterministic design of hybrid renewable energy systems." In 2012 2nd International Symposium on Environment-Friendly Energies and Applications (EFEA). IEEE, 2012. http://dx.doi.org/10.1109/efea.2012.6294064.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Finney, Charles E. A., K. Dean Edwards, Miroslav K. Stoyanov, and Robert M. Wagner. "Application of High Performance Computing for Studying Cyclic Variability in Dilute Internal Combustion Engines." In ASME 2015 Internal Combustion Engine Division Fall Technical Conference. American Society of Mechanical Engineers, 2015. http://dx.doi.org/10.1115/icef2015-1172.

Full text

Abstract:

Combustion instabilities in dilute internal combustion engines are manifest in cyclic variability (CV) in engine performance measures such as integrated heat release or shaft work. Understanding the factors leading to CV is important in model-based control, especially with high dilution where experimental studies have demonstrated that deterministic effects can become more prominent. Observation of enough consecutive engine cycles for significant statistical analysis is standard in experimental studies but is largely wanting in numerical simulations because of the computational time required to compute hundreds or thousands of consecutive cycles. We have proposed and begun implementation of an alternative approach to allow rapid simulation of long series of engine dynamics based on a low-dimensional mapping of ensembles of single-cycle simulations which map input parameters to output engine performance. This paper details the use Titan at the Oak Ridge Leadership Computing Facility to investigate CV in a gasoline direct-injected spark-ignited engine with a moderately high rate of dilution achieved through external exhaust gas recirculation. The CONVERGE™ CFD software was used to perform single-cycle simulations with imposed variations of operating parameters and boundary conditions selected according to a sparse grid sampling of the parameter space. Using an uncertainty quantification technique, the sampling scheme is chosen similar to a design of experiments grid but uses algorithms designed to minimize the number of samples required to achieve a desired degree of accuracy. The simulations map input parameters to output metrics of engine performance for a single cycle, and by mapping over a large parameter space, results can be interpolated from within that space. This interpolation scheme forms the basis for a low-dimensional ‘metamodel’ (or model of a model) which can be used to mimic the dynamical behavior of corresponding high-dimensional simulations. Simulations of high-EGR spark-ignition combustion cycles within a parametric sampling grid were performed and analyzed statistically, and sensitivities of the physical factors leading to high CV are presented. With these results, the prospect of producing low-dimensional metamodels to describe engine dynamics at any point in the parameter space will be discussed. Additionally, modifications to the methodology to account for nondeterministic effects in the numerical solution environment are proposed.

APA, Harvard, Vancouver, ISO, and other styles

10

Burjons, Elisabet, Fabian Frei, and Martin Raszyk. "From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata." In 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE, 2021. http://dx.doi.org/10.1109/lics52264.2021.9470688.

Full text

APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Deterministic and nondeterministic algorithm"

1

Caprile, Bruno, and Federico Girosi. A Nondeterministic Minimization Algorithm. Fort Belvoir, VA: Defense Technical Information Center, September 1990. http://dx.doi.org/10.21236/ada231013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Carrano, C. "Eztrack": A single-vehicle deterministic tracking algorithm. Office of Scientific and Technical Information (OSTI), December 2007. http://dx.doi.org/10.2172/924186.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Carrano, C. "Mtrack 1.0": A multi-vehicle, deterministic tracking algorithm. Office of Scientific and Technical Information (OSTI), May 2008. http://dx.doi.org/10.2172/945703.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Liang, Guanfeng, and Nitin Vaidya. Deterministic Consensus Algorithm with Linear Per-Bit Complexity. Fort Belvoir, VA: Defense Technical Information Center, August 2010. http://dx.doi.org/10.21236/ada555082.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Pornin, T. Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA). RFC Editor, August 2013. http://dx.doi.org/10.17487/rfc6979.

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!