Gottlob, Georg, Malizia, Enrico · arXiv (Cornell University) · 2014
The hypergraph duality problem DUAL is defined as follows: given two simple hypergraphs $\mathcal{G}$ and $\mathcal{H}$, decide whether $\mathcal{H}$ consists precisely of all minimal transversals of $\mathcal{G}$ (in which case we say that $\mathcal{G}$ is the dual of $\mathcal{H}$). This problem is equivalent to deciding whether two given non-redundant monotone DNFs are dual. It is known that non-DUAL, the complementary problem to DUAL, is in $\mathrm{GC}(\log^2 n,\mathrm{PTIME})$, where $\mathrm{GC}(f(n),\mathcal{C})$ denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $\mathcal{C}$. It was conjectured that non-DUAL is in $\mathrm{GC}(\log^2 n,\mathrm{LOGSPACE})$. In this paper we prove this conjecture and actually place the non-DUAL problem into the complexity class $\mathrm{GC}(\log^2 n,\mathrm{TC}^0)$ which is a subclass of $\mathrm{GC}(\log^2 n,\mathrm{LOGSPACE})$. We here refer to the logtime-uniform version of $\mathrm{TC}^0$, which corresponds to $\mathrm{FO(COUNT)}$, i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for non-DUAL that requires to guess $O(\log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in $\mathrm{FO(COUNT)}$. From this result, by the well known inclusion $\mathrm{TC}^0\subseteq\mathrm{LOGSPACE}$, it follows that DUAL belongs also to $\mathrm{DSPACE}[\log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $\mathcal{G}$ and $\mathcal{H}$, computes in quadratic logspace a transversal of $\mathcal{G}$ missing in $\mathcal{H}$.
Cited by 0Open access
L. Kari, S. Konstantinidis, S. Perron et al. · 2004
Abstract:- Given an arbitrary (nondeterministic) finite state automaton A we consider the problem of computing the Hamming distance of the language L(A) that is accepted by the automaton. This quantity is simply the minimum Hamming distance between any pair of distinct words from the language L(A). We show an algorithm that solves the problem in time quadratic with respect to the size of the given automaton. To our knowledge, this problem has not been addressed before. Key-Words:- automata, Hamming distance, regular language, shortest-path algorithm. 1.
Cited by 0
Christian Bierwirth, H. Kopfer, Dirk C. Mattfeld et al. · 2002
The application of adaptive optimization methods to production scheduling has recently become a research topic of broad interest. Genetic Algorithm approaches to scheduling concentrate on static problems, whereas real-world scheduling tends to be dynamic. This paper briefly outlines the application of a genetic algorithm to the dynamic job shop problem. In a second step the job shop is regarded as a non-deterministic optimization problem arising from the occurrence of job releases. A temporal decomposition of the nondeterministic problem leads to a scheduling control that combines simulation and adaptive search.
Cited by 32
Hefeng Wang, Lian-Ao Wu · Scientific Reports · 2016
An adiabatic quantum algorithm may lose quantumness such as quantum coherence entirely in its long runtime, and consequently the expected quantum speedup of the algorithm does not show up. Here we present a general ultrafast adiabatic quantum algorithm. We show that by applying a sequence of fast random or regular signals during evolution, the runtime can be reduced substantially, whereas advantages of the adiabatic algorithm remain intact. We also propose a randomized Trotter formula and show that the driving Hamiltonian and the proposed sequence of fast signals can be implemented simultaneously. We illustrate the algorithm by solving the NP-complete 3-bit exact cover problem (EC3), where NP stands for nondeterministic polynomial time, and put forward an approach to implementing the problem with trapped ions.
Cited by 26Open access
J Misra, David Gries · 1990
is free on u) : Each edge X v for v 2 hf::li is called a fan edge. The following (nondeterministic) algorithm constructs a fan F that is maximal, in that it cannot be extended: F := hY i; do (9v :: B) ! F := F cat v where v satisfies B od where B is the predicate B : X v is an edge v = 2 F 1 This work was done while the second author was on sabbatic from Cornell at Austin. 1 color of X v is free on the last vertex of F : The algorithm Our algorithm for coloring edge X Y is given below
Cited by 0
Georg Gottlob, Enrico Malizia · SIAM Journal on Computing · 2018
The hypergraph duality problem Dual is defined as follows: given two simple hypergraphs $\mathcal{G}$ and $\mathcal{H}$, decide whether $\mathcal{H}$ consists precisely of all minimal transversals of $\mathcal{G}$ (in which case we say that $\mathcal{G}$ is the dual of $\mathcal{H}$ or, equivalently, the transversal hypergraph of $\mathcal{H}$). This problem is equivalent to deciding whether two given nonredundant monotone disjunctive normal forms/conjunctive normal forms are dual. It is known that $\overline{{\sc Dual}}$, the complementary problem to Dual, is in GC($\log^2 n$, PTIME), where GC($f(n)$, $\mathcal{C}$) denotes the complexity class of all problems that after a nondeterministic guess of $O(f(n))$ bits can be decided (checked) within complexity class $\mathcal{C}$. It was conjectured that $\overline{{\sc Dual}}$ is in GC($\log^2 n$, LOGSPACE). In this paper we prove this conjecture and actually place the $\overline{{\sc Dual}}$ problem into the complexity class GC($\log^2 n$, TC$^{0}$) which is a subclass of GC($\log^2 n$, LOGSPACE). We here refer to the logtime-uniform version of TC$^{0}$, which corresponds to FO(COUNT), i.e., first order logic augmented by counting quantifiers. We achieve the latter bound in two steps. First, based on existing problem decomposition methods, we develop a new nondeterministic algorithm for $\overline{{\sc Dual}}$ that requires one to guess $O(\log^2 n)$ bits. We then proceed by a logical analysis of this algorithm, allowing us to formulate its deterministic part in FO(COUNT). From this result, by the well-known inclusion ${TC$^0$}\subseteq{LOGSPACE}$, it follows that Dual also belongs to ${DSPACE}[\log^2 n]$. Finally, by exploiting the principles on which the proposed nondeterministic algorithm is based, we devise a deterministic algorithm that, given two hypergraphs $\mathcal{G}$ and $\mathcal{H}$, computes in quadratic logspace a transversal of $\mathcal{G}$ missing in $\mathcal{H}$.
Cited by 20Open access
Peter Lammich · 2009
We present a formalization of Dynamic Pushdown Networks (DPNs) and the automata based algorithm for computing backward reachability sets using Isabelle/HOL. Dynamic pushdown networks are an abstract model for multithreaded, interprocedural programs with dynamic thread creation that was presented by Bouajjani, Mller-Olm and Touili in 2005. We formalize the notion of a DPN in Isabelle and describe the algorithm for computing the pre ∗-set from a regular set of configurations, and prove its correctness. We first give a nondeterministic description of the algorithm, from that we then infer a deterministic one, from which we can generate executable code using Isabelle’s code-generation
Cited by 1
Tomasz Jastrząb · Advances in parallel computing · 2020
The parallel induction algorithm discussed in the paper finds a minimal nondeterministic finite automaton (NFA) consistent with the given sample. The sample consists of examples and counterexamples, i.e., words that are accepted and rejected by the automaton. The algorithm transforms the problem to a family of constraint satisfaction problems solved in parallel. Only the first solution is sought, which means that upon finding a consistent automaton, the remaining processes terminate their execution. We analyze the parallel algorithm in terms of achieved speedups. In particular, we discuss the reasons of the observed superlinear speedups. The analysis includes experiments conducted for the samples defined over the alphabets of different sizes.
Cited by 0Open access
Hikaru Ohnishi, Yutaka Shimada, Kantaro Fujiwara et al. · Nonlinear Theory and Its Applications IEICE · 2017
Quadratic Assignment Problem (QAP) is one of the combinatorial optimization problems which are classified into Nondeterministic Polynomial time solvable (NP)-hard problems. Therefore, it is important to develop algorithms for finding good approximate solutions in short time. In this paper, we proposed an algorithm for approximately solving QAP by using chaotic neurodynamics. The proposed algorithm has three characteristics. First, compared with the conventional method, the number of neurons was substantially reduced. Second, the effect of external inputs to neurons was changed. Third, a new parameter tuning method was introduced. As a result, our algorithm can find good solutions compared with the conventional method using chaotic neurodynamics.
Cited by 3Open access
Anirban Majumdar, Sayan Mukherjee, Jean-François Raskin · ArXiv.org · 2025
This paper presents a state-merging algorithm for learning timed languages definable by Event-Recording Automata (ERA) using positive and negative samples in the form of symbolic timed words. Our algorithm, LEAP (Learning Event-recording Automata Passively), constructs a possibly nondeterministic ERA from such samples based on merging techniques. We prove that determining whether two ERA states can be merged while preserving sample consistency is an NP-complete problem, and address this with a practical SMT-based solution. Our implementation demonstrates the algorithm's effectiveness through examples. We also show that every ERA-definable language can be inferred using our algorithm with a suitable sample.
Cited by 0Open access
Pascal Minnerup · mediaTUM – the media and publications repository of the Technical University Munich (Technical University Munich) · 2017
Nondeterministic behavior of traffic participants and inaccurate sensors and actuators challenge the reliability of autonomous driving planning and control functions. This thesis presents a novel approach for efficiently testing the software implementation of such systems in a simulation environment. The algorithm splits the simulation into short sequences that cover different desired and undesired behaviors of the system. This way, the developed method is more efficient than existing approaches.
Cited by 1Open access
Michael C. Pirrung (419099), Richard V. Connors (1816930), Amy L. Odenbaugh (3008022) et al. · Figshare · 2016
A high fidelity, surface-based method of nucleic acid analysis has been developed based on DNA\npolymerase extension of primer−template complexes on DNA microchips. The ability of the method to\ndiscriminate against mismatches and provide an almost “digital” signal recommended it for molecular\ncomputation. A DNA computer with the capability of solving nondeterministic polynomial time (NP)-complete\nproblems (those whose time−complexity function rises exponentially with the problem size) in polynomial\ntime using this Arrayed Primer EXtension (APEX) method was experimentally demonstrated. An algorithm\ninvolving extension of surface-bound primer−template complexes, representing solutions and clauses of a\nBoolean formula, is described for the solution of two-, three-, and four-variable satisfiability (SAT) problems,\nincluding a 3SAT, exploiting the theoretical concepts of Lipton. A discussion of the principles of nondeterministic\ncomputing with APEX is also provided.
Cited by 0Open access
Kaelbling, L. P., Pasula, H. M., Zettlemoyer, L. S. · arXiv (Cornell University) · 2011
In this article, we work towards the goal of developing agents that can learn to act in complex worlds. We develop a probabilistic, relational planning rule representation that compactly models noisy, nondeterministic action effects, and show how such rules can be effectively learned. Through experiments in simple planning domains and a 3D simulated blocks world with realistic physics, we demonstrate that this learning algorithm allows agents to effectively model world dynamics.
Cited by 0Open access
Wim H. Hesselink · Formal Aspects of Computing · 2025
Waitfree linearization of data objects was introduced by Herlihy in 1991. The present article proposes an algorithm for waitfree linearization of a possibly nondeterministic data object in bounded memory, together with a complete proof of correctness supported by the proof assistant PVS. The project is exceptional in that the proofs of 70 invariants are recorded systematically, and that waitfree progress is quantified in waitfree complexity and is formally proved.
Cited by 0Open access
Matteo Mio, Alex Simpson · Electronic Proceedings in Theoretical Computer Science · 2013
The paper explores properties of {\L}ukasiewicz mu-calculus, a version of the quantitative/probabilistic modal mu-calculus containing both weak and strong conjunctions and disjunctions from {\L}ukasiewicz (fuzzy) logic. We show that this logic encodes the well-known probabilistic temporal logic PCTL. And we give a model-checking algorithm for computing the rational denotational value of a formula at any state in a finite rational probabilistic nondeterministic transition system.
Cited by 10Open access
Athiyah Rizqillah Adzhari, - · Repository at Universitas Pendidikan Indonesia (Universitas Pendidikan Indonesia) · 2020
ABSTRAK \n \nPenelitian ini membahas masalah penjadwalan mata kuliah di departemen pendidikan matematika FPMIPA Universitas Pendidikan Indonesia. Penjadwalan mata kuliah termasuk ke dalam jenis timetabling yang digolongkan sebagai NP-Hard Problem (Nondeterministic Polynomial Time). Oleh karena itu diperlukan suatu metode untuk menyelesaikan masalah penjadwalan mata kuliah. Pada penelitian ini digunakan algoritma Particle Swarm Optimization untuk menyelesaikan masalah penjadwalan mata kuliah di Departemen Pendidikan Matematika FPMIPA Universitas Pendidikan Indonesia. Algoritma Particle Swarm Optimization merupakan algoritma berbasis populasi yang mengeksploitasi partikel dalam pencarian. Hasil implementasi menunjukkan bahwa algoritma Particle Swarm Optimization dapat diimplementasikan untuk masalah penjadwalan mata kuliah di Departemen Pendidikan Matematika FPMIPA Universitas Pendidikan Indonesia. \n \nKata Kunci: Penjadwalan, Algoritma Particle Swarm Optimization, Model Optimisasi, Solusi Optimal. \n \nABSTRACT \n \nThis research disscuss about a lecture timetabling problem at Department of Mathematics Education, Faculty of Mathematics and Science Education, Indonesia. The problem is classified as NP-Hard Problem (Nondeterministic Polynomial Time). Therefore, we need a method to solve the lecture timetabling problem. In this research, we use particle swarm optimization algorithm to solve the problem. The algorithm is a population-based that uses particles searching. The computational result shows that the particle swarm optimization algorithm can be implemented for lecture timetabling problem at Department of Mathematics Education, Faculty of Mathematics and Science Education, Indonesia University of Education. \n \nKeyword: Timetabling, Particle Swarm Optimization Algorithm, Optimization Model, Optimal Solution.
Cited by 0Open access
Shengwen Zhou, Shuai Han, Ming Yang et al. · Scientific Reports · 2026
Customer demand in the production of building material for equipment groups is often regional. Thus, this paper introduces a batch delivery strategy and considers inventory costs. This work studies the scheduling of distributed assembly flexible workshops in equipment groups, batch delivery, and inventory cost problems to establish a mathematical model. This paper proposes a hybrid differential evolution algorithm with variable neighborhood search (VNS) to address this complex nondeterministic polynomial time hard problem. This algorithm combines the powerful global search capability of the differential evolution algorithm with the efficient local search capability of the VNS algorithm. Additionally, considering the characteristics of the batch delivery strategy, this paper designs a maximum batch strategy based on differences in completion times. Finally, through comparative experiments and data analysis, this work validates the effectiveness and superiority of the proposed algorithm.
Cited by 0Open access
Evgeny Dantsin, Andrei Voronkov · 1997
Unification in logic programming deals with tree-like data represented by terms. We extend this unification to terms that represent finite sets and bags (finite multisets). An extended unification algorithm is presented as an algorithm solving equality constraints. This algorithm runs in nondeterministic polynomial time. Thus, the unifiability problem for bags, finite sets and trees is shown to be NP-complete. Our results can be also regarded as results about handling complex values in deductive databases. Namely, our algorithm provides a procedural semantics of logic query languages for bags, finite sets and trees. Contents 1 Introduction 3 2 Bags, sets and trees 5 3 Complex values in logic programs 8 4 Unification algorithm 11 4.1 Some definitions and notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5 Unifiers 21 5.1 Unifiers for D computed by the algor...
Cited by 0
R. M. Hierons, M. Harman · 2015
Abstract. Stream X-machines have been used in order to specify a range of systems. One of the strengths of this approach is that, under certain well defined conditions, it is possible to produce a finite test that is guaranteed to determine the correctness of the implementation under test (IUT). Initially only determin-istic stream X-machines were considered in the literature. This is largely because the standard test algorithm relies on the stream X-machine being deterministic. More recently the problem of testing to determine whether the IUT is equiva-lent to a nondeterministic stream X-machine specification has been tackled ([16]). Since nondeterminism can be important for specifications, this is an extremely useful extension. In many cases, however, we wish to test for a weaker notion of correctness called conformance. This paper considers a particular form of nonde-terminism, within stream X-machines, that shall be called quasi-nondeterminism. It then investigates the generation of tests that are guaranteed to determine whether the IUT conforms to a quasi-nondeterministic stream X-machine speci-fication. The test generation algorithm given is a generalization of that used for testing from a deterministic stream X-machine.
Cited by 0
Ping‐Hei Chen, Mohsen Shahandashti · 2008
This paper proposes a new algorithm using Simulated Annealing (SA) for stochastic scheduling. Stochastic effects are added with nondeterministic activity durations. Simple simulated annealing can not properly handle such a complex problem so an improved version is produced and utilized within the algorithm. Generally, the availability of resources is not enough to complete all the current activities of the project and activities compete for multiple resources which stimulates considering multiple resource constraints in formulation. The superiority of the model over one of the famous heuristics is verified by a numerical example using Monte Carlo method (MC).
Cited by 4