Search results for "undecidability"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
17	Zhou Chaochen, Michael R. Hansen, Peter Sestoft	Decidability and Undecidability Results for Duration Calculus.	STACS	1993	DBLP DOI BibTeX RDF
17	Wojciech Penczek	On Undecidability of Propositional Temporal Logics on Trace Systems.	Inf. Process. Lett.	1992	DBLP DOI BibTeX RDF
17	Douglas Albert, Robert Baldinger, John Rhodes 0001	Undecidability of the Identity Problem for Finite Semigroups.	J. Symb. Log.	1992	DBLP DOI BibTeX RDF
17	Klaus Ambos-Spies, André Nies, Richard A. Shore	The Theory of the Recursively Enumerable Weak Truth-Table Degrees Is Undecidability.	J. Symb. Log.	1992	DBLP DOI BibTeX RDF
17	Ravi S. Sandhu	Undecidability of Safety for the Schematic Protection Model with Cyclic Creates.	J. Comput. Syst. Sci.	1992	DBLP DOI BibTeX RDF
17	William Landi	Undecidability of Static Analysis.	LOPLAS	1992	DBLP DOI BibTeX RDF
17	Jerzy Marcinkowski, Leszek Pacholski	Undecidability of the Horn-Clause Implication Problem	FOCS	1992	DBLP DOI BibTeX RDF	derivation trees, Horn-clause implication, atomic formulas, decidability problems, pure predicate logic, equality symbol
17	John S. Schlipf	A Survey of Complexity and Undecidability Results in Logic Programming.	Structural Complexity and Recursion-theoretic methods in Logic-Programming	1992	DBLP BibTeX RDF
17	Tomás Feder, Yatin P. Saraiya	Decidability and Undecidability of Equivalence for Linear Datalog with Applications to Normal-Form Optimizations.	ICDT	1992	DBLP DOI BibTeX RDF
17	David A. Klarner, Jean-Camille Birget, Wade Satterfield	On the Undecidability of the Freeness of Integer Matrix Semigroups.	Int. J. Algebra Comput.	1991	DBLP DOI BibTeX RDF
17	Samuel R. Buss	The Undecidability of k-Provability.	Ann. Pure Appl. Log.	1991	DBLP DOI BibTeX RDF
17	Frank J. Wroblewski	Undecidability in the Completion of Truth-Function Logic.	ISMVL	1991	DBLP DOI BibTeX RDF
17	Christine Ann Haught, Richard A. Shore	Undecidability and Initial Segments of the R.E. tt-Degrees.	J. Symb. Log.	1990	DBLP DOI BibTeX RDF
17	Rodney G. Downey	Corrigendum: Correction to "Undecidability of L(Finfty) and Other Lattices of r.e. Substructures".	Ann. Pure Appl. Log.	1990	DBLP DOI BibTeX RDF
17	Luigi Palopoli 0001	A new proof of undecidability of safety of logic queries.	SIGACT News	1990	DBLP DOI BibTeX RDF
17	Gilles Amiot	The undecidability of the second order predicate unification problem.	Arch. Math. Log.	1990	DBLP DOI BibTeX RDF
17	A. J. Kfoury, Jerzy Tiuryn, Pawel Urzyczyn	The Undecidability of the Semi-Unification Problem (Preliminary Report)	STOC	1990	DBLP DOI BibTeX RDF
17	Egon Wanke, Manfred Wiegers	Undecidability of the Bandwidth Problem on Linear Graph Languages.	Inf. Process. Lett.	1989	DBLP DOI BibTeX RDF
17	Jörg H. Siekmann, Peter Szabó	The Undecidability of the DA-Unification Problem.	J. Symb. Log.	1989	DBLP DOI BibTeX RDF
17	Peter F. Patel-Schneider	Undecidability of Subsumption in NIKL.	Artif. Intell.	1989	DBLP DOI BibTeX RDF
17	Friedhelm Hinz, Jürgen Dassow	A undecidability result for regular anguages and its applications to regulated rewriting.	Bull. EATCS	1989	DBLP BibTeX RDF
17	Rohit Parikh	Decidability and Undecidability in Distributed Transition Systems.	A Perspective in Theoretical Computer Science	1989	DBLP DOI BibTeX RDF
17	Karel Culík II, Sheng Yu 0001	Undecidability of CA Classification Schemes.	Complex Syst.	1988	DBLP BibTeX RDF
17	Moshe Y. Vardi	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries.	PODS	1988	DBLP DOI BibTeX RDF
17	Chang-jie Tang, Bowen Yin	Data Dependency and Undecidability in a Model of Historical Information System.	DS-3	1988	DBLP BibTeX RDF
17	Stephan Heilbrunner, Steffen Hölldobler	The Undecidability of the Unification and Matching Problem for Canonical Theories.	Acta Informatica	1987	DBLP DOI BibTeX RDF
17	Kevin J. Compton, C. Ward Henson, Saharon Shelah	Nonconvergence, undecidability, and intractability in asymptotic problems.	Ann. Pure Appl. Log.	1987	DBLP DOI BibTeX RDF
17	Sheryl Silibovsky Brady, Jeffrey B. Remmel	The undecidability of the lattice of R.E. closed subsets of an effective topological space.	Ann. Pure Appl. Log.	1987	DBLP DOI BibTeX RDF
17	Friedrich Otto	The Undecidability of Self-Embedding for Finite Semi-Thue and Thue Systems.	Theor. Comput. Sci.	1986	DBLP DOI BibTeX RDF
17	David Harel	Effective transformations on infinite trees, with applications to high undecidability, dominoes, and fairness.	J. ACM	1986	DBLP DOI BibTeX RDF
17	Rodney G. Downey	Undecidability of L(F∞) and other lattices of r.e. substructures.	Ann. Pure Appl. Log.	1986	DBLP DOI BibTeX RDF
17	Gregory L. Cherlin, Moshe Jarden	Undecidability of some elementary theories over pac fields.	Ann. Pure Appl. Log.	1986	DBLP DOI BibTeX RDF
17	David A. Plaisted	The Undecidability of Self-Embedding for Term Rewriting Systems.	Inf. Process. Lett.	1985	DBLP DOI BibTeX RDF
17	Alasdair Urquhart	The Undecidability of Entailment and Relevant Implication.	J. Symb. Log.	1984	DBLP DOI BibTeX RDF
17	Cornelia Kalfa	Some Undecidability Results in Strong Algebraic Languages.	J. Symb. Log.	1984	DBLP DOI BibTeX RDF
17	Friedrich Otto	Some Undecidability Results for Non-Monadic Church-Rosser Thue Systems.	Theor. Comput. Sci.	1984	DBLP DOI BibTeX RDF
17	Paliath Narendran, Robert McNaughton	The Undecidability of the Preperfectness of Thue Systems.	Theor. Comput. Sci.	1984	DBLP DOI BibTeX RDF
17	Valtteri Niemi	The Undecidability of Form Equivalence for Context-Free and E0L Forms.	Theor. Comput. Sci.	1984	DBLP DOI BibTeX RDF
17	David Harel, Mike Paterson	Undecidability of PDL with L={a^(2i)\|i>=0}.	J. Comput. Syst. Sci.	1984	DBLP DOI BibTeX RDF
17	Daniel E. Cohen	Modular machines, undecidability and incompleteness.	Logic and Machines	1983	DBLP DOI BibTeX RDF
17	Heinz-Dieter Ebbinghaus	Undecidability Of Some Domino Connectability Problems.	Math. Log. Q.	1982	DBLP DOI BibTeX RDF
17	Jürgen Albert	A Note on the Undecidability of Contextfreeness.	RAIRO Theor. Informatics Appl.	1982	DBLP DOI BibTeX RDF
17	Howard A. Blair	The Undecidability of Two Completeness Notions for the "Negation as Failure".	ICLP	1982	DBLP BibTeX RDF
17	Tomasz Imielinski, Witold Lipski Jr.	On th Undecidability of Equivalence Problems for Relational Expressions.	Advances in Data Base Theory	1982	DBLP BibTeX RDF
17	Wiktor Danko	A Criterion of Undecidability of Algorithmic Theories.	Fundam. Informaticae	1981	DBLP BibTeX RDF
17	Ronald V. Book	The Undecidability of a Word Problem: On a Conjecture of Strong, Maggiolo-Schettini and Rosen.	Inf. Process. Lett.	1981	DBLP DOI BibTeX RDF
17	Warren D. Goldfarb	The Undecidability of the Second-Order Unification Problem.	Theor. Comput. Sci.	1981	DBLP DOI BibTeX RDF
17	Alfred B. Manaster, Joseph G. Rosenstein	Two-Dimensional Partial Orderings: Undecidability.	J. Symb. Log.	1980	DBLP DOI BibTeX RDF
17	Narain H. Gehani	Generic Procedures: An Implementation and an Undecidability Result.	Comput. Lang.	1980	DBLP DOI BibTeX RDF
17	Salvatore Caporaso, Giovanni Pani	Undecidability vs transfinite induction for the consistency of hyperarithmetical sets.	Arch. Math. Log.	1980	DBLP DOI BibTeX RDF
17	Wiktor Danko	A Criterion of Undecidability of Algorithmic Theories.	MFCS	1980	DBLP DOI BibTeX RDF
17	Wolfgang Schönfeld	An Undecidability Result for Relation Algebras.	J. Symb. Log.	1979	DBLP DOI BibTeX RDF
17	Hiroakira Ono, Akira Nakamura	Undecidability of the First-Order Arithmetic A[P(x), 2x, x+1].	J. Comput. Syst. Sci.	1979	DBLP DOI BibTeX RDF
17	Lewis D. Baxter	The Undecidability of the Third Order Dyadic Unification Problem	Inf. Control.	1978	DBLP DOI BibTeX RDF
17	Ivan Korec	Decidability (Undecidability) of Equivalence of Minsky Machines with Components Consisting of at Most Seven (Eight) Instructions.	MFCS	1977	DBLP DOI BibTeX RDF
17	Jekeri Okee	A semantical proof of the undecidability of the monadic intuitionistic predicate calculus of the first order.	Notre Dame J. Formal Log.	1975	DBLP DOI BibTeX RDF
17	Dov M. Gabbay	The Undecidability of Intuitionistic Theories of Algebraically Closed Fields and Real Closed Fields.	J. Symb. Log.	1973	DBLP DOI BibTeX RDF
17	Gérard P. Huet	The Undecidability of Unification in Third Order Logic	Inf. Control.	1973	DBLP DOI BibTeX RDF
17	Grzegorz Rozenberg	Direct Proofs of the Undecidability of the Equivalence Problem for Sentential Forms of Linear Context-Free Grammars and the Equivalence Problem for 0L Systems.	Inf. Process. Lett.	1972	DBLP DOI BibTeX RDF
17	Solomon Garfunkel, Herbert S. Shank	On the Undecidability of Finite Planar Cubic Graphs.	J. Symb. Log.	1972	DBLP DOI BibTeX RDF
17	Dov M. Gabbay	Sufficient Conditions for the Undecidability of Intuitionistic Theories with Applications.	J. Symb. Log.	1972	DBLP DOI BibTeX RDF
17	Raymond E. Miller	Some Undecidability Results for Parallel Program Schemata.	SIAM J. Comput.	1972	DBLP DOI BibTeX RDF
17	Raymond E. Miller	A boundary between decidability and undecidability for parallel program schemata (Extended Abstract).	Proving Assertions About Programs	1972	DBLP DOI BibTeX RDF
17	Solomon Garfunkel, Herbert S. Shank	On the Undecidability of Finite Planar Graphs.	J. Symb. Log.	1971	DBLP DOI BibTeX RDF
17	James P. Jones	Effectively Retractable Theories and Degrees of Undecidability.	J. Symb. Log.	1969	DBLP DOI BibTeX RDF
17	Philip K. Hooper	The Undecidability of the Turing Machine Immortality Problem.	J. Symb. Log.	1966	DBLP DOI BibTeX RDF
17	Calvin C. Elgot, Michael O. Rabin	Decidability and Undecidability of Extensions of Second (First) Order Theory of (Generalized) Successor.	J. Symb. Log.	1966	DBLP DOI BibTeX RDF
17	Sheila A. Greibach	The Undecidability of the Ambiguity Problem for Minimal Linear Grammars	Inf. Control.	1963	DBLP DOI BibTeX RDF
17	Hilary Putnam	Decidability and Essential Undecidability.	J. Symb. Log.	1957	DBLP DOI BibTeX RDF
11	Stéphane Demri, Ranko Lazic 0001	LTL with the freeze quantifier and register automata.	ACM Trans. Comput. Log.	2009	DBLP DOI BibTeX RDF	Computational complexity, expressiveness
11	Guillem Godoy, Hugo Hernández	Undecidable properties of flat term rewrite systems.	Appl. Algebra Eng. Commun. Comput.	2009	DBLP DOI BibTeX RDF	Mathematics Subject Classification (2000) 16S15, 68Q42
11	Balder ten Cate, Maarten Marx	Axiomatizing the Logical Core of XPath 2.0.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	XML, XPath, Query rewriting, Axiomatization
11	Emanuel Kieronski, Lidia Tendera	On Finite Satisfiability of Two-Variable First-Order Logic with Equivalence Relations.	LICS	2009	DBLP DOI BibTeX RDF
11	Michael Ummels, Dominik Wojtczak	The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games.	ICALP (2)	2009	DBLP DOI BibTeX RDF
11	Martin Kutrib, Andreas Malcher	Cellular Automata with Sparse Communication.	CIAA	2009	DBLP DOI BibTeX RDF
11	Jos de Bruijn, Stijn Heymans	Complexity of the Stable Model Semantics for Queries on Incomplete Databases.	LPNMR	2009	DBLP DOI BibTeX RDF
11	Tero Harju	Post Correspondence Problem and Small Dimensional Matrices.	Developments in Language Theory	2009	DBLP DOI BibTeX RDF
11	Guillem Godoy, Ashish Tiwari 0001	Invariant Checking for Programs with Procedure Calls.	SAS	2009	DBLP DOI BibTeX RDF
11	Nikolaj S. Bjørner, Nikolai Tillmann, Andrei Voronkov	Path Feasibility Analysis for String-Manipulating Programs.	TACAS	2009	DBLP DOI BibTeX RDF
11	Giorgio Delzanno, Cinzia Di Giusto, Maurizio Gabbrielli, Cosimo Laneve, Gianluigi Zavattaro	The kappa-Lattice: Decidability Boundaries for Qualitative Analysis in Biological Languages.	CMSB	2009	DBLP DOI BibTeX RDF
11	Helmut Seidl, Kumar Neeraj Verma	Flat and One-Variable Clauses for Single Blind Copying Protocols: The XOR Case.	RTA	2009	DBLP DOI BibTeX RDF
11	Jakob Grue Simonsen	The -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity).	RTA	2009	DBLP DOI BibTeX RDF
11	Grégory Lafitte, Michael Weiss	Constructing New Aperiodic Self-simulating Tile Sets.	CiE	2009	DBLP DOI BibTeX RDF
11	Boris Motik	Combining Description Logics, Description Graphs, and Rules.	FroCoS	2009	DBLP DOI BibTeX RDF
11	Laurent Doyen 0001, Gilles Geeraerts, Jean-François Raskin, Julien Reichert	Realizability of Real-Time Logics.	FORMATS	2009	DBLP DOI BibTeX RDF
11	Martin Fränzle, Mani Swaminathan	Revisiting Decidability and Optimum Reachability for Multi-Priced Timed Automata.	FORMATS	2009	DBLP DOI BibTeX RDF
11	Slawomir Lasota 0001, Igor Walukiewicz	Alternating timed automata.	ACM Trans. Comput. Log.	2008	DBLP DOI BibTeX RDF	emptyness problem, timed automata, Alternation
11	David Toman 0001, Grant E. Weddell	On Keys and Functional Dependencies as First-Class Citizens in Description Logics.	J. Autom. Reason.	2008	DBLP DOI BibTeX RDF	Path-functional dependency, Relational keys, Description logics
11	Giorgio Delzanno, Roberto Montagna	Reachability analysis of fragments of mobile ambients in AC term rewriting.	Formal Aspects Comput.	2008	DBLP DOI BibTeX RDF	Petri nets, Term rewriting, Reachability, Mobile ambients
11	Carlos Areces, Diego Figueira, Santiago Figueira, Sergio Mera	Expressive Power and Decidability for Memory Logics.	WoLLIC	2008	DBLP DOI BibTeX RDF
11	Margus Veanes, Ando Saabas	On Bounded Reachability of Programs with Set Comprehensions.	LPAR	2008	DBLP DOI BibTeX RDF
11	Christel Baier, Nathalie Bertrand 0001, Marcus Größer	On Decision Problems for Probabilistic Büchi Automata.	FoSSaCS	2008	DBLP DOI BibTeX RDF
11	Sabrina Baselice, Piero A. Bonatti	Composing Normal Programs with Function Symbols.	ICLP	2008	DBLP DOI BibTeX RDF
11	Bruno Durand 0001, Andrei E. Romashchenko, Alexander Shen	Fixed Point and Aperiodic Tilings.	Developments in Language Theory	2008	DBLP DOI BibTeX RDF
11	Malay K. Ganai	Efficient Decision Procedure for Bounded Integer Non-linear Operations Using SMT().	Haifa Verification Conference	2008	DBLP DOI BibTeX RDF
11	Mathieu Sablik, Guillaume Theyssier	Topological Dynamics of 2D Cellular Automata.	CiE	2008	DBLP DOI BibTeX RDF
11	Rémi Brochenin, Stéphane Demri, Étienne Lozes	On the Almighty Wand.	CSL	2008	DBLP DOI BibTeX RDF
11	Paul Bell, Igor Potapov	Periodic and Infinite Traces in Matrix Semigroups.	SOFSEM	2008	DBLP DOI BibTeX RDF
11	Carlo A. Furia, Matteo Rossi	MTL with Bounded Variability: Decidability and Complexity.	FORMATS	2008	DBLP DOI BibTeX RDF
11	Riccardo Rosati 0001	On Combining Description Logic Ontologies and Nonrecursive Datalog Rules.	RR	2008	DBLP DOI BibTeX RDF