文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > Infinite String Rewrite Systems and Complexity
侵权投诉

Infinite String Rewrite Systems and Complexity

J.SymbolicComputation(1998)25,

Infinite String Rewrite Systems and Complexity

759–793

ArticleNo.sy970198

In niteStringRewriteSystemsandComplexity

JEAN-CAMILLEBIRGET

DepartmentofComputerScience,UniversityofNebraska,Lincoln,NE68588,U.S.A.Westudytherelationbetweentimecomplexityandderivationworkforthewordproblem

ofin nitelypresentedsemigroupsandgroups.Weintroducethenotionoftheworkofa

derivation(de nedasthesumofthelengthsofalltherulesusedinthederivation,with

multiplicity).Thefollowingresultsareproved:

(1)A nitelygeneratedsemigroupShasadecidablewordproblemi Sisembeddable

intoa nitelygeneratedsemigroupwithacomplete(i.e.con uentandterminat-

ing)presentationwhosesetofrewriterulesformsa nite-statesequentialpartial

function.

A nitelygeneratedsemigroupShasarepresentativefunctionwhichiscomputable

indeterministictime≤T(.)O(1)andhasalinearupperboundonitslength,i Sis

embeddableinasemigroupwithacompletepresentation A:R whereAis nite,

Risa nite-statesequentialpartialfunction,everyderivationhaswork≤T(.)O(1),

andreductiondoesnotincreaselengthsmorethanlinearly.

(2)Thewordproblemofa nitelygeneratedmonoid(orgroup)Sisdecidablein

nondeterministictime≤T(.)O(1)i Shasa(group)presentation A:R whereA

is nite,Ristheintersectionoftwodeterministiccontext-freelanguages,andthe

minimumderivationworkbetweenequivalentwordsx,yis≤T(|x|+|y|)O(1).(This

strengthensaresultofMadlenerandOtto.)

Wealsogiveresultsthatrelatethedeterministiccomputationalcomplexityofa

representativefunctionandtheworkofderivationsina nitelygeneratedin nite

presentation.

(3)EverydeterministicTuringmachinewithtimecomplexityO(T)isequivalenttoa

deterministicTuringmachinewhichhaltsafterO(T)steps,nomatterwhatcon-

gurationthismachinestartsin.(Thisisacomplexityversionofatheoremby

MartinDavis,whichplaysakeyroleintheconnectionbetweencomplexityand

stringrewriting.)

c1998AcademicPressLimited

Introduction

Thewordproblemofmonoidsandgroupsisbothanalgebraicandacomputationalproblem;thismakesitaveryinterestingobjectofstudy.Itisparticularlyinteresting

SupportedinpartbyN.S.F.grantDMS-9203981.PartofthisresearchwascarriedoutduringasabbaticalyearattheLaboratoired’InformatiqueTh´eoriqueetProgrammation,InstitutBlaisePascal,Universit´edeParis6,Paris,France. E-mail:birget@cse.unl.edu

0747–7171/97/060759+35$25.00/0c1998AcademicPressLimited

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email