論文の概要: On (co-lex) Ordering Automata

• arxiv url: http://arxiv.org/abs/2106.02309v1
• Date: Fri, 4 Jun 2021 07:41:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-08 01:38:11.374166
• Title: On (co-lex) Ordering Automata
• Title（参考訳）: 順序オートマタについて
• Authors: Giovanna D'Agostino and Nicola Cotumaccio and Alberto Policriti and Nicola Prezza
• Abstract要約: 言語Lを受け入れる正準、最小幅、部分的に順序付けられたオートマトンを提示できることを示す。 Hを用いて、言語を認識する最小限のオートマトンから、言語幅を効果的に計算できることを証明する。
• 参考スコア（独自算出の注目度）: 2.800608984818919
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted by A. But words can be ordered and among the many possible orders a very natural one is the co-lexicographic one. Such naturalness stems from the fact that it suggests a transfer of the order from words to the automaton's states. In a number of papers automata admitting a total ordering of states coherent with the ordering of the set of words reaching them have been proposed. Such class of ordered automata -- the Wheeler automata -- turned out to be efficiently stored/searched using an index. Unfortunately not all automata can be totally ordered as previously outlined. However, automata can always be partially ordered and an intrinsic measure of their complexity can be defined and effectively determined, as the minimum width of one of their admissible partial orders. As shown in previous works, this new concept of width of an automaton has useful consequences in the fields of graph compression, indexing data structures, and automata theory. In this paper we prove that a canonical, minimum-width, partially-ordered automaton accepting a language L -- dubbed the Hasse automaton H of L -- can be exhibited. H provides, in a precise sense, the best possible way to (partially) order the states of any automaton accepting L, as long as we want to maintain an operational link with the (co-lexicographic) order of Pf(L(A)). Using H we prove that the width of the language can be effectively computed from the minimum automaton recognizing the language. Finally, we explore the relationship between two (often conflicting) objectives: minimizing the width and minimizing the number of states of an automaton.
• Abstract（参考訳）: 決定論的有限オートマトンaの状態は、pf(l(a)) における単語の集合と同一視することができる。 しかし、単語は順序付け可能であり、多くの可能な順序のうち、非常に自然なものは共辞書である。 このような自然性は、単語からオートマトンの状態への順序の移動を示唆するという事実に由来する。 多くの論文において、それらに到達する単語の集合の順序と整合した状態の総順序を認めるオートマトンが提案されている。 このような順序付きオートマトン -- ウィーラーオートマトン -- のクラスは、インデックスを使用して効率的に保存/検索されることが判明した。 残念ながら、すべてのオートマトンを前述したように完全に順序付けできるわけではない。 しかし、オートマトンは常に部分的に順序付けでき、その複雑さの本質的な測度は、許容される部分順序の1つの最小幅として定義し、効果的に決定することができる。 前述したように、オートマトンの幅という新しい概念は、グラフ圧縮、データ構造のインデックス化、オートマトン理論の分野において有用な結果をもたらす。 本稿では、lのhasse automaton hと呼ばれる言語を受容する標準的で最小幅、半順序のオートマトンを提示できることを実証する。 H は、正確には、Pf(L(A)) の (co-lexicographic) 順序との (co-lexicographic) 操作リンクを維持したい限り、任意のオートマトンが L を受け入れる状態を(部分的に)順序付ける最良の方法である。 hを用いて、言語を認識できる最小のオートマトンから言語の幅を効果的に計算できることを証明する。 最後に、幅を最小化し、オートマトンの状態数を最小化する2つの目標(しばしば矛盾する)の関係について検討する。

関連論文リスト

• Learning Weighted Finite Automata over the Max-Plus Semiring and its Termination [2.024925013349319]
  最大余剰半環上での重み付きオートマトンに対するL*型学習アルゴリズムについて検討した。 表の整合性の維持に失敗する可能性を示し、従って、明らかに間違った仮説オートマトン上で等価なクエリを作成できることを示す。
  論文  参考訳（メタデータ） (2024-07-13T05:08:06Z)
• Counting Reward Automata: Sample Efficient Reinforcement Learning Through the Exploitation of Reward Function Structure [13.231546105751015]
  本稿では,形式言語として表現可能な任意の報酬関数をモデル化可能な有限状態機械変種であるカウント・リワード・オートマトンを提案する。 このような抽象機械を組み込んだエージェントが,現在の手法よりも大きなタスクの集合を解くことができることを実証する。
  論文  参考訳（メタデータ） (2023-12-18T17:20:38Z)
• Automata Cascades: Expressivity and Sample Complexity [90.53326983143644]
  カスケードは、それらのコンポーネントの観点から、オートマトンにおけるサンプルの複雑さを記述することができることを示す。 以上の結果から、無限入力アルファベットと、利用可能なデータ量で指数関数的な多数の状態を持つオートマトンを原理的に学習できることが示唆された。
  論文  参考訳（メタデータ） (2022-11-25T11:02:33Z)
• Automatic Label Sequence Generation for Prompting Sequence-to-sequence Models [105.4590533269863]
  完全自動プロンプト方式であるAutoSeqを提案する。 我々はシーケンス・ツー・シーケンス・モデルに自然言語プロンプトを採用する。 本手法は,数ショット学習におけるシーケンス・ツー・シーケンスモデルの可能性を明らかにする。
  論文  参考訳（メタデータ） (2022-09-20T01:35:04Z)
• On the Intersection of Context-Free and Regular Languages [71.61206349427509]
  我々はBar-Hillel構造を一般化し、$varepsilon$-arcsで有限状態オートマトンを扱う。 我々の構成が入力オートマトンと文法の両方の構造を符号化し、元の構成のサイズを維持した文法につながることを証明している。
  論文  参考訳（メタデータ） (2022-09-14T17:49:06Z)
• Alternating Good-for-MDP Automata [4.429642479975602]
  良質MDP(GFM)B"uchiautoaを用いて、悪質MDP(GFM)オートマトンを修復できることを示す。 非決定論的ラビンやB'uchiオートマトンへの翻訳は、ターゲットオートマトンをMDPの良さを必要とせずとも、指数的なコストがかかる。 意外な答えは、MDPプロパティを交代オートマトンに拡張する際には、はるかに少なめに支払わなければならないということです。
  論文  参考訳（メタデータ） (2022-05-06T14:01:47Z)
• Induction and Exploitation of Subgoal Automata for Reinforcement Learning [75.55324974788475]
  本稿では,Regressed Learning (RL)タスクにおけるサブゴールの学習と活用のためのISAを提案する。 ISAは、タスクのサブゴールによってエッジがラベル付けされたオートマトンであるサブゴールオートマトンを誘導することで強化学習をインターリーブする。 サブゴールオートマトンはまた、タスクの完了を示す状態と、タスクが成功せずに完了したことを示す状態の2つの特別な状態で構成されている。
  論文  参考訳（メタデータ） (2020-09-08T16:42:55Z)
• Ambiguity Hierarchy of Regular Infinite Tree Languages [77.34726150561087]
  言語が k アンビグラス (k アンビグラス) であれば、言語は k アンビグラス (k アンビグラスオートマトン) である。 オートマトンは k が mathbbN$ の約 $k に対して曖昧であれば有界不明瞭である。
  論文  参考訳（メタデータ） (2020-09-07T10:08:24Z)
• Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
  本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。 計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
  論文  参考訳（メタデータ） (2020-05-05T12:10:21Z)

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

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