Tagged Questions
1
vote
2answers
55 views
Sequences and Languages
Let $U$ be the following language. A string $s$ is in $U$ if it can be written as:
$s = 1^{a_1}01^{a_2}0 ... 1^{a_n}01^b$,
where $a_1,..., a_n$ are positive integers such that there is a 0-1 ...
2
votes
1answer
108 views
Function problem vs. decision problem
Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with ...
1
vote
1answer
275 views
Turing Machine Vs Linear Bounded Automata
Example of language accepted by Turing Machine but not by Linear Bounded Automata ?
Is there any EXPSPACE language?
4
votes
1answer
118 views
Minimal DFA satisfying a finite view of a language.
Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq ...
3
votes
1answer
140 views
Regular expressions which first disagree after an exponential length
Problem 8.24 of Sipser's Introduction to the Theory of Computation asks:
For each $n$, exhibit two regular expressions $R$ and $S$ of length $poly(n)$ where $L(R)\not =L(S)$, but where the first ...
4
votes
3answers
254 views
How complicated is the set of tautologies?
Consider the set $\mathcal T$ of all tautologies in the propositional calculus in which the only operators allowed are $\to$ and $\neg$, and involving only the two variables $x$ and $y$.
How ...
1
vote
1answer
106 views
Reduction over intersection of languages
Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$.
1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to ...
