Search results for "undecidable"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
126	Alexei G. Myasnikov	Generic Complexity of Undecidable Problems.	CSR	2007	DBLP DOI BibTeX RDF
41	Olivier Finkel	Undecidable Problems About Timed Automata.	FORMATS	2006	DBLP DOI BibTeX RDF
41	Paliath Narendran, Jonathan Stillman	It is Undecidable Whether the Knuth-Bendix Completion Procedure Generates a Crossed Pair.	STACS	1989	DBLP DOI BibTeX RDF
41	Juris Hartmanis	On the Complexity of Undecidable Problems in Automata Theory.	J. ACM	1969	DBLP DOI BibTeX RDF
39	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
33	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
33	Michal Kunc	The Simplest Language Where Equivalence of Finite Substitutions Is Undecidable.	FCT	2007	DBLP DOI BibTeX RDF
33	Pavel Krcál, Wang Yi 0001	Decidable and Undecidable Problems in Schedulability Analysis Using Timed Automata.	TACAS	2004	DBLP DOI BibTeX RDF
33	Vincent D. Blondel, Vincent Canterini	Undecidable Problems for Probabilistic Automata of Fixed Dimension.	Theory Comput. Syst.	2003	DBLP DOI BibTeX RDF
33	Eugene Asarin, Gerardo Schneider	Widening the Boundary between Decidable and Undecidable Hybrid Systems.	CONCUR	2002	DBLP DOI BibTeX RDF
33	Juhani Karhumäki, Leonid P. Lisovik	A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab*c.	STACS	2001	DBLP DOI BibTeX RDF
33	Paliath Narendran, Friedrich Otto	The Word Matching Problem Is Undecidable For Finite Special String-Rewriting Systems That Are Confluent.	ICALP	1997	DBLP DOI BibTeX RDF	matching, unification, equational theory, string-rewriting systems
33	Géraud Sénizergues	Some Undecidable Termination Problems for Semi-Thue Systems (Abstract).	RTA	1993	DBLP DOI BibTeX RDF
33	Max Dauchet	Termination of Rewriting is Undecidable in the One-Rule Case.	MFCS	1988	DBLP DOI BibTeX RDF
31	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
31	Thierry Joly	Encoding of the Halting Problem into the Monster Type & Applications.	TLCA	2003	DBLP DOI BibTeX RDF
31	Mohamed G. Gouda, Louis E. Rosier	Communicating Finite State Machines with Priority Channnels.	ICALP	1984	DBLP DOI BibTeX RDF
31	Neil D. Jones, Steven S. Muchnick	Even Simple Programs are Hard to Analyze.	POPL	1975	DBLP DOI BibTeX RDF
25	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
25	Eero Lehtonen	An Undecidable Permutation of the Natural Numbers.	RP	2009	DBLP DOI BibTeX RDF	Permutation, Undecidability
25	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
25	Victor L. Selivanov	A Useful Undecidable Theory.	CiE	2007	DBLP DOI BibTeX RDF	discrete weak semilattice, partition, theory, reducibility, undecidability, Semilattice
25	Ian M. Hodkinson, Frank Wolter, Michael Zakharyaschev	Decidable and Undecidable Fragments of First-Order Branching Temporal Logics.	LICS	2002	DBLP DOI BibTeX RDF
25	Vladimir A. Zakharov	The Equivalence Problem for Computational Models: Decidable and Undecidable Cases.	MCU	2001	DBLP DOI BibTeX RDF
25	Philippe Schnoebelen	Bisimulation and Other Undecidable Equivalences for Lossy Channel Systems.	TACS	2001	DBLP DOI BibTeX RDF
25	Steffen Hölldobler, Dietrich Kuske	The Boundary between Decidable and Undecidable Fragments of the Fluent Calculus.	LPAR	2000	DBLP DOI BibTeX RDF
25	Mark Harman, Chris Fox, Robert M. Hierons, David W. Binkley, Sebastian Danicic	Program Simplification as a Means of Approximating Undecidable Propositions.	IWPC	1999	DBLP DOI BibTeX RDF	Testing, Transformation, Slicing
25	Jordi Levy	Decidable and Undecidable Second-Order Unification Problems.	RTA	1998	DBLP DOI BibTeX RDF
25	Sergei G. Vorobyov	The First-Order Theory of One Step Rewriting in Linear Noetherian Systems is Undecidable.	RTA	1997	DBLP DOI BibTeX RDF
25	Ralf Treinen	The First-Order Theory of One-Step Rewriting is Undecidable.	RTA	1996	DBLP DOI BibTeX RDF
25	Parosh Aziz Abdulla, Bengt Jonsson 0001	Undecidable Verification Problems for Programs with Unreliable Channels.	ICALP	1994	DBLP DOI BibTeX RDF
25	Tao Jiang 0001, Arto Salomaa, Kai Salomaa, Sheng Yu 0001	Inclusion is Undecidable for Pattern Languages.	ICALP	1993	DBLP DOI BibTeX RDF	inclusion problems, patterns, decidability, pattern languages, equivalence problems
25	Benjamin C. Pierce	Bounded Quantification is Undecidable.	POPL	1992	DBLP DOI BibTeX RDF
25	Ivan Korec	Undecidable Problems Concerning Generalized Pascal Triangles of Commutative Algebras.	MFCS	1986	DBLP DOI BibTeX RDF
25	Li Miao, Da-Fang Zhang	A New Proof for the Undecidability of Context-Sensitive Synchronization-Sensitive Analysis.	FCST	2010	DBLP DOI BibTeX RDF	concurrent interprocedural program analysis, synchronization-sensitive analysis, undecidable problem, context-sensitive analysis
25	Wilfried Sieg	On mind & Turing's machines.	Nat. Comput.	2007	DBLP DOI BibTeX RDF	absolutely unsolvable (undecidable), axiom of infinity, Church’s Thesis, Diophantine problem, finite machine, general recursive function, mechanical computability, objective mathematics, subjective mathematics, Turing machine
25	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
25	Martin F. van Bommel, Grant E. Weddell	Reasoning About Equations and Functional Dependencies on Complex Objects.	IEEE Trans. Knowl. Data Eng.	1994	DBLP DOI BibTeX RDF	complex object types, property value path, property paths, property value navigation, directed labeled graph, equational constraint, stratification condition, data structures, query processing, database management systems, query languages, query language, query languages, object-oriented databases, directed graphs, reasoning, database theory, functional dependencies, decision procedures, conjunctive queries, undecidable, complex objects, semantic data models, object-oriented data models, equations, constraint theory, constraint theory, constraint language
25	Jean Vuillemin	Exact Real Computer Arithmetic with Continued Fractions.	IEEE Trans. Computers	1990	DBLP DOI BibTeX RDF	exact real computer arithmetic, computable real numbers, undecidable comparison, integer division, infinite 1/0, undefined 0/0 numbers, algebraic algorithm, transcendental algorithm, Gauss, LeLisp, products, digital arithmetic, positional, exponentials, number theory, special functions, continued fractions, arithmetic operations, logarithms, sums, trigonometric functions
25	Amir Pnueli, Roni Rosner	Distributed Reactive Systems Are Hard to Synthesize	FOCS	1990	DBLP DOI BibTeX RDF	elementarily decidable, distributed reactive system, propositional specification, nonelementarily decidable, distributed architecture, undecidable, finite-state
25	Samuel R. Buss, Christos H. Papadimitriou, John N. Tsitsiklis	On the Predictability of Coupled Automata: An Allegory about Chaos	FOCS	1990	DBLP DOI BibTeX RDF	coupled automata, symmetric global control, undecidable problem, complexity, predictability, chaos, dichotomy
25	John H. Reif, J. D. Tygar, Akitoshi Yoshida	The Computability and Complexity of Optical Beam Tracing	FOCS	1990	DBLP DOI BibTeX RDF	optical models, refractive surfaces, undecidable problem, PSPACE-hard problem, optical beam tracing, ray-tracing problem, reflective surfaces, incident angle, complexity, computability
25	Anne Condon, Richard J. Lipton	On the Complexity of Space Bounded Interactive Proofs (Extended Abstract)	FOCS	1989	DBLP DOI BibTeX RDF	space bounded interactive proofs, finite-state verifiers, Markov chains, finite-state machines, upper bound, undecidable, interactive proof systems, recursively enumerable language
25	Lenore Blum, Mike Shub, Steve Smale	On a Theory of Computation over the Real Numbers; NP Completeness, Recursive Functions and Universal Machines (Extended Abstract)	FOCS	1988	DBLP DOI BibTeX RDF	universal machines, partial recursive functions, undecidable sets, foundational issues, NP completeness, numerical analysis, theory of computation, recursive functions, real numbers
23	Paul Bell, Igor Potapov	The Identity Correspondence Problem and Its Applications.	ISAAC	2009	DBLP DOI BibTeX RDF
23	Fernando Rosa-Velardo, David de Frutos-Escrig	Decidability Results for Restricted Models of Petri Nets with Name Creation and Replication.	Petri Nets	2009	DBLP DOI BibTeX RDF
23	Stefan Wehr, Peter Thiemann 0001	On the Decidability of Subtyping with Bounded Existential Types.	APLAS	2009	DBLP DOI BibTeX RDF
23	Nicolas Ollinger	Tiling the Plane with a Fixed Number of Polyominoes.	LATA	2009	DBLP DOI BibTeX RDF
23	Mohamed Faouzi Atig, Tayssir Touili	Verifying Parallel Programs with Dynamic Communication Structures.	CIAA	2009	DBLP DOI BibTeX RDF
23	Alberto Bertoni, Christian Choffrut, Beatrice Palano	Context-Free Grammars and XML Languages.	Developments in Language Theory	2006	DBLP DOI BibTeX RDF
23	Parosh Aziz Abdulla, Johann Deneux, Joël Ouaknine, James Worrell 0001	Decidability and Complexity Results for Timed Automata via Channel Machines.	ICALP	2005	DBLP DOI BibTeX RDF
23	Boris Konev, Frank Wolter, Michael Zakharyaschev	Temporal Logics over Transitive States.	CADE	2005	DBLP DOI BibTeX RDF
23	Malgorzata Moczurad, Wlodzimierz Moczurad	Some Open Problems in Decidability of Brick (Labelled Polyomino) Codes.	COCOON	2004	DBLP DOI BibTeX RDF
23	Gösta Grahne, Alex Thomo	Query containment and rewriting using views for regular path queries under constraints.	PODS	2003	DBLP DOI BibTeX RDF
23	Leonard M. Adleman, Jarkko Kari, Lila Kari, Dustin Reishus	On the Decidability of Self-Assembly of Infinite Ribbons.	FOCS	2002	DBLP DOI BibTeX RDF
23	Mitsuharu Yamamoto, Jean-Marie Cottin, Masami Hagiya	Decidability of Safety Properties of Timed Multiset Rewriting.	FTRTFT	2002	DBLP DOI BibTeX RDF	real-time systems, timed automata, decidability, timed Petri nets
23	Parosh Aziz Abdulla, Christel Baier, S. Purushothaman Iyer, Bengt Jonsson 0001	Reasoning about Probabilistic Lossy Channel Systems.	CONCUR	2000	DBLP DOI BibTeX RDF
23	Erich Grädel, Martin Otto 0001, Eric Rosen	Undecidability Results on Two-Variable Logics.	STACS	1997	DBLP DOI BibTeX RDF
23	Tero Harju, Juhani Karhumäki, Daniel Krob	Remarks on Generalized Post Correspondence Problem.	STACS	1996	DBLP DOI BibTeX RDF
23	Serge Abiteboul, Richard Hull 0001	Data Functions, Datalog and Negation (Extended Abstract).	SIGMOD Conference	1988	DBLP DOI BibTeX RDF	DAPLEX, DATALOG
18	Matthew Fox	On Formally Undecidable Traits of Intelligent Machines.	CoRR	2024	DBLP DOI BibTeX RDF
18	Ken-etsu Fujita, Aleksy Schubert, Pawel Urzyczyn, Konrad Zdanowski	The existential fragment of second-order propositional intuitionistic logic is undecidable.	J. Appl. Non Class. Logics	2024	DBLP DOI BibTeX RDF
18	Juvenal Murwanashyaka	Weak essentially undecidable theories of concatenation, part II.	Arch. Math. Log.	2024	DBLP DOI BibTeX RDF
18	Shuo Ding, Qirun Zhang	Witnessability of Undecidable Problems.	Proc. ACM Program. Lang.	2023	DBLP DOI BibTeX RDF
18	Maurice Margenstern	The Domino Problem of the Hyperbolic Plane Is Undecidable: New Proof.	Complex Syst.	2023	DBLP DOI BibTeX RDF
18	Roland Guttenberg	Verification of Population Protocols with Unordered Data is undecidable.	CoRR	2023	DBLP DOI BibTeX RDF
18	Fabian Mitterwallner, Aart Middeldorp, René Thiemann	Linear Termination over N is Undecidable.	CoRR	2023	DBLP DOI BibTeX RDF
18	Marie Fortin, Louwe B. Kuijer, Patrick Totzke, Martin Zimmermann 0002	HyperLTL Satisfiability Is Highly Undecidable, HyperCTL* is Even Harder.	CoRR	2023	DBLP DOI BibTeX RDF
18	Benjamin Hellouin de Menibus, Victor H. Lutfalla, Camille Noûs	The Domino problem is undecidable on every rhombus subshift.	CoRR	2023	DBLP DOI BibTeX RDF
18	Christopher J. Eagle, Clovis Hamel, Sandra Müller, Franklin D. Tall	An undecidable extension of Morley's theorem on the number of countable models.	Ann. Pure Appl. Log.	2023	DBLP DOI BibTeX RDF
18	Rachel Greenfeld, Terence Tao	Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile.	Discret. Comput. Geom.	2023	DBLP DOI BibTeX RDF
18	Arkadiy Skopenkov	Extendability of Simplicial Maps is Undecidable.	Discret. Comput. Geom.	2023	DBLP DOI BibTeX RDF
18	Laura Kovács, Anton Varonka	What Else is Undecidable About Loops?	RAMiCS	2023	DBLP DOI BibTeX RDF
18	Benjamin Hellouin de Menibus, Victor H. Lutfalla, Camille Noûs	The Domino Problem Is Undecidable on Every Rhombus Subshift.	DLT	2023	DBLP DOI BibTeX RDF
18	Jonathan Geller	Baba is You is Undecidable.	CoG	2023	DBLP DOI BibTeX RDF
18	Steve Hanneke, Liu Yang 0001	Bandit Learnability can be Undecidable.	COLT	2023	DBLP BibTeX RDF
18	Alessandro Artale, Anton R. Gnatenko, Vladislav Ryzhikov, Michael Zakharyaschev	A Decidable Temporal DL-Lite Logic with Undecidable First-Order and Datalog-rewritability of Ontology-Mediated Atomic Queries (Extended Abstract).	Description Logics	2023	DBLP BibTeX RDF
18	Mnacho Echenim, Radu Iosif, Nicolas Peltier	Entailment is Undecidable for Symbolic Heap Separation Logic Formulæ with Non-Established Inductive Rules.	Inf. Process. Lett.	2022	DBLP DOI BibTeX RDF
18	Zlatan Damnjanovic	Mutual Interpretability of Weak Essentially Undecidable Theories.	J. Symb. Log.	2022	DBLP DOI BibTeX RDF
18	Nikolaos Galatos, Gavin St. John	Most Simple Extensions of FLe are Undecidable.	J. Symb. Log.	2022	DBLP DOI BibTeX RDF
18	Andreas Klingler, Mirte van der Eyden, Sebastian Stengele, Tobias Reinhart, Gemma De las Cuevas	Many bounded versions of undecidable problems are NP-hard.	CoRR	2022	DBLP DOI BibTeX RDF
18	Pedro Filipe, Carlos Caleiro, Sérgio Marcelino	Monadicity of Non-deterministic Logical Matrices is Undecidable.	NCL	2022	DBLP DOI BibTeX RDF
18	Maurice Margenstern	The domino problem of the hyperbolic plane is undecidable, new proof.	CoRR	2022	DBLP DOI BibTeX RDF
18	Matthieu Rosenfeld	It is undecidable whether the growth rate of a given bilinear system is 1.	CoRR	2022	DBLP BibTeX RDF
18	Jonathan Geller	Baba is You is Undecidable.	CoRR	2022	DBLP DOI BibTeX RDF
18	Lawrence C. Paulson	Wetzel: Formalisation of an Undecidable Problem Linked to the Continuum Hypothesis.	CoRR	2022	DBLP DOI BibTeX RDF
18	Hugo Gimbert	Distributed Asynchronous Games With Causal Memory are Undecidable.	Log. Methods Comput. Sci.	2022	DBLP DOI BibTeX RDF
18	Juvenal Murwanashyaka	Weak essentially undecidable theories of concatenation.	Arch. Math. Log.	2022	DBLP DOI BibTeX RDF
18	Amirfarhad Nilizadeh, Gary T. Leavens	Be Realistic: Automated Program Repair is a Combination of Undecidable Problems.	APR@ICSE	2022	DBLP DOI BibTeX RDF
18	Fabian Mitterwallner, Aart Middeldorp	Polynomial Termination Over ℕ Is Undecidable.	FSCD	2022	DBLP DOI BibTeX RDF
18	Lawrence C. Paulson	Wetzel: Formalisation of an Undecidable Problem Linked to the Continuum Hypothesis.	CICM	2022	DBLP DOI BibTeX RDF
18	Stepan L. Kuznetsov	Action Logic is Undecidable.	ACM Trans. Comput. Log.	2021	DBLP DOI BibTeX RDF
18	Hugo Gimbert	Distributed Asynchronous Games With Causal Memory are Undecidable.	CoRR	2021	DBLP BibTeX RDF
18	Martin Kolár	On formally undecidable propositions in nondeterministic languages.	CoRR	2021	DBLP BibTeX RDF
18	Honghao Fu, Carl A. Miller, William Slofstra	The membership problem for constant-sized quantum correlations is undecidable.	CoRR	2021	DBLP BibTeX RDF
18	Benedikt T. Boenninghoff, Robert M. Nickel, Dorothea Kolossa	O2D2: Out-Of-Distribution Detector to Capture Undecidable Trials in Authorship Verification.	CoRR	2021	DBLP BibTeX RDF
18	Manuel Bodirsky, Simon Knäuer, Jakub Rydval	Amalgamation is Undecidable.	CoRR	2021	DBLP BibTeX RDF
18	Erik Parmann, Thomas Ågotnes	Reasoning about strategic voting in modal logic quickly becomes undecidable.	J. Log. Comput.	2021	DBLP DOI BibTeX RDF
18	M. Clarence Protin	Type inhabitation of atomic polymorphism is undecidable.	J. Log. Comput.	2021	DBLP DOI BibTeX RDF
18	Tobias Fritz	Quantum logic is undecidable.	Arch. Math. Log.	2021	DBLP DOI BibTeX RDF