Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [definitions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
56 views

What is Shutt abstractiveness?

In software development, there is a pre-formal notion of abstraction. Several attempts have been made to formalize it. In particular, what is Shutt abstraction, or Shutt abstractiveness, and how does ...
Corbin's user avatar
  • 271
2 votes
1 answer
77 views

What Pure Type Systems have dependent types

What precisely are dependent types? Is it a syntactic property of some type system? This seems to suggest that dependent types are defined through phase distinctions. For example, if a variable is ...
Trebor's user avatar
  • 345
2 votes
0 answers
182 views

Semi-Thue systems and deterministic computation

I would like to use semi-Thue systems (a.k.a. string rewriting systems) to study complexity theory formally. Note that "semi-" in the name means "unidirectional [Thue system]". ...
Martin Dvorak's user avatar
0 votes
0 answers
56 views

Restrictions on set of infinitely many n's for which an algorithm breaks distributional hardness

Say we want to capture the notion that an efficiently samplable distribution $D(1^n)$ is hard with respect to some boolean function $f$ for a decision problem or some efficient relation $R$ for a ...
Nathan's user avatar
  • 179
1 vote
0 answers
138 views

Definition in some old paper about formal power series (automata theory) Part 2

I now know that $K \langle A \rangle$ is the set of all formal power series with finite support for some alphabet $A$ and field $K$. Now I have another question. Later this expression comes up $\...
Tim567's user avatar
  • 11
0 votes
0 answers
80 views

Definition in some old paper about formal power series (automata theory)

I have a question about a term in a paper about formal power series. It was never defined but the author used $K \langle A \rangle$, what set is $K \langle A \rangle$? Here $K$ is a field (commutative ...
Tim's user avatar
  • 1
0 votes
0 answers
124 views

Can an NP-search problem be defined non-constructively?

Given a random two-to-one function $f(x)$ from $n$ bits to $n$ bits, consider the following search problem: Find a polynomial number of pairs $(d,y)\in \{0,1\}^n\times\{0,1\}^n$ with $d\ne \bf 0$ ...
Mark S's user avatar
  • 1,125
0 votes
1 answer
353 views

What is a "Covering Function"?

In Idris2, I will sometimes get an error telling me that a function "is not covering", which is apparently distinct from it not being total (and I do understand what a total function is). I ...
MCLooyverse's user avatar
6 votes
1 answer
195 views

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

I am currently studying the complexity class $\exists \mathbb{R}$ which contains all problems that are reducible in polynomial time to the existential theory of the reals. In the literature ...
sebastian's user avatar
  • 173
0 votes
0 answers
160 views

Is the following graph an expander graph?

Let's say we have the following bipartite-graph, denoted $G=(L,R,E)$: It has the following adjacency matrix: I am having problems decoding a received word from what I was told is an expander code ...
Louie_the_unsolver's user avatar
3 votes
1 answer
399 views

Are there two definitions of Cobham's thesis?

In wikipedia, Cobham's thesis (or Cobham-Edmonds thesis) states: computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time So ...
user777's user avatar
  • 171
5 votes
1 answer
262 views

Kolmogorov Complexity of a Decidable Language

The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable ...
Raphael Augusto's user avatar
4 votes
1 answer
264 views

Why is differential privacy defined over the exponential function?

For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies $$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ ...
user9414424's user avatar
4 votes
1 answer
231 views

The theory of definitions in first order logic

I'm looking for a clear and thorough treatment of the theory of definitions in first order predicate logic from a syntactic/proof theoretic point of view (as opposed to semantic/model theoretic point ...
Evan Aad's user avatar
  • 354
4 votes
1 answer
317 views

What are "unranked trees"?

Recently I have some dispute with my colleagues and would like to clarify the following question. It is clear what are "ranked" trees. They are those, which produced by tree grammars, where each ...
Andrey Lebedev's user avatar
0 votes
1 answer
1k views

Definition of k-set cover

I'm trying to understand the sparsification lemma by Impagliazzo, Paturi and Zane (IPZ) (from this article) and in their proof they reduce the k-SAT problem to the k-set cover problem. But their ...
AstridNeu's user avatar
-3 votes
1 answer
127 views

Are DOF and Entropy directly related? [closed]

I found this definition of Entropy: Entropy measures the amount of random variation in a population. This means it measures the number of different states possible and the probability ...
4ndro1d's user avatar
  • 95
4 votes
1 answer
2k views

Definition of near-linear algorithm

There are quite a lot papers describing near-linear algorithms. They are usually iterative, with linear complexity of one iteration. Others have $O(n\log^k n)$ time compexity. I'm failed to find a ...
ov7a's user avatar
  • 141
6 votes
1 answer
356 views

Standard reference for basic model theory definitions

I am trying to give a formal presentation of the model-theoretical semantics of a language and I am a bit lost in the terminology. In particular, could somebody clarify the exact definitions of model-...
AnaK's user avatar
  • 203
8 votes
2 answers
489 views

Precise definition of syntatic categories / syntatic domains in abstract syntax

I have read the introductory parts of a couple of books on programming language semantics (Gordon, Winskel, Nielson & Nielson, Allison, Stump, Schmidt), and while I do understand what they mean by ...
josh's user avatar
  • 235
5 votes
0 answers
84 views

What is the difference between an Ontology and Knowledge Representation (KR)?

From my understanding an Ontology is a description of how a real object can be understood or represented (such as a chair being a collection of atoms, a piece of furniture part of a larger collection ...
P H Kaznowski's user avatar
5 votes
1 answer
488 views

On the notion of positive rank of a matrix

The positive rank of a square matrix is defined in Theorem $3$ of "Expressing Combinatorial Optimization Problems by Linear Programs" by Mihalis Yannakakis as follows: given a $n\times n$ matrix $A$, ...
Turbo's user avatar
  • 12.9k
2 votes
1 answer
332 views

What are different definitions of Universal Turing-machine?

I am not sure what is the appropriate way for this, but I would like to collect different possible definitions/variants of Universal Turing-machines. Here are the ones I know, post below if you know ...
domotorp's user avatar
  • 14k