Journal articles: '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

11

Birget, Jean-Camille. "Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem." International Journal of Algebra and Computation 08, no. 02 (April 1998): 235–94. http://dx.doi.org/10.1142/s0218196798000132.

Full text

Abstract:

The following algebraic characterization of the computational complexity of the word problem for finitely generated semigroups is proved, in the form of a refinement of the Higman Embedding Theorem: Let S be a finitely generated semigroup whose word problem has nondeterministic time complexity T (where T is a function on the positive integers which is superadditive, i.e. T(n+m) ≥T(n)+T(m)). Then S can be embedded in a finitely presented semigroup H in which the derivation distance between any two equivalent words x and y (and hence the isoperimetric function) is O (T(∣x∣+∣y∣)2). Moreover, there is a conjunctive linear-time reduction from the word problem of H to the word problem of S, so the word problems of S and H have the same nondeterministic time complexity (and also the same deterministic time complexity). Thus, a finitely generated semigroup S has a word problem in NTIME(T) (or in DTIME(To)) iff S is embeddable into a finitely presented semigroup H whose word problem is in NTIME(T) (respectively in DTIME(To)). In the other direction, if a finitely generated semigroup S is embeddable in a finitely presented semigroup H with isoperimetric function ≤ D (where D(n) ≥ n), then the word problem of S has nondeterministic time complexity O(D). The word problem of a finitely generated semigroup S is in NP (or more generally, in NTIME((T) O(1) )) iff S can be embedded in a finitely presented semigroup H with polynomial (respectively (T) O(1) ) isoperimetric function. An algorithmic problem L is in NP (or more generally, in NTIME((T) O(1) )) iff L is reducible (via a linear-time one-to-one reduction) to the word problem of a finitely presented semigroup with polynomial (respectively (T) O(1) ) isoperimetric function. In essence, this shows: (1) Finding embeddings into finitely presented semigroups or groups is an algebraic analogue of nondeterministic algorithm design; (2) the isoperimetric function is an algebraic analogue of nondeterministic time complexity.

APA, Harvard, Vancouver, ISO, and other styles

12

Coelho, Rajan Filomeno, and Philippe Bouillard. "Multi-Objective Reliability-Based Optimization with Stochastic Metamodels." Evolutionary Computation 19, no. 4 (December 2011): 525–60. http://dx.doi.org/10.1162/evco_a_00034.

Full text

Abstract:

This paper addresses continuous optimization problems with multiple objectives and parameter uncertainty defined by probability distributions. First, a reliability-based formulation is proposed, defining the nondeterministic Pareto set as the minimal solutions such that user-defined probabilities of nondominance and constraint satisfaction are guaranteed. The formulation can be incorporated with minor modifications in a multiobjective evolutionary algorithm (here: the nondominated sorting genetic algorithm-II). Then, in the perspective of applying the method to large-scale structural engineering problems—for which the computational effort devoted to the optimization algorithm itself is negligible in comparison with the simulation—the second part of the study is concerned with the need to reduce the number of function evaluations while avoiding modification of the simulation code. Therefore, nonintrusive stochastic metamodels are developed in two steps. First, for a given sampling of the deterministic variables, a preliminary decomposition of the random responses (objectives and constraints) is performed through polynomial chaos expansion (PCE), allowing a representation of the responses by a limited set of coefficients. Then, a metamodel is carried out by kriging interpolation of the PCE coefficients with respect to the deterministic variables. The method has been tested successfully on seven analytical test cases and on the 10-bar truss benchmark, demonstrating the potential of the proposed approach to provide reliability-based Pareto solutions at a reasonable computational cost.

APA, Harvard, Vancouver, ISO, and other styles

13

Botea, Adi, Akihiro Kishimoto, Evdokia Nikolova, Stefano Braghin, Michele Berlingerio, and Elizabeth Daly. "Computing Multi-Modal Journey Plans under Uncertainty." Journal of Artificial Intelligence Research 65 (August 16, 2019): 633–74. http://dx.doi.org/10.1613/jair.1.11422.

Full text

Abstract:

