11 votes
Accepted

Standard reference for basic model theory definitions

Here is one possibility, but other people might use different words. I will use first-order logic as a running example. Language The language is a collection of expressions, which are syntactic ...
  • 26.8k
10 votes
Accepted

Why is differential privacy defined over the exponential function?

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties: Composition: If $A(\cdot)$...
10 votes
Accepted

Are there two definitions of Cobham's thesis?

Cobham's thesis is essentially the Extended Church-Turing thesis. Historians of computer science have gone back and figured out who first proposed it, and attached his name to it. What Cobham was ...
8 votes

Definition of near-linear algorithm

A natural definition of "near-linear" should be: A function $f:\mathbb{N}\to\mathbb{N}$ is near-linear, if $~f(n)\in O(n^{1+\varepsilon})~$ for all $\varepsilon>0$.
  • 5,732
8 votes
Accepted

On the notion of positive rank of a matrix

There are examples of $n\times n$ real matrices of rank at most $3$ and non-negative rank at least $\sqrt{2n}$. So the non-negative rank cannot be bounded by any function of the rank in general. The ...
7 votes
Accepted

Precise definition of syntatic categories / syntatic domains in abstract syntax

Most people avoid giving precise descriptions of what a syntactic category is, because if you do it properly with all the details, the ratio of insight to necessary mathematical sophistication ends up ...
6 votes

The theory of definitions in first order logic

I don't have the books handy at the moment, but I think Shoenfield's "Mathematical Logic" and Hinman's "Fundamentals of Mathemtical Logic" would contain much if not all of what you're looking for. ...
6 votes
Accepted

What are different definitions of Universal Turing-machine?

I found some alternate definitions of Universal Turing Machine in papers related to the universality of small Turing machines and other models. See for example the four definitions (the first 3 are ...
5 votes
Accepted

Reductions weaker than polynomial-time for $\exists \mathbb{R}$

I would argue that the main issue with using many-one $\mathrm{NP}$-reduction to define completeness is that $\exists\mathbb{R}$-hardness under many-one $\mathrm{NP}$ reductions no longer implies $\...
  • 131
5 votes

Kolmogorov Complexity of a Decidable Language

Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^* KCDL(L_x)$, where $L_x$ is the language which consists only of the string $x$, and $=^*$ means equals up to an additive ...
4 votes

Precise definition of syntatic categories / syntatic domains in abstract syntax

I never found an explicit definition either, but I have inferred the folowing. As I understand, you split the language into syntactic domains; with the addition that syntactic domains must be fully ...
  • 962
2 votes

What are "unranked trees"?

You are Right if the Computing Power for XSD schema is free or freely available (Soft). Otherwise, it will be Hard.
2 votes
Accepted

Definition of k-set cover

The second definition uses the hitting set formulation, which is equivalent to the set cover problem. To see that, you may reverse the roles of sets and elements. You can find more information on the ...
  • 2,530
1 vote
Accepted

What is a "Covering Function"?

I finally found an answer here. @MaxNew was right; it's just a part of totality. A function definition is not covering if there is a possible input which has not been handled in the pattern matching.
1 vote

Are DOF and Entropy directly related?

Your question is really about the relationship between entropy and capacity. Let's define the latter as the total number of possible states. The former is defined, on any finite distribution $P=(p_1,...
  • 10.1k

Only top scored, non community-wiki answers of a minimum length are eligible