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 ...
- 27.5k
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 ...
- 23.9k
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)$...
- 18.1k
9
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 ...
- 18.1k
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,742
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 ...
- 32.1k
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.
...
- 161
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 ...
- 36.3k
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
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 ...
- 972
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.
- 21
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,560
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.
- 19
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.2k
Only top scored, non community-wiki answers of a minimum length are eligible