Multi-modal journey planning, which allows multiple types of transport within a single trip, is becoming increasingly popular, due to a strong practical interest and an increasing availability of data. In real life, transport networks feature uncertainty. Yet, most approaches assume a deterministic environment, making plans more prone to failures such as missed connections and major delays in the arrival. This paper presents an approach to computing optimal contingent plans in multi-modal journey planning. The problem is modeled as a search in an and/or state space. We describe search enhancements used on top of the AO* algorithm. Enhancements include admissible heuristics, multiple types of pruning that preserve the completeness and the optimality, and a hybrid search approach with a deterministic and a nondeterministic search. We demonstrate an NP-hardness result, with the hardness stemming from the dynamically changing distributions of the travel time random variables. We perform a detailed empirical analysis on realistic transport networks from cities such as Montpellier, Rome and Dublin. The results demonstrate the effectiveness of our algorithmic contributions, and the benefits of contingent plans as compared to standard sequential plans, when the arrival and departure times of buses are characterized by uncertainty.

APA, Harvard, Vancouver, ISO, and other styles

14

Essayeh, Chaimaa, Mohammed Raiss El-Fenni, and Hamza Dahmouni. "Cost-Effective Energy Usage in a Microgrid Using a Learning Algorithm." Wireless Communications and Mobile Computing 2018 (April 22, 2018): 1–11. http://dx.doi.org/10.1155/2018/9106430.

Full text

Abstract:

The microgrid is a new concept of integrating the distributed energy resources (DER) within the grid. The management of the heterogeneous sources of energy presents a challenge, especially as most of the DER are unpredictable. Besides, implementing microgrids should be economically beneficial to the customer; this will raise the challenge of decreasing the costs while ensuring the energy balance. In this paper, we used a stochastic approach based on a model-free Markov decision process (MDP) to derive the optimal strategy for the home energy management system. The approach aims to decrease the energy bill while taking into account the intermittency of the renewable energy resources (DER) and other constraints. While other proposals charge the battery from the utility energy, making the state of charge (SOC) of the battery a deterministic variable, our work adopts a scenario where the battery is charged from the excess of the generated energy, which makes the SOC a nondeterministic variable affected by the uncertain character of the renewable energy. Therefore, our model considers the randomness at two levels: renewable energy level and battery SOC level. We take into account the complexity of the solution, and we propose a simple strategy that can be implemented easily in microgrids.

APA, Harvard, Vancouver, ISO, and other styles

15

Zmaranda, Doina, Gianina Gabor, Daniela Elena Popescu, Codruta Vancea, and Florin Vancea. "Using Fixed Priority Pre-emptive Scheduling in Real-Time Systems." International Journal of Computers Communications & Control 6, no. 1 (March 1, 2011): 187. http://dx.doi.org/10.15837/ijccc.2011.1.2213.

Full text

Abstract:

For real-time applications, task scheduling is a problem of paramount importance. Several scheduling algorithms were proposed in the literature, starting from static scheduling or cyclic executives which provide very deterministic yet inflexible behaviour, to the so called best-effort scheduling, which facilitates maximum run-time flexibility but allows only probabilistic predictions of run-time performance presenting a non-predictable and nondeterministic solution. Between these two extremes lies fixed priority scheduling algorithms, such as Rate Monotonic, that is not so efficient for real-time purposes but exhibits a predictable approach because scheduling is doing offline and guarantees regarding process deadlines could be obtained using appropriate analysis methods. This paper investigates the use of Rate Monotonic algorithm by making adjustments in order to make it more suitable for real-time applications. The factors that motivate the interest for fixed priority scheduling algorithms such Rate Monotonic when doing with real-time systems lies in its associated analysis that could be oriented in two directions: schedulability analysis and analysis of process interactions. The analyzing process is carried out using a previously implemented framework that allows modelling, simulation and schedulability analysis for a set of real-time system tasks, and some of the results obtained are presented.

APA, Harvard, Vancouver, ISO, and other styles

16

Aldiab, Motasem, Emi Garcia-Palacios, Danny Crookes, and Sakir Sezer. "Packet Classification by Multilevel Cutting of the Classification Space: An Algorithmic-Architectural Solution for IP Packet Classification in Next Generation Networks." Journal of Computer Systems, Networks, and Communications 2008 (2008): 1–14. http://dx.doi.org/10.1155/2008/603860.

Full text

Abstract:

