The Experts below are selected from a list of 306108 Experts worldwide ranked by ideXlab platform
Erik D Demaine - One of the best experts on this subject based on the ideXlab platform.
-
pspace completeness of sliding block puzzles and other problems through the nondeterministic constraint logic Model of Computation
Theoretical Computer Science, 2005Co-Authors: Robert A Hearn, Erik D DemaineAbstract:We present a nondeterministic Model of Computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph Model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the "Generalized Rush Hour Logic" developed by Flake and Baum [Theoret. Comput. Sci. 270(1-2) (2002) 8951.We illustrate the importance of our Model of Computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1 × 2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush HourTM puzzles are PSPACE-complete [Theoret. Comput. Sci. 270(1-2) (2002) 895], of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [Int. J. Robot. Res. 3(4) (1984) 76], a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [In: Proc. Internat. Conf. on Fun with Algorithms, Elba, Italy, June 1998, pp. 65-76.], by showing that it is PSPACE-complete even if no barriers are allowed.
-
the nondeterministic constraint logic Model of Computation reductions and applications
International Colloquium on Automata Languages and Programming, 2002Co-Authors: Robert A Hearn, Erik D DemaineAbstract:We present a nondeterministic Model of Computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph Model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restrictedv ertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the "Generalized Rush Hour Logic" developed by Flake and Baum [2].We illustrate the importance of our Model of Computation by giving simple reductions to show that multiple motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restrictedto be all dominoes (1×2 blocks) andthe goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour? puzzles are PSPACE-complete [2], of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [1], by showing that it is PSPACE-complete even if no barriers are allowed.
-
pspace completeness of sliding block puzzles and other problems through the nondeterministic constraint logic Model of Computation
arXiv: Computational Complexity, 2002Co-Authors: Robert A Hearn, Erik D DemaineAbstract:We present a nondeterministic Model of Computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph Model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the ``Generalized Rush Hour Logic'' developed by Flake and Baum. We illustrate the importance of our Model of Computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1x2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour puzzles are PSPACE-complete, of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete, by showing that it is PSPACE-complete even if no barriers are allowed.
Steven Lindell - One of the best experts on this subject based on the ideXlab platform.
-
A constant-space sequential Model of Computation for first-order logic
Information & Computation, 1998Co-Authors: Steven LindellAbstract:We define and justify a natural sequential Model of Computation with a constant amount of read/write work space, despite unlimited (polynomial) access to read-only input and write-only output. The Model is both deterministic, uniform, and sequential. The constant work space is Modeled by a finite number of destructive read boolean variables, assignable by formulas over the canonical boolean operations. We then show that Computation on this Model is equivalent to expressibility in first-order logic, giving a duality between (read-once) constant-space serial algorithms and constant-time parallel algorithms.
-
LCC - A Constant-Space Sequential Model of Computation for First-Order Logic
Lecture Notes in Computer Science, 1995Co-Authors: Steven LindellAbstract:We define and justify a natural sequential Model of Computation with a constant amount of read/write work space, despite unlimited (polynomial) access to read-only input and write-only output. The Model is both deterministic, uniform, and sequential. The constant work space is Modeled by a finite number of destructive read boolean variables, assignable by formulas over the canonical boolean operations. We then show that Computation on this Model is equivalent to expressibility in first-order logic, giving a duality between (read-once) constant-space serial algorithms and constant-time parallel algorithms.
Robert A Hearn - One of the best experts on this subject based on the ideXlab platform.
-
pspace completeness of sliding block puzzles and other problems through the nondeterministic constraint logic Model of Computation
Theoretical Computer Science, 2005Co-Authors: Robert A Hearn, Erik D DemaineAbstract:We present a nondeterministic Model of Computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph Model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the "Generalized Rush Hour Logic" developed by Flake and Baum [Theoret. Comput. Sci. 270(1-2) (2002) 8951.We illustrate the importance of our Model of Computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1 × 2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush HourTM puzzles are PSPACE-complete [Theoret. Comput. Sci. 270(1-2) (2002) 895], of which we also give a simpler proof. We also greatly strengthen the conditions for the PSPACE-hardness of the Warehouseman's Problem [Int. J. Robot. Res. 3(4) (1984) 76], a classic motion-planning problem. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [In: Proc. Internat. Conf. on Fun with Algorithms, Elba, Italy, June 1998, pp. 65-76.], by showing that it is PSPACE-complete even if no barriers are allowed.
-
the nondeterministic constraint logic Model of Computation reductions and applications
International Colloquium on Automata Languages and Programming, 2002Co-Authors: Robert A Hearn, Erik D DemaineAbstract:We present a nondeterministic Model of Computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph Model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restrictedv ertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the "Generalized Rush Hour Logic" developed by Flake and Baum [2].We illustrate the importance of our Model of Computation by giving simple reductions to show that multiple motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restrictedto be all dominoes (1×2 blocks) andthe goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour? puzzles are PSPACE-complete [2], of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete [1], by showing that it is PSPACE-complete even if no barriers are allowed.
-
pspace completeness of sliding block puzzles and other problems through the nondeterministic constraint logic Model of Computation
arXiv: Computational Complexity, 2002Co-Authors: Robert A Hearn, Erik D DemaineAbstract:We present a nondeterministic Model of Computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph Model can be manipulated in order to reverse the direction of a particular edge is shown to be PSPACE-complete by a reduction from Quantified Boolean Formulas. We prove this result in a variety of special cases including planar graphs and highly restricted vertex configurations, some of which correspond to a kind of passive constraint logic. Our framework is inspired by (and indeed a generalization of) the ``Generalized Rush Hour Logic'' developed by Flake and Baum. We illustrate the importance of our Model of Computation by giving simple reductions to show that several motion-planning problems are PSPACE-hard. Our main result along these lines is that classic unrestricted sliding-block puzzles are PSPACE-hard, even if the pieces are restricted to be all dominoes (1x2 blocks) and the goal is simply to move a particular piece. No prior complexity results were known about these puzzles. This result can be seen as a strengthening of the existing result that the restricted Rush Hour puzzles are PSPACE-complete, of which we also give a simpler proof. Finally, we strengthen the existing result that the pushing-blocks puzzle Sokoban is PSPACE-complete, by showing that it is PSPACE-complete even if no barriers are allowed.
Vladimiro Sassone - One of the best experts on this subject based on the ideXlab platform.
-
Application and Theory of Petri Nets - On the Model of Computation of Place/Transition Petri Nets
Lecture Notes in Computer Science, 1994Co-Authors: José Meseguer, Ugo Montanari, Vladimiro SassoneAbstract:In the last few years, the sematics of Petri nets has been investigated in several different ways. Apart from the classical “token game”, one can Model the behaviour of Petri nets via non-sequential processes, via unfolding constructions, which provide formal relationships between nets and domains, and via algebraic Models, which view Petri nets as essentially algebraic theories whose Models are monoidal categories.
Damien Woods - One of the best experts on this subject based on the ideXlab platform.
-
Lower bounds on the Computational power of an optical Model of Computation
Natural Computing, 2008Co-Authors: Damien Woods, J. Paul GibsonAbstract:This work is concerned with the Computational complexity of a Model of Computation that is inspired by optical computers. We present lower bounds on the Computational power of the Model. Parallel time on the Model is shown to be at least as powerful as sequential space. This gives one of the two inclusions that are needed to show that the Model verifies the parallel Computation thesis. As a corollary we find that when the Model is restricted to simultaneously use polylogarithmic time and polynomial space, its power is lower bounded by the class NC. By combining these results with the known upper bounds on the Model, we find that the Model verifies the parallel Computation thesis and, when suitably restricted, characterises NC.
-
ISAAC - Upper bounds on the Computational power of an optical Model of Computation
Algorithms and Computation, 2005Co-Authors: Damien WoodsAbstract:We present upper bounds on the Computational power of an optical Model of Computation called the $\mathcal{C}_{2}$-CSM. We show that $\mathcal{C}_{2}$-CSM time is no more powerful than sequential space, thus giving one of the two inclusions that are necessary to show that the Model verifies the parallel Computation thesis. Furthermore we show that $\mathcal{C}_{2}$-CSMs that simultaneously use polynomial space and polylogarithmic time decide no more than the class NC.
-
An optical Model of Computation
Theoretical Computer Science, 2004Co-Authors: Damien Woods, Thomas J. NaughtonAbstract:We prove computability and complexity results for an original Model of Computation called the continuous space machine. Our Model is inspired by the theory of Fourier optics. We prove our Model can simulate analog recurrent neural networks, thus establishing a lower bound on its Computational power. We also define a Θ(log2n) unordered search algorithm with our Model.
-
MCU - On the Computational Power of a Continuous-Space Optical Model of Computation
Lecture Notes in Computer Science, 2001Co-Authors: Thomas J. Naughton, Damien WoodsAbstract:We introduce a continuous-space Model of Computation. This original Model is inspired by the theory of Fourier optics. We show a lower bound on the Computational power of this Model by Type-2 machine simulation. The limit on Computational power of our Model is nontrivial. We define a problem solvable with our Model that is not Type-2 computable. The theory of optics does not preclude a physical implementation of our Model.