11

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 entities, i.e., finite configurations without any a priori meaning. A language is described by the grammar, which determines which finite configurations are valid ...


9

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)$ is an $\varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(\cdot, a)$ is an $\varepsilon'$-DP algorithm, then the composed algorithm $A' \circ ...


8

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 construction I am aware of goes through extension complexity. An explanation follows. The extension complexity $xc(K)$ of a convex set $K$ in $\mathbb{R}^d$ is ...


7

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 being very, very low. John Reynolds' book Theories of Programming Languages has one of the more comprehensive explanations in its chapter 1, as does Robert ...


6

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. Probably not what you want but perhaps worth mentioning anyway is A. P. Morse's book "A Theory of Sets". This is a development of (a rather idiosyncratic version ...


6

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 equivalent and are similar to yours except that there there is also an explicit decoding function) in section 2 of Yurii Rogozhin, Small universal Turing ...


5

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 constant. The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be ...


5

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$.


4

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 generated by single different symbols, when you write down the grammar. So a syntactic domain is a subset of your language, and each domain is generated by one ...


2

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


2

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 wikipedia page.


1

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,p_2,\ldots,p_n)$, by $$ H(P) = \sum_{i=1}^n p_i\log(1/p_i).$$ When the distribution is uniform (i.e., $p_i\equiv1/n$), $H(P)=\log(n)$; this is the maximal value ...


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