Search results for "Computability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
16	Pierluigi Frisco	About P systems with symport/antiport.	Soft Comput.	2005	DBLP DOI BibTeX RDF	Symport/Antiport, Counter automaton, Membrane computing, Turing computability
16	Ulisses Ferreira	The sets of real and complex numbers are denumerable.	SIGACT News	2005	DBLP DOI BibTeX RDF	cantor, foundation of mathematics, foundations of computer science, numbers and sets, real, transfinite, computability, enumerability, mathematics, number theory, philosophy, halting problem
16	Shankara Narayanan Krishna, Gheorghe Paun	P Systems with Mobile Membranes.	Nat. Comput.	2005	DBLP DOI BibTeX RDF	matrix grammar, membrane computing, Turing computability
16	Jose Maria Turull Torres	Erratum for: A Study of Homogeneity in Relational Databases [Annals of Mathematics and Artificial Intelligence 33(2) (2001) 379-414].	Ann. Math. Artif. Intell.	2004	DBLP DOI BibTeX RDF	query computability, completeness of models, query languages, database machines
16	Francesco Bernardini, Marian Gheorghe 0001, Mike Holcombe	P X systems = P systems + X machines.	Nat. Comput.	2003	DBLP DOI BibTeX RDF	molecular computing, P systems, Turing computability, X machines
16	Rodica Ceterchi, Madhu Mutyam, Gheorghe Paun, K. G. Subramanian 0001	Array-rewriting P systems.	Nat. Comput.	2003	DBLP DOI BibTeX RDF	array languages, matrix grammar, membrane computing, P system, Turing computability
16	Mihai Ionescu, Carlos Martín-Vide, Andrei Paun, Gheorghe Paun	Unexpected universality results for three classes of P systems with symport/antiport.	Nat. Comput.	2003	DBLP DOI BibTeX RDF	membrane computing, P system, Turing computability, Chomsky hierarchy
16	Steffen Lempp, Charles F. D. McCoy, Andrei S. Morozov, Reed Solomon	Group Theoretic Properties of the Group of Computable Automorphisms of a Countable Dense Linear Order.	Order	2002	DBLP DOI BibTeX RDF	computability theory, effective algebra, reverse mathematics, lattice-ordered groups, automorphism groups
16	Evangelos Kranakis, Nicola Santoro	Distributed computing on oriented anonymous hypercubes with faulty components.	Distributed Comput.	2001	DBLP DOI BibTeX RDF	Faulty links and/or nodes, Boolean functions, Hypercubes, Computability, Anonymous networks
16	Jan A. Bergstra, Alban Ponse	Register-machine based processes.	J. ACM	2001	DBLP DOI BibTeX RDF	Kleene star, push-down operation, concurrency, computability, process algebra, expressivity, iteration, Bisimulation equivalence
16	Yoshinao Isobe, Kazuhito Ohmaki	A process logic for distributed system synthesis .	APSEC	2000	DBLP DOI BibTeX RDF	process logic, distributed system synthesis, concurrent behavior, interleaving behavior, DS algebra, SP logic, computability, process algebra, process algebra, satisfiability, algebraic specification, concurrency theory
16	Dimitris Achlioptas, Gregory B. Sorkin	Optimal myopic algorithms for random 3-SAT.	FOCS	2000	DBLP DOI BibTeX RDF	optimal myopic algorithms, random 3-SAT formula, 3-clauses, unit-clause propagation extensions, expressible algorithms, max-density multiple-choice knapsack problem, optimal knapsack solution structure, lower bounds, optimisation, computability, satisfiability, differential equations, differential equations, optimization problem, randomised algorithms
16	Emil Gizdarski, Hideo Fujiwara	Spirit: satisfiability problem implementation for redundancy identification and test generation.	Asian Test Symposium	2000	DBLP DOI BibTeX RDF	Boolean satisfiability method, SPIRIT, ATPG system, logic testing, computability, automatic test pattern generation, combinational circuits, combinational circuits, test pattern generation, test sets
16	Hidetomo Nabeshima, Katsumi Inoue, Hiromasa Haneda	Implementing an action language using a SAT solver.	ICTAI	2000	DBLP DOI BibTeX RDF	planning algorithms, plan search space, planning graph, SAT planning, AMP, domain description, Java, Java, data structures, data structure, planning (artificial intelligence), computability, inference mechanisms, satisfiability problem, SAT solver, reasoning about action, model generation, action language
16	Philippe Chatalic, Laurent Simon	Multi-resolution on compressed sets of clauses.	ICTAI	2000	DBLP DOI BibTeX RDF	compressed sets, compressed clauses, propositional clauses, compression power, structured instances, specialized operator, clause sets, polynomial size data structures, ZREs system, Davis-Putnam procedure, hard problems, SAT provers, zero-suppressed binary decision diagrams, computational complexity, data structures, data structures, data compression, theorem proving, computability, encodings, directed graphs, binary decision diagrams, set theory, multi-resolution, cut eliminations, ZBDDs
16	Michael Kifer	On the Decidability and Axiomatization of Query Finiteness in Deductive Databases.	J. ACM	1998	DBLP DOI BibTeX RDF	finite queries, finiteness constraints, horizontal decompositions, partial constraints, query processing, computability, axiomatization
16	R. Gregory Taylor	Motivating the Church-Turing thesis in the twenty-first century.	ITiCSE	1998	DBLP DOI BibTeX RDF	Church-Turing thesis, Markov algorithm, vector machine, Turing machine, computability theory, register machine
16	Fritz Henglein, Jakob Rehof	The Complexity of Subtype Entailment for Simple Types.	LICS	1997	DBLP DOI BibTeX RDF	subtype entailment complexity, atomic entailment, coNP-completeness, complexity-theoretic marker, exponential explosion, subtype inference, structural complexity bounds, computability, satisfiability, axiomatization, linear-time algorithm
16	Witold Charatonik, Andreas Podelski	Set Constraints with Intersection.	LICS	1997	DBLP DOI BibTeX RDF	satisfiability test, set-based program analysis, DEXPTIME-complete, complexity characterization, negative set constraints, negated conjuncts, negated inclusion, computability, decidability, intersection, inclusions, set constraints
16	Ramamohan Paturi, Pavel Pudlák, Francis Zane	Satisfiability Coding Lemma.	FOCS	1997	DBLP DOI BibTeX RDF	satisfying assignments, satisfying assignment, Satisfiability Coding Lemma, computability, randomized algorithm, satisfiability, deterministic algorithm, conjunctive normal form, Boolean formulae
16	Pietro Di Gianantonio	An Abstract Data Type for Real Numbers.	ICALP	1997	DBLP DOI BibTeX RDF	real number computability, denotational and operational semantics, abstract data types, domain theory
16	Masafumi Yamashita, Tsunehiko Kameda	Computing on Anonymous Networks: Part II-Decision and Membership Problems.	IEEE Trans. Parallel Distributed Syst.	1996	DBLP DOI BibTeX RDF	edge election, spanning tree construction, topology recognition, distributed computing, NP-completeness, computability, leader election, Anonymous network
16	Paul Beame, Toniann Pitassi	Simplified and Improved Resolution Lower Bounds.	FOCS	1996	DBLP DOI BibTeX RDF	resolution lower bounds, randomly generated formulas, random formulas, randomly chosen 3-CNF formula, lower bounds, computability, pigeonhole principle
16	Rajesh K. Gupta 0001	A framework for interactive analysis of timing constraints in embedded systems.	CODES	1996	DBLP DOI BibTeX RDF	constraint satisfiability, performance evaluation, real-time systems, embedded systems, timing, computability, logic design, satisfiability, timing constraints, interactive analysis, timing performance
16	Maria Alberta Alberti, Alberto Bertoni, Paola Campadelli, Giuliano Grossi, Roberto Posenato	A neural circuit for the maximum 2-satisfiability problem.	PDP	1995	DBLP DOI BibTeX RDF	maximum 2-satisfiability, neural circuit, 2-satisfiability problem, neural networks, FPGA, computability, neural nets
16	Richard Beigel, David Eppstein	3-Coloring in Time O(1.3446n): A No-MIS Algorithm.	FOCS	1995	DBLP DOI BibTeX RDF	duality (mathematics), 3-coloring, worst case time bounds, 3-edge-coloring, 3-list-coloring, common generalization, symbol-system satisfiability, duality transformation, computational complexity, computability, decidability, NP-complete problems, graph colouring, time bounds, 3-SAT
16	Jean-Michel Muller	Some Characterizations of Functions Computable in On-Line Arithmetic.	IEEE Trans. Computers	1994	DBLP DOI BibTeX RDF	piecewise affine functions, operands, arbitrarily long length, computability, digital arithmetic, finite automata, multiplication, division, elementary functions, finite automaton, online computing, rational numbers
16	John V. Tucker, Jeffery I. Zucker	Toward a General Theory of Computation and Specification over Abstract Data Types.	ICCI	1990	DBLP DOI BibTeX RDF	specification, computation, computability, abstract data type
16	Michael R. Fellows, Michael A. Langston	An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract)	FOCS	1989	DBLP DOI BibTeX RDF	obstruction sets, computing finite-basis characterizations, graph-theoretic analog, Myhill-Nerode characterization, computability, regular languages
14	Yunseok Lee, Holger Boche, Gitta Kutyniok	Computability of Optimizers.	IEEE Trans. Inf. Theory	2024	DBLP DOI BibTeX RDF
14	Asad Khaliq	On Computability of Computable Problems.	CoRR	2024	DBLP DOI BibTeX RDF
14	G. Pantelis	PECR: A formal system based on computability logic.	CoRR	2024	DBLP DOI BibTeX RDF
14	Thorben Tröbst, Vijay V. Vazirani	Cardinal-Utility Matching Markets: The Quest for Envy-Freeness, Pareto-Optimality, and Efficient Computability.	CoRR	2024	DBLP DOI BibTeX RDF
14	Antonin Callard, Léo Paviet Salomon, Pascal Vanier	Computability of extender sets in multidimensional subshifts.	CoRR	2024	DBLP DOI BibTeX RDF
14	Sebastiaan A. Terwijn	Fixed Point Theorems in Computability Theory.	CoRR	2024	DBLP DOI BibTeX RDF
14	Steffen Lempp, Joseph S. Miller, André Nies, Mariya Ivanova Soskova	Maximal Towers and Ultrafilter Bases in Computability Theory.	J. Symb. Log.	2023	DBLP DOI BibTeX RDF
14	Fedor Manin	Rational Homotopy Type and Computability.	Found. Comput. Math.	2023	DBLP DOI BibTeX RDF
14	Amin Farjudian, Eugenio Moggi	Robustness, Scott continuity, and computability.	Math. Struct. Comput. Sci.	2023	DBLP DOI BibTeX RDF
14	Daniel Mourad	Computability Theory: Constructive Applications of the Lefthanded Local Lemma and Characterizations of Some Classes of Cohesive Powers.	Bull. Symb. Log.	2023	DBLP DOI BibTeX RDF
14	Teerawat Thewmorakot	Computability Theory on Polish Metric Spaces.	Bull. Symb. Log.	2023	DBLP DOI BibTeX RDF
14	Chris J. Conidis	D. D. Dzhafarov and C. Mummert, Reverse Mathematics: Problems, Reductions, and Proofs. Theory and Applications of Computability. Springer Nature, Cham, 2022, xix + 488 pp.	Bull. Symb. Log.	2023	DBLP DOI BibTeX RDF
14	Waseet Kazmi	Ordered Groups, Computability and Cantor-Bendixson Rank.	Bull. Symb. Log.	2023	DBLP DOI BibTeX RDF
14	Alastair A. Abbott, Cezar Câmpeanu, Ludwig Staiger, Marius Zimand, Arto Salomaa	Frontiers of Computability, Randomness, and Complexity (dedicated to the 70th birthday of Professor Cristian Calude).	Theor. Comput. Sci.	2023	DBLP DOI BibTeX RDF
14	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions.	IEEE Trans. Inf. Theory	2023	DBLP DOI BibTeX RDF
14	Tomoyuki Yamakami	Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions.	CoRR	2023	DBLP DOI BibTeX RDF
14	Daniel Silva Graça, Ning Zhong	Robust non-computability and stability of dynamical systems.	CoRR	2023	DBLP DOI BibTeX RDF
14	Dieter Spreen	How Much Partiality Is Needed for a Theory of Computability?	CoRR	2023	DBLP DOI BibTeX RDF
14	Holger Boche, Andrea Grigorescu, Rafael F. Schaefer, H. Vincent Poor	Algorithmic Computability of the Capacity of Gaussian Channels with Colored Noise.	CoRR	2023	DBLP DOI BibTeX RDF
14	Dmitry Filippov	Canonicity and Computability in Homotopy Type Theory.	CoRR	2023	DBLP DOI BibTeX RDF
14	Sam Sanders	Exploring the abyss in Kleene's computability theory.	CoRR	2023	DBLP DOI BibTeX RDF
14	Sebastián Barbieri, Jarkko Kari, Ville Salo	The group of reversible Turing machines: subgroups, generators and computability.	CoRR	2023	DBLP DOI BibTeX RDF
14	Sam Sanders	The non-normal abyss in Kleene's computability theory.	CoRR	2023	DBLP DOI BibTeX RDF
14	Keehang Kwon	Implementing Dynamic Programming in Computability Logic Web.	CoRR	2023	DBLP DOI BibTeX RDF
14	Xu Huang	Synthetic Tait Computability the Hard Way.	CoRR	2023	DBLP DOI BibTeX RDF
14	Yunseok Lee, Holger Boche, Gitta Kutyniok	Computability of Optimizers.	CoRR	2023	DBLP DOI BibTeX RDF
14	Yannick Forster 0002, Dominik Kirst, Niklas Mück	Oracle Computability and Turing Reducibility in the Calculus of Inductive Constructions.	CoRR	2023	DBLP DOI BibTeX RDF
14	Douglas Cenzer, Christopher P. Porter	Randomness extraction in computability theory.	Comput.	2023	DBLP DOI BibTeX RDF
14	Clara Löh, Matthias Uschold	L2-Betti numbers and computability of reals.	Comput.	2023	DBLP DOI BibTeX RDF
14	Uri Andrews, Mingzhong Cai, David Diamondstone, Noah Schweber	Limit computability and ultrafilters.	Comput.	2023	DBLP DOI BibTeX RDF
14	Dieter Spreen	How much partiality is needed for a theory of computability?	Comput.	2023	DBLP DOI BibTeX RDF
14	Petr Sosík	Morphogenetic computing: computability and complexity results.	Nat. Comput.	2023	DBLP DOI BibTeX RDF
14	Dusko Pavlovic	Programs as Diagrams - In cooperation with the association Computability in Europe		2023	DOI RDF
14	Yannick Forster 0002, Dominik Kirst, Niklas Mück	Oracle Computability and Turing Reducibility in the Calculus of Inductive Constructions.	APLAS	2023	DBLP DOI BibTeX RDF
14	Holger Boche, Andrea Grigorescu, Rafael F. Schaefer, H. Vincent Poor	Algorithmic Computability of the Capacity of Additive Colored Gaussian Noise Channels.	GLOBECOM	2023	DBLP DOI BibTeX RDF
14	Gianluca Della Vedova, Besik Dundua, Steffen Lempp, Florin Manea (eds.)	Unity of Logic and Computation - 19th Conference on Computability in Europe, CiE 2023, Batumi, Georgia, July 24-28, 2023, Proceedings	CiE	2023	DBLP DOI BibTeX RDF
14	Dominik Kirst, Benjamin Peters	Gödel's Theorem Without Tears - Essential Incompleteness in Synthetic Computability.	CSL	2023	DBLP DOI BibTeX RDF
14	Djamel Eddine Amir	Computability of Topological Spaces. (Calculabilité des espaces topologiques).		2023	RDF
14	Merlin Carl	All Melodies Are Lost - Recognizability for Weak and Strong α-Register Machines.	CiE	2023	DBLP DOI BibTeX RDF
14	Russell G. Miller	Direct Construction of Scott Ideals.	CiE	2023	DBLP DOI BibTeX RDF
14	Alexey Barsukov, Florent R. Madelaine	On Guarded Extensions of MMSNP.	CiE	2023	DBLP DOI BibTeX RDF
14	Gabriele Buriola, Peter Schuster 0001, Ingo Blechschmidt	A Constructive Picture of Noetherian Conditions and Well Quasi-orders.	CiE	2023	DBLP DOI BibTeX RDF
14	Pawel Parys, Aleksander Wiacek	Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games.	CiE	2023	DBLP DOI BibTeX RDF
14	Victor L. Selivanov	Extending Wagner's Hierarchy to Deterministic Visibly Pushdown Automata.	CiE	2023	DBLP DOI BibTeX RDF
14	Vladislav Orekhovskii, Victor L. Selivanov	Logic vs Topology on Regular ømega-languages.	CiE	2023	DBLP DOI BibTeX RDF
14	Mariya Ivanova Soskova	The Relationship Between Local and Global Structure in the Enumeration Degrees.	CiE	2023	DBLP DOI BibTeX RDF
14	Vasco Brattka	On the Complexity of Learning Programs.	CiE	2023	DBLP DOI BibTeX RDF
14	Hong Hanh Tran, Guohua Wu	Cupping Computably Enumerable Degrees Simultaneously.	CiE	2023	DBLP DOI BibTeX RDF
14	Zeev Nutov	An $O(\sqrt{k})$-Approximation Algorithm for Minimum Power k Edge Disjoint st-Paths.	CiE	2023	DBLP DOI BibTeX RDF
14	Daniil Musatov, Georgii Potapov	Structural Complexity of Rational Interactive Proofs.	CiE	2023	DBLP DOI BibTeX RDF
14	Ivan Georgiev	Subrecursive Graphs of Representations of Irrational Numbers.	CiE	2023	DBLP DOI BibTeX RDF
14	Takayuki Kihara, Arno Pauly	De Groot Duality for Represented Spaces.	CiE	2023	DBLP DOI BibTeX RDF
14	Vittorio Cipriani, Arno Pauly	The Complexity of Finding Supergraphs.	CiE	2023	DBLP DOI BibTeX RDF
14	Pablo Arrighi, Amélia Durbec, Pierre Guillon 0001	Graph Subshifts.	CiE	2023	DBLP DOI BibTeX RDF
14	Alexander Shen	Inequalities for Entropies and Dimensions.	CiE	2023	DBLP DOI BibTeX RDF
14	Keita Hiroshima, Akitoshi Kawamura	Elementarily Traceable Irrational Numbers.	CiE	2023	DBLP DOI BibTeX RDF
14	Pacôme Perrotin, Sylvain Sené	Turning Block-Sequential Automata Networks into Smaller Parallel Networks with Isomorphic Limit Dynamics.	CiE	2023	DBLP DOI BibTeX RDF
14	Alexey Milovanov	Some Games on Turing Machines and Power from Random Strings.	CiE	2023	DBLP DOI BibTeX RDF
14	Suthee Ruangwises	Physical Zero-Knowledge Proof for Ball Sort Puzzle.	CiE	2023	DBLP DOI BibTeX RDF
14	Leonardo Nagami Coregliano	On the abstract chromatic number and its computability for finitely axiomatizable theories.	J. Comb. Theory, Ser. B	2022	DBLP DOI BibTeX RDF
14	Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, Dan Turetsky	Relationships between Computability-Theoretic Properties of Problems.	J. Symb. Log.	2022	DBLP DOI BibTeX RDF
14	Ilia Binder, Adi Glucksam, Cristobal Rojas, Michael Yampolsky	Computability in Harmonic Analysis.	Found. Comput. Math.	2022	DBLP DOI BibTeX RDF
14	Rupert Hölzl 0001, Christopher P. Porter	Degrees of Randomized Computability.	Bull. Symb. Log.	2022	DBLP DOI BibTeX RDF
14	Manlio Valenti	A journey through computability, topology and analysis.	Bull. Symb. Log.	2022	DBLP DOI BibTeX RDF
14	Eike Neumann	On the computability of the set of automorphisms of the unit square.	Theor. Comput. Sci.	2022	DBLP DOI BibTeX RDF
14	Hong Cui, Bruce Ford, Julian R. Starr, Anton Reznicek, Limin Zhang 0001, James A. Macklin	Authors' attitude toward adopting a new workflow to improve the computability of phenotype publications.	Database J. Biol. Databases Curation	2022	DBLP DOI BibTeX RDF
14	R. Padmanaban, M. Thirumaran, P. Anitha, A. Moshika	Computability evaluation of RESTful API using Primitive Recursive Function.	J. King Saud Univ. Comput. Inf. Sci.	2022	DBLP DOI BibTeX RDF
14	Amin Farjudian, Eugenio Moggi	Robustness, Scott Continuity, and Computability.	CoRR	2022	DBLP DOI BibTeX RDF
14	Clara Loeh, Matthias Uschold	L2-Betti numbers and computability of reals.	CoRR	2022	DBLP BibTeX RDF
14	Holger Boche, Rafael F. Schaefer, H. Vincent Poor	Algorithmic Computability and Approximability of Capacity-Achieving Input Distributions.	CoRR	2022	DBLP BibTeX RDF
14	Subrata Paul	Cellular Automata: Temporal Stochasticity and Computability.	CoRR	2022	DBLP DOI BibTeX RDF