Traditionally, the Internet provides only a “best-effort” service, treating all packets going to the same destination equally. However, providing differentiated services for different users based on their quality requirements is increasingly becoming a demanding issue. For this, routers need to have the capability to distinguish and isolate traffic belonging to different flows. This ability to determine the flow each packet belongs to is called packet classification. Technology vendors are reluctant to support algorithmic solutions for classification due to their nondeterministic performance. Although content addressable memories (CAMs) are favoured by technology vendors due to their deterministic high-lookup rates, they suffer from the problems of high-power consumption and high-silicon cost. This paper provides a new algorithmic-architectural solution for packet classification that mixes CAMs with algorithms based on multilevel cutting of the classification space into smaller spaces. The provided solution utilizes the geometrical distribution of rules in the classification space. It provides the deterministic performance of CAMs, support for dynamic updates, and added flexibility for system designers.

APA, Harvard, Vancouver, ISO, and other styles

17

RAVIKUMAR, BALA, and NICOLAE SANTEAN. "ON THE EXISTENCE OF LOOKAHEAD DELEGATORS FOR NFA." International Journal of Foundations of Computer Science 18, no. 05 (October 2007): 949–73. http://dx.doi.org/10.1142/s0129054107005078.

Full text

Abstract:

We investigate deterministically simulating (i.e., solving the membership problem for) nondeterministic finite automata (NFA), relying solely on the NFA's resources (states and transitions). Unlike the standard NFA simulation, involving an algorithm which stores at each step all the states reached nondeterministically while reading the input, we consider deterministic finite automata (DFA) with lookahead, which choose the “right” NFA transitions based on a fixed number of input symbols read ahead. This concept, known as lookahead delegation, arose in a formal study of web services composition and its subsequent practical applications. Here we answer several related questions, such as “when is lookahead delegation possible?” and “how hard is it to find a delegator with a given lookahead buffer size?”. In particular, we show that only finite languages have the property that all their NFA have delegators. This implies, among others, that delegation is a machine property, rather than a language property. We also prove that the existence of lookahead delegators for unambiguous NFA is decidable, thus partially solving an open problem. Finally, we show that finding delegators (even for a given buffer size) is hard in general, and is more efficient for unambiguous NFA, and we give an algorithm and a compact characterization for NFA delegation in general.

APA, Harvard, Vancouver, ISO, and other styles

18

Hosseinzadeh, Salaheddin, Hadi Larijani, Krystyna Curtis, and Andrew Wixted. "An Adaptive Neuro-Fuzzy Propagation Model for LoRaWAN." Applied System Innovation 2, no. 1 (March 18, 2019): 10. http://dx.doi.org/10.3390/asi2010010.

Full text

Abstract:

This article proposes an adaptive-network-based fuzzy inference system (ANFIS) model for accurate estimation of signal propagation using LoRaWAN. By using ANFIS, the basic knowledge of propagation is embedded into the proposed model. This reduces the training complexity of artificial neural network (ANN)-based models. Therefore, the size of the training dataset is reduced by 70% compared to an ANN model. The proposed model consists of an efficient clustering method to identify the optimum number of the fuzzy nodes to avoid overfitting, and a hybrid training algorithm to train and optimize the ANFIS parameters. Finally, the proposed model is benchmarked with extensive practical data, where superior accuracy is achieved compared to deterministic models, and better generalization is attained compared to ANN models. The proposed model outperforms the nondeterministic models in terms of accuracy, has the flexibility to account for new modeling parameters, is easier to use as it does not require a model for propagation environment, is resistant to data collection inaccuracies and uncertain environmental information, has excellent generalization capability, and features a knowledge-based implementation that alleviates the training process. This work will facilitate network planning and propagation prediction in complex scenarios.

APA, Harvard, Vancouver, ISO, and other styles

19

Kuznetsov, Andrew V. "Emergence in Interactive Embedded Art." International Journal of Art, Culture and Design Technologies 8, no. 2 (July 2019): 1–19. http://dx.doi.org/10.4018/ijacdt.2019070101.

Full text

Abstract:

This article is devoted to the problem of novelty in embedded art. Exciting possibilities of microelectronics for visual art are considered. Implementations of available microcontrollers, sensors and actuators are given. A new kind of interactions between spectators and artworks with embedded electronics was investigated. Special attention is paid to the effect of emergence, which is generated by this interaction. Computational artwork is being considered in a new unconventional context. An aesthetic difference between the deterministic and nondeterministic algorithms was shown. The combination of acrylic paintings with light-emitting diodes (LEDs) was systematically studied to give useful recommendations for an artistic community. Produced artifacts were demonstrated at exhibitions and were used to teach students at the university and VHS Freiburg, Germany. The results showed a great public interest in embedded electronic systems and a tremendous theoretical and practical perspective for the permanently developing contemporary art.

