Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

9
votes
2answers
129 views

Membership problem for certain class of unrestricted grammars

Consider an arbitrary context-free grammar $G$ over the alphabet $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$. To the productions of this grammar, add two fixed non-context-free productions $P$: ...
-1
votes
1answer
80 views

Consistency and completeness of any arbitrary 3-valued logic? [closed]

Based on the explanations here [1] I know that 3-valued first order logic has many different versions, which differ in the definition of their operations (e.g. implication). All of these (as far as I ...
3
votes
1answer
88 views

Decidability of first-order theory of real closed fields with functions

By a famous theorem of Tarski, the first-order theory of real closed fields is decidable, as it admits quantifier elimination. Can this result be extended so that propositions can be quantified over ...
5
votes
1answer
131 views

What language $L \in NCM$ has $\overline{L} \not \in NCM$?

$NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not ...
6
votes
3answers
187 views

Solving problems by deciding a logic

I am curious to know when open problems have been solved by expressing them in a specific logic, and then showing that this logic is decidable. I have two distinct cases in mind: The problem is ...
13
votes
4answers
337 views

What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
7
votes
1answer
115 views

Decidability of inductive invariant existence in Presburger arithmetic

Problem: Consider a finite number of control states (including an "initial" and a "bad" state), a finite number of integer variables, and for each ordered pair of states a transition relation ...
10
votes
1answer
198 views

What is the simplest computational model for which the emptiness problem is undecidable?

What is the simplest computational model for which the emptiness problem is undecidable? Emptiness problem for a computational model (e.g. finite state automaton, alternating pushdown automaton, ...
11
votes
1answer
79 views

Decidable theory of asymptotic growth

What are the known limits of the decidability of the comparison of growth rate of functions from $\mathbb{N} \to \mathbb{N}$? I am here thinking of the decidability of questions like "Is $x^x \sim ...
5
votes
1answer
154 views

What is known about $CFL \cap coCFL$?

CFL is the class of context-free languages; co-CFL the languages whose complements are context-free. So CFL $\neq$ co-CFL. Are there any nice characterizations or other basic facts about CFL $\cap$ ...
-1
votes
1answer
180 views

Deciding whether a turning machine guaranteed to halt solves sat [closed]

Suppose I give as input a Turing machine M guaranteed to halt in time n^c on inputs of length n for a universal constant c. Is there a Turing machine that given any such M can decide whether M solves ...
-2
votes
1answer
156 views

Intersection between context-free and context-sensitive language decidability [closed]

I'm trying to find a formal proof of the following fact: Given a context-free language, say $L_1$, and a context-sensitive language, say $L_2$, it is NOT decidable if their intersection is empty ...
0
votes
1answer
73 views

Is refuting candidate deciders of the halting problem computable? [closed]

No Turing machine can decide whether any given Turing machine will halt for a given input. That is: If you give me a Turing machine which you claim can take a Turing machine and an input for that ...
54
votes
12answers
5k views

A simple problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem which we do not ...
2
votes
1answer
79 views

Is it decidable whether the langauge accepted by a reversal-bounded counter machine is deterministic?

I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question: Given a non-deterministic reversal-bounded multicounter machine $M$, is there some ...
8
votes
2answers
303 views

Is meta-undecidability possible?

There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc. In this case I wonder whether a problem can be meta-undecidable. This means (at least in my ...
6
votes
0answers
191 views

Deciding if a language induced by a Presburger formula is context-free

Is the following problem decidable? Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ ...
17
votes
4answers
725 views

Checking if all products of a set of matrices eventually equal zero

I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix. This means exactly what ...
7
votes
1answer
811 views

Do natural generalizations of P versus NP exist?

Accepted Answer Scott Aaronson's answer has been "accepted" (mainly because it's the only answer!) One-sentence summary of answer  Plausibly natural generalizations of the P versus NP question ...
1
vote
0answers
164 views

Non-uniform CFG ambiguity decidability

The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version ...
7
votes
1answer
403 views

Does every Turing-recognizable undecidable language have a NP-complete subset?

Does every Turing-recognizable undecidable language have a NP-complete subset? The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
16
votes
2answers
302 views

Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?

I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).: If A ...
6
votes
3answers
292 views

Is it possible to compute whether two functions are extensional equal?

If you have two functions implementing a different sorting algorithm, is it then possible to infer by source code that they both have the same external properties? Meaning that they both will have a ...
5
votes
1answer
232 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
10
votes
3answers
1k views

Does P contain incomprehensible languages? (TCS community wiki)

Answer: not known Many thanks to all who helped refine this question and the definitions associated to it. The definitions of this wiki provided the starting point for the more recent TCS wiki ...