Chang Liu, Xiaowei Qin, Sihai Zhang et al. · Journal of Communications and Networks · 2011
In this paper, we consider resource allocation with proportional fairness in the downlink orthogonal frequency division multiple access relay networks, in which relay nodes operate in decode-and-forward mode. A joint optimization problem is formulated for relay selection, subcarrier assignment and power allocation. Since the formulated primal problem is nondeterministic polynomial time-complete, we make continuous relaxation and solve the dual problem by Lagrangian dual decomposition method. A near-optimal solution is obtained using Karush-Kuhn-Tucker conditions. Simulation results show that the proposed algorithm provides superior system throughput and much better fairness among users comparing with a heuristic algorithm.
Cited by 19
Yong Li, Andrea Turrini, Weizhi Feng et al. · Lecture notes in computer science · 2022
Abstract The determinization of a nondeterministic Büchi automaton (NBA) is a fundamental construction of automata theory, with applications to probabilistic verification and reactive synthesis. The standard determinization constructions, such as the ones based on the Safra-Piterman’s approach, work on the whole NBA. In this work we propose a divide-and-conquer determinization approach. To this end, we first classify the strongly connected components (SCCs) of the given NBA as inherently weak, deterministic accepting, and nondeterministic accepting. We then present how to determinize each type of SCC independently from the others; this results in an easier handling of the determinization algorithm that takes advantage of the structure of that SCC. Once all SCCs have been determinized, we show how to compose them so to obtain the final equivalent deterministic Emerson-Lei automaton, which can be converted into a deterministic Rabin automaton without blow-up of states and transitions. We implement our algorithm in our tool COLA and empirically evaluate COLA with the state-of-the-art tools Spot and Owl on a large set of benchmarks from the literature. The experimental results show that our prototype COLA outperforms Spot and Owl regarding the number of states and transitions.
Cited by 2Open access
Carsten Fritz · MACAU (Kiel University) · 2013
We analyze simulation relations as heuristics for the simplification of omega-automata, i.e., of finite automata working on infinite strings. Our focus is on alternating omega-automata. We introduce direct, delayed, and fair simulation for alternating Büchi automata (ABA) and show that these relations are preorders, they imply language containment, and they can be computed in polynomial time. We introduce quotient constructions for ABA suited for direct and delayed simulation, and we show that our notions of simulation are compatible with the standard translation of ABA to non-alternating automata. We apply these results to the problem of translating formulas of propositional linear-time temporal logic (LTL) to nondeterministic automata. We develop a translation algorithm from LTL to equivalent nondeterministic automata with an on-the-fly use of simulation relations for simplification, and we compare our approach to tableau-based translation algorithms. We extend our notion of delayed simulation to alternating parity automata (APA), introduce variants of this relation suited for quotienting of APA, and develop a simulation-based simplification algorithm for APA. We give a sketch of how to apply these results to a fragment of the modal mu-calculus.
Cited by 9Open access
June Sung Park · 2015
The OMG Essence standard has recently been published as the kernel for software engineering methods [1]. We show that the Essence view of software engineering is reminiscent of a nondeterministic, multidimensional finite state machine, and that the Essence lends support to a semi-Markov decision process model of software engineering which, in practice, facilitates a goal-driven adaptive software engineering. We develop an activity-state mapping algorithm and a goal-activity cover algorithm based on the Essence, which can help automate the health monitoring of project states and the adaptive planning of project activities in a software engineering project.
Cited by 6
Marta Kwiatkowska, Gethin Norman, David Parker et al. · 1999
Symbolic model checking for purely probabilistic processes using MTBDDs [12] was introduced in [4] and further developed in [20, 3]. In this paper we consider models for concurrent probabilistic systems similar to those of [28, 7, 5] and the concurrent Markov chains of [35, 13], which extend the purely probabilistic processes through the addition of nondeterministic choice. As a specification formalism we use probabilistic branchingtime temporal logic PBTL of [5, 7], which allows to express properties such as “under any scheduling of nondeterministic choices, the probability of φ holding until ψ is true is at least 0.78”. In [5, 7] it is shown that the verification of “until ” properties can be reduced to a linear programming problem and solved with the help of e.g. the simplex algorithm, but no symbolic model checking is considered. Based on the algorithms of [5, 7], we derive symbolic model checking procedure for PBTL over concurrent probabilistic systems using MTBDDs. We furthermore implement an experimental model checker using the Colorado University Decision Diagrams (CUDD) package [32]. Our key contribution is an implementation of the simplex algorithm in terms of MTBDDs. 1
Cited by 0
Stephen J. Balut · Management Science · 1973
The n job, one-machine scheduling problem is considered where set-up and processing times are random and the objective is to minimize the number of late jobs. In the deterministic case, Moore's algorithm is known to produce an optimal schedule. A chance-constrained formulation of the nondeterministic problem is derived in which a job is processed if the probability that it will be completed prior to its due date is greater than a specified level. A deterministic equivalent problem is achieved to which application of a modification of Moore's algorithm is proven to produce an optimal schedule.
Cited by 49
S. Pelozo, Pedro R. D’argenio · 2014
We present a framework to analyze security properties in distributed protocols. The framework is constructed on top of the so called (strongly) distributed schedulers where secrecy is also considered. Secrecy is presented as an equivalence class on actions to those components that do not have access to such secrets; however these actions can be distinguished by those with appropriate clearance. We also present an algorithm to solve bounded reachability analysis on this kind of models. The algorithm appropriately encodes the nondeterministic model by interpreting the decisions of the schedulers as parameters. The problem is then reduced to a polynomial optimization problem. Note:
Cited by 0
K. Penev, Aristides A. G. Requicha · 2002
A fixture is an arrangement of fixturing modules that locate and hold a workpart during a manufacturing operation. In this work we consider fixtures with frictionless point contacts and present a method for placement of contact points on a non-prismatic 3D workpart. It is a nondeterministic, potential field algorithm for contact point placement. The method provides a basic framework for the integration of heterogeneous high-level fixturing agents through an interface based on zones of attraction and repulsion on the workpart boundary. The algorithm may produce redundant fixtures, and can augment partial solutions to complete form closure fixtures.
Cited by 3
Robi Malik, Hugo Flordal, Hugo Flordal et al. · 2008
A two-pass algorithm for compositional synthesis of modular supervisors for largescale systems of composed finite-state automata is proposed. The first pass provides an efficient method to determine whether a supervisory control problem has a solution, without explicitly constructing the synchronous composition of all components. If a solution exists, the second pass yields an over-approximation of the least restrictive solution which, if nonblocking, is a modular representation of the least restrictive supervisor. Using a new type of equivalence of nondeterministic processes, called synthesis equivalence, a wide range of abstractions can be employed to mitigate state-space explosion throughout the algorithm. 1
Cited by 0
Sohn Kung Hsia, H. Sohn, D. Kung et al. · 2007
One of the biggest problems in regression testing of a concurrent or distributed program is nondeterministic behavior which may produce different results from previous test with same test data. To solve this, we propose a set of synchronized-communication primitives and a new replay algorithm which uses these primitives to arrange all the execution sequences of non-deterministic operations. Compare to existing replay mechanisms, our approach is applied to more general application programs in a distributed computing environment. It also significantly reduces the number of control processes and communication channels that are the overheads for controlling the sequences of nondeterministic operations. Keywords - distributed software testing, replay, non-determinacy, test sequence. 1 Introduction Typical regression testing is re-running after a test and correction to check that the error is corrected or other errors are introduced because of the modification of the program[4]. However, w...
Cited by 0
Christopher Colby, Patrice Godefroid, Lalita Jategaonkar Jagadeesan · ACM SIGPLAN Notices · 1998
We study in this paper the problem of analyzing implementations of open systems --- systems in which only some of the components are present. We present an algorithm for automatically closing an open concurrent reactive system with its most general environment, i.e., the environment that can provide any input at any time to the system. The result is a nondeterministic closed (i.e., self-executable) system which can exhibit all the possible reactive behaviors of the original open system. These behaviors can then be analyzed using VeriSoft, an existing tool for systematically exploring the state spaces of closed systems composed of multiple (possibly nondeterministic) processes executing arbitrary code. We have implemented the techniques introduced in this paper in a prototype tool for automatically closing open programs written in the C programming language. We discuss preliminary experimental results obtained with a large telephone-switching software application developed at Lucent Technologies.
Cited by 14Open access
Salah Karout, Munther Gdeisat, David R. Burton et al. · Applied Optics · 2007
A novel hybrid genetic algorithm (HGA) is proposed to solve the branch-cut phase unwrapping problem. It employs both local and global search methods. The local search is implemented by using the nearest-neighbor method, whereas the global search is performed by using the genetic algorithm. The branch-cut phase unwrapping problem [a nondeterministic polynomial (NP-hard) problem] is implemented in a similar way to the traveling-salesman problem, a very-well-known combinational optimization problem with profound research and applications. The performance of the proposed algorithm was tested on both simulated and real wrapped phase maps. The HGA is found to be robust and fast compared with three well-known branch-cut phase unwrapping algorithms.
Cited by 45
Jean-Camille Birget · International Journal of Algebra and Computation · 1998
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(T o )) iff S is embeddable into a finitely presented semigroup H whose word problem is in NTIME(T) (respectively in DTIME(T o )). 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.
Cited by 32
Jensen, Rune Møller · 2007
In this paper, we present an algorithm for learning nondeterministic multi-agent planning domains from execution examples. The algorithm uses a master-slave decomposition of two population-based stochastic local search algorithms and integrates binary decision diagrams to reduce the size of the search space. Our experimental results show that the learner has high convergence rates due to an aggressive exploitation of example-driven search and an efficient separation of concurrent activities. Moreover, even though the learning problem is at least as hard as learning disjoint DNF formulas, large domains can be learned accurately within a few minutes.
Cited by 0
Johanna Högberg · Natural Language Engineering · 2011
Abstract We present a randomised inference algorithm for regular tree languages. The algorithm takes as input two disjoint finite nonempty sets of trees 𝒫 and 𝒩 and outputs a nondeterministic finite tree automaton that accepts every tree in 𝒫 and rejects every tree in 𝒩. The output automaton typically represents a nontrivial generalisation of the examples given in 𝒫 and 𝒩. To obtain compact output automata, we use a heuristics similar to bisimulation minimisation. The algorithm has time complexity of $\ordo{\negsize \cdot \possize^2}$ , where n 𝒩 and n 𝒫 are the size of 𝒩 and 𝒫, respectively. Experiments are conducted on a prototype implementation, and the empirical results appear to second the theoretical results.
Cited by 2
Xiaochu Wang, Changhao Sun, Ting Sun · IEEE Transactions on Aerospace and Electronic Systems · 2019
Since star identification algorithms most likely yield multiple matching candidates, validation algorithms are required for star trackers. Traditional validation is performed in an iteratively cascaded way by incrementally introducing new star points for help, costing plenty of inefficient lookups and complex combinations, but leading to nondeterministic results only. Focusing on this problem, this paper considers a novel validation idea that the attitude estimate perturbation caused by bounded measuring noises should be bounded as well. As a result, a two-step validation algorithm is proposed following a noniterative deterministic structure. Theoretical analyses and simulation examples are both given to demonstrate the algorithm.
Cited by 9
David B. Johnson, Peter J. Keleher, Willy Zwaenepoel · 1990
In a distributed system using rollback recovery, information saved on stable storage during failure-free execution allows certain states of each process to be restored after a failure. For example, in a system of deterministic processes using message logging and checkpointing, a process state can be restored only if all messages received by the process since its previous checkpoint have been logged. In a system of nondeterministic processes using checkpointing alone, a process state can be restored only if it has been recorded in a checkpoint. Optimistic rollback recovery methods in general record this information asynchronously, assuming that a suitable recoverable system state can be constructed for use during recovery. A system state is called recoverable if and only if it is consistent and the state of each individual component process can be restored. This paper presents a simple algorithm for nding the maximum recoverable system state at any time in a system using optimistic rollback recovery. We show that in such a system, there is always a unique maximum recoverable system state, extending our previous result for deterministic systems using message logging and checkpointing. These new results can be applied both to deterministic and to nondeterministic systems. We have implemented this algorithm on a collection of SUN workstations running the V-System. The algorithm requires no additional communication in the system, and requires little storage for execution. 1
Cited by 0
Nir Piterman, Moshe Y. Vardi · 2002
Traditionally, model checking is applied to finite-state systems and regular specifications. While researchers have successfully extended the applicability of model checking to infinite-state systems, almost all existing work still consider regular specification formalisms. There are, however, many interesting non-regular properties one would like to model check. In this paper we study model checking of pushdown specifications. Our specification formalism is nondeterministic pushdown parity tree automata (PD-NPT). We show that the model-checking problem for regular systems and PD-NPT specifications can be solved in time exponential in the system and the specification. Our model-checking algorithm involves a new solution to the nonemptiness problem of nondeterministic pushdown tree automata, where we improve the best known upper bound from a tripleexponential to a single exponential. We also consider the model-checking problem for context-free systems and PD-NPT specifications and show that it is undecidable.
Cited by 0
Nir Piterman, Moshe Y. Vardi · 2002
Traditionally, model checking is applied to finite-state systems and regular specifications. While researchers have successfully extended the applicability of model checking to infinite-state systems, almost all existing work still consider regular specification formalisms. There are, however, many interesting non-regular properties one would like to model check. In this paper we study model checking of pushdown specifications. Our specification formalism is nondeterministic pushdown parity tree automata (PD-NPT). We show that the model-checking problem for regular systems and PD-NPT specifications can be solved in time exponential in the system and the specification. Our model-checking algorithm involves a new solution to the nonemptiness problem of nondeterministic pushdown tree automata, where we improve the best known upper bound from a tripleexponential to a single exponential. We also consider the model-checking problem for context-free systems and PD-NPT specifications and show that it is undecidable.
Cited by 0
Christopher Colby Loyola, Christopher Colby, Patrice Godefroid et al. · 1998
We study in this paper the problem of analyzing implementations of open systems --- systems in which only some of the components are present. We present an algorithm for automatically closing an open concurrent reactive system with its most general environment, i.e., the environment that can provide any input at any time to the system. The result is a nondeterministic closed (i.e., self-executable) system which can exhibit all the possible reactive behaviors of the original open system. These behaviors can then be analyzed using VeriSoft, an existing tool for systematically exploring the state spaces of closed systems composed of multiple (possibly nondeterministic) processes executing arbitrary code. We have implemented the techniques introduced in this paper in a prototype tool for automatically closing open programs written in the C programming language. We discuss preliminary experimental results obtained with a large telephone-switching software application developed at Lucent Tec...
Cited by 0