Recompression: Word Equations and Beyond

Jeż, Artur

doi:10.1007/978-3-642-38771-5_2

Recompression: Word Equations and Beyond

Jeż, A. (2013). Recompression: Word Equations and Beyond. In M.-P., Beal, & O., Carton (Eds.), Developments in Language Theory (pp. 12-26). Berlin: Springer. doi:10.1007/978-3-642-38771-5_2.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0015-3F32-8 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-0024-9CC2-1

資料種別: 会議論文

LaTeX : Recompression: {Word} Equations and Beyond

ファイル

表示: ファイル

非表示: ファイル

:

recompression_DLT.pdf (全文テキスト（全般）), 436KB

ファイルのパーマリンク:
-

ファイル名:
recompression_DLT.pdf

説明:
-

OA-Status:

閲覧制限:
非公開

MIMEタイプ / チェックサム:
application/pdf

技術的なメタデータ:

著作権日付:
-

著作権情報:
-

CCライセンス:
-

作成者

表示:

非表示:

作成者:
Jeż, Artur¹, 著者

所属:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019

内容説明

表示:

非表示:

キーワード: -

要旨: We present the technique of local recompression on the example of word equations. The technique is based on local modification of variables (replacing X by aX or Xa) and replacement of pairs of letters appearing in the equation by a `fresh' letter, which can be seen as a bottom-up building of an SLP (Straight-Line Programme) for the solution of the word equation, i.e. a compression. Using this technique we give a simple proof that satisfiability of word equations is in PSPACE. Furthermore we sketch the applications for some problems regarding the SLP compressed strings.

資料詳細

表示:

非表示:

言語: eng - English

日付: オンライン出版: 2013出版: 2013

出版の状態: 出版

ページ: -

出版情報: -

目次: -

査読: -

識別子（DOI, ISBNなど）: その他: Local-ID: 836DB038AE110EFEC1257C67004F0785-Jez2013DLTII
DOI: 10.1007/978-3-642-38771-5_2
BibTex参照ID: Jez2013DLTII

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Developments in Language Theory

省略形 : DLT 2013

副タイトル : 17th International Conference, DLT 2013, Marne-la-Vallée, France, June 18-21, 2013. Proceedings

種別: 会議論文集

著者・編者:
Beal, Marie-Pierre¹, 編集者
Carton, Olivier¹, 編集者

所属:
1 External Organizations, ou_persistent22

出版社, 出版地: Berlin : Springer

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 12 - 26 識別子（ISBN, ISSN, DOIなど）: ISBN: 978-3-642-38770-8

出版物 2

表示:

非表示:

出版物名: Lecture Notes in Computer Science

省略形 : LNCS

種別: 連載記事

著者・編者:

所属:

出版社, 出版地: -

ページ: - 巻号: 7907 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: ISSN: 0302-9743

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1

出版物 2