Questions about Software/Programs/Applications used by TCS researchers

learn more… | top users | synonyms

7
votes
0answers
252 views

Are there any implementations of Cook-Levin?

Does anyone know if there is an implementation of Cook-Levin? A program that gets an input like the following: $M$: the code of a machine model/simple program in a programming language like C, ...
1
vote
0answers
47 views

Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
-1
votes
1answer
348 views

Program optimization - 90/10 law

I found this "law" somewhere on Wikipedia: In software engineering, it is often a better approximation that 90% of the execution time of a computer program is spent executing 10% of the code ...
9
votes
1answer
583 views

Enumerate all solutions of a SAT problem

All the #SAT solvers I know, e.g RelSat, C2D, only return the number of satisfiable instances. But I want to know each of those instances? Is there such a #SAT solver or how I should modify an ...
2
votes
1answer
119 views

Approximate-#SAT solver

I am looking for a solver that computes an approximation to #SAT. In other words, given a formula $\phi(x)$ in CNF, approximately count the number of satisfying assignments to $\phi$. I'm interested ...
7
votes
2answers
227 views

Is there software for graph product calculation and visualization?

I am interested in finding a program which can calculate and preferably also visualize various products of not huge graphs. More specifically, I work with labeled, directed multigraphs, and would ...
-1
votes
2answers
261 views

Will we be able to use the current software in quantum computers? [closed]

I'm not sure if this should go here, so my apologies. The fact is that lately I have heard a lot about quantum computers and that they are not that far away. As it is a totally new technology, which ...
15
votes
5answers
116 views

Software package for decomposing quantum circuits

Is there any software package allowing decomposition of unitaries from $U(2^n)$ into quantum circuits over a predefined universal gate set?
7
votes
1answer
721 views

Computing volume of high-dimensional convex polyhedra

I am looking for software for computing/estimating volume of high-dimensional convex polyhedra. More specifically, I am interested in a program, which can handle bodies with $n$ vertices in ...
0
votes
0answers
162 views

Tool for managing scientific papers [duplicate]

Possible Duplicate: Do you use any article organizers? As part of my Ph.D. studies I need to create an overview of recently (since 2000) published papers with impact on my study field. ...
2
votes
0answers
177 views

Vertex counting on convex polytopes

I was wondering if anybody had any pointers to: ...
-1
votes
1answer
444 views

Generating a language from a given grammar

So I'm looking for a way of generating all words in language specified by a specific grammar and a alphabet. Is there an easy way to do this? The grammar is a stochastic context free grammar? Is there ...
3
votes
1answer
279 views

Are there good implementations for easy subclasses of NP-hard graph problems

Given graph G = (V,E) I need to solve some problems that are NP-Complete on G. However it could be that G belongs to some class where these problems has polynomial solutions (here is a great resource ...
10
votes
5answers
1k views

Best book on Simplex Method implementation?

I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in ...
9
votes
1answer
684 views

Program for computing Tree decomposition of a graph

Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my ...
4
votes
2answers
385 views

Software for Graph Analysis

I have some graph-data which I would like to analyze. If the software could automatically determine some characteristics (Is the graph planar, clique number or any other graph property) it would be ...
9
votes
6answers
1k views

Proof assistant for writing mathematics

I'd like to write mathematical proofs using some proof assistant. Everything will be written using first order logic (with equality) and natural deduction. The background is set theory (ZF). For ...
35
votes
8answers
1k views

Collaborative tools for dummies/professors

Suppose that coauthors from two or more different institutions are writing a paper in latex, and would like to do better than repeatedly emailing drafts back and forth. They realize they can open for ...
7
votes
2answers
375 views

A System for Visualizing Bibliography Information

I'm looking for a software for visualizing main trends in some field. Specifically, I want it to build a graph of the field with vertexes representing papers and edges representing how close papers ...
5
votes
2answers
206 views

Practical applications of the Theory of Equality with Uninterpreted Functions (EUF)

In these days I'm reading the book Decision Procedures - An Algorithmic Point of View. Chapters 3 and 4 deal with the Theory of Equality with Uninterpreted Functions (EUF). The authors give 3 toy ...
24
votes
1answer
644 views

Is there a reasonable automated proof system for TCS theorems?

Suppose I wanted to formalize Turing's proof regarding the halting problem so that a machine could check it. Some of the well-known automated theorem proving systems include Mizar, Coq, and HOL4. I ...
4
votes
5answers
2k views

What are theoretically sound programming languages for graph problems?

There are numerous graph theoretic tools/packages. Each with its pros and cons. What should be the semantics/syntax of a programming language meant to solve graph theoretic problems?
18
votes
5answers
1k views

Version control for collaboration (with word-level diffs)?

Most papers are now written collaboratively, and collaborators are often located in different places. I have always used version control systems for my documents and code, and have also found version ...
19
votes
6answers
2k views

Network / Social network analysis visualization tools?

I was using Jung ( http://jung.sourceforge.net/ ) to visualize page rank and found it a little slow and difficult to scale it beyond 100 nodes. I was wondering what other tools people use for network ...
8
votes
1answer
357 views

Tool for translating PDAs to CFGs

We know that all push down automata are representable using context-free grammars. Furthermore, there is an algorithm to construct a CFG from any PDA (e.g. Sipser's proof in intro to theory of ...
18
votes
9answers
5k views

What is the recommended software for drawing data structures such as graphs and trees?

When putting together results, it's often desirable to have some professional looking diagrams, rather than diagrams put together in MS Paint. What is the standard for drawing data structures?
17
votes
7answers
2k views

#SAT Solver download

Could anyone please point to one or more websites where is possible to download a working implementation of a #SAT solver? I'm interested in those returning the exact solution count, not an ...