Predicting Agent Behavior with Automata

# Illustrative sketch (not from the paper)
import collections
import torch
import torch.nn as nn

# 1. Insert activity sequences into a prefix tree (trie)
def build_trie(traces):
    root = {}
    for seq in traces:
        node = root
        for act in seq:
            node = node.setdefault(act, {})
    return root

# 2. Merge states that share the same last activity (right congruence)
def merge_states(trie):
    # map last activity -> list of nodes
    groups = collections.defaultdict(list)
    def dfs(node, path):
        if not node:
            return
        last = path[-1] if path else None
        groups[last].append(node)
        for act, child in node.items():
            dfs(child, path + [act])
    dfs(trie, [])
    # naive merge: collapse groups into a single representative
    fsm = {'states': [], 'trans': collections.Counter()}
    for last, nodes in groups.items():
        state_id = len(fsm['states'])
        fsm['states'].append(last)
        for n in nodes:
            for act in n:
                fsm['trans'][(state_id, act)] += 1
    return fsm

# 3. Filter rare transitions that appear exactly once
def filter_rare(trans_counter):
    return {k: v for k, v in trans_counter.items() if v > 1}

# 4. Use FSM state as context for next‑step prediction (PyTorch example)
class NextStepModel(nn.Module):
    def __init__(self, n_states, vocab_size, embed_dim=32):
        super().__init__()
        self.state_emb = nn.Embedding(n_states, embed_dim)
        self.token_emb = nn.Embedding(vocab_size, embed_dim)
        self.fc = nn.Linear(embed_dim * 2, vocab_size)
    def forward(self, state_idx, prev_token):
        s = self.state_emb(state_idx)
        t = self.token_emb(prev_token)
        x = torch.cat([s, t], dim=-1)
        return self.fc(x)

# 5. Extract per‑state behavioral features (frequency, avg length, error flag)
def extract_features(traces, fsm):
    freq = collections.Counter()
    length_sum = collections.Counter()
    error = collections.Counter()
    for seq in traces:
        state = 0  # start state placeholder
        for act in seq:
            freq[state] += 1
            length_sum[state] += len(act)
            if act.lower().startswith('error'):
                error[state] = 1
            # transition to next state (simplified)
            state = (state + 1) % len(fsm['states'])
    features = {}
    for s in range(len(fsm['states'])):
        features[s] = {
            'visit_freq': freq[s],
            'avg_len': length_sum[s] / max(1, freq[s]),
            'has_error': error.get(s, 0)
        }
    return features

// Illustrative sketch (not from the paper)
const fs = require('fs');

// 1. Build a trie from activity traces (array of arrays)
function buildTrie(traces) {
  const root = {};
  for (const seq of traces) {
    let node = root;
    for (const act of seq) {
      if (!node[act]) node[act] = {};
      node = node[act];
    }
  }
  return root;
}

// 2. Merge states that share the same last activity (right congruence)
function mergeStates(trie) {
  const groups = {};
  function dfs(node, path) {
    const last = path.length ? path[path.length - 1] : null;
    if (!groups[last]) groups[last] = [];
    groups[last].push(node);
    for (const act in node) {
      dfs(node[act], path.concat(act));
    }
  }
  dfs(trie, []);
  const fsm = { states: [], trans: {} };
  let stateId = 0;
  for (const last in groups) {
    fsm.states.push(last);
    for (const n of groups[last]) {
      for (const act in n) {
        const key = `${stateId}|${act}`;
        fsm.trans[key] = (fsm.trans[key] || 0) + 1;
      }
    }
    stateId++;
  }
  return fsm;
}

// 3. Filter transitions that appear exactly once
function filterRare(trans) {
  const filtered = {};
  for (const k in trans) {
    if (trans[k] > 1) filtered[k] = trans[k];
  }
  return filtered;
}

// 4. Use FSM state as context for a next‑step predictor (placeholder function)
function predictNext(stateIdx, prevToken, model) {
  // model could be a TensorFlow.js model; here we just illustrate the API
  return model.predict({ state: stateIdx, token: prevToken });
}

// 5. Extract per‑state behavioral features
function extractFeatures(traces, fsm) {
  const freq = {};
  const lenSum = {};
  const error = {};
  for (const seq of traces) {
    let state = 0; // start state placeholder
    for (const act of seq) {
      freq[state] = (freq[state] || 0) + 1;
      lenSum[state] = (lenSum[state] || 0) + act.length;
      if (/^error/i.test(act)) error[state] = 1;
      state = (state + 1) % fsm.states.length; // simplified transition
    }
  }
  const features = {};
  for (let s = 0; s < fsm.states.length; s++) {
    const visits = freq[s] || 0;
    features[s] = {
      visitFreq: visits,
      avgLen: visits ? lenSum[s] / visits : 0,
      hasError: error[s] || 0
    };
  }
  return features;
}