The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
254 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
4
votes
3answers
368 views

Aftermath of the incompletness theorem proof

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 ...
9
votes
5answers
1k views

Resources for learning formal math?

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.) ...
10
votes
1answer
1k views

Formal System and Formal Logical System

I was reading the Wikipedia article for Mathematical_logic. When reaching Formal_logical_systems, I was curious about its definition and clicked into its own article Logical_system, which redirected ...
5
votes
5answers
690 views

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 ...
2
votes
3answers
279 views

Why can't we use memoization to parse unambiguous context-free grammars in linear time?

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 ...
1
vote
2answers
353 views

Why is it hard to parse unambiguous context-free grammar in linear time?

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 ...
4
votes
2answers
4k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
3
votes
1answer
118 views

What is the minimal axiomatization of a set of structures?

I wonder what the minimal axiomatization of a set of structures mean? I came across this term from Wikipedia: For a theory $T\in A,$ let $F(T)$ be the set of all structures that satisfy the ...
2
votes
1answer
228 views

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
0
votes
3answers
85 views

Are axioms assumed to be true in a formal system?

In a logical system, there is assignment of truth values to the sentences in the language, and axioms are assigned the true value. A logical system is a formal system. In a formal system, there is ...
0
votes
2answers
127 views

Does a formal system having inference rules imply that it is a logic system?

From Wikipedia Formal systems in mathematics consist of the following elements: A finite set of symbols (i.e. the alphabet), that can be used for constructing formulas (i.e. finite ...