• Top
  • Documentation
  • Books
  • Recursion-and-induction
  • Boolean-reasoning
    • Ipasir
    • Aignet
      • Base-api
      • Aignet-construction
      • Representation
        • Aignet-impl
        • Node
        • Network
          • Lookup-id
          • Lookup-stype
          • Aignet-extension-p
          • Aignet-nodes-ok
          • Aignet-outputs-aux
          • Aignet-nxsts-aux
          • Fanin
          • Aignet-outputs
          • Lookup-reg->nxst
          • Aignet-lit-fix
          • Stype-count
          • Aignet-fanins
          • Aignet-nxsts
          • Aignet-idp
          • Aignet-norm
          • Aignet-norm-p
          • Aignet-id-fix
          • Fanin-count
          • Proper-node-listp
          • Fanin-node-p
          • Node-list
          • Aignet-litp
        • Combinational-type
        • Stypep
        • Typecode
      • Aignet-copy-init
      • Aignet-simplify-marked-with-tracking
      • Aignet-cnf
      • Aignet-simplify-with-tracking
      • Aignet-complete-copy
      • Aignet-eval
      • Semantics
      • Aignet-transforms
      • Aignet-simplify-marked
      • Aignet-read-aiger
      • Aignet-write-aiger
      • Aignet-abc-interface
      • Utilities
    • Aig
    • Satlink
    • Truth
    • Ubdds
    • Bdd
    • Faig
    • Bed
    • 4v
  • Projects
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Testing-utilities
  • Math

• Network

Lookup-id

Core function for looking up an AIG node in the logical AIG network by its ID.

Signature

(lookup-id id aignet) → suffix

Arguments

id — Guard (natp id).

aignet — Guard (node-listp aignet).

Returns

suffix — Tail of the aignet up to (and including) the idth node.
    Type (node-listp suffix).

Definitions and Theorems

Function: lookup-id