APA, Harvard, Vancouver, ISO, and other styles

20

Ouyang, Chun-Juan, Ming Leng, Jie-Wu Xia, and Huan Liu. "Vague Sets Security Measure for Steganographic System Based on High-Order Markov Model." Security and Communication Networks 2017 (2017): 1–13. http://dx.doi.org/10.1155/2017/1790268.

Full text

Abstract:

Security measure is of great importance in both steganography and steganalysis. Considering that statistical feature perturbations caused by steganography in an image are always nondeterministic and that an image is considered nonstationary, in this paper, the steganography is regarded as a fuzzy process. Here a steganographic security measure is proposed. This security measure evaluates the similarity between two vague sets of cover images and stego images in terms of n-order Markov chain to capture the interpixel correlation. The new security measure has proven to have the properties of boundedness, commutativity, and unity. Furthermore, the security measures of zero order, first order, second order, third order, and so forth are obtained by adjusting the order value of n-order Markov chain. Experimental results indicate that the larger n is, the better the measuring ability of the proposed security measure will be. The proposed security measure is more sensitive than other security measures defined under a deterministic distribution model, when the embedding is low. It is expected to provide a helpful guidance for designing secure steganographic algorithms or reliable steganalytic methods.

APA, Harvard, Vancouver, ISO, and other styles

21

Luk'yanov, B. D. "Deterministic realizations of nondeterministic automata." Cybernetics and Systems Analysis 32, no. 4 (July 1996): 493–504. http://dx.doi.org/10.1007/bf02366771.

Full text

APA, Harvard, Vancouver, ISO, and other styles

22

