On the Turing Completeness of the Semantic Web
Pages 291 - 308
Abstract
The evidenced fact that "Linking is as powerful as computing" in a dynamic web context has lead to evaluating Turing completeness for hypertext systems based on their linking model. The same evaluation can be applied to the Semantic Web domain too. RDF is the default data model of the Semantic Web links, so the evaluation comes back to whether or not RDF can support the required computational power at the linking level. RDF represents semantic relationships with explicitly naming the participating triples, however the enumeration is only one method amongst many for representing relations, and not always the most efficient or viable. In this paper we firstly consider that Turing completeness of binary-linked hypertext is realized if and only if the links are dynamic (functional). Ashman's Binary Relation Model (BRM) showed that binary relations can most usefully be represented with Mili's pE (predicate-expression) representation, and Moreau and Hall concluded that hypertext systems which use the pE representation as the basis for their linking (relation) activities are Turing-complete. Secondly we consider that RDF ---as it is- is a static version of a general ternary relations model, called TRM. We then conclude that the current computing power of the Semantic Web depends on the dynamicity supported by its underlying TRM. The value of this is firstly that RDF's triples can be considered within a framework and compared to alternatives, such as the TRM version of pE, designated pfE (predicate-function-expression). Secondly, that a system whose relations are represented with pfE is likewise going to be Turing-complete. Thus moving from RDF to a pfE representation of relations would give far greater power and flexibility within the Semantic Web applications.
References
[1]
Nürnberg, P.J., Ashman, H.: What was the question? Reconciling open hypermedia and World Wide Web research. In: Proceedings of the Tenth ACM Conference on Hypertext and Hypermedia: Returning to Our Diverse Roots. ACM Press, Darmstadt (1999)
[2]
Berners-Lee, T., Hendler, J., Lassila, O.: The semantic web. Sci. Am. 284(5), 34---44 (2001)
[3]
Ashman, H.: Electronic document addressing: dealing with change. ACM Comput. Surv. 32(3), 201---212 (2000)
[4]
Moreau, L., Hall, W.: On the expressiveness of links in hypertext systems. Comput. J. 41, 459---473 (1998)
[5]
Mili, A.: A relational approach to the design of deterministic programs. Acta Informatica 20(4), 315---328 (1983)
[6]
W3C: Resource Description Framework (RDF): Concepts and Abstract Syntax. Feb 2004}; Available from: http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/ (2006)
[7]
W3C-Working-Group: Defining N-ary Relations on the Semantic Web. June 2006}; Available from: http://www.w3.org/TR/swbp-n-aryRelations/ (2006)
[8]
Recommendation, W.C.: RDF Test Cases. June 2006}; Available from: http://www.w3.org/TR/rdf-testcases/ (2004)
[9]
W3C: Turtle, Terse RDF Triple Language. July 2013}; Available from: http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/ (2013)
[10]
Berners-Lee, T.: Notation 3 (N3). June 2006}; Available from: http://www.w3.org/DesignIssues/Notation3 (1998)
[11]
Ashman, H.: Relations modelling sets of hypermedia links and navigation. Comput. J. 43, 345---363 (2000)
[12]
Ashman, H.: Theory and Practice of Large-Scale Hypermedia Systems. PhD Thesis, The Royal Melbourne Institute of Technology, Australia (1997)
[13]
Ashman, H., Garrido, A., Kukkonen, H.O.: Hand-made and computed links, precomputed and dynamic links. In: Proceedings of Hypermedia - Information Retrieval - Multimedia '97 (HIM '97). Dortmund (1997)
[14]
Hall, W., Hill, G., Davis, H.: The microcosm link service. In: Proceedings of the Fifth ACM Conference on Hypertext. ACM Press, Seattle (1993)
[15]
Verbyla, J., Ashman, H.: A user-configurable hypermedia-based interface via the functional model of the link. Hypermedia 6(3), 193---208 (1994)
[16]
Berners-Lee, T., Fischetti, M., Foreword By-Dertouzos, M.L.: Weaving the Web: The original design and ultimate destiny of the World Wide Web by its inventor. HarperInformation (2000)
[17]
Berners-Lee, T.: Semantic Web Road Map. W3C Electronic Journal (1998)
[18]
Antoniou, G., van-Harmelen, F.: A Semantic Web Primer. MIT Press, Cambridge (2004)
[19]
Palmer, S.B.: The Semantic Web: An Introduction. 15/08/2005}; Available from: http://infomesh.net/2001/swintro/ (2001)
[20]
Goble, C., et al.: Conceptual open hypermedia = the semantic web?. In: The Second International Workshop on the Semantic Web. Hong Kong (2001)
[21]
Carr, L., et al.: Conceptual linking: ontology-based open hypermedia. In: Proceedings of the 10th International Conference on World Wide Web. ACM Press, Hong Kong (2001)
[22]
Bhaumik, A., et al.: Towards hypermedia support for database systems. In: Proceedings of the 34th Hawaiian International Conference on System Sciences. IEEE, Hawaii (2001)
[23]
Bieber, M.: Dynamic Hypermedia Engine (D.H.E). CIS Department, New Jersey Institute of Technology 15/08/2005}; Available from: http://www.cis.njit.edu/~bieber/dhe-overview.html (2000)
[24]
Chen, X., et al.: Integrating Web Systems through Linking. www2003.org 15/08/2005}; Available from: http://www2003.org/cdrom/papers/poster/p145/p145-chen.htm (2004)
[25]
Qiu, Z.: Hyperstructure-Based Search Methods for the World Wide Web. PhD Thesis, Darmstadt Technical University, Denmark (2004)
[26]
W3C: RDFa 1.1 Primer, Rich Structured Data Markup for Web Document. July 2013}; Available from: http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/ (2012)
[27]
Halasz, F., Schwartz, M.: The Dexter hypertext reference model. Commun. ACM 37(2), 30---39 (1994)
[28]
Stotts, P.D., Furuta, R.: Adding browsing semantics to the hypertext model. In: Proceedings of the ACM Conference on Document Processing Systems. ACM (1988)
[29]
Millard, D.E., et al.: FOHM: a fundamental open hypertext model for investigating interoperability between hypertext domains. In: Proceedings of the Eleventh ACM Conference on Hypertext and Hypermedia. ACM Press, San Antonio (2000)
[30]
Oinas-Kukkonen, H.: What is inside a link?Commun. ACM 41(7), 98 (1998)
[31]
Takahashi, K.: Metalevel links: more power to your links. Commun. ACM 41(7), 103---105 (1998)
[32]
Bieber, M., et al.: Fourth generation hypermedia: some missing links for the World Wide Web. Int. J. Hum. Comput. Stud. 47(1), 31---65 (1997)
[33]
Shum, S.B.: The missing link: hypermedia usability research and the web. ACM SIGCHI Bulletin 28(4), 68---75 (1996)
[34]
Abiteboul, S., Vianu, V.: Queries and computation on the Web. In: Database Theory--ICDT'97, p. 262---275. Springer (1997)
[35]
Hartig, O.: SPARQL for a web of linked data: semantics and computability. In: The Semantic Web: Research and Applications, pp. 8---23. Springer (2012)
[36]
Thistlewaite, P.: Automatic construction and management of large open webs. Inf. Process. Manag. 33(2), 161---173 (1997)
[37]
Jain, K.: D-RDF: Dynamic Resource Description Framework. ProQuest (2007)
[38]
W3C: XML Linking Language (XLink) Version 1.0. 17/07/2008}; Available from: http://www.w3.org/TR/xlink/ (2001)
[39]
Bry, F., et al.: SPARQLog: SPARQL with rules and quantification. In: Semantic Web Information Management, pp. 341---370. Springer (2010)
[40]
Carr, L., et al.: The distributed link service: a tool for publishers, authors and readers. In: Proceedings of the 4th International WWW Conference. Boston (1995)
Recommendations
Using the relation ontology Metarel for modelling Linked Data as multi-digraphs
Linked Data for Health Care and the Life SciencesThe Semantic Web standards OWL and RDF are often used to represent biomedical information as Linked Data; however, the OWL/RDF syntax, which combines both, was never optimised for querying. By combining two formal paradigms for modelling Linked Data, ...
RDF, Jena, SparQL and the 'Semantic Web'
SIGUCCS '09: Proceedings of the 37th annual ACM SIGUCCS fall conference: communication and collaborationThe Resource Description Format (RDF) is used to represent information modeled as a "graph": a set of individual objects, along with a set of connections among those objects. In that role, RDF is one of the pillars of the so-called Semantic Web. This ...
Querying semantic web data with SPARQL
PODS '11: Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsThe Semantic Web is the initiative of the W3C to make information on the Web readable not only by humans but also by machines. RDF is the data model for Semantic Web data, and SPARQL is the standard query language for this data model. In the last ten ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2015 Springer Science+Business Media New York.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 February 2015
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in