(defun lookup-id (id aignet)
       (declare (xargs :guard (and (natp id) (node-listp aignet))))
       (let ((__function__ 'lookup-id))
            (declare (ignorable __function__))
            (cond ((endp aignet) (node-list-fix aignet))
                  ((and (fanin-node-p (car aignet))
                        (equal (fanin-count aignet) (lnfix id)))
                   (node-list-fix aignet))
                  (t (lookup-id id (cdr aignet))))))

Theorem: node-listp-of-lookup-id

(defthm node-listp-of-lookup-id
        (b* ((suffix (lookup-id id aignet)))
            (node-listp suffix))
        :rule-classes :rewrite)

Theorem: lookup-id-of-nfix-id

(defthm lookup-id-of-nfix-id
        (equal (lookup-id (nfix id) aignet)
               (lookup-id id aignet)))

Theorem: lookup-id-nat-equiv-congruence-on-id

(defthm lookup-id-nat-equiv-congruence-on-id
        (implies (nat-equiv id id-equiv)
                 (equal (lookup-id id aignet)
                        (lookup-id id-equiv aignet)))
        :rule-classes :congruence)

Theorem: lookup-id-of-node-list-fix-aignet

(defthm lookup-id-of-node-list-fix-aignet
        (equal (lookup-id id (node-list-fix aignet))
               (lookup-id id aignet)))

Theorem: lookup-id-node-list-equiv-congruence-on-aignet

(defthm lookup-id-node-list-equiv-congruence-on-aignet
        (implies (node-list-equiv aignet aignet-equiv)
                 (equal (lookup-id id aignet)
                        (lookup-id id aignet-equiv)))
        :rule-classes :congruence)

Theorem: fanin-count-of-lookup-id

(defthm fanin-count-of-lookup-id
        (implies (<= (nfix n) (fanin-count aignet))
                 (equal (fanin-count (lookup-id n aignet))
                        (nfix n))))

Theorem: fanin-count-of-cdr-lookup-id

(defthm fanin-count-of-cdr-lookup-id
        (implies (consp (lookup-id n aignet))
                 (equal (fanin-count (cdr (lookup-id n aignet)))
                        (+ -1 (nfix n)))))

Theorem: output-ctype-of-lookup-id

(defthm output-ctype-of-lookup-id
        (not (equal (ctype (stype (car (lookup-id id aignet))))
                    (out-ctype))))

Theorem: output-stype-of-lookup-id

(defthm output-stype-of-lookup-id
        (and (not (equal (stype (car (lookup-id id aignet)))
                         :po))
             (not (equal (stype (car (lookup-id id aignet)))
                         :nxst))))

Theorem: fanin-node-p-of-lookup-id

(defthm fanin-node-p-of-lookup-id
        (fanin-node-p (car (lookup-id id aignet))))

Theorem: lookup-id-0

(defthm lookup-id-0
        (equal (lookup-id 0 aignet) nil))

Theorem: lookup-id-in-bounds

(defthm lookup-id-in-bounds
        (iff (consp (lookup-id n aignet))
             (and (< 0 (nfix n))
                  (<= (nfix n) (fanin-count aignet)))))

Theorem: lookup-id-in-bounds-when-positive

(defthm lookup-id-in-bounds-when-positive
        (implies (posp n)
                 (iff (consp (lookup-id n aignet))
                      (<= (nfix n) (fanin-count aignet)))))

Theorem: lookup-id-aignet-extension-p

(defthm lookup-id-aignet-extension-p
        (aignet-extension-p aignet (lookup-id id aignet)))

Theorem: lookup-id-in-extension

(defthm lookup-id-in-extension
        (implies (and (aignet-extension-p new orig)
                      (<= (nfix id) (fanin-count orig)))
                 (equal (lookup-id id new)
                        (lookup-id id orig))))

Theorem: lookup-id-in-extension-inverse

(defthm lookup-id-in-extension-inverse
        (implies (and (aignet-extension-bind-inverse)
                      (<= (nfix id) (fanin-count orig)))
                 (equal (lookup-id id orig)
                        (lookup-id id new))))

Theorem: fanin-count-of-cdr-lookup-bound-by-id

(defthm fanin-count-of-cdr-lookup-bound-by-id
        (implies (consp (lookup-id id aignet))
                 (< (fanin-count (cdr (lookup-id id aignet)))
                    (nfix id)))
        :rule-classes :linear)

Theorem: lookup-id-of-fanin-count-of-suffix

(defthm lookup-id-of-fanin-count-of-suffix
        (implies (and (aignet-extension-p y x)
                      (consp x)
                      (fanin-node-p (car x)))
                 (equal (lookup-id (fanin-count x) y)
                        (node-list-fix x))))

Theorem: true-listp-lookup-id-of-node-listp

(defthm true-listp-lookup-id-of-node-listp
        (implies (node-listp aignet)
                 (true-listp (lookup-id id aignet)))
        :rule-classes :type-prescription)

Theorem: lookup-id-of-nil

(defthm lookup-id-of-nil
        (equal (lookup-id x nil) nil))

Theorem: lookup-id-of-cons

(defthm lookup-id-of-cons
        (equal (lookup-id id (cons node rest))
               (if (and (fanin-node-p node)
                        (equal (nfix id)
                               (+ 1 (fanin-count rest))))
                   (cons (node-fix node)
                         (node-list-fix rest))
                   (lookup-id id rest))))

Theorem: lookup-id-of-fanin-count

(defthm lookup-id-of-fanin-count
        (implies (fanin-node-p (car x))
                 (equal (lookup-id (fanin-count x) x)
                        (node-list-fix x))))

Theorem: fanin-count-of-lookup-id-when-consp

(defthm fanin-count-of-lookup-id-when-consp
        (implies (consp (lookup-id id aignet))
                 (equal (fanin-count (lookup-id id aignet))
                        id)))

Theorem: posp-when-consp-of-lookup-id

(defthm posp-when-consp-of-lookup-id
        (implies (consp (lookup-id id aignet))
                 (posp id))
        :rule-classes :forward-chaining)

Theorem: lookup-id-consp-forward-to-id-bound-nfix

(defthm lookup-id-consp-forward-to-id-bound-nfix
        (implies (and (consp (lookup-id id aignet)))
                 (<= (nfix id) (fanin-count aignet)))
        :rule-classes :forward-chaining)

Theorem: lookup-id-consp-forward-to-id-bound

(defthm lookup-id-consp-forward-to-id-bound
        (implies (and (consp (lookup-id id aignet))
                      (natp id))
                 (<= id (fanin-count aignet)))
        :rule-classes :forward-chaining)

Theorem: lookup-id-out-of-bounds

(defthm lookup-id-out-of-bounds
        (implies (< (fanin-count aignet) (nfix id))
                 (equal (lookup-id id aignet) nil)))