Search results for "TURING"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
15	David Buchfuhrer, Christopher Umans	The Complexity of Boolean Formula Minimization.	ICALP (1)	2008	DBLP DOI BibTeX RDF
15	Zhang Yinsheng	The Mathematic Model of Consciousness.	Asia International Conference on Modelling and Simulation	2008	DBLP DOI BibTeX RDF	Mathematic Model of Consciousness, homomorphic model, Jean Piaget
15	Paul R. Cohen	What Shall We Do Next? The Challenges of AI Midway through Its First Century.	PRICAI	2008	DBLP DOI BibTeX RDF
15	Jarkko Kari, Nicolas Ollinger	Periodicity and Immortality in Reversible Computing.	MFCS	2008	DBLP DOI BibTeX RDF
15	Joan M. Lucas, Jonathan Jarvis	Incorporating transformations into jflap for enhanced understanding of automata.	SIGCSE	2008	DBLP DOI BibTeX RDF	automata, educational software, undecidability, jflap
15	Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker	Oracles and Advice as Measurements.	UC	2008	DBLP DOI BibTeX RDF
15	Turlough Neary	On the Computational Complexity of Spiking Neural P Systems.	UC	2008	DBLP DOI BibTeX RDF
15	Luca Cardelli, Gianluigi Zavattaro	On the Computational Power of Biochemistry.	AB	2008	DBLP DOI BibTeX RDF
15	Amir M. Ben-Amram, Neil D. Jones, Lars Kristiansen	Linear, Polynomial or Exponential? Complexity Inference in Polynomial Time.	CiE	2008	DBLP DOI BibTeX RDF	linear time complexity, static program analysis, polynomial time complexity, implicit computational complexity
15	Harry Buhrman, John M. Hitchcock	NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly.	CCC	2008	DBLP DOI BibTeX RDF	hard sets, polynomial advice, instance complexity
15	Jesús Aranda, Cinzia Di Giusto, Mogens Nielsen, Frank D. Valencia	CCS with Replication in the Chomsky Hierarchy: The Expressive Power of Divergence.	APLAS	2007	DBLP DOI BibTeX RDF
15	Mark Burgin	Universality, Reducibility, and Completeness.	MCU	2007	DBLP DOI BibTeX RDF	problem completeness, algorithm, computability, reducibility, universal, computing power, problem hardness
15	Grégory Lafitte, Michael Weiss	Universal Tilings.	STACS	2007	DBLP DOI BibTeX RDF
15	Zoltán Csörnyei, Gergely Dévai	An Introduction to the Lambda Calculus.	CEFP	2007	DBLP DOI BibTeX RDF
15	Fatih Altiparmak, Selnur Erdal, Ozgur Ozturk, Hakan Ferhatosmanoglu	A Multi-metric Similarity Based Analysis of Microarray Data.	BIBM	2007	DBLP DOI BibTeX RDF
15	Itamar Pitowsky	From Logic to Physics: How the Meaning of Computation Changed over Time.	CiE	2007	DBLP DOI BibTeX RDF
15	Joel David Hamkins, Russell G. Miller	Post's Problem for Ordinal Register Machines.	CiE	2007	DBLP DOI BibTeX RDF	ordinal computability, ordinal register machine, Post’s Problem, computability
15	Richard Chang 0001, Suresh Purini	Bounded Queries and the NP Machine Hypothesis.	CCC	2007	DBLP DOI BibTeX RDF
15	Ryan Williams 0001	Inductive Time-Space Lower Bounds for Sat and Related Problems.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	68Q17, Subject classification
15	Ann M. Bouchard, Gordon C. Osbourn	Dynamic self-assembly in living systems as computation.	Nat. Comput.	2006	DBLP DOI BibTeX RDF	biological information processing, microtubule, motor protein, protein network, unary number, algorithm, computation, computing, information, self-assembly, stochastic, random access machine
15	Antonio Montalbán	There is no ordering on the classes in the generalized high/low hierarchies.	Arch. Math. Log.	2006	DBLP DOI BibTeX RDF
15	John M. Hitchcock, Aduri Pavan	Comparing Reductions to NP-Complete Sets.	ICALP (1)	2006	DBLP DOI BibTeX RDF
15	Turlough Neary, Damien Woods	P-completeness of Cellular Automaton Rule 110.	ICALP (1)	2006	DBLP DOI BibTeX RDF
15	Ehud Shapiro	Injecting Life with Computers.	ILP	2006	DBLP DOI BibTeX RDF
15	Keng Meng Ng, Frank Stephan 0001, Guohua Wu	Degrees of Weakly Computable Reals.	CiE	2006	DBLP DOI BibTeX RDF
15	William B. Langdon, Riccardo Poli	The Halting Probability in Von Neumann Architectures.	EuroGP	2006	DBLP DOI BibTeX RDF
15	István Németi, Hajnal Andréka	New Physics and Hypercomputation.	SOFSEM	2006	DBLP DOI BibTeX RDF
15	Serge Haddad, Laura Recalde, Manuel Silva Suárez	On the Computational Power of Timed Differentiable Petri Nets.	FORMATS	2006	DBLP DOI BibTeX RDF
15	Edward D. Lazowska, David A. Patterson 0001	Computing research: a looming crisis.	Comput. Commun. Rev.	2005	DBLP DOI BibTeX RDF	computing research, innovation
15	Michael Roe	Non-repudiation and the Metaphysics of Presence.	Security Protocols Workshop	2005	DBLP DOI BibTeX RDF
15	Ee-Chien Chang, Sung Woo Choi, DoYong Kwon, Hyungju Park, Chee-Keng Yap	Shortest path amidst disc obstacles is computable.	SCG	2005	DBLP DOI BibTeX RDF	disc obstacles, guaranteed precision computation, real RAM model, robust numerical algorithms, shortest path, exact geometric computation, exponential complexity
15	Falk Unger	On Small Hard Leaf Languages.	MFCS	2005	DBLP DOI BibTeX RDF
15	Peng Yin 0003, Sudheer Sahu, Andrew J. Turberfield, John H. Reif	Design of Autonomous DNA Cellular Automata.	DNA	2005	DBLP DOI BibTeX RDF
15	Klaus Meer, Martin Ziegler 0001	An Explicit Solution to Post's Problem over the Reals.	FCT	2005	DBLP DOI BibTeX RDF
15	Victor Poupet	Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods.	STACS	2005	DBLP DOI BibTeX RDF	real-time, Cellular automata, neighborhoods
15	Peter Koepke	Computing a Model of Set Theory.	CiE	2005	DBLP DOI BibTeX RDF
15	Charles M. Harris	Symmetric Enumeration Reducibility.	CiE	2005	DBLP DOI BibTeX RDF
15	Angsheng Li	The Low Splitting Theorem in the Difference Hierarchy.	CiE	2005	DBLP DOI BibTeX RDF
15	Ryan Williams 0001	Parallelizing time with polynomial circuits.	SPAA	2005	DBLP DOI BibTeX RDF	parallel speedup, circuit complexity, alternation
15	Petr Sosík, Ondrej Valík	On Evolutionary Lineages of Membrane Systems.	Workshop on Membrane Computing	2005	DBLP DOI BibTeX RDF
15	Aleksandar Ignjatovic, Arun Sharma 0001	Some applications of logic to feasibility in higher types.	ACM Trans. Comput. Log.	2004	DBLP DOI BibTeX RDF	higher-order complexity, second-order theories, functionals, bounded arithmetic
15	Ehud Shapiro	Invited talk: injecting life with computers.	PEPM	2004	DBLP DOI BibTeX RDF	computer diagnosis and therapy, autonomous computers, DNA computing, molecular computers
15	Ruben Gamboa, John R. Cowles	A Mechanical Proof of the Cook-Levin Theorem.	TPHOLs	2004	DBLP DOI BibTeX RDF
15	Jérôme Durand-Lose	Abstract Geometrical Computation for Black Hole Computation.	MCU	2004	DBLP DOI BibTeX RDF
15	Angelos Stavrou, John Ioannidis, Angelos D. Keromytis, Vishal Misra, Dan Rubenstein	A Pay-per-Use DoS Protection Mechanism for the Web.	ACNS	2004	DBLP DOI BibTeX RDF
15	Ehud Shapiro	Invited talk: injecting life with computers.	PPDP	2004	DBLP DOI BibTeX RDF	computer diagnosis and therapy, autonomous computers, DNA computing, molecular computers
15	Peter Bürgisser, Felipe Cucker	Counting complexity classes for numeric computations II: algebraic and semialgebraic sets.	STOC	2004	DBLP DOI BibTeX RDF	counting complexity classes, geometric degree, semialgebraic sets, completeness, Betti numbers, Euler characteristic
15	Rainer Knauf, Setsuo Tsuruta, Hirokazu Ihara, Avelino J. Gonzalez, Torsten Kurbad	Improving AI Systems? Dependability by Utilizing Historical Knowledge.	PRDC	2004	DBLP DOI BibTeX RDF
15	Vikraman Arvind, T. C. Vijayaraghavan	Abelian Permutation Group Problems and Logspace Counting Classes.	CCC	2004	DBLP DOI BibTeX RDF
15	Christian Glaßer, Alan L. Selman, Samik Sengupta	Reductions between Disjoint NP-Pairs.	CCC	2004	DBLP DOI BibTeX RDF
15	Claudio Sacerdoti Coen	A Constructive Proof of the Soundness of the Encoding of Random Access Machines in a Linda Calculus with Ordered Semantics.	ICTCS	2003	DBLP DOI BibTeX RDF
15	Robert Rettinger, Klaus Weihrauch	The computational complexity of some julia sets.	STOC	2003	DBLP DOI BibTeX RDF	julia sets, computational complexity
15	Rahul Santhanam, Dieter van Melkebeek	Holographic Proofs and Derandomization.	CCC	2003	DBLP DOI BibTeX RDF
15	Julia Khodor, David K. Gifford	Programmed Mutagenesis Is Universal.	Theory Comput. Syst.	2002	DBLP DOI BibTeX RDF
15	Harumichi Nishimura	On Quantum Computation with Some Restricted Amplitudes.	STACS	2002	DBLP DOI BibTeX RDF
15	Peter A. Beling	Exact Algorithms for Linear Programming over Algebraic Extensions.	Algorithmica	2001	DBLP DOI BibTeX RDF	Ellipsoid method, Computational complexity, Linear programming, Polynomial-time algorithms, Symbolic computation, Algebraic numbers
15	Julia Khodor, David K. Gifford	Programmed Mutagenesis Is a Universal Model of Computation.	DNA	2001	DBLP DOI BibTeX RDF
15	Umesh V. Vazirani	Quantum Algorithms.	FCT	2001	DBLP DOI BibTeX RDF
15	Bruce M. Maggs, Berthold Vöcking	Improved Routing and Sorting on Multibutterflies.	Algorithmica	2000	DBLP DOI BibTeX RDF	Ellipsoid method, Computational complexity, Linear programming, Polynomial-time algorithms, Symbolic computation, Algebraic numbers
15	Jirí Wiedermann	Towards a Computational Theory of Everything.	IFIP TCS	2000	DBLP DOI BibTeX RDF
15	Jan van Leeuwen, Jirí Wiedermann	On the Power of Interactive Computing.	IFIP TCS	2000	DBLP DOI BibTeX RDF
15	Holger Spakowski, Jörg Vogel 0001	Theta2p-Completeness: A Classical Approach for New Results.	FSTTCS	2000	DBLP DOI BibTeX RDF
15	Lance Fortnow, Dieter van Melkebeek	Time-Space Tradeoffs for Nondeterministic Computation.	CCC	2000	DBLP DOI BibTeX RDF	Satisfiability, Time-space tradeoffs
15	Felipe Cucker	Solving polynomial systems: a complexity theory viewpoint.	ISSAC	2000	DBLP DOI BibTeX RDF
15	John H. Reif	Parallel Biomolecular Computation: Models and Simulations.	Algorithmica	1999	DBLP DOI BibTeX RDF	Parallel RAM, Nondeterministic computation, Recombinant DNA, Parallel computation, DNA, NP, Biomolecular computation, Biotechnology
15	Bin Fu, Richard Beigel	A Comparison of Resource-Bounded Molecular Computation Models.	Algorithmica	1999	DBLP DOI BibTeX RDF
15	Rudolf Freund, Lila Kari, Gheorghe Paun	DNA Computing Based on Splicing: The Existence of Universal Computers.	Theory Comput. Syst.	1999	DBLP DOI BibTeX RDF
15	Jirí Wiedermann	The Computational Limits to the Cognitive Power of the Neuroidal Tabula Rasa.	ALT	1999	DBLP DOI BibTeX RDF
15	Penousal Machado, Francisco Baptista Pereira, Amílcar Cardoso, Ernesto Costa	Busy Beaver - The Influence of Representation.	EuroGP	1999	DBLP DOI BibTeX RDF
15	John Watrous	Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity.	CCC	1999	DBLP DOI BibTeX RDF	quantum computation, graph connectivity, space-bounded computation
15	Michael Prasse, Peter Rittgen	Bemerkungen zu Peter Wegners Ausführungen über Interaktion und Berechenbarkeit.	Inform. Spektrum	1998	DBLP DOI BibTeX RDF	Interaktionsmaschine, Turingmaschine, Churchsche These, Berechenbarkeit, Algorithmus
15	Takashi Mihara, Shao Chin Sung	A Quantum Polynomial Time Algorithm in Worst Case for Simon's Problem.	ISAAC	1998	DBLP DOI BibTeX RDF
15	Harry Buhrman, Dieter van Melkebeek, Kenneth W. Regan, D. Sivakumar, Martin Strauss 0001	A Generalization of Resource-Bounded Measure, With an Application (Extended Abstract).	STACS	1998	DBLP DOI BibTeX RDF
15	Cristian Calude, Peter Hertling, Bakhadyr Khoussainov, Yongge Wang	Recursively Enumerable Reals and Chaitin Omega Numbers.	STACS	1998	DBLP DOI BibTeX RDF
15	Bin Fu, Richard Beigel	A Comparison of Resource-Bounded Molecular Computation Models.	ISTCS	1997	DBLP DOI BibTeX RDF
15	Rolf Backofen, Peter Clote	Evolution as a Computational Engine.	CSL	1997	DBLP DOI BibTeX RDF
15	Elena Pezzoli	On the Computational Complexity of Type 2 Functionals.	CSL	1997	DBLP DOI BibTeX RDF
15	Klaus-Jörn Lange, Pierre McKenzie, Alain Tapp	Reversible Space Equals Deterministic Space.	CCC	1997	DBLP DOI BibTeX RDF	determinism, reversible computation, Complexity classes, space bounds
15	Ulrich Hertrampf	Acceptance by Transformation Monoids (with an Application to Local Self Reductions).	CCC	1997	DBLP DOI BibTeX RDF	local self reduction, bottleneck machine, structural complexity
15	Stephen A. Fenner, Steven Homer, Randall Pruim, Marcus Schaefer 0001	Hyper-Polynomial Hierarchies and the NP-Jump.	CCC	1997	DBLP DOI BibTeX RDF
15	Jack H. Lutz, Yong Zhao	The Density of Weakly Complete Problems under Adaptive Reductions.	CCC	1997	DBLP DOI BibTeX RDF	dense languages, polynomial reductions, sparse languages, weak completeness, computational complexity, complexity classes, resource-bounded measure
15	Hermann Ney, Ute Essen, Reinhard Kneser	On the Estimation of 'Small' Probabilities by Leaving-One-Out.	IEEE Trans. Pattern Anal. Mach. Intell.	1995	DBLP DOI BibTeX RDF	Stochastic language modeling, zero-frequency problem, generalization capability, maximum likelihood estimation, leaving-one-out
15	Stephen A. Fenner, Jack H. Lutz, Elvira Mayordomo	Weakly Useful Sequences.	ICALP	1995	DBLP DOI BibTeX RDF
15	Hans-Jörg Burtschick	Comparing Counting Classes for Logspace, One-way Logspace, and First-order.	MFCS	1995	DBLP DOI BibTeX RDF
15	Wolfgang Merkle, Yongge Wang	Separations by Random Oracles and "Almost" Classes for Generalized Reducibilities.	MFCS	1995	DBLP DOI BibTeX RDF
15	Carsten Damm, Markus Holzer 0001	Inductive Counting Below LOGSPACE.	MFCS	1994	DBLP DOI BibTeX RDF
15	Martin Dietzfelbinger, Martin Hühne	Matching Upper and Lower Bounds for Simulation of Several Tapes on One Multidimensional Tape.	FSTTCS	1994	DBLP DOI BibTeX RDF
15	Yenjo Han, Lane A. Hemaspaandra, Thomas Thierauf	Threshold Computation and Cryptographic Security.	ISAAC	1993	DBLP DOI BibTeX RDF
15	Cynthia Dwork, Larry J. Stockmeyer	Finite State Verifiers I: The Power of Interaction.	J. ACM	1992	DBLP DOI BibTeX RDF	complexity theory, finite state automata, interactive proof systems, probabilistic automata, Arthur-Merlin games
15	Hava T. Siegelmann, Eduardo D. Sontag	On the Computational Power of Neural Nets.	COLT	1992	DBLP DOI BibTeX RDF
15	David Alex Lamb, Kevin A. Schneider	Formalization of information hiding design methods.	CASCON	1992	DBLP BibTeX RDF
15	Viliam Geffert	Speed-Up Theorem Without Tape Compression.	MFCS	1990	DBLP DOI BibTeX RDF
15	Etienne Grandjean, J. M. Robson	RAM with Compact Memory: A Realistic and Robust Model of Computation.	CSL	1990	DBLP DOI BibTeX RDF
15	Rafail Ostrovsky	An Efficient Software Protection Scheme.	CRYPTO	1989	DBLP DOI BibTeX RDF
15	Jeffrey D. Ullman, Moshe Y. Vardi	The Complexity of Ordering Subgoals.	PODS	1988	DBLP DOI BibTeX RDF
15	Michael Kaminski	A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor.	J. ACM	1987	DBLP DOI BibTeX RDF
15	Steven Homer	Minimal degrees for polynomial reducibilities.	J. ACM	1987	DBLP DOI BibTeX RDF
15	Oscar H. Ibarra, Sam M. Kim, Louis E. Rosier	Space and Time Efficient Simulations and Characterizations of Some Restricted Classes of PDAs.	ICALP	1984	DBLP DOI BibTeX RDF
15	Juraj Hromkovic	On the Power of Alternation in Finite Automata.	MFCS	1984	DBLP DOI BibTeX RDF
15	Paul M. B. Vitányi	On the Simulation of Many Storage Heads by a Single One (Extended Abstract).	ICALP	1983	DBLP DOI BibTeX RDF