J.SymbolicComputation(1998)25,

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
Complexity of sequences ... 暂无评价 14页 免费 Multi-Agent Systems and ... 暂无评价 3页 免费 Infinite String Rewrite ... 暂无评价 35页 1财富值 ...
Infinite String Rewrite ... 暂无评价 35页 1财富值 Well-foundedness of ...nite Labelled Rewrite Systems Adam Koprowski and Hans Zantema Eindhoven ...
generation systems and e... 14页 1财富值 Infinite String Rewrite ... 暂无评价 35页 1财富值 Bi-Hamiltonian manifolds... 暂无评价 12页 免费 Quantum...
The complexity of normal form rewrite sequences for Associativity The ...1992. Term Rewrite Systems. In Samson Abramsky, Dov M. Gabbay, and T. ...
暂无评价 20页 免费 On the Complexity of Dec... 暂无评价 3页 免费...General Terms: Theory Additional Key Words and Phrases: Rewrite Systems, Con...
Process Rewrite Systems (PRSs), an infinite-state formalism (non Turing-powerful) which subsumes many common models such as Pushdown Processes and Petri ...
Recycling Computed Answers in Rewrite Systems for Abduction Lambda 1 ... for previously computed subgoals that reduces the computational complexity. ...
finitely describe infinite sequences of structur隐藏... and therefore inherit the complexity of these ...Completion of rewrite systems with membership ...
On the Complexity of Dec... 暂无评价 3页 ...1 Introduction String rewriting systems have played...Its elements are refered to as rewrite +1 rules...
gradual increase in the complexity of the ...infinite systems to start by considering finite ...wn if and only if we can rewrite w as y1…...
热门文档