Primitive-Recursive Solver and Regular Model Extraction for Parity Tree Specifications
ProvedDistLTLSynth.Char.regular_tree_parity_solverPrimitive-recursive decision procedure and regular model extraction for finite parity tree specifications (TreeSpecCode).
Let describe a -branching labeled tree language over with root admissibility , parent-direction-child compatibility , and deterministic parity branch monitor . There exist a primitive-recursive solver , specification encoder , and primitive-recursive regular-tree label evaluator such that:
and whenever , unfolding along finite node addresses yields a valid accepting regular tree.
This theorem supplies the parity-game solver and regular-tree strategy synthesis required to decide symbolic component tree nonemptiness and construct realizing distributed algorithms in Theorem 3.4.
Formalization Note Factoring the specification encoder packTS from the two-argument evaluator unfoldLabelPacked keeps product-encoding arity minimal for Primrec composition.
import Mathlib import Definitions.Def_DistLTLSynth_Char_Model import Definitions.Def_DistLTLSynth_Char_LTL import Definitions.Def_DistLTLSynth_Char_Automata import Definitions.Def_DistLTLSynth_Char_ComponentTree import Definitions.Def_DistLTLSynth_Char_SynthesisEngine
namespace DistLTLSynth.Char
theorem regular_tree_parity_solver :
∃ (solveTreePG : TreeSpecCode → Option (List ℕ))
(packTS : TreeSpecCode → ℕ)
(unfoldLabelPacked : ℕ → List ℕ → ℕ),
Primrec solveTreePG ∧
Primrec packTS ∧
Primrec₂ unfoldLabelPacked ∧
(∀ (ts : TreeSpecCode) (σ : List ℕ),
solveTreePG ts = some σ →
ValidAcceptingTree ts (fun addr =>
⟨(unfoldLabelPacked (Nat.pair (packTS ts) (Encodable.encode σ)) (addr.map Fin.val)) % (ts.2.1 + 1),
Nat.mod_lt _ (Nat.succ_pos _)⟩)) ∧
(∀ (ts : TreeSpecCode),
solveTreePG ts ≠ none ↔
∃ t : List (Fin (ts.1 + 1)) → Fin (ts.2.1 + 1), ValidAcceptingTree ts t) := by sorry
end DistLTLSynth.Char