論文の概要: The Krohn-Rhodes Logics
- arxiv url: http://arxiv.org/abs/2304.09639v1
- Date: Wed, 19 Apr 2023 13:24:04 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-20 14:22:37.600326
- Title: The Krohn-Rhodes Logics
- Title(参考訳): Krohn-Rhodes論理
- Authors: Alessandro Ronca
- Abstract要約: パストはフリップフロップと呼ばれるある種類の素数オートマトンのカスケードに対応することを示す。
本稿では,他の素数オートマトンを捕捉し,したがって過去の表現性を拡張できる新しい時間演算子を提案する。
- 参考スコア(独自算出の注目度): 94.11680944837197
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We present a new family of modal temporal logics of the past, obtained by
extending Past LTL with a rich set of temporal operators based on the theory by
Krohn and Rhodes for automata cascades. The theory says that every automaton
can be expressed as a cascade of some basic automata called prime automata.
They are the building blocks of all automata, analogously to prime numbers
being the building blocks of all natural numbers. We show that Past LTL
corresponds to cascades of one kind of prime automata called flip-flops. In
particular, the temporal operators of Past LTL are captured by flip-flops, and
they cannot capture any other prime automaton, confining the expressivity
within the star-free regular languages. We propose novel temporal operators
that can capture other prime automata, and hence extend the expressivity of
Past LTL. Such operators are infinitely-many, and they yield an infinite number
of logics capturing an infinite number of distinct fragments of the regular
languages. The result is a yet unexplored landscape of extensions of Past LTL,
that we call Krohn-Rhodes Logics, each of them with the potential of matching
the expressivity required by specific applications.
- Abstract(参考訳): 我々は,過去におけるモーダル時間論理の新たな族を,Krohn と Rhodes による自動カスケードの理論に基づくテンポラル作用素のリッチな集合による past LTL を拡張して得られる。
理論によれば、全てのオートマトンは素オートマトンと呼ばれる基本的なオートマトンのカスケードとして表現できる。
これらはすべてのオートマトンの構成要素であり、すべての自然数の構成要素である素数と類似している。
過去のltlはflip-flopsと呼ばれる1種類の素オートマタのカスケードに対応している。
特に、過去LTLの時間演算子はフリップフロップによって捕捉され、他の素数オートマトンを捕捉することはできず、星のない正規言語での表現性を補う。
我々は,他の素オートマトンを捕捉し,それゆえ過去のltlの表現性を拡張できる新しい時間演算子を提案する。
そのような作用素は無限多量であり、正規言語の無限個の異なる断片をキャプチャする無限個の論理を生成する。
その結果は、まだ探索されていない過去LTLの拡張の風景であり、Krohn-Rhodes Logics と呼び、それぞれが特定のアプリケーションで要求される表現性に一致する可能性がある。
関連論文リスト
- Large Language Models as General Pattern Machines [64.75501424160748]
我々は,事前訓練された大規模言語モデル (LLM) が,複雑なトークンシーケンスを自動回帰的に完了することを示す。
驚いたことに、語彙からランダムにサンプリングされたトークンを用いてシーケンスが表現された場合でも、パターン完了の習熟度を部分的に保持することができる。
本研究では,ロボット工学における問題に対して,これらのゼロショット機能がどのように適用されるかを検討する。
論文 参考訳(メタデータ) (2023-07-10T17:32:13Z) - Automata Cascades: Expressivity and Sample Complexity [90.53326983143644]
カスケードは、それらのコンポーネントの観点から、オートマトンにおけるサンプルの複雑さを記述することができることを示す。
以上の結果から、無限入力アルファベットと、利用可能なデータ量で指数関数的な多数の状態を持つオートマトンを原理的に学習できることが示唆された。
論文 参考訳(メタデータ) (2022-11-25T11:02:33Z) - On the Intersection of Context-Free and Regular Languages [71.61206349427509]
我々はBar-Hillel構造を一般化し、$varepsilon$-arcsで有限状態オートマトンを扱う。
我々の構成が入力オートマトンと文法の両方の構造を符号化し、元の構成のサイズを維持した文法につながることを証明している。
論文 参考訳(メタデータ) (2022-09-14T17:49:06Z) - A Sahlqvist-style Correspondence Theorem for Linear-time Temporal Logic [10.029813712651471]
線形時間時間時間論理(LTL)のためのShlqvist型対応定理を開発する。
モーダル作用素 F, G, X, U を用いて構築されたサルクヴィスト公式の有意なクラスを同定する。
本論文の主な成果は、一階言語で定義可能なフレーム条件に対するソルクヴィスト公式の対応性を証明することである。
論文 参考訳(メタデータ) (2022-06-13T08:36:13Z) - On (co-lex) Ordering Automata [2.800608984818919]
言語Lを受け入れる正準、最小幅、部分的に順序付けられたオートマトンを提示できることを示す。
Hを用いて、言語を認識する最小限のオートマトンから、言語幅を効果的に計算できることを証明する。
論文 参考訳(メタデータ) (2021-06-04T07:41:58Z) - Learning a natural-language to LTL executable semantic parser for
grounded robotics [18.273615074415922]
子どもたちは、言語が文脈でどのように使われているかを観察し、それを自分自身で使おうとすることによって、明らかな容易さで母国語を習得する。
我々は、自然言語コマンドの実行に使用できる潜伏した言語表現を発見する、接地型セマンティック再構成を訓練することで、同じことができるロボットに向けて一歩前進する。
私たちのモデルは、文と実行のペアとエグゼキュータで訓練されています。
論文 参考訳(メタデータ) (2020-08-07T17:28:32Z) - Glushkov's construction for functional subsequential transducers [91.3755431537592]
グルシコフの構成は多くの興味深い性質を持ち、トランスデューサに適用するとさらに明らかになる。
正規表現の特別な風味を導入し、効率よく$epsilon$-free 機能的次数重み付き有限状態トランスデューサに変換することができる。
論文 参考訳(メタデータ) (2020-08-05T17:09:58Z) - Towards Metric Temporal Answer Set Programming [3.463142129350435]
我々は、前者と同じセマンティック基盤に基づいて論理を開発し、従って境界時間ステップのシンプルな時間領域を使用する。
これにより、統一フレームワークにおけるすべての変種を比較し、最終的にそれらを共通の実装で組み合わせることができます。
論文 参考訳(メタデータ) (2020-08-05T10:30:14Z) - Superposition for Lambda-Free Higher-Order Logic [62.997667081978825]
本稿では,意図的および拡張的クラス数$lambda$-free高階論理に対して,難解な完全重ね合わせ計算を導入する。
計算は完全単調でなくてもよい項順でパラメタ化され、$lambda$フリーの高次語彙パスとKnuth-Bendixの順序を使うことができる。
論文 参考訳(メタデータ) (2020-05-05T12:10:21Z) - On the Linguistic Capacity of Real-Time Counter Automata [1.8072051868187933]
リアルタイムカウンターマシンの能力を形式文法として研究する。
対向言語は補数、和、交叉、その他多くの共通集合演算の下で閉じていることを示す。
この研究は、リカレントニューラルネットワークを理解することに興味のある形式言語理論に一般的な貢献をする。
論文 参考訳(メタデータ) (2020-04-15T03:37:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。