# Questions tagged [terminology]

questions about definitions, terms, and common names in theoretical computer science.

95 questions
Filter by
Sorted by
Tagged with
79 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 ...
46 views

481 views

### Complexity of blind sort?

We all know that the minimal complexity of a comparison-based sorting algorithm is $\Omega(n \log n)$ comparisons. I'm trying to do a blind sort, i.e. given a number $n$ output a circuit (with boolean,...
2k views

### Why is lambda calculus a "calculus"?

The only definition of "calculus" I'm aware of is the study of limits, derivatives, integrals, etc. in analysis. In what sense is lambda calculus (or things like mu calculus) a "calculus"? How does it ...
111 views

### How to say "select the largest" when there can be more than one [closed]

Many algorithms include a step such as "select the largest number from a given numeric array", or "select the leftmost point from a given set of points", etc. In many cases, it is possible that the ...
837 views

### what is "one-to-one reduction from a function f to another function g"

I am reading a paper called "Rational Proof". It mentioned the following one-to-one reduction. I cannot google an introduction of it. An excerpt from the paper. "Recall that a one-to-one reduction ...
233 views

### Typing relations terminology – how do I read typing relations?

I am currently trying to read up on type theory and have some quick questions on terminology. In the following rule, $$\frac{x:T_1 \vdash t_2 : T_2}{\vdash \lambda x:T_1.t_2:T_1\to T_2}$$ How ...
2k views

### How can a problem be in NP, be NP-hard and not NP-complete?

For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP. However, in the famous paper "The ellipsoid method and its consequences in ...
4k views

### Is propositional resolution a complete proof system?

This question is about propositional logic and all occurrences of "resolution" should be read as "propositional resolution". This question is something extremely basic but it has been bothering me ...
1k views

### Equivalent definitions of time constructibility

We say that a function $f:\mathbb{N}\rightarrow\mathbb{N}$ is time-constructible, if there exists a deterministic multi-tape Turing machine $M$ that on all inputs of length $n$ makes at most $f(n)$ ...
198 views

### Labels for terms in the lambda calculus

In the lambda calculus, are there commonly accepted names for $x$ and $M$ when they appear in $\lambda x [M]$ ? Something along the lines of "binder" and "bindee"?
593 views

### Why is combinational logic called so?

What is the significance of the word "combinational" in combinational logic?
710 views

### Why are perfect graphs called perfect?

Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is ...
1 vote