All Questions

0
votes
0answers
21 views

A programming language extending Scheme with static typing [on hold]

I have developed programming language called Theme-D extending Scheme with static typing. See Theme-D home page. Some features of Theme-D include ...
0
votes
1answer
19 views

How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?

I might unncecessarily overthinking here, but I had this weird possibly meaning less doubt: When grammar is neither LL nor LR, it means, both LL and LR parsing tables involve conflicts. LL parsing ...
0
votes
1answer
29 views

Semantics of E and A operators

I'm referring to a book where E and A were defined in text as follows The formula $A \phi$ states that all the executions out of the current state satisfy property $\phi$ whereas $E\phi$ states ...
-3
votes
1answer
73 views

Could we define the decimal notation of a natural number as a series of operations applied to 0?

People have made mistakes. For that reason, there probably is a demand by some people for a computer program that's easier to verify makes the calculations properly. I think that according to the ...
0
votes
0answers
12 views

Finding rank of newly inserted node in AVL tree augmented with rank of node

My prof was talking about how to augment a tree to efficiently find the key with a given rank. On the way to getting the right answer (store the size of the subtree rooted at each node), he proposed ...
0
votes
0answers
28 views

Proof of lemma from Hong's article about multi-threaded max flow algorithm

I'm struggling to prove Lemma 3 and Lemma 4 from an article about parallel version of push-relabel algorithm: A lock-free multi-threaded algorithm for the maximum flow problem. Lemma 3. Any trace ...
0
votes
1answer
23 views

CYK result de-transformation

Suppose we have a rules derived from a treebank. And in order to get a syntax tree of a given sentence we use the cyk algorithm. In order to use the cyk we should convert the rules into chomsky normal ...
0
votes
1answer
20 views

Algorithm for automatic construction of natural deduction proofs

I was wondering if there exists any algorithm for automatic construction of nautral deduction proofs. I'm interested in propositional logic and first order logic. If there is no algoritm, can you ...
-2
votes
0answers
41 views

why is discrete maths needed to understand algorithms?

I am new to algorithms. I need to know is it necessary to study discrete maths to understand algorithms. If so, why? In particular, is it necessary for understanding algorithms or is it only necessary ...
0
votes
0answers
9 views

How translation, transcription and annotation are related?

From a linguistic point of view, translation, transcription and annotation are three specific terms that introduce some (different) meanings. However, when it comes to the application, it seems that ...
3
votes
0answers
15 views

Normal colorings of cubic graphs (part 1)

Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent edges are colored with either five colors, or ...
0
votes
0answers
16 views

Boolean circuit size of $i$th bit of determinant?

Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. Is there a polynomial size boolean circuit for $i$th bit of ...
0
votes
0answers
18 views

what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata

my doubt is what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata ? both of them when started at a state q for a string w will ...
2
votes
0answers
64 views

Proving NP-completeness of an extension in List Coloring Problem

In the List Coloring Problem (LCP), one is given an undirected graph $G(V,E)$, each vertex $v \in V$ is given a list of permissible colors $L(v) \subseteq \{1,2,\dots,k\}$, we want to find a coloring $...
1
vote
1answer
27 views

Reduction to proof undecidability of the problem: machine M and N accept infinitely many words

I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and ...
0
votes
1answer
33 views

Online algorithm for finding of clique of size k

I am trying to write an online algorithm that can detect cliques of size k. I first start out with a set of vertices. For each iteration, I add an edge. The algorithm will detect the first time an ...
0
votes
0answers
17 views

Constucting QAP in the pinoccho paper

In this paper Pinocchio: Nearly Practical Verifiable Computation, on page 3 there is a way to construct the QAP and example doing it. Question : they say We pick an arbitrary root rg ∈ F for ...
1
vote
1answer
19 views

What is the index of the leftest child of node in a k-nery heap?

Suppose the root node‘s index is 1, what is the index of the leftest child of a node e in a k-nery heap? What is the parent‘s index of a node in k-nery heap? All questions regarding my problem I ...
0
votes
2answers
27 views

