TSO-to-TSO linearizability is undecidable
0
Citation
23
Reference
10
Related Paper
Keywords:
Undecidable problem
Linearizability
Theory of computation
Undecidable problem
Linearizability
Theory of computation
Cite
Citations (0)
Undecidable problem
Linearizability
Cite
Citations (5)
Weakly well-designed SPARQL patterns is a recent generalisation of well-designed patterns, which preserve good computational properties but also capture almost all patterns that appear in practice. Subsumption is one of static analysis problems for SPARQL, along with equivalence and containment. In this paper we show that subsumption is undecidable for weakly well-designed patterns, which is in stark contrast to well-designed patterns, and to equivalence and containment.
Undecidable problem
Containment (computer programming)
Named graph
Cite
Citations (0)
Undecidable problem
Halting problem
Cite
Citations (4)
Weakly well-designed SPARQL patterns is a recent generalisation of well-designed patterns, which preserve good computational properties but also capture almost all patterns that appear in practice. Subsumption is one of static analysis problems for SPARQL, along with equivalence and containment. In this paper we show that subsumption is undecidable for weakly well-designed patterns, which is in stark contrast to well-designed patterns, and to equivalence and containment.
Undecidable problem
Named graph
Containment (computer programming)
Cite
Citations (0)
Undecidable problem
Line (geometry)
Cite
Citations (0)
Undecidable problem
Theory of computation
Constant (computer programming)
Recurrence relation
Cite
Citations (0)
The infinite Post Correspondence Problem (ωPCP) was shown to be undecidable by Ruohonen (1985) in general. Blondel and Canterini [Theory Comput. Syst. 36 (2003) 231–245] showed that ωPCP is undecidable for domain alphabets of size 105, Halava and Harju [RAIRO–Theor. Inf. Appl. 40 (2006) 551–557] showed that ωPCP is undecidable for domain alphabets of size 9. By designing a special coding, we delete a letter from Halava and Harju's construction. So we prove that ωPCP is undecidable for domain alphabets of size 8.
Undecidable problem
Cite
Citations (8)
Linearizability
Undecidable problem
Cite
Citations (4)
Abstract In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets.
Undecidable problem
Halting problem
Cite
Citations (40)