All Questions

31,139 questions
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 ...
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 ...
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 ...
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 ...
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 ...
28 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
64 views

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-...