Without Rare Metals [on hold]

One often sees assertions that these are "necessary" for modern military and consumer computing applications. I presume that without these rare metals, the devices could be manufactured, but would be ...
0
votes
1answer
45 views

How can I write a genetic programming algorithm, given that the Halting problem is unsolvable?

I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as ...
1
vote
0answers
22 views

prove $ L=\{M\ |\ M\ is\ a\ TM\ and\ \forall.x\in \Sigma^*\ with\ |x|>2,\ M\ on\ x\ runs\ at\ most\ 4|x|^2\ steps\}\notin R$

I am trying to prove that the language $$ L=\{M\ |\ M\ is\ a\ TM\ and\ \forall.x\in \Sigma^*\ with\ |x|>2,\ M\ on\ x\ runs\ at\ most\ 4|x|^2\ steps\} $$ belongs to $Co-RE$ but not to $R$. ...
0
votes
1answer
16 views

Is there a problem in this BN form language?

I am working on a simple text query language. I am using the SLY parser, which itself is an LR parser/shift-reduce parser. I am running into problems with the following language specification, but I ...
-1
votes
0answers
18 views

Transversal of matrices [on hold]

Pseudocode too will do the job
3
votes
0answers
22 views

Non-linear optimization of a family of functions

I'd like some advice about the following problem (resolution methods, problem category, etc.). The context is about the coregistration of several images all-in-once ($n$ images, $f_{i,j}$ the ...
1
vote
1answer
44 views

Search vs planning in artificial intelligence

I'm studying artificial intelligence following the Russell & Norvig book. We did a search and planning part that for me is the same (at least on the representation). I'd like to know what is the ...
0
votes
0answers
14 views

Why we need size of the page table should be some fraction of virtual address space

The Page Table should have all virtual page number which are in its logical address space, Why it's the case? Is it because we want to access Page Table entry fast just like an array where key is ...
3
votes
1answer
45 views

Why are four context sensitive grammar (CSG) rules needed to represent AB -> CD?

In Wikipedia of Kuroda normal form, it says A straightforward technique attributed to György Révész transforms a grammar in Kuroda's form to Chomsky's CSG: AB → CD is replaced by four context-...
0
votes
0answers
14 views

Any ways to reduce the length of the code? [closed]

The question is to convert from 12 hour format,input is of the form 00:00:00AM to 24 hour format.I want to reduce the length of the code.My code is: def Input(): s=input() return(s) def ...
-3
votes
1answer
49 views

Church Turing thesis

What is the exact statement of the Church Turing thesis? Is it fair to say anything computable in the physical world can be computed by a Turing machine? If so, how does a Turing machine handle ...
5
votes
4answers
2k views

Are Finite Automata Turing Complete?

Something is Turing Complete if it can be used to simulate any Turing Machine. So, can a Finite Automaton simulate a Turing Machine? On the question Can regular languages be Turing complete? they ...
1
vote
1answer
27 views

Thorup : What is the meaning of super distance?

While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance. It says: "For each vertex we have a super distance $D(v)\geq d(v)$" $d(v)$ must ...
1
vote
1answer
44 views

Upper bound $T(n) = 9T(\sqrt[3]{n}) + O(1)$

The problem is this: Use the recursion-tree method to give a good asymptotic upper bound on $$ T(n) = 9T(\sqrt[3]n) + \Theta(1). $$ I am able to get the tree started and find a pattern with the sub-...
0
votes
0answers
33 views

Prove language is non-regular using pumping lemma

I'm working through an exercise in Peter Linz's book at the end of chapter 4 and am completely stumped. I believe you have to somehow use complement of L but, I'm not sure. Any help would be ...
3
votes
1answer
55 views

Forcing an edge to be in S-T min-cut

Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e. So, I tried couple of steps, first, ...
3
votes
1answer
79 views
+50

Mistake in a proof of termination phase of Simplex algorithm in CLRS?

