All Questions

0
votes
0answers
16 views

Automata as term rewriting systems

It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words ...
-1
votes
0answers
17 views

What is the difference between a Top type and a Unit type

Wikipedia defines a Top type: (edited for readability) The Top type [...] is the universal supertype, as all other types in any given type system are subtypes of Top However, the article goes on ...
-3
votes
0answers
32 views

How can we solve the recurrence $T(n) = T(n/2) + log^2(n)$ [on hold]

I am trying to solve the following recurrence: $T(n) = T(n/2) + log^2(n)$ So far I have come up with the following expression $T(n) = \sum^{log(n)}_0 2^klog(n/2^k)$ I cannot figure out a way to ...
-4
votes
0answers
19 views

Prove that language in L

How to prove that $L = \{(\phi,x) | \space Boolean \space formula \space \phi \space is \space true \space on \space a \space set \space of \space x\} $ lies in L?
3
votes
3answers
124 views

When a type is a value?

In functional programming and in the theoretical setting of the $\lambda$-calculus it is standard to consider a lambda abstraction $\lambda x.M$ as a value. In my understanding, the intuitive reason ...
2
votes
0answers
54 views

What is the competitive ratio of a $d$-way associative LRU cache?

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
11
votes
1answer
139 views

Is { ww' | HamDist(w,w')>1 } context-free?

After reading the recent question "Is the complement of $\{ www \mid ...\}$ context-free?"; I remembered a similar problem I wasn't able to disprove: Is $L = \{ ww' \mid w,w' \in \{0,1\}^* \land |w|...
3
votes
0answers
101 views

Algebraic construction of $\varepsilon$-biased sets

See the edit at the bottom Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by $$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-...
3
votes
1answer
138 views

Continuous mathematics and formal language theory

Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics. For example, solving the intersection non-emptiness problem for a context-free ...
5
votes
0answers
89 views

Reversible polynomial circuit iff polynomial reversible circuit?

My question is about efficiently computable bijective functions. Informally I'm interested in: If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective ...
-5
votes
1answer
49 views

Can I prove this polynomial reduction?

Consider Barely-3-SAT: given a CNF $F=\wedge^m C_i$ determine whether there is an assignment such that exactly one clause $C_k$ is true all the others are false. I want to show this is $NP$-complete. ...
2
votes
1answer
108 views

For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and ...
3
votes
0answers
73 views

Is Circuit Minimization $P$-hard under logspace reductions?

By Circuit Minimization, I am referring to the following decision problem. Circuit Minimization Input: A bit string $x$ and a number $k$. Question: Does there exist a Boolean Circuit $C$...
-3
votes
2answers
147 views

Do Turing complete languages automatically have efficient algorithms [on hold]

Every Turing complete programming language can describe an algorithm that sorts sequences. Is it also true that every Turing complete language can describe an algorithm that sorts sequences in $\...
8
votes
1answer
144 views

Is the complement of { www | … } context-free?

It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?
-3
votes
0answers
62 views

The order complexity of an algorithm [on hold]

have a code that involves a 2 to 1 pairing of numbers. The code for this is ...
5
votes
1answer
207 views

Size of complement of context-free language

Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$. What is known about $|\bar L_n|$? Note that it is known that $|L_n|$ is either ...
0
votes
2answers
197 views

NP-hard problems on the class of caterpillars

