Questions tagged [software]

Questions about Software/Programs/Applications used by TCS researchers

Filter by
Sorted by
Tagged with
36
votes
8answers
2k 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 ...
28
votes
1answer
845 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 ...
22
votes
5answers
2k 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 ...
21
votes
10answers
3k 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 ...
21
votes
9answers
12k 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?
20
votes
5answers
2k 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 ...
20
votes
6answers
3k 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 /...
15
votes
5answers
464 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?
14
votes
5answers
2k 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 ...
12
votes
6answers
2k 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 ...
11
votes
2answers
1k 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 ...
9
votes
1answer
1k 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 $d$-...
8
votes
5answers
6k 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?
8
votes
1answer
440 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 ...
8
votes
0answers
337 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, $\vec{...
7
votes
2answers
336 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 ...
7
votes
2answers
454 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 ...
6
votes
2answers
280 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 ...
5
votes
2answers
470 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 ...
4
votes
1answer
177 views

Have fixed parameter integer program algorithms ever been implemented for research use?

Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
3
votes
1answer
330 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 ...
3
votes
1answer
561 views

Is there a tool for finding Nash equilibria in parametric games?

There are a few tools, either online or offline, that could solve (find equilibrium) in a game explicitly given as a real-valued matrix. Such tools are Game Theory Explorer and Gambit. However, as ...
3
votes
1answer
281 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 ...
3
votes
0answers
184 views

Min dominating set software

I need a fast min-dominating-set code for some complexity lower bounds research I am doing. I could transform to SAT and use an off the shelf SAT solver; but I was hoping min-dom-set had something ...
3
votes
0answers
85 views

Software that generates and solves a Lasserre hierarchy

Suppose L is a linear program that is a relaxation of some 0/1 integer linear program ILP. There is a systematic way to construct SDP relaxations of ILP that are tighter than L by using a Lasserre ...
3
votes
0answers
240 views

Vertex counting on convex polytopes

I was wondering if anybody had any pointers to: ...
2
votes
1answer
113 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 ...
2
votes
0answers
61 views

Has Khachiyan/Porkolob's convex integer optimization been implemented?

Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
1
vote
1answer
169 views

Practical approaches to solving whether programs will halt

What kinds of systems are available that accept a certain program $P$ and attempts to figure out "the program does terminate" or "the program does not terminate" and output a proof of one or the other?...
0
votes
0answers
163 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. Creating ...
0
votes
1answer
1k 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 ...
-1
votes
1answer
3k 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 (known ...
-1
votes
2answers
280 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 ...
-2
votes
1answer
44 views

Differences in the requirements for different bit architectures [closed]

I've noticed that software that exists as a 32-bit-version and a 64-bit-version often has higher system requirements if you want to install the 64-bit version. One example is Windows 10 The 32-bit ...