There is a pseudo-code for Simplex algorithm in CLRS: The proof consists from three-part loop invariant: Proof We use the following three-part loop invariant: At the start of each iteration ...
0
votes
0answers
19 views

counting the integer solutions to 1000a + 100b + 10c + d where 0 < x,y < 20 [closed]

I am trying to figure out the integer solutions to 1000a + 100b + 10c + d where 0 < x,y < 20. I can print out the solutions by replacing n = n + 1 with 'print(a,b,c,d)' and removing the 'print(n)...
1
vote
1answer
36 views

Assigning $m$ balls to $n$ buckets - recursive algorithm

I came across the following problem and the answer to that problem: Given $m$ balls and $n$ bins, find out how many ways to assign the balls to the bins. Notice the bins have no order: for example, ...
1
vote
0answers
37 views

Algorithm for deducing values

I have a group of logical conditions and need to deduce values that would NOT satisfy them. For example: City != New York && Location = Museum ...
4
votes
3answers
81 views

How to give a context-sensitive grammar for a^nba^nba^nb?

I am struggling on this problem since days: $L = \{a^nba^nba^nb \mid n \in \Bbb N\}$. I have to give for this language a context-sensitive grammar.
3
votes
1answer
32 views

Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?

In Introduction to Automata Theory, Languages, and Computation, John Hopcroft mentioned[1] In fact, a PDA In fact the languages of one counter machines are accepted by deterministic PDA's although ...
1
vote
0answers
16 views

Overlay two Voronoi Diagrams and calculate membership and areas of intersecting polygons

I would like to generate a composite diagram of two Voronoi diagrams. I'm currently researching the cgal library for options, but I'm not sure if my precise application is covered. Basically, I have ...
0
votes
0answers
32 views

How to prove that extended euclidean algorithm has time complexity log(max(m,n)) ?'

I tried to search on internet and also thought by myself but was unsuccessful. Intuitively i think it should be O(max(m,n)). can someone give easy explanation since i am beginner in algorithms.
0
votes
0answers
22 views

I need advices and guidance! [closed]

I have a lot of questions and a lot of doubts of what should i do with my life. The thing is, i finished IT college in Bosnia and Herzegovina ( 3 year bachelors degree). I didn’t master any IT skills ...
-1
votes
0answers
40 views

Longest simple circuit and P=NP relation

Given the following function: $$\:f\left(G,v\right)\:=\:size\:of\:the\:longest\:simple\:circuit\:in\:a\:directed\:graph\:G\:that\:contains\:v$$ Output: Function returns a natural number or 0, which ...
1
vote
1answer
25 views

Logical characterization of $NC^1$

Morioka in his 2005 dissertation [1] referenced "On Uniformity within $NC^1$" by Barrington, Immerman, and Straubing. Using the following statement: Every $\mathbf{NC^1}$-predicate is computed by ...
0
votes
1answer
22 views

What is a good example of a textbook on programming, using Python? [closed]

I am looking for a textbook (for a course I am about to teach) that introduces programming generally - with Python as the example language. That is, I am not looking for the many many books on "how to ...
1
vote
1answer
17 views

$NL^2 = NDSPACE(\log^2n)$ is closed under complement

From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement. From Immerman–Szelepcsényi theorem we have $NL = coNL$. Why then $NL^2 = coNL^2$
1
vote
1answer
25 views

Categorising problems into complexity classes

Am I correct in saying that there are two ways to categorise a problem in complexity theory: Find an algorithm that solves it. If the algorithm runs in polynomial time, then we can put it into P-...
-1
votes
0answers
7 views

Complete AES code?bin C#? [closed]

I have designed a new encryption routine and am learning to code to write it. If I was able to examine how AES is quite literally written in C# I could probably reduce a month of studying followed by ...
1
vote
1answer
60 views

Given price and number of pages of each book, What is the maximum number of pages you can buy?

You are in a book shop which sells n different books. You know the price and number of pages of each book. You have decided that the total price of your purchases will be at most x. What is the ...

15 30 50 per page