論文の概要: Classical and quantum Merlin-Arthur automata
- arxiv url: http://arxiv.org/abs/2212.13801v1
- Date: Wed, 28 Dec 2022 12:46:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-09 03:36:41.461951
- Title: Classical and quantum Merlin-Arthur automata
- Title(参考訳): 古典的および量子的メルリン・アーサーオートマトン
- Authors: Abuzer Yakary{\i}lmaz
- Abstract要約: メルリン・アーサー決定論、確率論、量子有限状態オートマトンを定義する。
我々はMA-DFAが一定の長さの証明書を使用しており、マルチエントリーDFAと等価であることを示す。
線形長証明書では、MA-PostPFAはカットポイント1/2を持ついくつかの非確率ユニタリ言語を認識できる。
任意に長い証明書で、有界エラーMA-PostQFAはすべての一意決定可能な言語を検証する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce Merlin-Arthur (MA) automata as Merlin provides a single
certificate and it is scanned by Arthur before reading the input. We define
Merlin-Arthur deterministic, probabilistic, and quantum finite state automata
(resp., MA-DFAs, MA-PFAs, MA-QFAs) and postselecting MA-PFAs and MA-QFAs
(resp., MA-PostPFA and MA-PostQFA). We obtain several results using different
certificate lengths.
We show that MA-DFAs use constant length certificates, and they are
equivalent to multi-entry DFAs. Thus, they recognize all and only regular
languages but can be exponential and polynomial state efficient over binary and
unary languages, respectively. With sublinear length certificates, MA-PFAs can
recognize several nonstochastic unary languages with cutpoint 1/2. With linear
length certificates, MA-PostPFAs recognize the same nonstochastic unary
languages with bounded error. With arbitrarily long certificates, bounded-error
MA-PostPFAs verify every unary decidable language. With sublinear length
certificates, bounded-error MA-PostQFAs verify several nonstochastic unary
languages. With linear length certificates, they can verify every unary
language and some NP-complete binary languages. With exponential length
certificates, they can verify every binary language.
- Abstract(参考訳): 我々はMerlin-Arthur Automaticaを紹介し、Merlinは単一の証明書を提供し、入力を読む前にArthurによってスキャンされる。
本稿では,Merlin-Arthurによる決定論的,確率的,量子有限状態オートマトン(Resp.,MA-DFAs,MA-PFA,MA-QFAs)を定義し,MA-PFAsとMA-QFAs(resp.,MA-PostPFA,MA-PostQFAs)をポストセレクトする。
異なる証明書長を用いていくつかの結果を得る。
我々はMA-DFAが一定の長さの証明書を使用することを示す。
したがって、すべての正規言語と正規言語のみを認識できるが、指数関数と多項式状態はそれぞれ二進言語と一進言語よりも効率的である。
線形長証明書では、MA-PFAはカットポイント1/2を持ついくつかの非確率的ユニタリ言語を認識できる。
線形長証明では、MA-PostPFAは同じ非確率的な単言語を有界エラーで認識する。
任意に長い証明書で、有界エラーMA-PostPFAはすべての一意決定可能な言語を検証する。
サブ線形長証明書では、有界エラーMA-PostQFAはいくつかの非確率的ユニタリ言語を検証する。
線形長証明では、すべてのユニタリ言語とNP完全バイナリ言語を検証できる。
指数長証明書を使用すると、すべてのバイナリ言語を検証できる。
関連論文リスト
- OMGEval: An Open Multilingual Generative Evaluation Benchmark for Large
Language Models [59.54423478596468]
OMGEvalは、オープンソースの多言語生成テストセットであり、異なる言語におけるLLMの能力を評価することができる。
各言語について、OMGEvalは804のオープンエンド質問を提供し、LLMの重要な機能を幅広くカバーしている。
具体的には、OMGEvalの現在のバージョンには5つの言語(Zh, Ru, Fr, Es, Ar)が含まれている。
論文 参考訳(メタデータ) (2024-02-21T04:42:41Z) - Extrapolating Large Language Models to Non-English by Aligning Languages [109.09051737966178]
既存の大きな言語モデルは、異なる言語間で異なる能力を示す。
本稿では,言語間のセマンティックアライメントを構築することで,英語以外の言語に事前学習したLLMを強化する。
論文 参考訳(メタデータ) (2023-08-09T13:32:06Z) - ReadMe++: Benchmarking Multilingual Language Models for Multi-Domain
Readability Assessment [13.462025799236816]
自動多言語可読性評価のための大規模言語モデルの体系的研究と包括的評価を行う。
我々は、アラビア語、英語、フランス語、ヒンディー語、ロシア語で9757文の人間のアノテーションを付加した多言語マルチドメインデータセットであるReadMe++を構築した。
実験の結果、ReadMe++で微調整されたモデルは、単一ドメインデータセットでトレーニングされたモデルよりも優れていることがわかった。
論文 参考訳(メタデータ) (2023-05-23T18:37:30Z) - MUTANT: A Multi-sentential Code-mixed Hinglish Dataset [16.14337612590717]
本稿では,多言語記事から多文コード混合テキスト(MCT)を識別する新しいタスクを提案する。
ユースケースとして、多言語の記事を活用し、第一級の多文コード混合Hinglishデータセットを構築します。
MUTANTデータセットは67kの記事と85kのHinglish MCTからなる。
論文 参考訳(メタデータ) (2023-02-23T04:04:18Z) - Adapters for Enhanced Modeling of Multilingual Knowledge and Text [54.02078328453149]
言語モデルは多言語言語モデル(MLLM)に拡張された。
知識グラフは、注意深いキュレーションを必要とし、少数の高リソース言語でのみ利用可能である、明示的な三重形式で事実を含む。
我々は,MLLMを多言語知識グラフ(MLKG)からの知識で拡張し,言語や知識グラフのタスクに多くの言語で取り組むことを提案する。
論文 参考訳(メタデータ) (2022-10-24T21:33:42Z) - Do Multi-Lingual Pre-trained Language Models Reveal Consistent Token
Attributions in Different Languages? [42.47155960879255]
多言語 PLM が異なる言語で一貫したトークン属性を示すかどうかは不明である。
3つの下流タスクにおける広範囲な実験により、多言語 PLM は多言語同義語に大きく異なる属性を割り当てることを示した。
スペイン語は、PLMのトレーニングに使用される際、異なる言語で最も一貫性のあるトークン属性を達成している。
論文 参考訳(メタデータ) (2021-12-23T04:40:06Z) - Prix-LM: Pretraining for Multilingual Knowledge Base Construction [59.02868906044296]
複数言語による知識構築と完成のための統合フレームワークである Prix-LM を提案する。
既存の多言語KBから抽出したモノリンガルトリプルとクロスリンガルリンクの2種類の知識を利用する。
複数の言語におけるリンク予測、言語間リンク、バイリンガル語彙誘導など、標準的なエンティティ関連タスクの実験は、その効果を実証している。
論文 参考訳(メタデータ) (2021-10-16T02:08:46Z) - Multilingual Autoregressive Entity Linking [49.35994386221958]
mGENREはMultilingual Entity Linking問題のためのシーケンス対シーケンスシステムである。
与えられた言語で言及すると、mGENREはターゲットエンティティの名前を左から右へ、トークンごとに予測します。
提案手法の有効性を3つのMELベンチマーク実験を含む広範囲な評価により示す。
論文 参考訳(メタデータ) (2021-03-23T13:25:55Z) - X-FACTR: Multilingual Factual Knowledge Retrieval from Pretrained
Language Models [103.75890012041366]
言語モデル(LM)は、事実の知識を捉えるのに驚くほど成功した。
しかし、LMの実際の表現能力の研究は、ほぼ間違いなく英語で行われている。
我々は23の語型的多様言語に対するクローゼスタイルプローブのベンチマークを作成する。
論文 参考訳(メタデータ) (2020-10-13T05:29:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。