Fugu-MT 論文翻訳(概要): An Analysis of On-the-fly Determinization of Finite-state Automata

論文の概要: An Analysis of On-the-fly Determinization of Finite-state Automata

arxiv url: http://arxiv.org/abs/2308.14077v1
Date: Sun, 27 Aug 2023 11:51:27 GMT
ステータス: 処理完了
システム内更新日: 2023-08-29 17:04:38.909546
Title: An Analysis of On-the-fly Determinization of Finite-state Automata
Title（参考訳）: 有限状態オートマトンにおけるオンザフライ決定の解析
Authors: Ivan Baburin and Ryan Cotterell
Abstract要約: 有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
参考スコア（独自算出の注目度）: 65.268245109828
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper we establish an abstraction of on-the-fly determinization of finite-state automata using transition monoids and demonstrate how it can be applied to bound the asymptotics. We present algebraic and combinatorial properties that are sufficient for a polynomial state complexity of the deterministic automaton constructed on-the-fly. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of polynomial complexity. Furthermore, we extend our ideas to weighted finite-state automata.
Abstract（参考訳）: 本稿では,遷移モノイドを用いた有限状態オートマタのオンザフライ決定の抽象化を確立し,漸近関数のバウンドにどのように適用できるかを示す。決定論的オートマトンをオンザフライで構築した多項式状態の複雑性に十分である代数的および組合せ的特性を示す。本研究の特別なケースは,非決定論的遷移が多数存在するオートマトンが多項式複雑性の決定をほぼ常に認めている点である。さらに,重み付き有限状態オートマトンへの拡張も行う。

関連論文リスト

Complexity-constrained quantum thermodynamics [0.2796197251957244]
任意の状態のリセットに必要な最小の熱力学的作業は、複雑性に制約のあるプロセスを通じて、状態の複雑性エントロピーによって定量化されることを示す。複雑性エントロピーは、作業コストと状態を再セットする複雑性コストの間のトレードオフを定量化する。複雑性エントロピーの情報理論的応用を同定する。
論文参考訳（メタデータ） (2024-03-07T19:00:01Z)
Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata [0.0]
非決定論的有限オートマトンは、最大で "one" (曖昧) 、"polynomially many" (fw) の受け入れパス、あるいは各固定された構成につながる計算/関数パスを持つ。我々はこれらの変種が計算力において互いに異なるという証明が得られていない仮定で証明する。
論文参考訳（メタデータ） (2023-11-16T15:52:24Z)
Edge of entanglement in non-ergodic states: a complexity parameter formulation [0.0]
非エルゴード純状態の絡み合いエントロピーのサブシステムサイズスケーリングを分析する。複雑性パラメータの再スケーリングは、幅広い純粋な非エルゴード状態の絡み合いエントロピーの臨界状態を特定するのに役立つ。
論文参考訳（メタデータ） (2023-10-19T14:52:43Z)
Universality of critical dynamics with finite entanglement [68.8204255655161]
臨界近傍の量子系の低エネルギー力学が有限絡みによってどのように変化するかを研究する。その結果、時間依存的臨界現象における絡み合いによる正確な役割が確立された。
論文参考訳（メタデータ） (2023-01-23T19:23:54Z)
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。アルファベットのサイズについては、定値対分離の複雑さがある。
論文参考訳（メタデータ） (2023-01-22T22:08:28Z)
Circuit Complexity through phase transitions: consequences in quantum state preparation [0.0]
量子多体系の基底状態を作成するための回路の複雑さを解析する。特に、基底状態が量子相転移に近づくにつれて、この複雑さがどのように成長するか。
論文参考訳（メタデータ） (2023-01-11T19:00:10Z)
Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
論文参考訳（メタデータ） (2021-06-23T16:33:33Z)
Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
時間に依存しない深さの量子回路を生成するための構成的アルゴリズムを提案する。一次元横フィールドXYモデルにおけるアンダーソン局在化を含む、モデルの特殊クラスに対するアルゴリズムを強調する。幅広いスピンモデルとフェルミオンモデルに対して正確な回路を提供するのに加えて、我々のアルゴリズムは最適なハミルトニアンシミュレーションに関する幅広い解析的および数値的な洞察を提供する。
論文参考訳（メタデータ） (2021-04-01T19:06:00Z)
The Variational Method of Moments [65.91730154730905]
条件モーメント問題は、観測可能量の観点から構造因果パラメータを記述するための強力な定式化である。 OWGMMの変動最小値再構成により、条件モーメント問題に対する非常に一般的な推定器のクラスを定義する。同じ種類の変分変換に基づく統計的推測のためのアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-12-17T07:21:06Z)
On the Complexity of Symbolic Finite-State Automata [7.386725677365395]
我々は,SFAの手順(交点,空白など)の複雑さを再考し,象徴的オートマトンに適した措置に従って分析する。我々は SFA の特殊形式、正規化された SFA ときちんとした SFA 、および単調有効ブール代数上の SFA に注意を払う。
論文参考訳（メタデータ） (2020-11-10T20:55:55Z)

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