Tagged Questions
15
votes
3answers
481 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 ...
2
votes
1answer
248 views
FSMs with finite memory
Consider an FSM and a finite set of variables. The FSM has the special property that each state contains a set of commands, with each command taking the form of "variable = expr(variable, ...)" e.g., ...
16
votes
5answers
467 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 ...
