Tag Info

New answers tagged

2

There are many research areas both in the theory and practice of distributed databases. One of the main practical challenges is that of implementing efficient concurrency control mechanisms for distributed and geo-replicated databases. In order to execute transactions efficiently, such mechanisms can provide weaker guarantees than serialisability, which ...


-1

To prove that it is in NP, suppose we know the order in which dots are removed, and the position of the snake at these moments. Then we need only show that the snake needs only a polynomial number of moves in between the removal of two consecutive dots. If the snake has length $l$, then within $l$ moves, either all of the snakes original nodes will be empty ...


2

The first theorem of the form you are asking about was proved by Y. Moschovakis in Notation systems and recursive ordered fields, Compositio Mathematica 17:40–71 (1965). Then in the context of Type Two Effectivity a similar theorem was proved by P. Hertling, see A real number structure that is effectively categorical, Mathematical Logic Quarterly, ...


3

To turn my comment into an answer... Andrej Bauer in this post makes the parenthetical claim An important theorem states that any two representations of reals which are acceptable are actually computably isomorphic. He never explicitly defines acceptable or cites the theorem. I assume the OPs question is the following. What theorem is Andrej Bauer ...


2

No, it is undecidable. Imagine a TM that outputs a sequence $0.1111\ldots$ that may be finite or not. If it is finite, the conversion algorithm should give some fraction like $\frac{11\ldots11}{10\ldots000}$. If it is infinite (the TM doesn't halt) then the output should be $\frac{1}{9}$. Any program that converts between the $TM$ representation of a number ...


1

There is a nice software which generates small planar graphs with respect to isomorphism which might help. As I see one of the problem was to generate non-isomorphic planar graphs and most of those planar graphs (on less than 15 vertices) are of small treewidth. For checking whether their treewidth is smaller than given value $k$, one way is to use ...


4

I assume you've looked online, though I'd be amazed if a 1980s master's thesis was online. Ask one of the authors: they should have read the thesis before citing it, which suggests that at least one of them has access to a copy or, at least, had access at the time they wrote the paper. If that fails, try asking your university library. Also, although the ...


1

This thread is old and OP's question has been answered but I'd like to add another algorithm to find all such pairs in linear time. Nobody mentioned Partition Refinement! This algorithm finds the equivalence classes of false twins. The algorithm relies on an efficient procedure that refines a partition. Given a set S and a partition P = {X1, ..., Xn}. ...


1

One can enumerate all pairs $G,B$ where $G$ is a planar graph with treewidth at most $k$, $B$ is a bag of size $k$ such that there exist a tree-decomposition of $G$ with $B$ as a bag. Now for every pair $G,B$ where $G$ has $n-1$ vertices we build a new graph $G'$ for every subset $S$ of $B$ by adding a vertex $v$ with $S$ as neighbours and let $B'$ be a ...


6

The following book covers some material related to the proof of the graph minor theorem (Chapter 12). Reinhard Diestel: Graph Theory, 4th edition, Graduate Texts in Mathematics 173. The author states: "[...] we have to be modest: of the actual proof of the minor theorem, this chapter will convey only a very rough impression. However, as with most truly ...


3

I realized that in Fischer, Meyer, and Rosenberg (1968) Theorem 1.3, it is proven that "The language of marked palindrome is not recognizable by any one-way $k-CM$ which operates in time less than $T(n) = 2^{(n/2k)}$." The same result also appears in Petersen (2009).


9

There is a new preprint by Stephan Kreutzer and Ken-ichi Kawarabayashi, in which they apparently show that the statement (5.1) is true for all digraphs. Stephan Kreutzer and Ken-ichi Kawarabayashi: The directed grid theorem. arXiv:1411.5681 [cs.DM]


2

What about the 1999 classical (first?) book on the topic by Rod Downey and Mike Fellows? Two years ago, I heard that Rod and Mike were going to bring out a second edition of their book -- may be it is out now. Mike's website http://www.mrfellows.net should have more info. You can sign up for his mailing list (newsletter) which comes out every 2-3 months.


4

For question (2): the subgraph and induced subgraph relations give rise to well quasi orders on some restricted classes of graphs. One of the main references there is an article by G. Ding, Subgraphs and well-quasi-ordering, J. Graph Theory, 16: 489–502, 1992, doi:10.1002/jgt.3190160509. The paper shows that both orderings yield wqos on the class of ...


2

For what concerns the use of non-flat domains, babou already gave examples. I can add that sometimes it may even be useful to see integers as streams: there's ⊥, above which there are 0 and S⊥, above the latter there are S0 and SS⊥, and so on. I know that in the early 90s Loïc Colson worked on models using the above interpretation of integers, although I ...


3

A partial answer to the second question: exponential lower bounds for explicit functions for any class that contains 3-CNF do not translate into exponential lower bounds for unlimited nondeterminism, because one can transform any circuit of size $S$ into a nondeterministic 3-CNF of size $O(S)$ with non-determinism $S$, even if you want non-determinism less ...


4

With only flat domains, you cannot define limits to construct "infinite" structures, such as looping structures, for data or for programs. Fixpoint constructions in denotational semantics (since you used that tag) use non flat domains. Maybe you should give examples of domains that are taken as flat, while it would be better to do differently. Many problems ...


6

No, it is not decidable. A good heuristic to answer such questions is the following: every computable map is continuous. If you could decide whether $f(x) = 0$ for all $x \in \mathbb{C}$, then the characteristic map $d$ of such a decision procedure, namely $$d : f \mapsto \begin{cases} 1 & \text{if $\forall x \in \mathbb{C} . f(x) = 0$}\\ 0 & ...


2

Another model possibly to explore, is that of the Feasible RAM model. This is a modified real RAM model for Real computation, Feasible RAM, or a modified RAM model which uses both the discrete, and real valued arithmetic operations. This model allows for real, and discrete operations, and the Turing model, is interchangeable with it. The Feasible RAM model ...



Top 50 recent answers are included