Y. Fang, X. Zhang, Xuya Cong et al. · 2025
This paper studies the design of nondeterministic supervisors for Petri nets with uncontrollable and unobservable transitions under replacement attacks. We focus on the problem of liveness enforcement. We use the basic reachability graph (BRG) to deal with the unobservable and uncontrollable transitions in the Petri net. Then, we observe the transition in real time, and disable the transition online and randomly according to the disabled set computed by the proposed algorithm, so as to eliminate the ambiguity of the system observation brought by replacement attack. To the best of knowledge, this algorithm is the first to propose a liveness enforcement nondeterministic supervisor that tolerates replacement attacks in systems with unobservable and uncontrollable transitions.
Cited by 0
Angelo Borsotti, Luca Breveglieri, Angelo Morzenti et al. · 2025
Speculative data-parallel algorithms for language recognition have been widely experimented for various types of finitestate automata (FA), deterministic (DFA) and nondeterministic (NFA), often derived fromregular expressions (RE). Such an algorithm cuts the input string into chunks, independently recognizes each chunk in parallel by means of identical FAs, and at last joins the chunk results and checks the overall consistency. In chunk recognition, it is necessary to speculatively start the FAs in any state, thus causing an overhead that reduces the speedup over a serial algorithm. The existing data-parallel DFA-based recognizers suffer from an excessive number of starting states, and the NFA-based ones suffer from the number of nondeterministic transitions.
Cited by 1Open access
Yifan Xie, Xiang Yin, Shaoyuan Li · IEEE Transactions on Automatic Control · 2021
In this article, we investigate the enforcement of opacity via supervisory control in the context of discrete-event systems. A system is said to be opaque if the intruder, which is modeled as a passive observer, can never infer confidently that the system is at a secret state. The design objective is to synthesize a supervisor such that the closed-loop system is opaque even when the control policy is publicly known. In this article, we propose a new approach for enforcing opacity using nondeterministic supervisors. A nondeterministic supervisor is a decision mechanism that provides <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a set of control decisions</i> at each instant, and randomly picks a specific control decision from the decision set to actually control the plant. Compared with the standard deterministic control mechanism, such a nondeterministic control mechanism can enhance the plausible deniability of the controlled system as the online control decision is a random realization and cannot be implicitly inferred from the control policy. We provide a sound and complete algorithm for synthesizing a nondeterministic opacity-enforcing supervisor. Furthermore, we show that nondeterministic supervisors are strictly more powerful than deterministic supervisors in the sense that there may exist a nondeterministic opacity-enforcing supervisor even when deterministic supervisors cannot enforce opacity.
Cited by 26
Adolfo Gustavo, Serra Seca Neto, Marcelo Finger · 2008
When a computer program is written to implement a nondeterministic algorithm, it must have a strategy for choosing the next step that is going to be performed. Automated Theorem Provers (ATP’s) usually implement nondeterministic algorithms, therefore the representation of strategies is a very important part of their design. A multi-strategy theorem prover is an ATP where we can vary the strategy without modifying the implementation. In this paper we present some remarks towards the development of an aspect-oriented multi-strategy prover. 1
Cited by 0
L. Petrone · 1968
A definition of meaning is given for languages that possess a parsing algorithm. This definition leads to consider a class of mappings called syntax directed mappings. The behavior of contextfree languages is studied in relation to the defined class of mappings and it is shown that the translation can be implemented in two passes: first by a nondeterministic push down automaton and then by a two-way deterministic push down automaton. Nondeterministic sequential machines are also studied as a particular elementary case of syntax directed mappings.
Cited by 11
Fuchun Liu, Hai Lin, Zbigniew Dziong · Automatica · 2013
Cited by 0
Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse · 2005
Abstract. We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q-branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q ≥ 0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers.
Cited by 0
Dimitris J. Kavvadias, Elias C. Stavropoulos · 2003
We present an algorithm that checks the duality of a pair of monotone Boolean expressions in disjunctive normal form in polynomial time plus O(log&amp;sup2; n/log log n) nondeterministic guesses, where n is the size of the input, thus improving a previous result of Kavvadias and Stavropoulos [IPL, 85(1):1-6, 2003] and Eiter et al. [STOC 2003] which placed the problem in co-NP[log&amp;sup2; n], the subclass of co-NP where only the first O(log&amp;sup2; n) steps are nondeterministic.
Cited by 0
Boris Melnikov · Fundamenta Informaticae · 2010
We consider in this paper the problem of edge-minimization for nondeterministic finite automata and some connected questions. We shall formulate a new algorithm solving this problem; this algorithm is a simplification of two ones published before. The connected problems include at first algorithms of combining states. We formulate some new sufficient conditions for the possibility of such combining.
Cited by 16
Huiqin Li, Yongyi Yan, Chao Dong et al. · 2023
To ensure the safety of discrete event systems, detecting the nonblocking property of the system is an effective approach. This paper proposes a matrix-based method to address the nonblocking property detection problem for partially observed discrete event systems. Firstly, we introduce nondeterministic output functions to represent the state dependency and nondeterministic of partial event observations, and model the partially observed discrete event systems as Mealy finite state machines with nondeterministic output functions. Furthermore, we utilize a novel matrix method called semi-tensor product to establish algebraic expressions for the finite state machine. Based on the obtained algebraic expressions, we analyze the nonblocking property verification problems of the finite state machine from a state perspective. We propose an algebraic algorithm to identify potentially blocking states in the finite state machine.
Cited by 0
L. Iocchi, T. Lukasiewicz, D. Nardi et al. · 2004
about actions with sensing under qualitative and probabilistic uncertainty, which is an extension of the description logic by actions with nondeterministic and probabilistic effects. We define a formal semantics of PN-ALCK in terms of deterministic, nondeterministic, and probabilistic transitions between epistemic states, which are sets of possible states of the world. We introduce the notions of a conditional plan and its goodness under qualitative and probabilistic uncertainty. We then formulate the problem of conditional planning in this framework, and we present an algorithm for solving it. This algorithm is based on a reduction to reasoning in description logics, and is shown to be sound and complete in the sense that it generates all optimal plans. We also describe an application in a robotic-soccer scenario.
Cited by 0
Boris Melnikov, M. R. Saifullina · Russian Mathematics · 2009
In this paper we consider algorithms which allow one to combine several states of a nondeterministic finite automaton into one state. Along with the algorithms for combining states, we adduce one more algorithm for the equivalent transformation of a non-deterministic finite automaton, namely, an algorithm for adding cycles. Problems under consideration imply the development of robust computer programs.
Cited by 1
2015
Abstract. We present detailed description of simulation of nondeterministic nite automata (NFA) for approximate string matching. This simulation uses bit parallelism and used algorithm is called Shift-Or algorithm. Using knowledge of simulation of NFA by Shift-Or algorithm we design modication of Shift-Or algorithm for approximate string matching using generalized Levenshtein distance and modication for exact and approximate sequence matching. Key words: nite automata, approximate string matching, simulation of non-deterministic nite automata, bitwise parallelism 1
Cited by 0
Christel Baier A, Holger Hermanns B · 2008
Bisimulations that abstract from internal computation have proven to be useful for verification of compositionally defined transition systems. In the literature of probabilistic extensions of such transition systems, similar bisimulations are rare. In this paper, we introduce weak and branching bisimulation for fully probabilistic systems, transition systems where nondeterministic branching is replaced by probabilistic branching. In contrast to the nondeterministic case, both relations coincide. We give an algorithm to decide weak (and branching) bisimulation with a time complexity cubic in the number of states of the fully probabilistic system. This meets the worst case complexity for deciding branching bisimulation in the nondeterministic case. In addition, the relation is shown to be a congruence with respect to the operators of PLSCCS, a lazy synchronous probabilistic variant of CCS. We illustrate that due to these properties, weak bisimulation provides all the crucial ingredients
Cited by 0
Mohammad Poursina · Journal of Computational and Nonlinear Dynamics · 2015
In this paper, an advanced algorithm is presented to efficiently form and solve the equations of motion of multibody problems involving uncertainty in the system parameters and/or excitations. Uncertainty is introduced to the system through the application of polynomial chaos expansion (PCE). In this scheme, states of the system, nondeterministic parameters, and constraint loads are projected onto the space of specific orthogonal base functions through modal values. Computational complexity of traditional methods of forming and solving the resulting governing equations drastically grows as a cubic function of the size of the nondeterministic system which is significantly larger than the original deterministic multibody problem. In this paper, the divide-and-conquer algorithm (DCA) will be extended to form and solve the nondeterministic governing equations of motion avoiding the construction of the mass and Jacobian matrices of the entire system. In this strategy, stochastic governing equations of motion of each individual body as well as those associated with kinematic constraints at connecting joints are developed in terms of base functions and modal terms. Then using the divide-and-conquer scheme, the entire system is swept in the assembly and disassembly passes to recursively form and solve nondeterministic equations of motion for modal values of spatial accelerations and constraint loads. In serial and parallel implementations, computational complexity of the method is expected to, respectively, increase as a linear and logarithmic function of the size.
Cited by 10
Ruirui Huang, Longfei Wang · Research Square · 2025
Cited by 0Open access
Tzu-Han Hsu, Borzoo Bonakdarpour, Bernd Finkbeiner et al. · Lecture notes in computer science · 2023
Abstract Many types of attacks on confidentiality stem from the nondeterministic nature of the environment that computer programs operate in. We focus on verification of confidentiality in nondeterministic environments by reasoning about asynchronous hyperproperties . We generalize the temporal logic to allow nested trajectory quantification, where a trajectory determines how different execution traces may advance and stutter. We propose a bounded model checking algorithm for based on QBF-solving for a fragment of and evaluate it by various case studies on concurrent programs, scheduling attacks, compiler optimization, speculative execution, and cache timing attacks. We also rigorously analyze the complexity of model checking .
Cited by 7Open access
Parosh Aziz Abdulla, Johanna Högberg, et al. · 2010
We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of O(ˆr m log n), where ˆr is the maximum rank of the input alphabet, m is the total size of the transition table, and n is the number of states.
Cited by 0
Friedhelm Meyer auf der Heide, Kamil Swirkot · 2013
We study the complexity theory for the local distributed setting introduced by Korman, Peleg and Fraigniaud in their seminal paper [3]. They have defined three complexity classes LD (Local Decision), NLD (Nondeterministic Local Decision) and NLD#n. The class LD consists of all languages which can be decided with a constant number of communication rounds. The class NLD consists of all lan-guages which can be verified by a nondeterministic algorithm with a constant number of communication rounds. In order to define the nondeterministic classes, they have transferred the notation of nondeter-minism into the distributed setting by the use of certificates and verifiers. The classNLD#n consists of all languages which can be verified by a nondeterministic algorithm where each node has access to an oracle for the number of nodes. They have shown the hierarchy LD ( NLD ( NLD#n. Our main contributions are strict hierarchies within the classes defined by Korman, Peleg and Fraig-niaud. We define additional complexity classes: the class LD(t) consists of all languages which can be decided with at most t communication rounds. The class NLD(O(f)) consists of all languages which can be verified by a local verifier such that the size of the certificates that are needed to verify the language are bounded by a function from O(f). Our main result is the following hierarchy within the nondeterministic classes: LD ( NLD(O(1)) ( NLD(O(log n)) ( NLD(O(n)) ( NLD(O(n2)) ⊆ NLD(O(n2 + |w|)) = NLD. In order to prove this hierarchy, we give several lower bounds on the sizes of certificates that are needed to verify some languages from NLD. For the deterministic classes we prove the following hierarchy:
Cited by 0
Ruirui Huang, Longfei Wang · Numerical Algorithms · 2025
Cited by 0