My question is whether there exist an NP-hard problem that has only a caterpillar as input. By saying only caterpillar as input, I wanted to emphasize that no function (eg: weights on vertices or ...
0
votes
0answers
103 views

Star seperators to explain computational complexity of algorithms on a class of graphs?

A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
12
votes
1answer
282 views

Is there a P-complete language X such that succinct-X is in P?

I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
-3
votes
0answers
252 views

Is there any chance these results are correct? [closed]

P versus NP is considered as one of the most important open problems in computer science. This consists in knowing the answer of the following question: Is P equal to NP? A precise statement of the P ...
3
votes
0answers
208 views

new subset sum approach results

I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $O{n/2 \choose n/4}$, demonstrating as well the hardest target value is ...
0
votes
0answers
55 views

Coordinate descent in integer programing: when does it work?

Denote $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to minimize a function $f:N\rightarrow \mathbb{R}$. It is very easy to minimize $f$ coordinate by coordinate so ...
-1
votes
0answers
56 views

Approximate Multi Covering with Randomized Rounding

In the set multicover problem we are given a set $N$ of $n$ elements and a set $S$ of $m$ subsets of $N$. Additionally, each element has a coverage requirement (the number of times it has to be ...
2
votes
1answer
83 views

Maximum-minimum satisfiability

In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\...
-1
votes
0answers
70 views

minimal DFA corresponding to complement of a language [closed]

is it necessary that number of states in minimal DFA for a language corresponding to L' is equal to the number of states in minimal DFA of the language corresponding to L. here L' is the complement ...
3
votes
2answers
99 views

Minimum relevant variables in linear system - additive approximation

In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$ A x = b $$ and the goal is to find a solution $x$ with as few nonzero variables as ...
-3
votes
0answers
50 views

Optimal algorithm to compare lines of different files without repetition [closed]

I have 1600 ASCII files with 1000 lines in each file. Each line has only one entry and is a floating point number e.g. 1.67923. Let's denote the line1 of file1 with ...
0
votes
0answers
110 views

Decomposition for a certain class of graphs

Suppose a graph, $G = (V,E)$ is characterized as a lattice/network of cliques as in the picture below. Does there exist some decomposition principle (i.e. on the right) for $G$, that yields some ...
1
vote
1answer
65 views

Algorithm for K-best NON perfect bipartite matchings

I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best....
6
votes
0answers
123 views

Immutable Space Model

I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence? What is generally known about models of ...
4
votes
2answers
205 views

Is this partition problem strongly NP-complete?

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
0
votes
1answer
79 views

maximize edges minus vertices in a weighted graph

for a given weighted vertices and edges graph, we want to find the maximum subgraph. the maximum subgraph is made of some vertices and some edges of the given graph which sum of the edges minus sum of ...
0
votes
0answers
28 views

NuSMV - How to indicate the execution should visit some states infinitely often?

I have the following kripke structure: I need my model to follow the LTL constraint that state d will be visited infinitely often: LTLSPEC G F (modelState=d) ...
2
votes
0answers
137 views

Best polynomial-time approximation factor for NP-optimization problems

Let us say that a function $f(n)$ is the best approximation factor for an NP-optimization problem, if both of the following hold: There exist a polynomial-time algorithm $A,$ and an integer $n_0$, ...
0
votes
1answer
64 views

Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

I've learned from several sources that an LL(1) grammar is: unambiguous, not left-recursive, and, deterministic (left-factorized). What I can't fully understand is why the above is true for any LL(1)...
-4
votes
0answers
74 views

Prove that if A is NP-complete and B is coNP-complete, than AxB is NP-, coNP-complete

AxB means cartesian product of A and B. May someone help me with this? I even have no idea how to prove that AxB belongs to NP or coNP
12
votes
3answers
430 views

Feel dissatisfied after each submission

I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly ...
6
votes
0answers
98 views

Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
0
votes
0answers
84 views

Maximum Weight Independent Set on a Changing Graph?

Suppose I have an optimal solution to the maximum weight independent/stable set problem on an arbitrary graph. If I were to induce a clique among a subset of its vertices (and perhaps add in some ...
1
vote
0answers
48 views

The definition of weakest precondition for a non-deterministic language

In the classical IMP language, the definition of weakest precondition is: definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t" This is stating that from state s, after ...
3
votes
1answer
99 views

Strong seeded randomness extractors with low entropy loss

I would like to implement a strong seeded randomness extractor for flat sources as a part of my project. Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
3
votes
0answers
159 views

What is a good route for a math student to self study computer science systematically and efficiently?

I decided to ask this question after being attracted by how much one can do with the knowledge in computer science, including iOS application development, game(or mods) development, website creating, ...
6
votes
1answer
110 views

Separating words and graph isomorphism

I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's. In both cases the ultimate goal is to differentiate ...
3
votes
0answers
91 views

Busy Beaver Equivalent for the Untyped Lambda Calculus

In the same way that the Busy Beaver function is defined for Turing Machines, we could define a similar function for the untyped lambda calculus: Over all terms in the ULC composed of ...
-2
votes
0answers
39 views

How to prove that models of indirect and direct RAM machines are equivalent?

as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
0
votes
3answers
151 views

Hamiltonian cycle vs co-NP [closed]

I am trying to understand co-NP and its implications properly. The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows: ...
-2
votes
0answers
74 views

Is it there any cellular automata model of the universe where uncomputable things could happen?

There are several papers that propose that the universe itself is analogous to a cellular automata. Obviously, these papers assume that the universe is computable. But is it there any cosmological ...
2
votes
2answers
732 views

What to do as a Theoretical computer science PhD student in a free time?

I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff ...
1
vote
0answers
18 views

Pass ordering for greedy local search algorithms

Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for. I have a problem with the following setup: I have a (finite) totally ...

15 30 50 per page