Questions about how specific notions have to be understood as well as conventions of notation.

learn more… | top users | synonyms

0
votes
1answer
19 views

Are neural networks dynamical systems?

Dynamical systems are those whose evolution can be described by a rule, evolves with time and is deterministic. In this context can I say that Neural networks have a rule of evolution which is the ...
-1
votes
0answers
18 views

What is a productive set of all natural numbers

I'm trying to come up with a recursive language with a non-recursive subset. Many if not all of the examples I've found describe all natural numbers as recursively enumerable and their productive set ...
1
vote
2answers
64 views

What is the term for this set

I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set? A common practical use case would be ...
3
votes
1answer
60 views

Conceptual question about entropy and information

Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
2
votes
1answer
38 views

Is there a limit on the length of queries for the oracle?

Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My ...
5
votes
1answer
44 views

What is $Prop$ in the calculus of constructions?

I'm looking at the Calculus of Constructions and its place in the Lambda Cube. If I understand correctly, each axis of the cube can be thought of as adding another operation involving types to the ...
7
votes
2answers
100 views

Combinatory interpretation of lambda calculus

According to Peter Selinger, The Lambda Calculus is Algebraic (PDF). Early in this article he says: The combinatory interpretation of the lambda calculus is known to be imperfect, because it ...
2
votes
0answers
27 views

What is a semantic cognitive map

Based on: J. P. Carvalho, "On the Semantics and the Use of Fuzzy Cognitive Maps in Social Sciences" (WCCI, 2010 -- PDF) and Richard Dagan's web page Cognitive Mapping. A cognitive map consists of ...
5
votes
1answer
55 views

Difference between hypervisor and exokernel

An hypervisor (1st type) is a software that creates and run virtual machines, managing guest's operative systems's requests to the hardware. An exokernel is an operative system kernel, that let's ...
2
votes
1answer
58 views

Use of Big-O Notation: Size of Input vs Input

It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size ...
-2
votes
1answer
33 views

Generative grammars and analytic grammars?

What are a generative grammar and an analytic grammar? How are they different from a formal grammar? Is the recursive definition of the language of a propositional calculus, a first order logic ...
0
votes
1answer
48 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), ...
0
votes
0answers
44 views

What are the formal grammars of the following recursively-defined formal languages [closed]

In a propositional calculus, a first order logic system, or the set of lambda expressions, its formal languages is defined recursively. It starts with some strings in such a language, and then ...
1
vote
1answer
72 views

recursive lambda expressions

From http://www.seas.gwu.edu/~rhyspj/spring09cs145/lab8/lab82.html The lambda operator does not bind every occurrence of its variable because "shadowing" can occur. A variable is bound by its ...
0
votes
0answers
5 views

How to talk about caching [migrated]

I hope all is well. In your experience, which is most grammatical? It's still cached to your phone. It's still cached in your phone. It's still cached on your phone. I find myself gravitating ...
1
vote
1answer
28 views

Is random access allowed in the Bit Complexity model, or is it just expensive?

In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word). In the Bit Complexity model (no wiki article, sorry), ...
1
vote
3answers
82 views

Additional clarification about Simultaneous Multithreading

I was looking for comments about SMT and got several responses. The last one looks strange: Simultaneous multithreading, which can only be implemented on a multicore system, executes the ...
1
vote
3answers
86 views

What exactly is computer science? [duplicate]

I have a question that, no matter how much I think about, I do not have the answer to. The question is what exactly is computer science? The reason I am asking is that I went into college thinking ...
-1
votes
2answers
57 views

What is theory behind graphs relations? [closed]

I have been trying to understand, what is the actual meaning of 2 graphs being: Symmetric Transitive Reflexive A graph being a subgraph of another graph And ...
1
vote
0answers
20 views

Difference between cognitive map, semantic network and ontology

Cognitive maps represent mental models which have connections between concepts that represent entities, goals. Ontologies represent vocabularies for knowledge representation. It explains the semantics ...
5
votes
1answer
60 views

Inconsistent state of a lock

I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to ...
1
vote
1answer
36 views

In an M/M/1 Queue, what does exponential distribution of service time mean?

I was reading about the M/M/1 Queue and that we assume new customers arrive according to a Poisson distribution, and each customer takes an amount of time to ...
3
votes
3answers
85 views

Correct term for “string consisting of words”

In a paper I am writing I want to make distinction between (1) string consisting of any characters and (2) string consisting of a chain of words from known language, with possible delimiters. My ...
1
vote
0answers
22 views

What is the difference between “objective function”, “error function”, “criterion function” and “cost function” in the context of neural networks?

The title says it all: I have seen three functions so far, that seem to be the same / similar: error function criterion function cost function objective function I am currently working on ...
3
votes
2answers
81 views

Composition of combinators with arities greater than one

In combinatory logic, the axiom of composibility asserts that for any two combinators, $A$ and $B$, there exists a combinator $C$ that composes $A$ and $B$. That is, for all $A,B,x$ there exists a ...
1
vote
1answer
61 views

What does it mean for a function to be decidable? (homework)

