論文の概要: Unambiguity and Fewness for Nonuniform Families of Polynomial-Size
Nondeterministic Finite Automata
- arxiv url: http://arxiv.org/abs/2311.09979v1
- Date: Thu, 16 Nov 2023 15:52:24 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-17 13:39:07.083895
- Title: Unambiguity and Fewness for Nonuniform Families of Polynomial-Size
Nondeterministic Finite Automata
- Title（参考訳）: 多項式サイズ非決定性有限オートマトンの非一様族に対する曖昧性と最小性
- Authors: Tomoyuki Yamakami
- Abstract要約: 非決定論的有限オートマトンは、最大で "one" (曖昧) 、"polynomially many" (fw) の受け入れパス、あるいは各固定された構成につながる計算/関数パスを持つ。
我々はこれらの変種が計算力において互いに異なるという証明が得られていない仮定で証明する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Nonuniform families of polynomial-size finite automata, which are series of
indexed finite automata having polynomially many inner states, are used in the
past literature to solve nonuniform families of promise decision problems.
Among such nonuniform families of finite automata, we focus our attention, in
particular, on the variants of nondeterministic finite automata, which have at
most "one" (unambiguous), "polynomially many" (few) accepting computation
paths, or unambiguous/few computation paths leading to each fixed
configuration. When such machines are limited to make only one-way head moves,
we can prove with no unproven hardness assumptions that some of these variants
are different in computational power from each other. As for two-way machines
restricted to instances of polynomially-bounded length, families of two-way
polynomial-size nondeterministic finite automata are equivalent in power to
families of polynomial-size unambiguous finite automata.
- Abstract（参考訳）: 多項式サイズの有限オートマトン(英語版)の非一様族は、多項式的に多くの内部状態を持つ指数付き有限オートマトン(英語版)の級数である。
有限オートマトン(英語版)の非一様系のうち、特に、最も「一」(曖昧)、「多」(複数)、あるいは各固定構成につながる不明確な/数演算経路を持つ非決定的有限オートマトン(英語版)の変種に着目している。
そのような機械が一方方向の頭の動きだけに制限されている場合、これらの変種が互いに計算力が異なるという証明できない硬さの仮定で証明できる。
多項式有界長のインスタンスに制限された二方向機械について、二方向多項式サイズの非決定論的有限オートマトン族は、多項式サイズの不明確な有限オートマトン族と同値である。
関連論文リスト
- Polynomial Threshold Functions of Bounded Tree-Width: Some Explainability and Complexity Aspects [0.6554326244334868]
多変量体のツリー幅は、ハイパーグラフのツリー幅であり、その項に対応するハイパーエッジを持つ。
有界木幅の符号としてのブール関数の表現はしきい値表現と呼ばれる。
論文 参考訳（メタデータ） (2025-01-14T18:28:08Z) - Fermionic cellular automata in one dimension [72.49909271232748]
フェルミオンモードの一次元鎖に対する量子セルオートマトンを考える。
最寄りのオートマチックの完全なキャラクタリゼーションが与えられる。
論文 参考訳（メタデータ） (2025-01-09T16:22:15Z) - MultiMax: Sparse and Multi-Modal Attention Learning [60.49318008131978]
SoftMaxは現代の機械学習アルゴリズムのユビキタスな成分である。
分散性はSoftMaxの変種族によって達成できるが、それらはしばしば代替損失関数を必要とし、多重モダリティを保たない。
入力入力範囲に応じて出力分布を適応的に変調するMultiMaxを提案する。
論文 参考訳（メタデータ） (2024-06-03T10:51:43Z) - On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
二進体 $mathbbF$ 上の極大族を特徴づける。
我々の発見は、よりオープンないくつかの質問を呼び起こし、この研究の拡張バージョンで対処する予定です。
論文 参考訳（メタデータ） (2024-05-14T16:30:28Z) - Structure of universal formulas [13.794391803767617]
本稿では,大域近似特性と無限VC次元の弱い性質を結合するクラス階層を導入する。
活性化するニューロンの層が1つ以上ある固定サイズニューラルネットワークは任意の有限集合上の関数を近似できないことを示す。
任意の有限集合上の関数を近似する2層ニューラルネットワークを含む関数族を例に挙げるが、定義領域全体においてそれを行うことができない。
論文 参考訳（メタデータ） (2023-11-07T11:50:25Z) - Higher Level Completeness for Permutation Polynomials [0.0]
有限体上の完全置換の概念を一般化し、奇標数体における次数$kge1$への完全性を定義する。
すべての有限体に対する高次完全性の条件を満たす性質の2つの族を構築する。
論文 参考訳（メタデータ） (2023-10-19T04:47:53Z) - An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
有限状態オートマトンをオンザフライで決定する手法の抽象化を確立し, オートマトンにどのように適用できるかを実証する。
我々の発見の特別な例は、多くの非決定論的遷移を持つオートマトンが、ほとんど常に複雑性の決定性を持っていることである。
論文 参考訳（メタデータ） (2023-08-27T11:51:27Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Polymers for Extreme Conditions Designed Using Syntax-Directed
Variational Autoencoders [53.34780987686359]
現在、機械学習ツールは、望まれる特性を持つ材料候補を事実上スクリーニングするために使用される。
このアプローチは非効率であり、人間の想像力が知覚できる候補によって厳しく制約されている。
文法指向の変分オートエンコーダ(VAE)とガウス過程回帰(GPR)モデルを用いて、3つの極端な条件下で頑健なポリマーを発見する。
論文 参考訳（メタデータ） (2020-11-04T21:36:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。