资源描述：
《on the mathematical properties of linguistic theories .pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、OntheMathematicalPropertiesofLinguisticTheoriesIC.RaymondPerraultArtificialIntelligenceCenterSRIInternationalMenloPark,CA94025andCenterfortheStudyofLanguageandInformationStanfordUniversityMetatheoreticalfindingsregardingthedecidability,generativecapac
2、ity,andrecognitioncomplexityofseveralsyntactictheoriesaresurveyed.Theseincludecontext-free,transformational,lexical-func-tional,generalizedphrasestructure,treeadjunct,andstratificationalgrammars.Thepaperconcludeswithadiscussionoftheimplicationsofthese
3、resultswithrespecttolinguistictheory.1.Introduction2.PreliminaryDefinitionsThedevelopmentofnewformalismsforexpressingWeassumethatthereaderisfamiliarwiththebasicdefi-linguistictheorieshasbeenaccompanied,atleastsincenitionsofregular,context-free(CF),con
4、text-sensitiveChomskyandMiller'searlyworkoncontext-free(CS),recursive,andrecursivelyenumerable(r.e.)languages,bythestudyoftheirmetatheory.Inparticular,languages,aswellaswiththeiracceptors(seeHopcroftnumerousresultsonthedecidability,generativecapacity,
5、andUllman1979).Wewillbemuchconcernedwiththeand,morerecently,therecognitioncomplexityoftheseproblemofrecognizingwhetherastringiscontainedinaformalismshavebeenpublished(andrumored!).Thisgivenlanguage(therecognitionproblem)andwiththatofpapersurveyssomeof
6、theseresultsanddiscussestheirlThisresearchwassponsoredinpartbytheNationalScienceandsignificanceforlinguistictheory.However,wewillavoidEngineeringResearchCouncilofCanadaunderGrantA9285.Itwasentirelytheissueofwhetheronetheoryismoredescrip-madepossiblein
7、partbyagiftfromtheSystemsDevelopmentFounda-tivelyadequatethananother.Wewillconsidercontext-tion.AnearlierversionofthispaperappearedintheProceedingsofthefree,transformational,lexical-functional,generalized21stAnnualMeetingoftheAssociationforComputation
8、alLinguistics,Cambridge,MA,June1983.phrasestructure,treeadjunct,andstratificationalIwouldliketothankBobBerwick,AlexBorgida,JimHoover,grammars)AravindJoshi,LauriKarttunen,FernandoPereira,StanleyPeters,PeterAlthoughthispaperfocusesonmetatheoreti
