Questions tagged [theory]
The theory tag has no summary.
65 questions
10
votes
2
answers
3k
views
Is there a theory around reverse computing?
I'm trying to find a way to compute the set of inputs that lead to a specific output given an expression.
For example, if you take the expression :
...
- 203
3
votes
2
answers
1k
views
Does concatenating a language with Σ* always result in the universal language?
I'm trying to understand how language concatenation works with the universal language (i.e., Σ*). Suppose I have a language like L = {aⁿ}, and I concatenate it with the universal language. For example:...
- 91
2
votes
2
answers
161
views
What is a formal distinction between language feature and library feature, and does such distinction apply to any programming language?
What is a formal distinction between language feature and library feature, and does such distinction apply to any programming language?
In C++, Haskell, and other languages I'm more familiar with:
If ...
- 137
0
votes
1
answer
140
views
Efficiently Merging Sorted (Key, Value) Lists
I'm working with multiple ordered lists, each containing tuples of the form (key, value), where each list is sorted in ascending order by ...
- 75
0
votes
1
answer
60
views
Appearance of Start symbol on right side of production in Chomsky normal form if start symbol production is present
If there is a production which derives empty from start symbol, then can the start symbol appear on the right side of any other rule in Chomsky Normal Form? if no, why?
- 1
0
votes
0
answers
48
views
Characterization of all comparison sorting algorithms
In analogy to group theory, where all finite groups have been characterized, can we do something similar for comparison sorting algorithms (CSAs).
Maybe we first need a way to define isomorphism ...
- 101
2
votes
0
answers
105
views
How to prove that if L is a regular language, then f(L) is also a regular language?
If $f$ is a function of integers, define $f(L)$ as:
$$
f(L) = \{w \mid \text{for some } x, \text{ where } |x| = f(|w|), \, wx \in L \}.
$$
This means $f(L)$ is the set of strings $w$ such that there ...
- 21
1
vote
0
answers
56
views
Caching terminology
In docs sites, blogs, tools and on StackExchange, I often see various caching terms used interchangeably (though I suspect they differ).
Is there a theoretical difference between these terms:
...
- 111
16
votes
2
answers
2k
views
What is so fundamental about polynomial functions that they are used to demarcate the Hardness boundary in NP complexity classes?
This question has been bugging me ever since I first came across the concept of NP, NP-Complete, and NP-Hard a few years back: what is so fundamental about the polynomial functions that they are used ...
- 261
1
vote
2
answers
400
views
Two Generals' Problem - Thought Experiment
After reading the Two Generals' Problem, I am wondering as to why there isn't any solution and please correct me if I am missing something.
What if, the generals decide that they will attack if they ...
- 111
0
votes
1
answer
70
views
Are there any example of practical application of counter machines?
I am currently working on a presentation over how counter machines are as effective as Turing machines. During my research, I found out that random access machines are an improved version of counter ...
2
votes
0
answers
104
views
Theoretical origin of acquire semantics only for reads?
What theoretical concept lies behind the strong restriction of acquire semantics - to reads, and release semantics - to writes? (With papers titles and authors, if possible.)
Is it related to ...
- 171
0
votes
0
answers
169
views
For an NFA with langauge: {w ∈ {0, 1}*: the length of w is odd but not a multiple of three}. How many states are required?
For an NFA with language: {w ∈ {0, 1}*: the length of w is odd but not a multiple of three}. How many states are required?
This is the work I have come up with so far:
q0: non-accepting state - ...
- 1
2
votes
1
answer
89
views
Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular
There is an exercise in a book about finite automata that I couldn't solve:
Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular either, using the fact that REG is ...
- 2,058
-4
votes
1
answer
89
views
Turing Machine Decidability [closed]
Consider the language $L = \{\langle M_1,\ M_2 \rangle \mid \exists x : x \in L(M_1) \cap L(M_2)\}$. Show that $L$ is not decidable.
I'm attempting a proof by contradiction but I'm having trouble with ...
- 1