Visibly Pushdown Automaton (VPA) nested wordをアクセプトするオートマトンをnested wordオートマトンという。VPAはnested wordオートマトンと等価な普通の(nested wordでない)語を受理するオートマトン。 nested wordオートマトンと関係がありそうだなあ……

Nested word 直感的には、XMLのような構造や、callイベントやretイベントを持つトレースをイメージすると良いかと. 定義 アルファベット上の長さのnested wordは組として定義される。ここで、は長さの上の語で、は長さのマッチング関係である。 マッチング関…