Decision procedures for automata, grammars and strings
Algorithms deciding questions about finite automata, regular expressions and context-free grammars given as data: emptiness, membership, universality, equivalence, and computable grammar reduction, together with the encodings of automata and grammars they operate on; and satisfiability of string constraints (word equations with regular membership and length bounds).
- Encodings of context-free grammars
- Primitive recursive list operations
- Emptiness of context-free grammars
- Computable reduction of context-free grammars
- Encoded finite automata
- Decision procedures for finite automata
- Emptiness of context-free and regular intersections
- Decision procedures for regular expressions
- String constraints and word equations
Loading dependency explorer…
The dependency explorer needs JavaScript and its graph data.