論文の概要: The single-use restriction for register automata and transducers over infinite alphabets

• arxiv url: http://arxiv.org/abs/2406.18934v1
• Date: Thu, 27 Jun 2024 07:01:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-28 14:57:01.178826
• Title: The single-use restriction for register automata and transducers over infinite alphabets
• Title（参考訳）: 無限アルファベット上のレジスタオートマトンとトランスデューサの単一使用制限
• Authors: Rafał Stefański,
• Abstract要約: 無限アルファベット上のレジスタオートマトンとトランスデューサの単一使用制限について検討する。 オートマトンモデルでは、一方のレジスタオートマトン、両側のレジスタオートマトン、軌道上の有限なモノイドが同じ表現力を持つことを示す。 トランスデューサモデルでは、単用ミーリーマシンと単用双方向トランスデューサがクローン・ローデス分解定理のバージョンを認めていることを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This thesis studies the single-use restriction for register automata and transducers over infinite alphabets. The restriction requires that a read-access to a register should have the side effect of destroying its contents. This constraint results in robust classes of languages and transductions. For automata models, we show that one-way register automata, two-way register automata, and orbit-finite monoids have the same expressive power. For transducer models, we show that single-use Mealy machines and single-use two-way transducers admit versions of the Krohn-Rhodes decomposition theorem. Moreover, single-use Mealy machines are equivalent to an algebraic model called local algebraic semigroup transductions. Additionally, we show that single-use two-way transducers are equivalent to single-use streaming string transducers (SSTs) over infinite alphabets and to regular list functions with atoms. Compared with the previous work arXiv:1907.10504, this thesis offers a coherent narrative on the single-use restriction. We introduce an abstract notion of single-use functions and use them to define all the discussed single-use models. We also introduce and study the algebraic models of local semigroup transduction and local rational semigroup transduction.
• Abstract（参考訳）: この論文は、無限アルファベット上のレジスタオートマトンとトランスデューサの単一使用制限を研究する。 この制限は、レジスタへの読み取りアクセスがその内容を破壊する副作用を持つべきである。 この制約は、言語とトランスダクションの堅牢なクラスをもたらす。 オートマトンモデルでは、一方のレジスタオートマトン、両側のレジスタオートマトン、軌道上の有限なモノイドが同じ表現力を持つことを示す。 トランスデューサモデルでは、単用ミーリーマシンと単用双方向トランスデューサがクローン・ローデス分解定理のバージョンを認めていることを示す。 さらに、シングルユース・ミーリーマシンは局所代数的半群変換と呼ばれる代数的モデルと等価である。 さらに、単一用途の双方向トランスデューサは、無限アルファベット上のシングルユースストリーミング文字列トランスデューサ(SST)と、原子を持つ正規リスト関数と等価であることを示す。 以前の『arXiv:1907.10504』と比較すると、この論文は単一使用制限に関する一貫性のある物語を提供する。 シングルユース関数の抽象概念を導入し、それらを用いて、議論されたシングルユースモデルを全て定義する。 また、局所半群変換と局所有理半群変換の代数モデルを導入・研究する。

関連論文リスト

• Protocols for Creating Anyons and Defects via Gauging [0.0]
  非アベリア・エノンのリボン作用素と対称性欠陥を実装する物理プロトコルを提供する。 これを、$mathbbZ_3$トーリック符号と$S_3$量子倍の値で示す。
  論文  参考訳（メタデータ） (2024-11-06T19:00:01Z)
• Autoregressive Speech Synthesis without Vector Quantization [135.4776759536272]
  テキストから音声合成(TTS)のための新しい連続値トークンに基づく言語モデリング手法であるMELLEを提案する。 MELLEはテキスト条件から直接連続メル-スペクトログラムフレームを自動回帰生成する。
  論文  参考訳（メタデータ） (2024-07-11T14:36:53Z)
• Complex Event Recognition with Symbolic Register Transducers: Extended Technical Report [51.86861492527722]
  本稿では,オートマトンに基づく複合イベント認識システムを提案する。 本システムは,記号とレジスタオートマトンを組み合わせたオートマトンモデルに基づいている。 我々は、イベントストリーム上のパターンを検出するために、SRTをCERでどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2024-07-03T07:59:13Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Analyzing Transformers in Embedding Space [59.434807802802105]
  学習したトランスフォーマーの全てのパラメータを埋め込み空間に投影することで解釈する理論解析を提案する。 予め訓練されたモデルと微調整されたモデルの両方のパラメータを埋め込み空間で解釈できることを示す。 我々の発見は、少なくとも部分的には、モデル仕様から抽象化し、埋め込み空間でのみ動作する解釈手法への扉を開く。
  論文  参考訳（メタデータ） (2022-09-06T14:36:57Z)
• Building Qutrit Diagonal Gates from Phase Gadgets [0.0]
  本稿では、元の(量子)ZX-計算に近づいた書き直しを可能にする、元のキュートリットZX-計算のフレキシブルな変種を示す。 そこで我々は,量子ビットのグラフィカルフーリエ理論を拡張するために,新たな量子ビット固有のトリックを考案した。 両タイプの制御が任意の量子ビットZまたはX相ゲートに対してどのように実装され、アンシラフリーであり、クリフォードと位相ゲートのみを用いるかを示す。
  論文  参考訳（メタデータ） (2022-04-28T17:44:40Z)
• Compressing Many-Body Fermion Operators Under Unitary Constraints [0.6445605125467573]
  本稿では,2体演算子の単一粒子基底変換に匹敵する複雑性を有する因子分解を行う数値アルゴリズムを提案する。 この数値計算法の適用例として,汎用ユニタリクラスタ演算子を近似するために,我々のプロトコルが利用できることを示す。
  論文  参考訳（メタデータ） (2021-09-10T17:42:18Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• Glushkov's construction for functional subsequential transducers [91.3755431537592]
  グルシコフの構成は多くの興味深い性質を持ち、トランスデューサに適用するとさらに明らかになる。 正規表現の特別な風味を導入し、効率よく$epsilon$-free 機能的次数重み付き有限状態トランスデューサに変換することができる。
  論文  参考訳（メタデータ） (2020-08-05T17:09:58Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。