Search results for "undecidability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
61	Frank Wolter, Michael Zakharyaschev	Undecidability of the unification and admissibility problems for modal and description logics.	ACM Trans. Comput. Log.	2008	DBLP DOI BibTeX RDF	admissible rule, description logic, decidability, Unification, hybrid logic
61	Thomas A. Henzinger, Jean-François Raskin	Robust Undecidability of Timed and Hybrid Systems.	HSCC	2000	DBLP DOI BibTeX RDF
59	Zhiyao Liang, Rakesh M. Verma	Improving Techniques for Proving Undecidability of Checking Cryptographic Protocols.	ARES	2008	DBLP DOI BibTeX RDF	insider, authentication, formal method, cryptographic protocol, undecidability, secrecy
50	Petr Jancar, Jirí Srba	Undecidability Results for Bisimilarity on Prefix Rewrite Systems.	FoSSaCS	2006	DBLP DOI BibTeX RDF
48	Petr Jancar, Jirí Srba	Undecidability of bisimilarity by defender's forcing.	J. ACM	2008	DBLP DOI BibTeX RDF	process algebra, undecidability, pushdown automata, Bisimilarity
48	Koji Nakazawa, Makoto Tatsuta, Yukiyoshi Kameyama, Hiroshi Nakano	Undecidability of Type-Checking in Domain-Free Typed Lambda-Calculi with Existence.	CSL	2008	DBLP DOI BibTeX RDF	domain-free type system, undecidability, existential type, CPS-translation
48	Oleg V. Kudinov, Victor L. Selivanov	Undecidability in the Homomorphic Quasiorder of Finite Labeled Forests.	CiE	2006	DBLP DOI BibTeX RDF	homomorphic quasiorder, elementary theory, Tree, undecidability, forest, labeled tree
48	Judith Gal-Ezer, Dvir Lanzberg, Daphna Shahak	Introducing undecidability.	ITiCSE	2004	DBLP DOI BibTeX RDF	pedagogy, undecidability
44	Max I. Kanovich	The Expressive Power of Horn Monadic Linear Logic.	CSL	2001	DBLP DOI BibTeX RDF
40	Sergei G. Vorobyov	Structural Decidable Extensions of Bounded Quantification.	POPL	1995	DBLP DOI BibTeX RDF	(W)SnS, bounded universal type quantification, essential undecidability, parametric and inheritance polymorphisms, second-order polymorphic typed ?-calculus, system F?, decidability, subtyping, undecidability
39	Jasper Berendsen, Taolue Chen, David N. Jansen	Undecidability of Cost-Bounded Reachability in Priced Probabilistic Timed Automata.	TAMC	2009	DBLP DOI BibTeX RDF
39	Sergio Giro	Undecidability Results for Distributed Probabilistic Systems.	SBMF	2009	DBLP DOI BibTeX RDF
39	Jörg Endrullis, Herman Geuvers, Hans Zantema	Degrees of Undecidability in Term Rewriting.	CSL	2009	DBLP DOI BibTeX RDF
39	Petr Jancar	Selected Ideas Used for Decidability and Undecidability of Bisimilarity.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF	decidability, bisimulation equivalence
39	Ian M. Hodkinson, Angelo Montanari, Guido Sciavicco	Non-finite Axiomatizability and Undecidability of Interval Temporal Logics with C, D, and T.	CSL	2008	DBLP DOI BibTeX RDF
39	Naoki Kobayashi 0001, Takashi Suto	Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the pi -Calculus.	ICALP	2007	DBLP DOI BibTeX RDF
39	Paul Bell, Igor Potapov	Lowering Undecidability Bounds for Decision Questions in Matrices.	Developments in Language Theory	2006	DBLP DOI BibTeX RDF	vector reachability, matrix semigroups, piecewise linear maps, membership, Theory of computing
39	Neil Immerman, Alexander Moshe Rabinovich, Thomas W. Reps, Shmuel Sagiv, Greta Yorsh	The Boundary Between Decidability and Undecidability for Transitive-Closure Logics.	CSL	2004	DBLP DOI BibTeX RDF
39	Richard Mayr	Undecidability of Weak Bisimulation Equivalence for 1-Counter Processes.	ICALP	2003	DBLP DOI BibTeX RDF	1-counter nets, 1-counter machines, bisimulation
39	Arthur Charlesworth	The undecidability of associativity and commutativity analysis.	ACM Trans. Program. Lang. Syst.	2002	DBLP DOI BibTeX RDF	Associative function, commutative function, loop program, recursively enumerable, reduction, recursive, sequence, scan, undecidable, parallel prefix, primitive recursive
39	Jirí Srba	Undecidability of Weak Bisimilarity for Pushdown Processes.	CONCUR	2002	DBLP DOI BibTeX RDF
39	Piotr Chrzastowski-Wachtel	Testing Undecidability of the Reachability in Petri Nets with the Help of 10th Hilbert Problem.	ICATPN	1999	DBLP DOI BibTeX RDF
39	Ralf Treinen	A New Method for Undecidability Proofs of First Order Theories.	FSTTCS	1990	DBLP DOI BibTeX RDF
37	James Brotherston, Max I. Kanovich	Undecidability of Propositional Separation Logic and Its Neighbours.	LICS	2010	DBLP DOI BibTeX RDF	bunched logic, heap models, separation logic, undecidability
37	Leon Horsten, Philip D. Welch	The Undecidability of Propositional Adaptive Logic.	Synth.	2007	DBLP DOI BibTeX RDF	Dynamic logic, Undecidability, Paraconsistent logic, Adaptive logic
37	Joseph S. Miller, Lawrence S. Moss	The Undecidability of Iterated Modal Relativization.	Stud Logica	2005	DBLP DOI BibTeX RDF	iterated relativization, modal logic, undecidability, Dynamic epistemic logic
37	R. J. Mac Dawson, R. Paré, D. A. Pronk	Undecidability of the Free Adjoint Construction.	Appl. Categorical Struct.	2003	DBLP DOI BibTeX RDF	free adjoint construction, abacus, undecidability, 2-category
37	Rodney G. Downey, André Nies	Undecidability Results for Low Complexity Degree Structures.	CCC	1997	DBLP DOI BibTeX RDF	undecidability results, low complexity degree structures, EXPTIME degrees, polynomial time Turing, many-one reducibility, coding method, ideal lattices, hyper-polynomial time classes, Boolean algebra, Boolean algebras
34	Matthias C. Caro	From undecidability of non-triviality and finiteness to undecidability of learnability.	Int. J. Approx. Reason.	2023	DBLP DOI BibTeX RDF
33	Yevgeny Kazakov, Ulrike Sattler, Evgeny Zolin	How Many Legs Do I Have? Non-Simple Roles in Number Restrictions Revisited.	LPAR	2007	DBLP DOI BibTeX RDF
33	Rajeev Alur, Kenneth L. McMillan, Doron A. Peled	Deciding Global Partial-Order Properties.	Formal Methods Syst. Des.	2005	DBLP DOI BibTeX RDF	partial order logics, model checking, concurrency, temporal logics
33	Nachum Dershowitz	Primitive Rewriting.	Processes, Terms and Cycles	2005	DBLP DOI BibTeX RDF
33	Raffaella Gentilini	Reachability Problems on Extended O-Minimal Hybrid Automata.	FORMATS	2005	DBLP DOI BibTeX RDF
33	Martin Fränzle	Model-checking dense-time Duration Calculus.	Formal Aspects Comput.	2004	DBLP DOI BibTeX RDF	Dense-time Duration Calculus, Model-checking, Decidability
33	Ranko Lazic 0001, Thomas Christopher Newcomb, A. W. Roscoe 0001	On Model Checking Data-Independent Systems with Arrays with Whole-Array Operations.	25 Years Communicating Sequential Processes	2004	DBLP DOI BibTeX RDF
33	Viktor Kuncak, Martin C. Rinard	Existential Heap Abstraction Entailment Is Undecidable.	SAS	2003	DBLP DOI BibTeX RDF	Program Verification, Shape Analysis, Type Checking, Monadic Second-Order Logic, Typestate, Graph Homomorphism, Post Correspondence Problem
31	Eero Lehtonen	An Undecidable Permutation of the Natural Numbers.	RP	2009	DBLP DOI BibTeX RDF	Permutation, Undecidability
31	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
31	Wan-Hui Tseng, Chin-Feng Fan	Handling Malicious Code on Control Systems.	SAFECOMP	2007	DBLP DOI BibTeX RDF	control systems security, malicious code classification, undecidability
31	Victor L. Selivanov	A Useful Undecidable Theory.	CiE	2007	DBLP DOI BibTeX RDF	discrete weak semilattice, partition, theory, reducibility, undecidability, Semilattice
31	T. S. Jayram, Phokion G. Kolaitis, Erik Vee	The containment problem for REAL conjunctive queries with inequalities.	PODS	2006	DBLP DOI BibTeX RDF	bag semantics, bag-set semantics, conjunctive queries, undecidability, query containment, inequalities
31	Julien Cervelle, Enrico Formenti, Benoît Masson	Basic Properties for Sand Automata.	MFCS	2005	DBLP DOI BibTeX RDF	sand automata, ultimate periodicity, undecidability, reversibility
31	Dipankar Sarkar 0001, S. C. De Sarkar	A Set of Inference Rules for Quantified Formula Handling and Array Handling in Verification of Programs Over Integers.	IEEE Trans. Software Eng.	1989	DBLP DOI BibTeX RDF	quantified formula handling, array handling, undecidability problem, automated verifier, quantified formulas, bound-extension rule, bound-modification, theorem proving, program verification, program verification, first-order logic, inference mechanisms, decidability, inference rules, integer arithmetic
31	Martin K. Solomon	Some properties of relational expressions.	ACM Southeast Regional Conference	1979	DBLP DOI BibTeX RDF	equi-join, predicate lock, Concurrency, query optimization, relational algebra, undecidability, relational calculus, predicate calculus, natural join
28	Matthias Baaz, Agata Ciabattoni, Norbert Preining	SAT in Monadic Gödel Logics: A Borderline between Decidability and Undecidability.	WoLLIC	2009	DBLP DOI BibTeX RDF
28	Carlos Olarte, Frank D. Valencia	The expressivity of universal timed CCP: undecidability of Monadic FLTL and closure operators for security.	PPDP	2008	DBLP DOI BibTeX RDF	first-order linear temporal logic, security protocols, closure operators, concurrent constraint programming
28	Nicolas Ollinger	Two-by-Two Substitution Systems and the Undecidability of the Domino Problem.	CiE	2008	DBLP DOI BibTeX RDF
28	Vesa Halava, Mika Hirvensalo	Improved matrix pair undecidability results.	Acta Informatica	2007	DBLP DOI BibTeX RDF
28	Artur Jez, Alexander Okhotin	Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.	CSR	2007	DBLP DOI BibTeX RDF
28	David Janin	On the (High) Undecidability of Distributed Synthesis Problems.	SOFSEM (1)	2007	DBLP DOI BibTeX RDF
28	Sara Adams, Joël Ouaknine, James Worrell 0001	Undecidability of Universality for Timed Automata with Minimal Resources.	FORMATS	2007	DBLP DOI BibTeX RDF
28	Andrzej Grzegorczyk	Undecidability without Arithmetization.	Stud Logica	2005	DBLP DOI BibTeX RDF	discernibility, Kurt Gödel, Alfred Tarski, representability, decidability, arithmetization, concatenation
28	Marc Bezem	On the Undecidability of Coherent Logic.	Processes, Terms and Cycles	2005	DBLP DOI BibTeX RDF
28	Jérôme Durand-Lose	Abstract Geometrical Computation: Turing-Computing Ability and Undecidability.	CiE	2005	DBLP DOI BibTeX RDF	Analog model of computation, Turing universality, Cellular automata, Geometry, Abstract geometrical computation
28	Venkatesh Mysore, Amir Pnueli	Refining the Undecidability Frontier of Hybrid Automata.	FSTTCS	2005	DBLP DOI BibTeX RDF
28	Erich Grädel, Martin Otto 0001, Eric Rosen	Undecidability results on two-variable logics.	Arch. Math. Log.	1999	DBLP DOI BibTeX RDF
28	Vesa Halava, Mika Hirvensalo, Ronald de Wolf	Decidability and Undecidability of Marked PCP.	STACS	1999	DBLP DOI BibTeX RDF
28	Daniel Kirsten	Some Undecidability Results Related to the Star Problem in Trace Monoids.	STACS	1999	DBLP DOI BibTeX RDF
28	Petr Jancar, Faron Moller	Techniques for Decidability and Undecidability of Bisimilarity.	CONCUR	1999	DBLP DOI BibTeX RDF
28	Alfons Geser, Aart Middeldorp, Enno Ohlebusch, Hans Zantema	Relative Undecidability in the Termination Hierarchy of Single Rewrite Rules.	TAPSOFT	1997	DBLP DOI BibTeX RDF
28	Erich Grädel, Martin Otto 0001, Eric Rosen	Undecidability Results on Two-Variable Logics.	STACS	1997	DBLP DOI BibTeX RDF
28	Jerzy Marcinkowski	Undecidability of the First Order Theory of One-Step Right Ground Rewriting.	RTA	1997	DBLP DOI BibTeX RDF
28	Alfons Geser, Aart Middeldorp, Enno Ohlebusch, Hans Zantema	Relative Undecidability in Term Rewriting.	CSL	1996	DBLP DOI BibTeX RDF
28	Friedrich Otto	Some Undecidability Results for Weakly Confluent Monadic String-Rewriting Systems.	AAECC	1991	DBLP DOI BibTeX RDF
28	Paul S. Wang	The Undecidability of the Existence of Zeros of Real Elementary Functions.	J. ACM	1974	DBLP DOI BibTeX RDF
22	Kshitij Bansal, Rémi Brochenin, Étienne Lozes	Beyond Shapes: Lists with Ordered Data.	FoSSaCS	2009	DBLP DOI BibTeX RDF
22	Davide Bresolin, Dario Della Monica, Valentin Goranko, Angelo Montanari, Guido Sciavicco	Decidable and Undecidable Fragments of Halpern and Shoham's Interval Temporal Logic: Towards a Complete Classification.	LPAR	2008	DBLP DOI BibTeX RDF
22	Jarkko Kari	The Tiling Problem Revisited (Extended Abstract).	MCU	2007	DBLP DOI BibTeX RDF
22	Riccardo Rosati 0001	The Limits of Querying Ontologies.	ICDT	2007	DBLP DOI BibTeX RDF
22	Stéphane Demri, Deepak D'Souza, Régis Gascon	A Decidable Temporal Logic of Repeating Values.	LFCS	2007	DBLP DOI BibTeX RDF
22	Patricia Bouyer, Nicolas Markey	Costs Are Expensive!	FORMATS	2007	DBLP DOI BibTeX RDF
22	Tachio Terauchi, Alex Aiken	On Typability for Rank-2 Intersection Types with Polymorphic Recursion.	LICS	2006	DBLP DOI BibTeX RDF
22	Felix Klaedtke, Harald Rueß	Monadic Second-Order Logics with Cardinalities.	ICALP	2003	DBLP DOI BibTeX RDF
22	Nicolas Ollinger	The Intrinsic Universality Problem of One-Dimensional Cellular Automata.	STACS	2003	DBLP DOI BibTeX RDF
22	Thomas Heimrich, Günther Specht	Enhancing ECA Rules for Distributed Active Database Systems.	Web, Web-Services, and Database Systems	2002	DBLP DOI BibTeX RDF
22	Marcin Jurdzinski, Mogens Nielsen	Hereditary History Preserving Bisimilarity Is Undecidable.	STACS	2000	DBLP DOI BibTeX RDF
22	Salvatore La Torre, Margherita Napoli	A Decidable Dense Branching-Time Temporal Logic.	FSTTCS	2000	DBLP DOI BibTeX RDF
22	A. J. Kfoury, Santiago M. Pericás-Geertsen	Type Inference for Recursive Definitions.	LICS	1999	DBLP DOI BibTeX RDF	type systems, type inference, lambda calculus, unification, software specification
22	Rajeev Alur, Kenneth L. McMillan, Doron A. Peled	Deciding Global Partial-Order Properties.	ICALP	1998	DBLP DOI BibTeX RDF
22	Jacek Chrzaszcz	Polymorphic Subtyping Without Distributivity.	MFCS	1998	DBLP DOI BibTeX RDF
22	David Harel	Towards a Theory of Recursive Structures.	MFCS	1998	DBLP DOI BibTeX RDF
22	Matteo Baldoni, Laura Giordano 0001, Alberto Martelli	A Tableau for Multimodal Logics and Some (Un)Decidability Results.	TABLEAUX	1998	DBLP DOI BibTeX RDF	Multimodal logics, Prefixed Tableaux methods, Decidability, Formal Grammars
22	David Harel	Towards a theory of Recursive Structures.	Computer Science Today	1995	DBLP DOI BibTeX RDF
22	Anatoli Degtyarev, Andrei Voronkov	Simultaneous Regid E-Unification Is Undecidable.	CSL	1995	DBLP DOI BibTeX RDF
22	David Harel	Towards a Theory of Recursive Structures.	STACS	1994	DBLP DOI BibTeX RDF
22	Matthias Baaz, Richard Zach	Algorithmic Structuring of Cut-free Proofs.	CSL	1992	DBLP DOI BibTeX RDF
20	Florian Berger, Rolf Klein	A traveller's problem.	SCG	2010	DBLP DOI BibTeX RDF	affine mappings, continuous dijkstra, frogger, pseudo-polynomial approximation, computational geometry, partition, np-hardness, motion planning, undecidability
20	Caslav Brukner	Quantum complementarity and logical indeterminacy.	Nat. Comput.	2009	DBLP DOI BibTeX RDF	Quantum complementarity, Logical indeterminacy, Mathematical undecidability
20	Max I. Kanovich, Paul D. Rowe, Andre Scedrov	Policy Compliance in Collaborative Systems.	CSF	2009	DBLP DOI BibTeX RDF	Collaboration, Complexity, Policies, Confidentiality, Undecidability
20	Maurice Margenstern	The Periodic Domino Problem Is Undecidable in the Hyperbolic Plane.	RP	2009	DBLP DOI BibTeX RDF	hyperbolic plane, periodic tiling problem, tilings, undecidability
20	Zhiyao Liang, Rakesh M. Verma	Complexity of Checking Freshness of Cryptographic Protocols.	ICISS	2008	DBLP DOI BibTeX RDF	Athena, NP-completeness, Cryptographic protocols, undecidability, replay attack, model checker, freshness, challenge response
20	Erik D. Demaine, Robert A. Hearn	Constraint Logic: A Uniform Framework for Modeling Computation as Games.	CCC	2008	DBLP DOI BibTeX RDF	games, undecidability, hardness
20	Decheng Ding, Klaus Weihrauch, Yongcheng Wu	Absolutely Non-effective Predicates and Functions in Computable Analysis.	TAMC	2007	DBLP DOI BibTeX RDF	measure, computability, representation, set, undecidability
20	Phokion G. Kolaitis, Jonathan Panttaja, Wang Chiew Tan	The complexity of data exchange.	PODS	2006	DBLP DOI BibTeX RDF	database dependencies, complexity, data exchange, schema mappings, heterogenous databases, undecidability, data translation
20	Jia Xu	Making Software Timing Properties Easier to Inspect and Verify.	IEEE Softw.	2003	DBLP DOI BibTeX RDF	preruntime scheduling, verification, real time, predictability, software, code, inspection, undecidability, timing properties, state space explosion
20	Venkatesan T. Chakaravarthy	New results on the computability and complexity of points - to analysis.	POPL	2003	DBLP DOI BibTeX RDF	flow-insensitive, complexity, pointer analysis, undecidability, flow-sensitive
20	Giuseppe Longo	Computer modelling and natural phenomena.	ESEC / SIGSOFT FSE	2003	DBLP DOI BibTeX RDF	computational models in biology, continuous models, digital approximation and discrete data structures, plastiticy and degeneracy in neural systems, unpredictability and undecidability, dynamical systems, causal relations
20	Larry J. Stockmeyer, Albert R. Meyer	Cosmological lower bound on the circuit complexity of a small problem in logic.	J. ACM	2002	DBLP DOI BibTeX RDF	WS1S, practical undecidability, computational complexity, lower bound, logic, Circuit complexity, decision problem
20	Markus Müller-Olm, Helmut Seidl	On optimal slicing of parallel programs.	STOC	2001	DBLP DOI BibTeX RDF	complexity, parallel programs, slicing, undecidability, interprocedural analysis
20	Rajeev Alur, Thomas A. Henzinger	Back to the Future: Towards a Theory of Timed Regular Languages	FOCS	1992	DBLP DOI BibTeX RDF	theory of timed regular languages, two-way timed automata, temporal logic, undecidability, boolean operations, PSPACE-complete