Tagged Questions
15
votes
3answers
479 views
What is the minimal extension of FO that captures the class of regular languages?
Context: relations between logic and automata
Büchi's Theorem states that Monadic Second Order logic over strings (MSO) captures the class of regular languages. The proof actually shows that ...
4
votes
1answer
187 views
What is an unambiguous language in the sense of Schützenberger?
I'm reading Thomas Wilke's survey on the connections between Temporal Logic and finite automata, finite semigroups and first-order logic.
In Theorem 6 (by Kamp), the fragment ...
16
votes
5answers
459 views
Ambiguity and Logic
In automata theory (finite automata, pushdown automata, ...) and in complexity, there is a notion of "ambiguity". An automaton is ambiguous if there is a word $w$ with at least two distinct accepting ...
