Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g.  Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
This is somewhat of a minor point about the incompletness theorem, but I'm always a little unsure: So one proves that there is a formula which is unprovable in the theory of consideration. Okay, at ...
I'd like to learn formal math. Preferably, though not necessarily, starting with predicate logic/first order logic rather than higher order logic. I am trying to find resources (papers, books etc.) ...
Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?
Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...
This is a follow-up question to Why is it hard to parse unambiguous context-free grammar in linear time? I know that Parsing Expression Grammars (PEG) can be parsed in linear time using a packrat ...
From this question, I gather that whether unambiguous CF grammar can be parsed in linear time is an open problem. I'd like to know what the major roadblocks to achieve this are. That is, what made the ...
What makes a context free grammar ambiguous?