Beteendebeskrivningsbaserade Web Service Composition (WSC) problem handlar om automatisk konstruktion av en koordinator webbtjänst som styr en uppsättning av webbtjänster för att nå målen stater. Trots dess betydelse och konsekvenser finns det dock mycket få studier om beräkningskomplexen i WSC-problemet. För att ta itu med detta problem presenterar vi fyra nya teoretiska rön om WSC-problemet: (1) Att lösa problemet med sammansättningen av deterministiska webbtjänster för ett begränsat fall (när samordnarens webbtjänst har fullständig information om tillstånden för alla webbtjänster) är PSPACE-hård, (2) Att lösa problemet med sammansättningen av deterministiska webbtjänster för ett allmänt fall (när samordnarens webbtjänst har ofullständig information om tillstånden för webbtjänster) är EXPACE-hård, (3) Att lösa problemet med sammansättningen av icke-deterministiska webbtjänster på fullständig information är EXP-hård, och (4) Att lösa problemet med sammansättningen av icke-deterministiska webbtjänster på ofullständig information (vilket är det vanligaste fallet) är 2-EXP-hård. Dessa resultat tyder på att det krävs fler ansträngningar för att utarbeta effektiva tillnärmningslösningar till WSC-problemet.
Nam och al. REF studerade beräkningskomplexiteterna i beteendebeskrivningsbaserad webbtjänstsammansättning, och drog slutsatsen att kompositionsproblemet för icke-deterministiska webbtjänster med ofullständig information, att vara 2-EXP-komplett.
On the Computational Complexity of Behavioral Description-Based Web Service Composition
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Computer Science']}