論文の概要: Ambiguity Hierarchy of Regular Infinite Tree Languages
- arxiv url: http://arxiv.org/abs/2009.02985v3
- Date: Wed, 11 Aug 2021 18:36:38 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-21 03:15:54.023283
- Title: Ambiguity Hierarchy of Regular Infinite Tree Languages
- Title（参考訳）: 正規無限木言語のあいまいさ階層
- Authors: Alexander Rabinovich and Doron Tiferet
- Abstract要約: 言語が k アンビグラス (k アンビグラス) であれば、言語は k アンビグラス (k アンビグラスオートマトン) である。
オートマトンは k が mathbbN$ の約 $k に対して曖昧であれば有界不明瞭である。
- 参考スコア（独自算出の注目度）: 77.34726150561087
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: An automaton is unambiguous if for every input it has at most one accepting
computation. An automaton is k-ambiguous (for k > 0) if for every input it has
at most k accepting computations. An automaton is boundedly ambiguous if it is
k-ambiguous for some $k \in \mathbb{N}$. An automaton is finitely
(respectively, countably) ambiguous if for every input it has at most finitely
(respectively, countably) many accepting computations.
The degree of ambiguity of a regular language is defined in a natural way. A
language is k-ambiguous (respectively, boundedly, finitely, countably
ambiguous) if it is accepted by a k-ambiguous (respectively, boundedly,
finitely, countably ambiguous) automaton. Over finite words every regular
language is accepted by a deterministic automaton. Over finite trees every
regular language is accepted by an unambiguous automaton. Over $\omega$-words
every regular language is accepted by an unambiguous B\"uchi automaton and by a
deterministic parity automaton. Over infinite trees Carayol et al. showed that
there are ambiguous languages.
We show that over infinite trees there is a hierarchy of degrees of
ambiguity: For every k > 1 there are k-ambiguous languages that are not k - 1
ambiguous; and there are finitely (respectively countably, uncountably)
ambiguous languages that are not boundedly (respectively finitely, countably)
ambiguous.
- Abstract（参考訳）: オートマトンは、全ての入力に対して少なくとも1つの計算を受け入れている場合、曖昧である。
オートマトンが k-曖昧 (k > 0) であるとは、すべての入力に対して少なくとも k が計算を受け付けることを言う。
オートマトンは、ある$k \in \mathbb{N}$に対して k-曖昧であれば有界不明瞭である。
オートマトンが有限に(可算的に)あいまいであることは、すべての入力が最大有限に(可算的に)多くの計算を受け付けることである。
正規言語の曖昧さの度合いは自然な方法で定義される。
言語がk曖昧(可算、可算、可算、可算)であるとは、それがk曖昧(可算、可算、可算、可算、可算)オートマトンによって受け入れられることである。
有限語上、すべての正規言語は決定論的オートマトンによって受け入れられる。
有限木上のすべての正規言語はあいまいなオートマトンによって受け入れられる。
$\omega$-words以上の正規言語は、曖昧なB\「uchi」オートマトンと決定論的パリティオートマトンによって受け入れられる。
無限木上のカライオールらはあいまいな言語が存在することを示した。
すべての k > 1 に対して、k - 1 のあいまいでない k-あいまいな言語が存在し、有限(数えきれないほど、数えきれないほどに)あいまいな言語が有界でない(振り返ってみれば、数え切れないほど)あいまいな言語が存在する。
関連論文リスト
- Directed Regular and Context-Free Languages [0.6906005491572399]
言語$L$は、$L$のすべての単語が$L$の共通の(散在した)スーパーワードを持っている場合、emphdirectedされる。
文脈自由言語では、有向性問題はcoNEXP完全であることが知られている。
文脈自由言語では、有向性問題はPSPACE完全であることを示す。
論文 参考訳（メタデータ） (2024-01-13T16:13:45Z) - Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
論文 参考訳（メタデータ） (2023-10-23T18:26:00Z) - Lexinvariant Language Models [84.2829117441298]
離散語彙記号から連続ベクトルへの写像であるトークン埋め込みは、任意の言語モデル(LM)の中心にある
我々は、語彙記号に不変であり、したがって実際に固定トークン埋め込みを必要としないテクスチトレキシン変種モデルについて研究する。
十分長い文脈を条件として,レキシン変項LMは標準言語モデルに匹敵する難易度が得られることを示す。
論文 参考訳（メタデータ） (2023-05-24T19:10:46Z) - The boundaries of meaning: a case study in neural machine translation [0.0]
2016年以降、サブワードセグメンテーションアルゴリズムは言語モデリング、機械翻訳、その他のタスクに広く利用されている。
これらのアルゴリズムは、しばしば単語を「時代」、「on」、「t」、「ist」といった意味的に不透明なものに切り分ける。
論文 参考訳（メタデータ） (2022-10-02T20:26:20Z) - On the Intersection of Context-Free and Regular Languages [71.61206349427509]
我々はBar-Hillel構造を一般化し、$varepsilon$-arcsで有限状態オートマトンを扱う。
我々の構成が入力オートマトンと文法の両方の構造を符号化し、元の構成のサイズを維持した文法につながることを証明している。
論文 参考訳（メタデータ） (2022-09-14T17:49:06Z) - On (co-lex) Ordering Automata [2.800608984818919]
言語Lを受け入れる正準、最小幅、部分的に順序付けられたオートマトンを提示できることを示す。
Hを用いて、言語を認識する最小限のオートマトンから、言語幅を効果的に計算できることを証明する。
論文 参考訳（メタデータ） (2021-06-04T07:41:58Z) - Language learnability in the limit for general metrics: a Gold-Angluin
result [91.3755431537592]
我々は、blum and blum (1975) によるniyogi の拡張版の定理を用いて、任意の計量における任意の言語族の極限における学習可能性に必要な条件を証明している。
言語ファミリーがさらにすべての有限言語を含むと仮定すると、同じ条件は限界における学習可能性にも十分になる。
論文 参考訳（メタデータ） (2021-03-24T13:11:09Z) - RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。
Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。
明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文 参考訳（メタデータ） (2020-10-15T04:42:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。