All Questions

31,062 questions
17 views

Polynomial-time Compute the Number of States resulting from the NFA to DFA (greedy) conversion?

The canonical NFA to DFA conversion, starting with an NFA with $n$ states, can result in a DFA with $2^n$ states. However, in many cases, there are states that are "unnecessary," such as when ...
42 views

Construct a DFA from the regular expression (a)*+(aab)*

I've broken down the expression into two simpler DFAs but right now I'm stuck. I don't know what to do with the expression a*, my solution currently (as presented above) is a NFA, not DFA.
27 views

I'm trying to speed up the following function in c++: ...
36 views

Algorithm for Unique Selections

Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set. A selection is unique if there's one and only one way it can happen—that is, one and only one ...
21 views

Algorithm to select elements from a ranked list of lists

I have a list of lists of objects. Each of the lists of objects is ranked according to a numeric field of the object. The big list is ranked according to the highest numeric value of the field of all ...
23 views

Minimize sequence storage by overlapping prefixes

I bumped into this problem today, and after a bit of pondering, I think I have a solution in $O(n^3)$, which is better than no solution or an $O(n!)$ solution, but my answer still isn't great. Can ...
27 views

Recognizably turing machine question (reject / loop)

The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way? Give a deterministic TM D that recognizes L such that ...
28 views

Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?
21 views

Translating java code into mathematics expression/formulas [closed]

I would like to convert my Java code into mathematics expressions/formulas and algorithm pseudocodes, just like ones in computer science research papers. Is there any tool does that (e.g. Eclipse ...
15 views

Cat Dog classifier in tensorflow, fundamental problem! [closed]

I am trying to build an image classifier for a set of images containing cats and dogs. I am very new to the dark art of creating Neural Network models. I have had success building models with Keras in ...
25 views

Why do we simulate the universal TM to simulate another TM M instead of simulating M directly?

In the proof of the time hierarchy theorem given on page 69 of Arora-Barak, we define a TM D as follows: "On input $x$, run for $|x|^{1.4}$ steps the Universal TM $\ \mathcal{U}$ of Theorem 1.9 to ...
16 views

Confused about 3rd rule of CFG pumping lemma

Let $L = \{\space ww \space | \space w \in \{0,1\}^*$} (need to prove that $L$ is not CFL) Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the ...
55 views

Conditions for a binary tree being balanced

Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced. If you disprove, the counterexample should consist of an infinite ...
9 views

Approximate Matching - two plane geometries with n points

I'm trying to do approximate matching of one plane geometry with n points to a big set of other plane geometries. The aim is to get the closest shape (rotation and scale agnostic) My idea would be to ...
17 views

Is using British accent dataset helpful while training American speech recognition? [closed]

I'm training a robust speech recognition system with as much data as possible. The target recognition speech will be American English, but I found some free British English datasets also. Now the ...
27 views

Does Google's PageRank count as a sorting algorithm?

Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?
21 views

Splay tree amortized cost analysis

I am looking into the amortized analysis of splay trees and seem to be missing something. Pretty much every resource uses the accounting method which I believe I grasp. What confuses me is the part ...
22 views

Partitioning a graph with specific constraints

We have an exercise where we need to find the partitions G[V1] and G[V2] of a graph G=(V,E), that fulfill the following constraints. We also know that there exists at least one partition that fulfills ...
12 views

19 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
78 views

Can these two languages be reduced to one another?

Given: $L_1=\left\{ \left\langle M\right\rangle :L\left(M\right)\ni w_{0}\right\}$ $L_2=\left\{ \left\langle M\right\rangle :L\left(M\right)=\left\{ w_{0}\right\} \right\}$ I believe I've managed ...
14 views

Multiple inputs for the same parameter [closed]

I would like to know what are my options for handling multiple inputs for the same field from a different user. I guess that is a BigData\probablity&statistics question. A link to read on such ...
27 views

Is it possible to do forward-chaining in Prolog?

Prolog (or any logic programming system) actually acts as SAT solver, that returns the valid values for the variables that are mentioned in the query. It can also be used as theorem prover if one does ...
24 views

Analysis of Basic Recursive Functions

I'm trying to understand the contrast between run-time for this function ...
23 views

How to visualize non-deterministic pushdown automata?

My friend and I are working on this project for our Formal Languages and Automata class that consists in building a pushdown automaton. A part of the project that is bothering me is how to visualize ...
35 views

Is it possible to write a fully-decidable type system for the J language?

I'm experimenting with the J array language, a dynamically-typed array language with mutable assignment, subtyping, and function overloading (just like traditional APL). It is unclear to me whether ...
13 views

Analysing data from amazon textract - python [closed]

I am creating a piece of software for my company where I need to check the math on invoices we receive from companies. The pdf invoices vary from 20-100 pages. The invoice we receive from each company ...
8 views

About logarithmic cost model and bit complexity model?

So I heard that there are such models for finding time complexity of an algorithm as logarithmic cost model and bit complexity model. But from the information I have found in the internet, I cannot ...
16 views

Is multi-theory approach the only way to do “higher-order” logic programming?

Lets consider logic program: likes(John, Vincent) loves(John, Ann) lusts(John, Tom) is_good(likes) is_good(loves) ~is_good(lusts) This program has 6 statements, ...
64 views

Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?

A minimum-spanning-tree (MST) path is always $V-1$ edges and a Hamiltonian Cycle (HC) is always $V$ edges. Because the HC has an extra edge we could say that in general, the weight of every ...
12 views

Log-space reduction from $USTCON$

Is it possible to use $USTCON$ log-space decision algorithm in order to show reduction from $USTCON$ to some other decision problem $A$? I mean - the reduction will run $USTCON$ decision algorithm and ...
99 views

Can I simplify successive XOR operations?

I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions). We have a rectangle of known ...
35 views

Are all uncomputable problems, undecidable?

Is there a proof that shows that: "A problem is uncomputable iff it is undecidable"?
We say that two languages $L_1,L_2$ are decreasing reducible if there exists a polynomial time reduction $f:\Sigma^*\to\Sigma^*$ and there exists $n\in\mathbb{N}$ such that for every $x\in\Sigma^*$ ...