Use this tag whenever you have a question about what some particular symbol/notation means.

learn more… | top users | synonyms

4
votes
1answer
29 views

Determining Number of States in a Turing Machine

I am looking at an example Turing machine in my textbook, Automata and Computability by Dexter C. Kozen, and I'm confused as to how they determine the number of states this particular machine has. ...
0
votes
1answer
13 views

Principles of Programming Languages: Understanding Judgements

I am taking a principles of programming languages class right now and am trying to understand the following judgement form. ...
6
votes
1answer
56 views

Use of Big O Notation in a recent paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
2
votes
1answer
89 views

Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
3
votes
2answers
61 views

Origins of misconception about using equality signs with Landau notation

From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other ...
1
vote
1answer
31 views

What does superscript + mean in relational algebra?

What does superscript + mean in relational algebra? Suppose $A$ is a subset of attributes of all attributes in a relation $R$. What does $A^+$ mean?
4
votes
1answer
51 views

In type systems, is there a name for SQL's way of cutting and combining record types into new types?

I'd like to have this feature in my application programming language (which these days, is Scala), but when I went to learn more about it on the internets, I realized I don't know the name of it. I'm ...
3
votes
1answer
82 views

Notation for average case complexity of an algorithm

I'm just wondering what the correct notation is when referring to an average case complexity of an algorithm that was calculated by doing empirical analysis. For example, I have tested my algorithm ...
0
votes
0answers
26 views

What are these notations O(1)/O(n)/O(log n)? [duplicate]

I am a newbie here I recently read tutorials on java about collection framework. The time complexity of various objects in reading/writing data What does it mean? ...
1
vote
0answers
64 views

Correct mapping “update” notation for computer science papers

A nice easy one. I'm interested to know the most standard and accepted way to denote the update of a mapping in the context of a theoretical computer science paper. By example, suppose we have a ...
2
votes
1answer
233 views

What does the R superscript notation mean in regular/formal languages?

What does the capital R superscript notation mean in regular languages? I am working on a homework assignment and don't recall my professor mentioning what the what the R superscript means. For ...
3
votes
2answers
258 views

What type of formal notation is being used here to represent functional algorithms?

Interested in learning more about algorithm design in functional programming, I picked up Andrew Bird's Pearls of Functional Algorithm Design. I have experience with a number of programming ...
5
votes
2answers
113 views

Numeral systems other than unary used in nature or in animal and human behaviours

Representing numeric values using positional notation is one of the milestones in the history of arithmetic. Babylons used a base 60 system, Maya a base 20 system; base 10 system became "the standard" ...