論文の概要: The Image of the Process Interpretation of Regular Expressions is Not Closed under Bisimulation Collapse

• arxiv url: http://arxiv.org/abs/2303.08553v2
• Date: Sun, 12 Nov 2023 12:52:31 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-14 22:18:09.301593
• Title: The Image of the Process Interpretation of Regular Expressions is Not Closed under Bisimulation Collapse
• Title（参考訳）: 正規表現のプロセス解釈のイメージは、バイシミュレーション崩壊下で閉じていない
• Authors: Clemens Grabmayer
• Abstract要約: 0 が得られれば 1 の付加的な存在から生じる現象について報告する。 1自由正規表現の解釈はバイシミュレーション崩壊の下で閉じるが、任意の正規表現の解釈ではそうではない。 1-transitions と LEE' を持つプロセスグラフに精製できるプロセスグラフの特性は、バイシミュレート崩壊下では保存されないことを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Axiomatization and expressibility problems for Milner's process semantics (1984) of regular expressions modulo bisimilarity have turned out to be difficult for the full class of expressions with deadlock 0 and empty step~1. We report on a phenomenon that arises from the added presence of 1 when 0 is available, and that brings a crucial reason for this difficulty into focus. To wit, while interpretations of 1-free regular expressions are closed under bisimulation collapse, this is not the case for the interpretations of arbitrary regular expressions. Process graph interpretations of 1-free regular expressions satisfy the loop existence and elimination property LEE, which is preserved under bisimulation collapse. These features of LEE were applied for showing that an equational proof system for 1-free regular expressions modulo bisimilarity is complete, and that it is decidable in polynomial time whether a process graph is bisimilar to the interpretation of a 1-free regular expression. While interpretations of regular expressions do not satisfy the property LEE in general, we show that LEE can be recovered by refined interpretations as graphs with 1-transitions refined interpretations with 1-transitions (which are similar to silent steps for automata). This suggests that LEE can be expedient also for the general axiomatization and expressibility problems. But a new phenomenon emerges that needs to be addressed: the property of a process graph `to can be refined into a process graph with 1-transitions and with LEE' is not preserved under bisimulation collapse. We provide a 10-vertex graph with two 1-transitions that satisfies LEE, and in which a pair of bisimilar vertices cannot be collapsed on to each other while preserving the refinement property. This implies that the image of the process interpretation of regular expressions is not closed under bisimulation collapse.
• Abstract（参考訳）: milner's process semantics (1984) の正規表現の公理化と表現可能性問題は、デッドロック 0 と空のステップ~1 を持つ式の全クラスでは困難であることが判明した。 我々は、0 が利用可能になったときに 1 の追加の存在から生じる現象を報告し、この困難に焦点をあてる重要な理由について報告する。 ウィットにとって、1自由正規表現の解釈は二乗の崩壊下で閉じられているが、任意の正規表現の解釈はそうではない。 1-自由正規表現のプロセスグラフ解釈は、二相崩壊下で保存されるループの存在と除去性 LEE を満たす。 リーのこれらの特徴は、1自由正規表現に対する方程式証明系が完備であること、およびプロセスグラフが1自由正規表現の解釈と双類似であるかどうかを多項式時間で決定可能であることを示すために適用された。 正規表現の解釈は一般には LEE の性質を満たすものではないが、LEE は 1-遷移を持つグラフ(これはオートマチックのサイレントステップに似ている)の洗練された解釈によって復元可能であることを示す。 これはリーが一般の公理化や表現可能性問題にも期待できることを示唆している。 プロセスグラフの「to」の性質は、1-transitions と LEE を持つプロセスグラフに洗練され、バイシミュレーションの崩壊の下では保存されない。 リーを満たす2つの1-遷移を持つ10-バーテックスグラフを提供し、精細性を維持しつつ2つの相似頂点を互いに崩壊させることができないようにする。 このことは、正規表現のプロセス解釈のイメージがバイシミュレーション崩壊の下で閉じていないことを意味する。

関連論文リスト

• Sequence graphs realizations and ambiguity in language models [1.4732811715354455]
  計算的観点から,シーケンスグラフの実現可能性とあいまいさについて検討する。 大きさが 3 の窓に対して、w が定数であるとしても、すべての不変量の硬さを証明する。 本稿では、実現可能性問題を解く整数プログラムと、列挙問題の解法を動的プログラミングで結論付ける。
  論文  参考訳（メタデータ） (2024-02-13T22:22:51Z)
• Maieutic Prompting: Logically Consistent Reasoning with Recursive Explanations [71.2950434944196]
  ノイズや一貫性のない言語モデルでさえも問題に対する正しい答えを推測するMaieutic Promptingを開発する。 Maieutic Promptingは最先端のプロンプト法よりも最大20%精度が高い。
  論文  参考訳（メタデータ） (2022-05-24T06:36:42Z)
• Does BERT really agree ? Fine-grained Analysis of Lexical Dependence on a Syntactic Task [70.29624135819884]
  目的の構文テンプレート上で,BERTが語彙非依存の主観値数アグリーメント(NA)を実行できる範囲について検討した。 名詞文では,単純なテンプレートに対してモデルがよく一般化されるが,1つのアトラクターが存在する場合,語彙非依存の構文一般化を行うことができないことが示唆された。
  論文  参考訳（メタデータ） (2022-04-14T11:33:15Z)
• Abstract Interpretation on E-Graphs [2.1700203922407497]
  本稿では,電子グラフに対する抽象解釈の適用について考察し,電子グラフ内では,抽象領域に関連する格子整合演算がeクラスの自然な解釈を持つことを示す。 この拡張抽象論では、この点を説明するのにInterval Arithmetic (IA) を用いる。
  論文  参考訳（メタデータ） (2022-03-17T09:29:44Z)
• Implicit Regularization in ReLU Networks with the Square Loss [56.70360094597169]
  モデルパラメータの明示的な関数によって、平方損失による暗黙の正規化を特徴付けることは不可能であることを示す。 非線形予測器の暗黙的正規化を理解するためには,より一般的な枠組みが必要であることが示唆された。
  論文  参考訳（メタデータ） (2020-12-09T16:48:03Z)
• A Differentiable Relaxation of Graph Segmentation and Alignment for AMR Parsing [75.36126971685034]
  我々は、アライメントとセグメンテーションをモデルの潜在変数として扱い、エンドツーエンドのトレーニングの一部としてそれらを誘導する。 また,AMRの個々の構造を扱うために手作りされたLyu2018AMRPAのセグメンテーションルールに依存するモデルにもアプローチした。
  論文  参考訳（メタデータ） (2020-10-23T21:22:50Z)
• Recursive Rules with Aggregation: A Simple Unified Semantics [0.6662800021628273]
  本稿では,集約を伴う再帰の統一的意味論について述べる。 意味論を形式的に定義し、意味論の重要な性質を証明し、先行意味論と比較する。 私たちのセマンティクスはシンプルで、すべてのケースで望ましい結果と一致しています。
  論文  参考訳（メタデータ） (2020-07-26T04:42:44Z)
• Generalized Entropy Regularization or: There's Nothing Special about Label Smoothing [83.78668073898001]
  本稿では, ラベル平滑化を含むエントロピー正則化器群を紹介する。 モデル性能のばらつきはモデルのエントロピーによって大きく説明できる。 我々は,他のエントロピー正規化手法の使用を推奨する。
  論文  参考訳（メタデータ） (2020-05-02T12:46:28Z)
• Pseudo-Convolutional Policy Gradient for Sequence-to-Sequence Lip-Reading [96.48553941812366]
  唇読解は唇運動系列から音声内容を推測することを目的としている。 seq2seqモデルの伝統的な学習プロセスには2つの問題がある。 本稿では,これら2つの問題に対処するために,PCPGに基づく新しい手法を提案する。
  論文  参考訳（メタデータ） (2020-03-09T09:12:26Z)
• Semantics of negative sequential patterns [0.0]
  パターンマイニングにおいて、負のシーケンシャルパターンは、発生すべきイベントと他のイベント(負のイベントと呼ばれる)からなるシーケンスによって指定され、欠落する。 本稿では、このような直感的な表記の曖昧さを隠蔽し、パターンとシーケンスの包含関係に関する8つの意味を識別する。
  論文  参考訳（メタデータ） (2020-02-17T12:48:37Z)

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

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