Abstract
We define an operational semantics and a type system for manipulating semistructured data that contains hidden information. The data model is simple labeled trees with a hiding operator. Data manipulation is based on patternmatching, with types that track the use of hidden labels.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
S. Abiteboul, P. Buneman, D. Suciu.: Data on the Web. Morgan Kaufmann Publishers, 2000.
S. Abiteboul, P. Kanellakis: Object identity as a query language primitive. Journal of the ACM, 45(5):798–842, 1998. A first version appeared in SIGMOD’89.
S. Abiteboul, D. Quass, J. McHugh, J. Widom, and J. Wiener. The Lorel Query Language for Semistructured Data. International Journal on Digital Libraries, 1(1), pp. 68–88, April 1997.
M.P. Atkinson, F. Bancilhon, et al.: The Object-Oriented Database System Manifesto. Building an Object-Oriented Database System, The Story of O2, 1992, pp. 3–20.
V. Benzaken, G. Castagna, A. Frisch: CDuce: a white paper. PLAN-X: Programming Language Technologies for XML, Pittsburgh PA, Oct. 2002. http://www.cduce.org.
S. Boag, D. Chamberlin, M.F. Fernandez, D. Florescu, J. Robie, J. Siméon: XQuery 1.0: An XML Query Language, W3C Working Draft, 2002, http://www.w3.org/TR/xquery.
T. Bray, J. Paoli, C.M. Sperberg-McQueen, E. Maler: Extensible Markup Language (XML) 1.0 (Second Edition), W3C document, http://www.w3.org/TR/REC-xml.
P. Buneman, S.B. Davidson, G.G. Hillebrand, D. Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996, pp. 505–516.
L. Caires: A Model for Declarative Programming and Specification with Concurrency and Mobility. Ph.D. Thesis, Dept. de Informática, FTC, Universidade Nove de Lisboa, 1999.
L. Caires, L Cardelli: A Spatial Logic for Concurrency: Part I. Proc. TACS 2001, Naoki Kobayashi and Benjamin C. Pierce (Eds.). LNCS. 2215. Springer, 2001, pp 1–37. To appear in Iamp;C.
L. Caires, L. Cardelli: A Spatial Logic for Concurrency: Part II. Proc. CONCUR’02, 2002.
C. Calcagno, L. Cardelli, A.D. Gordon, Deciding Validity in a Spatial Logic for Trees. Draft.
C. Calcagno, H. Yang, P.W. O'Hearn: Computability and Complexity Results for a Spatial Assertion Language for Data Structures. Proc. FSTTCS 2001, pp. 108–119.
L. Cardelli, P. Gardner, G. Ghelli, A Spatial Logic for Querying Graphs. Proc. ICALP’02, Peter Widmayer et al. (Eds.). LNCS 2380, Springer, 2002. pp 597–610.
L. Cardelli, G. Ghelli, A Query Language Based on the Ambient Logic. Proc. ESOP’01, David Sands (Ed.). LNCS 2028, Springer, 2001, pp. 1–22.
L. Cardelli, A.D. Gordon, Anytime, Anywhere. Modal Logics forMobile Ambients. Proc. of the 27th ACM Symposium on Principles of Programming Languages, 2000, pp. 365–377.
S. Cluet, S. Jacqmin, and J. Simeon. The New YATL: Design and Specifications. INRIA, 1999.
E. Cohen: Validity and Model Checking for Logics of Finite Multisets. Draft.
D. Florescu, A. Deutsch, A. Levy, D. Suciu, M. Fernandez: A Query Language for XML. In Proc. of Eighth International World Wide Web Conference, 1999.
D. Florescu, A. Levy, M. Fernandez, D. Suciu, A Query Language for aWeb-Site Management System. SIGMOD Record, vol. 26, no. 3, pp. 4–11, September, 1997.
M.J. Gabbay: A Theory of Inductive Definitions with a-Equivalence: Semantics, Implementation, Programming Language. Ph.D. Thesis, University of Cambridge, 2000.
M.J. Gabbay, A.M. Pitts, A New Approach to Abstract Syntax Involving Binders. Proc. LICS1999. IEEE Computer Society Press, 1999. pp 214–224.
M.J. Gabbay: FM-HOL, A Higher-Order Theory of Names. In Thirty Five years of Automath, Heriot-Watt University, Edinburgh, April 2002. Inforal Proc., 2002.
A.D. Gordon: Notes on Nominal Calculi for Security andMobility. R. Focardi, R. Gorrieri (Eds.): Foundations of Security Analysis and Design. LNCS 2171. Springer, 1998.
A.D. Gordon, A. Jeffrey: Typing Correspondence Assertions for Communication Protocols. MFPS 17, Elsevier Electronic Notes in Theoretical Computer Science, Vol 45, 2001.
H. Hosoya, B. C. Pierce: XDuce: A Typed XML Processing Language (Preliminary Report). WebDB (Selected Papers) 2000, pp: 226–244
R. Milner: Communicating and Mobile Systems: the π-Calculus. Cambridge U. Press, 1999.
P.W. O'Hearn, D. Pym: Logic of Bunched Implication. Bulletin of Symbolic Logic 5(2), pp 215–244, 1999.
P.W. O'Hearn, J.C. Reynolds, H. Yang: Local Reasoning about Programs that Alter Data Structures. Proc. CSL 2001, pp. 1–19.
A.M. Pitts: Nominal Logic, A First Order Theory of Names and Binding. Proc. TACS 2001, Naoki Kobayashi and Benjamin C. Pierce (Eds.). LNCS 2215. Springer, 2001, pp 219–242.
A.M. Pitts, M.J. Gabbay: A Metalanguage for Programming with Bound Names Modulo Renaming. R. Backhouse and J.N. Oliveira (Eds.): MPC 2000, LNCS 1837, Springer, pp. 230–255.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cardelli, L., Gardner, P., Ghelli, G. (2003). Manipulating Trees with Hidden Labels. In: Gordon, A.D. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2003. Lecture Notes in Computer Science, vol 2620. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36576-1_14
Download citation
DOI: https://doi.org/10.1007/3-540-36576-1_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00897-2
Online ISBN: 978-3-540-36576-1
eBook Packages: Springer Book Archive