๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The derivational complexity of string rewriting systems

โœ Scribed by Yuji Kobayashi

Book ID
113927724
Publisher
Elsevier Science
Year
2012
Tongue
English
Weight
277 KB
Volume
438
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

Infinite String Rewrite Systems and Comp
Infinite String Rewrite Systems and Complexity
โœ Jean-Camille Birget ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 712 KB

We study the relation between time complexity and derivation work for the word problem of infinitely presented semigroups and groups. We introduce the notion of the work of a derivation (defined as the sum of the lengths of all the rules used in the derivation, with multiplicity). The following resu

Some properties of finite special string
Some properties of finite special string-rewriting systems
โœ Louxin Zhang ๐Ÿ“‚ Article ๐Ÿ“… 1992 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 567 KB

This paper investigates decision problems of finite, special string-rewriting systems . There are two main results . The first one is that the word problem for a finite, special string-rewriting system T on alphabet A is reducible to its restricted version: given a word w, is w congruent to any fixe

On termination of confluent one-rule str
On termination of confluent one-rule string-rewriting systems
โœ Kayoko Shikishima-Tsuji; Masashi Katsura; Yuji Kobayashi ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 507 KB

The termination of a confluent one-rule string-rewriting system R = (s + I} is reduced to that of another one-rule system K = {s' -B t') such that s' is self-overlap-free &of). A necessary and sufficient condition is given for termination of a one-rule system R = {s --+ t} such that s is sof and s o