Nested word とは

より具体的にはオートマトンと形式言語理論において、ネストされた単語は、伝統的に線形秩序構造をモデル化するために使用されているように、単語の共同一般化としてAlurとMadhusudanによって提案された概念であり、階層構造。ネストされた単語のための有限状態のアクセプタ、いわゆるネストされた単語オートマトンは、有限オートマトンの一般的な表現を単語に表現します。有限のネストされた単語オートマトンによって受け入れられる言語の線形エンコーディングは、視覚的にプッシュダウン言語のクラスを与える。後者の言語クラスは、規則的言語と決定論的文脈自由言語との間に適切に位置する。 2004年に導入されて以来、これらのコンセプトはその分野で多くの研究を引き起こしました。