Note: This is part of a homework exercise. I am asking for clarifications, not a solution! Given: Assume $g: \mathbb{N} \mapsto \mathbb{N}, g\in R$ ($R$ is the class of recursive functions) is a ...
0
votes
1answer
31 views

Name for almost random memory distribution on the heap

If I had a heap like the following: with blue blocks being occupied memory and white blocks being free memory What is the general name given to the situation illustrated, where the free and ...
3
votes
2answers
93 views

Correspondence between automata and formal grammars?

From Wikipedia Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string ...
0
votes
0answers
18 views

Clarification of the difference between join and composition of relational algebra

Hi i am statistics major student with limited mathematics knowledge. I would like to know the difference between join and composition of relations. My understanding from the reference book: Sets, ...
3
votes
2answers
90 views

Are there any CS-trees named after flora-trees?

This is meant to be a fun question, and I hope it's not too off topic. Is there a defined mathematical object or data structure that has a name collision with a type of physical tree in the real ...
1
vote
1answer
41 views

What is the difference between symbol recognition, classification and identification?

I've just wondered if there is a difference between symbol recognition, classification and identification. What would you use when you have a hand-written symbol and you want to get the LaTeX code ...
1
vote
3answers
106 views

What happens with trios, full trio, (full) semi-AFL, (full) AFL if we require closure under intersection?

Wikipedia says: A trio is a family of languages closed under e-free homomorphism, inverse homomorphism, and intersection with regular language. A full trio, also called a cone, is a trio ...
1
vote
2answers
55 views

Question about the definition of complexity class oracles

If $B$ is a complexity class, then the class $P^B$ (for example) is defined as the set of problems that can be run in polynomial time, given an oracle to every problem in $B$. That's what they told ...
0
votes
1answer
91 views

What does “finite state transduction” mean?

Wikipedia says, the regular languages are closed under arbitrary finite state transductions, like quotient K / L with a regular language. I wonder what kinds of operations "finite state ...
2
votes
1answer
62 views

Describe a TM through denotation of the transition function

I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language $$ L ={\{w\#w} \mid w \in {\{0,1}\}^*\} $$ over the input alphabet: $$ ...
1
vote
1answer
63 views

Formal language inverse

How can you specify the "inverse" of a word, so: let's say a word consists of a's and b's the language is: $ww^{-1}$ the second word is the same as the first but every a is replaced by b and every b ...
1
vote
2answers
99 views

Syntax and formal grammar of a formal language

For a formal language, I wonder what differences and relations are between its syntax and its formal grammar. A formal grammar is a set of formation rules that describe how to generate the strings ...
6
votes
5answers
131 views

What does apostrophe-like symbol in the superscript mean?

It's hard to look up the meaning of a symbol if you don't know what it is called in the context that it is written. That apostrophe-type symbol in the sequence notation - what is that?
0
votes
1answer
28 views

Is everything in CS either a numeric method or a symbolic method?

Or maybe also a combination of the two, but not something else, whether numeric, nor symbolic. Do they cover the whole field?
3
votes
1answer
154 views

Name for this algorithm?

I'm trying to figure out if there is a proper or commonly accepted name for this particular function (f). ...
2
votes
1answer
288 views

Consistency and completeness imply soundness?

I understand that soundness implies consistency. Also, I understand that consistency alone does not imply soundness. But shouldn't consistency + completeness imply soundness? Scott Aaronson in his ...
1
vote
3answers
62 views

NP-completeness: Reduce to or reduce from?

Very simple question, but a mistake I make often enough that I'd love to have a standard reference. I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve ...
4
votes
1answer
58 views

NFAs with more than one initial state

I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it ...
3
votes
3answers
305 views

Can't understand why the DP Subset Sum algorithm is not polynomial

I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial. Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the ...
7
votes
2answers
123 views

Is there a canonical definition of “pure” function?

StackOverflow pointed me here, so the question might be a bit in a layman's terms. Wikipedia defines pure functions as In computer programming, a function may be described as a pure function if ...
1
vote
1answer
58 views

Definition of “c-competitive” algorithm

What is the definition of a "c-competitive" algorithm? For example what does it mean, if we say that there is a 2-competitive algorithm for packet routing?
0
votes
2answers
40 views

Automata with no transition for some character

Given an automaton and an alphabet $\{a, b\} $, and the language accepted by the automaton is $ab^*$. Such an automata can be found here: My question is: this automaton cannot process the word ...
2
votes
2answers
152 views

Don't understand this graph definition

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows: Given a graph $G= \langle V_G, E_G ...
0
votes
1answer
28 views

What does “finding an optimal action” for a bandit mean?

In Sutton and Barto's reinforcement learning book, in multi-armed bandit problem a phrase has been used. "finding an optimal action" using greedy/$\epsilon$-greedy algorithm. When it is said that an ...
3
votes
0answers
32 views

Is there a term for the common semantics of global variables, static local variables, and fields?

I'm working on a graph representation of software for a static analysis project, and I'm finding a distinction that I have no name for between different types of variables. On one side of the ...