KUPFERMAN, ORNA, GILA MORGENSTERN, and ANIELLO MURANO. "TYPENESS FOR ω-REGULAR AUTOMATA." International Journal of Foundations of Computer Science 17, no. 04 (August 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 the complexity and complication of translations between the various classes of automata. For example, we prove that deterministic Büchi automata are co-Büchi type; it follows that a translation from deterministic Büchi to deterministic co-Büchi automata, when exists, involves no blow up. On the other hand, we prove that nondeterministic Büchi automata are not co-Büchi type; it follows that a translation from a nondeterministic Büchi to nondeterministic co-Büchi automata, when exists, should be more complicated than just redefining the acceptance condition. As a third example, by proving that nondeterministic co-Büchi automata are Büchi-powerset type, we show that a translation of nondeterministic co-Büchi to deterministic Büchi automata, when exists, can be done applying the subset construction. We give a complete picture of typeness for the weak, Büchi, co-Büchi, Rabin, and Streett acceptance conditions, and discuss its usefulness.

APA, Harvard, Vancouver, ISO, and other styles

23

HUYNH, DUNG T. "THE COMPLEXITY OF DECIDING CODE AND MONOID PROPERTIES FOR REGULAR SETS." International Journal of Algebra and Computation 02, no. 01 (March 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

24

Holzer, Markus, and Martin Kutrib. "One-Time Nondeterministic Computations." International Journal of Foundations of Computer Science 30, no. 06n07 (September 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

25

VAN ZIJL, LYNETTE. "MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS." International Journal of Foundations of Computer Science 16, no. 05 (October 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

26

Maryanto, Eddy. "AUTOMATA SEBAGAI MODEL PENGENAL BAHASA." Jurnal Ilmiah Matematika dan Pendidikan Matematika 1, no. 2 (October 30, 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

27

Bischof, Simon, Joachim Breitner, Jürgen Graf, Martin Hecker, Martin Mohr, and Gregor Snelting. "Low-deterministic security for low-nondeterministic programs1." Journal of Computer Security 26, no. 3 (April 9, 2018): 335–66. http://dx.doi.org/10.3233/jcs-17984.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Niwiński, Damian, and Igor Walukiewicz. "Deciding Nondeterministic Hierarchy of Deterministic Tree Automata." Electronic Notes in Theoretical Computer Science 123 (March 2005): 195–208. http://dx.doi.org/10.1016/j.entcs.2004.05.015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

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 automaton of the same type that has window size two. Furthermore, we study the expressive power of shrinking RWW- and RRWW-automata the window size of which is just one or two. We show that for shrinking RRWW-automata that are nondeterministic, window size one suffices, while for nondeterministic shrinking RWW-automata, we already need window size two to accept all growing context-sensitive languages. In the deterministic case, shrinking RWW- and RRWW-automata of window size one accept only regular languages, while those of window size two characterize the Church-Rosser languages.

APA, Harvard, Vancouver, ISO, and other styles

30

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 (April 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

31

MESSERSCHMIDT, HARTMUT, and FRIEDRICH OTTO. "ON DETERMINISTIC CD-SYSTEMS OF RESTARTING AUTOMATA." International Journal of Foundations of Computer Science 20, no. 01 (February 2009): 185–209. http://dx.doi.org/10.1142/s0129054109006516.

Full text

Abstract:

Three variants of determinism are introduced for CD-systems of restarting automata, called strict determinism, global determinism, and local determinism. In mode = 1 globally deterministic CD-systems of restarting automata are of the same expressive power as nonforgetting deterministic restarting automata of the same type, which corresponds to the situation for nondeterministic CD-systems. On the other hand, for the various types of restarting automata without auxiliary symbols, strictly deterministic CD-systems of restarting automata are strictly less expressive than the corresponding deterministic types of nonforgetting restarting automata. Further, globally deterministic CD-systems of restarting automata can be simulated by locally deterministic CD-systems of restarting automata of the same type. In fact, we conjecture that, for all types of restarting automata without auxiliary symbols, the latter are strictly more expressive than the former, but they are strictly less expressive than the corresponding nondeterministic CD-systems of restarting automata.

APA, Harvard, Vancouver, ISO, and other styles

32

Geffert, Viliam, and Zuzana Bednárová. "Minimal Size of Counters for (Real-Time) Multicounter Automata." Fundamenta Informaticae 181, no. 2-3 (August 4, 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

33

Moshkov, Mikhail. "Deterministic and Nondeterministic Decision Trees for Rough Computing." Fundamenta Informaticae 41, no. 3 (2000): 301–11. http://dx.doi.org/10.3233/fi-2000-41303.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

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

35

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." ACM SIGPLAN Notices 51, no. 1 (April 8, 2016): 284–97. http://dx.doi.org/10.1145/2914770.2837647.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Berghammer, R., and H. Zierer. "Relational algebraic semantics of deterministic and nondeterministic programs." Theoretical Computer Science 43 (1986): 123–47. http://dx.doi.org/10.1016/0304-3975(86)90172-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Bebják, Andrej, and Ivana Štefáneková. "Separation of deterministic, nondeterministic and alternating complexity classes." Theoretical Computer Science 88, no. 2 (October 1991): 297–311. http://dx.doi.org/10.1016/0304-3975(91)90379-g.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Escudero, Juan Garcia. "Deterministic and nondeterministic quasicrystal patterns with even symmetries." Ferroelectrics 250, no. 1 (February 2001): 327–30. http://dx.doi.org/10.1080/00150190108225093.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Stearns, Richard E. "Deterministic versus nondeterministic time and lower bound problems." Journal of the ACM 50, no. 1 (January 2003): 91–95. http://dx.doi.org/10.1145/602382.602409.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Brasher, J. D., C. F. Hester, and H. J. Caulfield. "Virtually-deterministic quantum computing of nondeterministic polynomial problems." International Journal of Theoretical Physics 30, no. 7 (July 1991): 973–77. http://dx.doi.org/10.1007/bf00673989.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

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

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

ITO, AKIRA, KATSUSHI INOUE, and ITSUO TAKANAMI. "THE SIMULATION OF TWO-DIMENSIONAL ONE-MARKER AUTOMATA BY THREE-WAY TURING MACHINES." International Journal of Pattern Recognition and Artificial Intelligence 03, no. 03n04 (December 1989): 393–404. http://dx.doi.org/10.1142/s0218001489000309.

Full text

Abstract:

We denote a two-dimensional deterministic (nondeterministic) one-marker automaton by 2-DM1 (2-NM1), and a three-way two-dimensional deterministic (nondeterministic) Turing machine by TR2-DTM (TR2-NTM). In this paper, we show that the necessary and sufficient space for TR2-NTMs to simulate 2-DM1s (2-NM1s) is n log n (n2), and the necessary and sufficient space for TR2-DTMs to simulate 2-DM1s (2-NM1s) is 2O(n log n) (2 O(n2)), where n is the number of columns of rectangular input tapes.

APA, Harvard, Vancouver, ISO, and other styles

43

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

Full text

Abstract:

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

APA, Harvard, Vancouver, ISO, and other styles

44

Kwee, Kent, and Friedrich Otto. "Nondeterministic Ordered Restarting Automata." International Journal of Foundations of Computer Science 29, no. 04 (June 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

45

Han, Yo-Sub, Sang-Ki Ko, Timothy Ng, and Kai Salomaa. "State Complexity of Insertion." International Journal of Foundations of Computer Science 27, no. 07 (November 2016): 863–78. http://dx.doi.org/10.1142/s0129054116500349.

Full text

Abstract:

It is well known that the resulting language obtained by inserting a regular language to a regular language is regular. We study the nondeterministic and deterministic state complexity of the insertion operation. Given two incomplete DFAs of sizes m and n, we give an upper bound (m+2)·2mn−m−1·3m and find a lower bound for an asymp-totically tight bound. We also present the tight nondeterministic state complexity by a fooling set technique. The deterministic state complexity of insertion is 2Θ(mn) and the nondeterministic state complexity of insertion is precisely mn+2m, where m and n are the size of input finite automata. We also consider the state complexity of insertion in the case where the inserted language is bifix-free or non-returning.

APA, Harvard, Vancouver, ISO, and other styles

46

Grädel, Erich, and Yuri Gurevich. "Tailoring recursion for complexity." Journal of Symbolic Logic 60, no. 3 (September 1995): 952–69. http://dx.doi.org/10.2307/2275767.

Full text

Abstract:

AbstractWe design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC1 -circuits.

APA, Harvard, Vancouver, ISO, and other styles

47

Fernau, Henning, Martin Kutrib, and Matthias Wendlandt. "Self-Verifying Pushdown and Queue Automata." Fundamenta Informaticae 180, no. 1-2 (May 12, 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 or realtime nondeterministic queue automaton languages whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f, but the gain in economy of description eventually exceeds f when changing from the former system to the latter.

APA, Harvard, Vancouver, ISO, and other styles

48

Nagy, Benedek. "Union-Freeness Revisited — Between Deterministic and Nondeterministic Union-Free Languages." International Journal of Foundations of Computer Science 32, no. 05 (April 23, 2021): 551–73. http://dx.doi.org/10.1142/s0129054121410070.

Full text

Abstract:

Union-free expressions are regular expressions without using the union operation. Consequently, (nondeterministic) union-free languages are described by regular expressions using only concatenation and Kleene star. The language class is also characterised by a special class of finite automata: 1CFPAs have exactly one cycle-free accepting path from each of their states. Obviously such an automaton has exactly one accepting state. The deterministic counterpart of such class of automata defines the deterministic union-free (d-union-free, for short) languages. In this paper [Formula: see text]-free nondeterministic variants of 1CFPAs are used to define n-union-free languages. The defined language class is shown to be properly between the classes of (nondeterministic) union-free and d-union-free languages (in case of at least binary alphabet). In case of unary alphabet the class of n-union-free languages coincides with the class of union-free languages. Some properties of the new subregular class of languages are discussed, e.g., closure properties. On the other hand, a regular expression is in union normal form if it is a finite union of union-free expressions. It is well known that every regular expression can be written in union normal form, i.e., all regular languages can be described as finite unions of (nondeterministic) union-free languages. It is also known that the same fact does not hold for deterministic union-free languages, that is, there are regular languages that cannot be written as finite unions of d-union-free languages. As an important result here we show that every regular language can be defined by a finite union of n-union-free languages. This fact also allows to define n-union-complexity of regular languages.

APA, Harvard, Vancouver, ISO, and other styles

49

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 (January 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

50

Kutrib, Martin, Andreas Malcher, and Matthias Wendlandt. "Set Automata." International Journal of Foundations of Computer Science 27, no. 02 (February 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

Journal articles on the topic 'Deterministic and nondeterministic algorithm'

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