@Preamble{
"\input tugboat.def" #
"\input path.sty" #
"\hyphenation{
Ka-ra-ba-ba
mark-up
round-up
stan-dard-is-er-ings-raad
}"
}
@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
@String{j-ACTA-INFO = "Acta Informatica"}
@String{j-APPL-MATH-COMP = "Applied Mathematics and Computation"}
@String{j-CACM = "Communications of the ACM"}
@String{j-CCCUJ = "C/C++ Users Journal"}
@String{j-COMP-J = "The Computer Journal"}
@String{j-COMP-NET-AMSTERDAM = "Computer Networks (Amsterdam, Netherlands:
1999)"}
@String{j-COMP-SURV = "ACM Computing Surveys"}
@String{j-COMPUT-SCI-ENG = "Computing in Science and Engineering"}
@String{j-COMPUTER = "Computer"}
@String{j-COMPUTING = "Computing"}
@String{j-DDJ = "Dr. Dobbs Journal"}
@String{j-FORTRAN-FORUM = "ACM Fortran Forum"}
@String{j-FUT-GEN-COMP-SYS = "Future Generation Computer Systems"}
@String{j-IBM-SYS-J = "IBM Systems Journal"}
@String{j-IEEE-DISTRIB-SYST-ONLINE = "IEEE Distributed Systems Online"}
@String{j-INFO-PROC-LETT = "Information Processing Letters"}
@String{j-INT-J-COMP-PROC-ORIENTAL-LANG = "International Journal of
Computer Processing of Oriental
Languages (IJCPOL)"}
@String{j-INT-J-COMPUT-SYST-SCI-ENG = "International Journal of Computer
Systems Science and Engineering"}
@String{j-J-ACM = "Journal of the ACM"}
@String{j-J-CHEM-INFO-COMP-SCI = "Journal of Chemical Information and Computer
Sciences"}
@String{j-J-PAR-DIST-COMP = "Journal of Parallel and Distributed
Computing"}
@String{j-J-SYST-SOFTW = "The Journal of Systems and Software"}
@String{j-J-UCS = "J.UCS: Journal of Universal Computer
Science"}
@String{j-JCD = "ACM Journal of Computer Documentation"}
@String{j-LECT-NOTES-COMP-SCI = "Lecture Notes in Computer Science"}
@String{j-LIB-HI-TECH = "Library Hi Tech"}
@String{j-LINUX-J = "Linux Journal"}
@String{j-MATH-COMPUT-SCI = "Mathematics in Computer Science"}
@String{j-MINI-MICRO-SYSTEMS = "Mini-Micro Systems"}
@String{j-OPER-SYS-REV = "Operating Systems Review"}
@String{j-SCI-PROG = "Scientific Programming"}
@String{j-SIAM-J-COMPUT = "SIAM Journal on Computing"}
@String{j-SIGCSE = "SIGCSE Bulletin (ACM Special Interest Group
on Computer Science Education)"}
@String{j-SIGMOD = "SIGMOD Record (ACM Special Interest
Group on Management of Data)"}
@String{j-SIGPLAN = "ACM SIG{\-}PLAN Notices"}
@String{j-SPE = "Soft\-ware\emdash Prac\-tice and Experience"}
@String{j-THEOR-COMP-SCI = "Theoretical Computer Science"}
@String{j-TISSEC = "ACM Transactions on Information and System
Security"}
@String{j-TOCL = "ACM Transactions on Computational Logic"}
@String{j-TODS = "ACM Transactions on Database Systems"}
@String{j-TOIS = "ACM Transactions on Information Systems"}
@String{j-TOIT = "ACM Transactions on Internet Technology
(TOIT)"}
@String{j-TOPLAS = "ACM Transactions on Programming
Languages and Systems"}
@String{j-TWEB = "ACM Transactions on the Web (TWEB)"}
@String{j-VLDB-J = "VLDB Journal: Very Large Data Bases"}
@String{pub-ACM = "ACM Press"}
@String{pub-ACM:adr = "New York, NY, USA"}
@String{pub-AP = "Academic Press"}
@String{pub-AP:adr = "New York, USA"}
@String{pub-APRESS = "Apress"}
@String{pub-APRESS:adr = "Berkeley, CA, USA"}
@String{pub-AW = "Ad{\-d}i{\-s}on-Wes{\-l}ey"}
@String{pub-AW:adr = "Reading, MA, USA"}
@String{pub-CMP-BOOKS = "CMP Books"}
@String{pub-CMP-BOOKS:adr = "6600 Silacci Way, Gilroy, CA 95020, USA"}
@String{pub-CORIOLIS = "Coriolis Group Books"}
@String{pub-CORIOLIS:adr = "Scottsdale, AZ, USA"}
@String{pub-COURSE-TECHNOLOGY = "Course Technology"}
@String{pub-COURSE-TECHNOLOGY:adr = "Cambridge, MA, USA"}
@String{pub-CRC = "CRC Press"}
@String{pub-CRC:adr = "2000 N.W. Corporate Blvd., Boca Raton, FL
33431-9868, USA"}
@String{pub-HUNGRY-MINDS = "Hungry Minds"}
@String{pub-HUNGRY-MINDS:adr = "909 Third Avenue, New York, NY 10022, USA"}
@String{pub-IBM-REDBOOKS = "IBM Redbooks"}
@String{pub-IBM-REDBOOKS:adr = "11400 Burnet Road, Austin, TX 78758-3493,
USA"}
@String{pub-IDG = "IDG Books"}
@String{pub-IDG:adr = "San Mateo, CA, USA"}
@String{pub-IRWIN-MCGRAW-HILL = "Irwin\slash McGraw Hill"}
@String{pub-IRWIN-MCGRAW-HILL:adr = "Boston, MA, USA"}
@String{pub-ISO = "International Organization for
Standardization"}
@String{pub-ISO:adr = "Geneva, Switzerland"}
@String{pub-ITP = "International Thomson Publishing"}
@String{pub-ITP:adr = "5101 Madison Road, Cincinnati, OH
45227, USA; Bonn, Germany"}
@String{pub-MANNING = "Manning Publications"}
@String{pub-MANNING:adr = "Greenwich, CT, USA"}
@String{pub-MCGRAW-HILL = "Mc{\-}Graw-Hill"}
@String{pub-MCGRAW-HILL:adr = "New York, NY, USA"}
@String{pub-MICROSOFT = "Microsoft Press"}
@String{pub-MICROSOFT:adr = "Bellevue, WA, USA"}
@String{pub-MORGAN-KAUFMANN = "Morgan Kaufmann Publishers"}
@String{pub-MORGAN-KAUFMANN:adr = "Los Altos, CA 94022, USA"}
@String{pub-MT = "M\&T Books"}
@String{pub-MT:adr = "M\&T Publishing, Inc., 501 Galveston Drive,
Redwood City, CA 94063, USA"}
@String{pub-NIST = "National Institute for Standards
and Technology"}
@String{pub-NIST:adr = "Gaithersburg, MD, USA"}
@String{pub-NEW-RIDERS = "New Riders Publishing"}
@String{pub-NEW-RIDERS:adr = "Carmel, IN, USA"}
@String{pub-ORA = "O'Reilly \& {Associates, Inc.}"}
@String{pub-ORA:adr = "103a Morris Street, Sebastopol, CA
95472, USA, Tel: +1 707 829 0515,
and 90 Sherman Street, Cambridge, MA
02140, USA, Tel: +1 617 354 5800"}
@String{pub-ORA-MEDIA = "O'Reilly Media, Inc."}
@String{pub-ORA-MEDIA:adr = "1005 Gravenstein Highway North, Sebastopol,
CA 95472, USA"}
@String{pub-OSBORNE = "Osborne/McGraw-Hill"}
@String{pub-OSBORNE:adr = "Berkeley, CA, USA"}
@String{pub-PEACHPIT = "Peachpit Press, Inc."}
@String{pub-PEACHPIT:adr = "1085 Keith Avenue, Berkeley, CA 94708, USA"}
@String{pub-PH = "Pren{\-}tice-Hall"}
@String{pub-PH:adr = "Englewood Cliffs, NJ 07632, USA"}
@String{pub-PHPTR = "Pren{\-}tice-Hall PTR"}
@String{pub-PHPTR:adr = "Upper Saddle River, NJ 07458, USA"}
@String{pub-PRIMA = "Prima Publishing"}
@String{pub-PRIMA:adr = "Roseville, CA, USA"}
@String{pub-QUE = "Que Corporation"}
@String{pub-QUE:adr = "Indianapolis, IN, USA"}
@String{pub-SAMS = "SAMS Publishing"}
@String{pub-SAMS:adr = "Indianapolis, IN, USA"}
@String{pub-SV = "Springer-Verlag Inc."}
@String{pub-SV:adr = "New York, NY, USA"}
@String{pub-SYBEX = "Sybex"}
@String{pub-SYBEX:adr = "2021 Challenger Driver, Suite 100,
Alameda, CA 94501, USA"}
@String{pub-WILEY = "Wiley"}
@String{pub-WILEY:adr = "New York, NY, USA"}
@String{pub-WROX = "Wrox Press"}
@String{pub-WROX:adr = "Chicago, IL, USA"}
@String{ser-LNCS = "Lecture Notes in Computer Science"}
@Article{Apel:2010:CUF,
author = "Sven Apel and Delesley Hutchins",
title = "A calculus for uniform feature composition",
journal = j-TOPLAS,
volume = "32",
number = "5",
pages = "19:1--19:??",
month = may,
year = "2010",
CODEN = "ATPSDT",
DOI = "https://doi.org/10.1145/1745312.1745316",
ISSN = "0164-0925 (print), 1558-4593 (electronic)",
ISSN-L = "0164-0925",
bibdate = "Fri May 21 12:28:30 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/toplas/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "The goal of {\em feature-oriented programming\/} (FOP)
is to modularize software systems in terms of features.
A {\em feature\/} refines the content of a base
program. Both base programs and features may contain
various kinds of software artifacts, for example,
source code in different languages, models, build
scripts, and documentation. We and others have noticed
that when composing features, different kinds of
software artifacts can be refined in a uniform way,
regardless of what they represent. We present gDeep, a
core calculus for feature composition, which captures
the language independence of FOP; it can be used to
compose features containing many different kinds of
artifact in a type-safe way. The calculus allows us to
gain insight into the principles of FOP and to define
general algorithms for feature composition and
validation. We provide the formal syntax, operational
semantics, and type system of gDeep and outline how
languages like Java, Haskell, Bali, and XML can be
plugged in.",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Programming Languages and
Systems",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J783",
keywords = "feature composition; Feature-oriented programming;
principle of uniformity; type systems",
}
@Article{Bex:2010:ICR,
author = "Geert Jan Bex and Frank Neven and Thomas Schwentick
and Stijn Vansummeren",
title = "Inference of concise regular expressions and {DTDs}",
journal = j-TODS,
volume = "35",
number = "2",
pages = "11:1--11:??",
month = apr,
year = "2010",
CODEN = "ATDSD3",
DOI = "https://doi.org/10.1145/1735886.1735890",
ISSN = "0362-5915 (print), 1557-4644 (electronic)",
ISSN-L = "0362-5915",
bibdate = "Wed Apr 28 13:44:08 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/tods/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "We consider the problem of inferring a concise
Document Type Definition (DTD) for a given set of
XML-documents, a problem that basically reduces to
learning {\em concise\/} regular expressions from
positive examples strings. We identify two classes of
concise regular expressions --- the single occurrence
regular expressions (SOREs) and the chain regular
expressions (CHAREs) --- that capture the far majority
of expressions used in practical DTDs. For the
inference of SOREs we present several algorithms that
first infer an automaton for a given set of example
strings and then translate that automaton to a
corresponding SORE, possibly repairing the automaton
when no equivalent SORE can be found. In the process,
we introduce a novel automaton to regular expression
rewrite technique which is of independent interest.
When only a very small amount of XML data is available,
however (for instance when the data is generated by Web
service requests or by answers to queries), these
algorithms produce regular expressions that are too
specific. Therefore, we introduce a novel learning
algorithm crx that directly infers CHAREs (which form a
subclass of SOREs) without going through an automaton
representation. We show that crx performs very well
within its target class on very small datasets.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on Database Systems",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J777",
keywords = "Regular expressions; schema inference; XML",
}
@Article{Bonifati:2010:SMQ,
author = "Angela Bonifati and Elaine Chang and Terence Ho and
Laks V. Lakshmanan and Rachel Pottinger and Yongik
Chung",
title = "Schema mapping and query translation in heterogeneous
{P2P XML} databases",
journal = j-VLDB-J,
volume = "19",
number = "2",
pages = "231--256",
month = apr,
year = "2010",
CODEN = "VLDBFR",
DOI = "https://doi.org/10.1007/s00778-009-0159-9",
ISSN = "1066-8888 (print), 0949-877X (electronic)",
ISSN-L = "1066-8888",
bibdate = "Wed Apr 21 16:41:50 MDT 2010",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "Peers in a peer-to-peer data management system often
have heterogeneous schemas and no mediated global
schema. To translate queries across peers, we assume
each peer provides correspondences between its schema
and a small number of other peer schemas. We focus on
query reformulation in the presence of heterogeneous
XML schemas, including data---metadata conflicts. We
develop an algorithm for inferring precise mapping
rules from informal schema correspondences. We define
the semantics of query answering in this setting and
develop query translation algorithm. Our translation
handles an expressive fragment of XQuery and works both
along and against the direction of mapping rules. We
describe the HePToX heterogeneous P2P XML data
management system which incorporates our results. We
report the results of extensive experiments on HePToX
on both synthetic and real datasets. We demonstrate our
system utility and scalability on different P2P
distributions.",
acknowledgement = ack-nhfb,
fjournal = "VLDB Journal: Very Large Data Bases",
journal-URL = "http://portal.acm.org/toc.cfm?id=J869",
keywords = "Heterogeneous Peer-to-Peer XML databases; Schema
mapping; XML query translation",
}
@Article{Bramandia:2010:OUR,
author = "Ramadhana Bramandia and Jiefeng Cheng and Byron Choi
and Jeffrey Xu Yu",
title = "Optimizing updates of recursive {XML} views of
relations",
journal = j-VLDB-J,
volume = "18",
number = "6",
pages = "1313--1333",
month = dec,
year = "2010",
CODEN = "VLDBFR",
ISSN = "1066-8888 (print), 0949-877X (electronic)",
ISSN-L = "1066-8888",
bibdate = "Tue Mar 16 08:21:44 MDT 2010",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
acknowledgement = ack-nhfb,
fjournal = "VLDB Journal: Very Large Data Bases",
journal-URL = "http://portal.acm.org/toc.cfm?id=J869",
}
@Article{Buehrer:2010:DPS,
author = "Gregory Buehrer and Srinivasan Parthasarathy and
Shirish Tatikonda",
title = "A distributed placement service for graph-structured
and tree-structured data",
journal = j-SIGPLAN,
volume = "45",
number = "5",
pages = "355--356",
month = may,
year = "2010",
CODEN = "SINODQ",
DOI = "https://doi.org/10.1145/1837853.1693511",
ISSN = "0362-1340 (print), 1523-2867 (print), 1558-1160
(electronic)",
ISSN-L = "0362-1340",
bibdate = "Tue Aug 31 22:39:18 MDT 2010",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "Effective data placement strategies can enhance the
performance of data-intensive applications implemented
on high end computing clusters. Such strategies can
have a significant impact in localizing the
computation, in minimizing synchronization
(communication) costs, in enhancing reliability (via
strategic replication policies), and in ensuring a
balanced workload or enhancing the available bandwidth
from massive storage devices (e.g. disk
arrays).\par
Existing work has largely targeted the placement of
relatively simple data types or entities (e.g.
elements, vectors, sets, and arrays). Here we
investigate several hash-based distributed data
placement methods targeting tree- and graph- structured
data, and develop a locality enhancing placement
service for large cluster systems. Target applications
include the placement of a single large graph (e.g. Web
graph), a single large tree (e.g. large XML file), a
forest of graphs or trees (e.g. XML database) and other
specialized graph data types - bi-partite (query-click
graphs), directed acyclic graphs etc. We empirically
evaluate our service by demonstrating its use in
improving mining executions for pattern discovery,
nearest neighbor searching, graph computations, and
applications that combine link and content analysis.",
acknowledgement = ack-nhfb,
fjournal = "ACM SIGPLAN Notices",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J706",
keywords = "data placement; distributed computing; structured
data",
}
@Article{Chou:2010:EXM,
author = "Shih-Chien Chou and Chun-Hao Huang",
title = "An extended {XACML} model to ensure secure information
access for {Web} services",
journal = j-J-SYST-SOFTW,
volume = "83",
number = "1",
pages = "77--84",
month = jan,
year = "2010",
CODEN = "JSSODM",
ISSN = "0164-1212",
ISSN-L = "0164-1212",
bibdate = "Tue Sep 7 07:27:05 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www.sciencedirect.com/science/journal/01641212",
acknowledgement = ack-nhfb,
fjournal = "The Journal of systems and software",
journal-URL = "http://www.sciencedirect.com/science/journal/01641212",
}
@Article{Cohen:2010:LDX,
author = "Edith Cohen and Haim Kaplan and Tova Milo",
title = "Labeling Dynamic {XML} Trees",
journal = j-SIAM-J-COMPUT,
volume = "39",
number = "5",
pages = "2048--2074",
month = "????",
year = "2010",
CODEN = "SMJCAT",
DOI = "",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
ISSN-L = "0097-5397",
bibdate = "Tue May 18 08:22:16 MDT 2010",
bibsource = "http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP/39/5;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
acknowledgement = ack-nhfb,
fjournal = "SIAM Journal on Computing",
journal-URL = "http://epubs.siam.org/sicomp",
}
@Article{Consens:2010:EXW,
author = "Mariano P. Consens and Ren{\'e}e J. Miller and Flavio
Rizzolo and Alejandro A. Vaisman",
title = "Exploring {XML} {Web} collections with {DescribeX}",
journal = j-TWEB,
volume = "4",
number = "3",
pages = "11:1--11:??",
month = jul,
year = "2010",
CODEN = "????",
DOI = "https://doi.org/10.1145/1806916.1806920",
ISSN = "1559-1131 (print), 1559-114X (electronic)",
ISSN-L = "1559-1131",
bibdate = "Sat Aug 14 15:42:40 MDT 2010",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www.math.utah.edu/pub/tex/bib/string-matching.bib;
http://www.math.utah.edu/pub/tex/bib/tweb.bib",
abstract = "As Web applications mature and evolve, the nature of
the semistructured data that drives these applications
also changes. An important trend is the need for
increased flexibility in the structure of Web
documents. Hence, applications cannot rely solely on
schemas to provide the complex knowledge needed to
visualize, use, query and manage documents. Even when
XML Web documents are valid with regard to a schema,
the actual structure of such documents may exhibit
significant variations across collections for several
reasons: the schema may be very lax (e.g., RSS feeds),
the schema may be large and different subsets of it may
be used in different documents (e.g., industry
standards like UBL), or open content models may allow
arbitrary schemas to be mixed (e.g., RSS extensions
like those used for podcasting). For these reasons,
many applications that incorporate XPath queries to
process a large Web document collection require an
understanding of the actual structure present in the
collection, and not just the schema.\par
To support modern Web applications, we introduce
DescribeX, a powerful framework that is capable of
describing complex XML summaries of Web collections.
DescribeX supports the construction of heterogeneous
summaries that can be declaratively defined and refined
by means of axis path regular expression (AxPREs).
AxPREs provide the flexibility necessary for
declaratively defining complex mappings between
instance nodes (in the documents) and summary nodes.
These mappings are capable of expressing order and
cardinality, among other properties, which can
significantly help in the understanding of the
structure of large collections of XML documents and
enhance the performance of Web applications over these
collections. DescribeX captures most summary proposals
in the literature by providing (for the first time) a
common declarative definition for them. Experimental
results demonstrate the scalability of DescribeX
summary operations (summary creation, as well as
refinement and stabilization, two key enablers for
tailoring summaries) on multi-gigabyte Web
collections.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Transactions on the Web (TWEB)",
keywords = "Semistructured data; structural summaries; XML;
XPath",
}
@Article{Ding:2010:PCM,
author = "Jason Jianxun Ding and Abdul Waheed and Jingnan Yao
and Laxmi N. Bhuyan",
title = "Performance characterization of multi-thread and
multi-core processors based {XML} application oriented
networking systems",
journal = j-J-PAR-DIST-COMP,
volume = "70",
number = "5",
pages = "584--597",
month = may,
year = "2010",
CODEN = "JPDCER",
ISSN = "0743-7315 (print), 1096-0848 (electronic)",
ISSN-L = "0743-7315",
bibdate = "Wed Sep 1 16:27:28 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www.sciencedirect.com/science/journal/07437315",
acknowledgement = ack-nhfb,
fjournal = "Journal of Parallel and Distributed Computing",
journal-URL = "http://www.sciencedirect.com/science/journal/07437315",
}
@Article{Fisher:2010:NDD,
author = "Kathleen Fisher and Yitzhak Mandelbaum and David
Walker",
title = "The next 700 data description languages",
journal = j-J-ACM,
volume = "57",
number = "2",
pages = "10:1--10:??",
month = jan,
year = "2010",
CODEN = "JACOAH",
DOI = "https://doi.org/10.1145/1667053.1667059",
ISSN = "0004-5411",
ISSN-L = "0004-5411",
bibdate = "Mon Mar 15 11:20:36 MDT 2010",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "In the spirit of Landin, we present a calculus of
dependent types to serve as the semantic foundation for
a family of languages called {\em data description
languages}. Such languages, which include pads,
datascript, and packettypes, are designed to facilitate
programming with {\em ad hoc data}, that is, data not
in well-behaved relational or xml formats. In the
calculus, each type describes the physical layout and
semantic properties of a data source. In the semantics,
we interpret types simultaneously as the in-memory
representation of the data described and as parsers for
the data source. The parsing functions are robust,
automatically detecting and recording errors in the
data stream without halting parsing. We show the
parsers are type-correct, returning data whose type
matches the simple-type interpretation of the
specification. We also prove the parsers are
``error-correct,'' accurately reporting the number of
physical and semantic errors that occur in the returned
data. We use the calculus to describe the features of
various data description languages, and we discuss how
we have used the calculus to improve pads.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "Journal of the ACM",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J401",
keywords = "ad hoc data formats; context-sensitive grammars; data
description languages; data processing; data-dependent
grammars; dependent types; domain-specific languages;
PADS; Parsing",
}
@Article{Gao:2010:EEQ,
author = "Jun Gao and Jiaheng Lu and Tengjiao Wang and Dongqing
Yang",
title = "Efficient evaluation of query rewriting plan over
materialized {XML} view",
journal = j-J-SYST-SOFTW,
volume = "83",
number = "6",
pages = "1029--1038",
month = jun,
year = "2010",
CODEN = "JSSODM",
ISSN = "0164-1212",
ISSN-L = "0164-1212",
bibdate = "Tue Sep 7 07:27:05 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www.sciencedirect.com/science/journal/01641212",
acknowledgement = ack-nhfb,
fjournal = "The Journal of systems and software",
journal-URL = "http://www.sciencedirect.com/science/journal/01641212",
}
@Article{Hwang:2010:WCS,
author = "Jeong Hee Hwang and Keun Ho Ryu",
title = "A weighted common structure based clustering technique
for {XML} documents",
journal = j-J-SYST-SOFTW,
volume = "83",
number = "7",
pages = "1267--1274",
month = jul,
year = "2010",
CODEN = "JSSODM",
ISSN = "0164-1212",
ISSN-L = "0164-1212",
bibdate = "Tue Sep 7 07:27:06 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www.sciencedirect.com/science/journal/01641212",
acknowledgement = ack-nhfb,
fjournal = "The Journal of systems and software",
journal-URL = "http://www.sciencedirect.com/science/journal/01641212",
}
@Article{Kabak:2010:SAE,
author = "Yildiray Kabak and Asuman Dogac",
title = "A survey and analysis of electronic business document
standards",
journal = j-COMP-SURV,
volume = "42",
number = "3",
pages = "11:1--11:??",
month = mar,
year = "2010",
CODEN = "CMSVAN",
DOI = "https://doi.org/10.1145/1670679.1670681",
ISSN = "0360-0300 (print), 1557-7341 (electronic)",
ISSN-L = "0360-0300",
bibdate = "Thu Mar 25 09:34:56 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/surveys/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "No document standard is sufficient for all purposes
because the requirements significantly differ among
businesses, industries, and geopolitical regions. On
the other hand, the ultimate aim of business document
interoperability is to exchange business data among
partners without any prior agreements related to the
document syntax and semantics. Therefore, an important
characteristic of a document standard is its ability to
adapt to different contexts, its extensibility, and its
customization. The UN/CEFACT Core Component Technical
Specification (CCTS) is an important landmark in this
direction.\par
In this article, we present a survey and an analysis of
some of the prominent UN/CEFACT CCTS-based electronic
document standards. We describe their document design
principles and discuss how they handle customization
and extensibility. We address their industry relevance
and the recent efforts for their harmonization and
convergence. We conclude by mentioning some emerging
efforts for the semantic interoperability of different
document standards.",
acknowledgement = ack-nhfb,
articleno = "11",
fjournal = "ACM Computing Surveys",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J204",
keywords = "Document Interoperability Standards; eBusiness; Global
Standards One (GS1) XML; OAGIS Business Object
Documents (BODs); OASIS Universal Business Language
(UBL); UN/CEFACT Core Component Technical Specification
(CCTS)",
}
@Article{Lee:2010:SCE,
author = "Ki-Hoon Lee and Kyu-Young Whang and Wook-Shin Han and
Min-Soo Kim",
title = "Structural consistency: enabling {XML} keyword search
to eliminate spurious results consistently",
journal = j-VLDB-J,
volume = "19",
number = "4",
pages = "503--529",
month = aug,
year = "2010",
CODEN = "VLDBFR",
DOI = "https://doi.org/10.1007/s00778-009-0177-7",
ISSN = "1066-8888 (print), 0949-877X (electronic)",
ISSN-L = "1066-8888",
bibdate = "Wed Aug 18 12:06:22 MDT 2010",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "XML keyword search is a user-friendly way to query XML
data using only keywords. In XML keyword search, to
achieve high precision without sacrificing recall, it
is important to remove spurious results not intended by
the user. Efforts to eliminate spurious results have
enjoyed some success using the concepts of LCA or its
variants, SLCA and MLCA. However, existing methods
still could find many spurious results. The fundamental
cause for the occurrence of spurious results is that
the existing methods try to eliminate spurious results
locally without global examination of all the query
results and, accordingly, some spurious results are not
consistently eliminated. In this paper, we propose a
novel keyword search method that removes spurious
results consistently by exploiting the new concept of
structural consistency. We define structural
consistency as a property that is preserved if there is
no query result having an ancestor-descendant
relationship at the schema level with any other query
results. A naive solution to obtain structural
consistency would be to compute all the LCAs (or
variants) and then to remove spurious results according
to structural consistency. Obviously, this approach
would always be slower than existing LCA-based ones. To
speed up structural consistency checking, we must be
able to examine the query results at the schema level
without generating all the LCAs. However, this is a
challenging problem since the schema-level query
results do not homomorphically map to the
instance-level query results, causing serious false
dismissal. We present a comprehensive and practical
solution to this problem and formally prove that this
solution preserves structural consistency at the schema
level without incurring false dismissal. We also
propose a relevance-feedback-based solution for the
problem where our method has low recall, which occurs
when it is not the user's intention to find more
specific results. This solution has been prototyped in
a full-fledged object-relational DBMS Odysseus
developed at KAIST. Experimental results using real and
synthetic data sets show that, compared with the
state-of-the-art methods, our solution significantly
(1) improves precision while providing comparable
recall for most queries and (2) enhances the query
performance by removing spurious results early.",
acknowledgement = ack-nhfb,
fjournal = "VLDB Journal: Very Large Data Bases",
journal-URL = "http://portal.acm.org/toc.cfm?id=J869",
keywords = "Keyword search; Odysseus DBMS; Spurious results;
Structural consistency; Structural summary; XML",
}
@Article{Lin:2010:NXK,
author = "Xudong Lin and Ning Wang and De Xu and Xiaoning Zeng",
title = "A novel {XML} keyword query approach using entity
subtree",
journal = j-J-SYST-SOFTW,
volume = "83",
number = "6",
pages = "990--1003",
month = jun,
year = "2010",
CODEN = "JSSODM",
ISSN = "0164-1212",
ISSN-L = "0164-1212",
bibdate = "Tue Sep 7 07:27:05 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www.sciencedirect.com/science/journal/01641212",
acknowledgement = ack-nhfb,
fjournal = "The Journal of systems and software",
journal-URL = "http://www.sciencedirect.com/science/journal/01641212",
}
@Article{Liu:2010:IXS,
author = "Ziyang Liu and Yu Huang and Yi Chen",
title = "Improving {XML} search by generating and utilizing
informative result snippets",
journal = j-TODS,
volume = "35",
number = "3",
pages = "19:1--19:??",
month = jul,
year = "2010",
CODEN = "ATDSD3",
DOI = "https://doi.org/10.1145/1806907.1806911",
ISSN = "0362-5915 (print), 1557-4644 (electronic)",
ISSN-L = "0362-5915",
bibdate = "Wed Jul 28 15:53:01 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/tods/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "Snippets are used by almost every text search engine
to complement the ranking scheme in order to
effectively handle user searches, which are inherently
ambiguous and whose relevance semantics are difficult
to assess. Despite the fact that XML is a standard
representation format of Web data, research on
generating result snippets for XML search remains
limited.\par
To tackle this important yet open problem, in this
article, we present a system extract which generates
snippets for XML search results. We identify that a
good XML result snippet should be a meaningful
information unit of a small size that effectively
summarizes this query result and differentiates it from
others, according to which users can quickly assess the
relevance of the query result. We have designed and
implemented a novel algorithm to satisfy these
requirements. Furthermore, we propose to cluster the
query results based on their snippets. Since XML result
clustering can only be done at query time,
snippet-based clustering significantly improves the
efficiency while compromising little clustering
accuracy. We verified the efficiency and effectiveness
of our approach through experiments.",
acknowledgement = ack-nhfb,
articleno = "19",
fjournal = "ACM Transactions on Database Systems",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J777",
keywords = "clustering; keyword search; snippets; XML",
}
@Article{Liu:2010:RSI,
author = "Ziyang Liu and Yi Chen",
title = "Return specification inference and result clustering
for keyword search on {XML}",
journal = j-TODS,
volume = "35",
number = "2",
pages = "10:1--10:??",
month = apr,
year = "2010",
CODEN = "ATDSD3",
DOI = "https://doi.org/10.1145/1735886.1735889",
ISSN = "0362-5915 (print), 1557-4644 (electronic)",
ISSN-L = "0362-5915",
bibdate = "Wed Apr 28 13:44:08 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/tods/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "Keyword search enables Web users to easily access XML
data without the need to learn a structured query
language and to study possibly complex data schemas.
Existing work has addressed the problem of selecting
qualified data nodes that match keywords and connecting
them in a meaningful way, in the spirit of inferring
the {\em where clause\/} in XQuery. However, how to
infer the {\em return clause\/} for keyword searches is
an open problem.\par
To address this challenge, we present a keyword search
engine for data-centric XML, XSeek, to infer the
semantics of the search and identify return nodes
effectively. XSeek recognizes possible entities and
attributes inherently represented in the data. It also
distinguishes between predicates and return
specifications in query keywords. Then based on the
analysis of both XML data structures and keyword
patterns, XSeek generates return nodes. Furthermore,
when the query is ambiguous and it is hard or
impossible to determine the desirable return
information, XSeek clusters the query results according
to their semantics based on the user-specified
granularity, and enables the user to easily browse and
select the desired ones. Extensive experimental studies
show the effectiveness and efficiency of XSeek.",
acknowledgement = ack-nhfb,
articleno = "10",
fjournal = "ACM Transactions on Database Systems",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J777",
keywords = "keyword search; result clustering; XML",
}
@Article{Martens:2010:CDP,
author = "Wim Martens and Frank Neven and Thomas Schwentick",
title = "Complexity of Decision Problems for {XML} Schemas and
Chain Regular Expressions",
journal = j-SIAM-J-COMPUT,
volume = "39",
number = "4",
pages = "1486--1530",
month = "????",
year = "2010",
CODEN = "SMJCAT",
DOI = "",
ISSN = "0097-5397 (print), 1095-7111 (electronic)",
ISSN-L = "0097-5397",
bibdate = "Tue May 18 08:22:14 MDT 2010",
bibsource = "http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP/39/4;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
acknowledgement = ack-nhfb,
fjournal = "SIAM Journal on Computing",
journal-URL = "http://epubs.siam.org/sicomp",
}
@Article{Miori:2010:DTI,
author = "Vittorio Miori and Dario Russo and Massimo Aliberti",
title = "Domotic technologies incompatibility becomes user
transparent",
journal = j-CACM,
volume = "53",
number = "1",
pages = "153--157",
month = jan,
year = "2010",
CODEN = "CACMA2",
DOI = "https://doi.org/10.1145/1629175.1629211",
ISSN = "0001-0782 (print), 1557-7317 (electronic)",
ISSN-L = "0001-0782",
bibdate = "Thu Feb 4 17:12:32 MST 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/cacm/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "The potential of current technologies in smart
automation has been largely unexploited. Pervasive
computing vision is still far from being achieved,
especially with regard to Domotics and home
applications. In fact, even though many implementations
have started to appear in several contexts, few
applications have been made available for the home
environment and the general public. This is mainly due
to the segmentation of standards and proprietary
solutions, which are currently confusing the market
with a sparse offer of uninteroperable devices and
systems.\par
Although modern houses are equipped with smart
technological appliances, still very few of these
appliances can be seamlessly connected to each
other.\par
Moreover, inter-working capabilities are required
beyond house boundaries, towards external services and
towards other houses as nodes of a global
network.\par
Therefore, the main goal of this research is to find
solutions to the problem of interoperability that will
be in line with open and widely recognized
standards.\par
The result is a computing framework based on open
communication standards, capable of abstracting the
peculiarities of underlying heterogeneous technologies,
and letting them co-exist and interwork, without
eliminating their differences. Interoperability can
thus be made potentially feasible between any domotic
technology, both currently existing, and still to be
defined.\par
Currently, domotic technology vendors concentrate on
building closed relationships with their customers, and
leveraging their economic investments by establishing
barriers against new manufacturers entering the
market.\par
Examples of current domotic protocols are X10, Konnex,
LonWorks, UPnP, HAVi, and Jini supporting various
communication standards (Ethernet, FireWire, Bluetooth,
ZigBee, IrDA and proprietary buses). We believe that no
domotic technology currently has the potential to
actually play a leading role. Within this wide and
heterogeneous framework, the market logic is to tie
consumers to a particular domotic protocol, which then
forces them to only purchase conforming devices in
order to keep a consistent level of
interoperability.\par
In recent years several interesting and innovative
solutions have emerged, with a reasonable level of
scalability and dependability, providing
interoperability among heterogeneous home
systems.\par
Twente University has proposed a solution that aims at
supporting heterogeneous technologies (including legacy
ones) with a 'cluster cultures' approach. The
architecture outlines a 'touch and play' system which,
at device registration time, enables a
zero-configuration environment for the exchange of
credentials among its gateways and to register device
services in a hierarchical structure. The architecture
provides a high level of security by using
cryptographic algorithms.\par
Waseda University have proposed a framework designed to
easily enable the integration of legacy middleware and
legacy services and clients, with a predefined path for
the inclusion of new, future, middleware. This is
accomplished mainly through the use of a Virtual
Service Gateway. This connects one piece of middleware
to another by exploiting a Protocol Conversion Manager,
whose task is to convert the different middleware
protocols into the specific internal protocol used by
the Virtual Service Gateway. Information about the
location and functions of services is provided by a
Virtual Service Repository.\par
Another interesting project is the 'Domotic House
Gateway.' It implements an event-based mechanism which
is used to exchange messages between the single device
and the system. These events are internally converted
into logical events so as to clearly separate the
actual physical issues from the semantics that goes
beyond the devices and their role within the house. One
level of the architecture implements a rule-based core
that can be dynamically adapted either by the system
itself or manually through external interfaces. Each
device needs a device driver, which is responsible for
translating its low level or hardware states and
activities into events that can be managed by the
system.\par
Another promising approach, in line with our research,
is proposed by the Open Building Information Exchange
group who are working to create standard XML and Web
Services guidelines to facilitate information exchange
among mechanical and electrical systems in building
automation.\par
One such important European project in this context is
Amigo. This project was aimed at Ambient Intelligence
features for the networked home environment and the
usability of the system was among its main goals and
included three major guidelines: user-friendly
interfaces, interoperability, and automatic discovery
of devices and services.\par
All these projects resolved the interoperability
problem with several approaches, all of which are
different from what we consider, in our vision, as the
optimal solutions.\par
Lastly, we enlist a prototype previously created by our
research laboratory. This solution had the limitation
of abstracting each device typology with a Web service
implementing their specific functionalities. The
implementation of a new ad hoc Web service was needed
whenever a new category of device needed to be included
in the network. In addition, this prototype solved the
problem of cooperation by virtualizing devices
belonging to each domotic system onto the others. This
solution, however, had a drawback: the same device
appeared virtually replicated on every single domotic
system, thus creating data replications and possible
consistency problems.",
acknowledgement = ack-nhfb,
fjournal = "Communications of the ACM",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J79",
}
@Book{Pilgrim:2010:HR,
author = "Mark Pilgrim",
title = "{HTML5}: up and running",
publisher = pub-ORA,
address = pub-ORA:adr,
pages = "250",
year = "2010",
ISBN = "0-596-80602-7",
ISBN-13 = "978-0-596-80602-6",
LCCN = "????",
bibdate = "Wed Jul 28 20:15:48 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
z3950.bibsys.no:2100/BIBSYS",
acknowledgement = ack-nhfb,
}
@Article{Romei:2010:XDM,
author = "Andrea Romei and Franco Turini",
title = "{XML} data mining",
journal = j-SPE,
volume = "40",
number = "2",
pages = "101--130",
day = "??",
month = feb,
year = "2010",
CODEN = "SPEXBL",
DOI = "https://doi.org/10.1002/spe.944",
ISSN = "0038-0644 (print), 1097-024X (electronic)",
ISSN-L = "0038-0644",
bibdate = "Wed Mar 17 10:16:22 MDT 2010",
bibsource = "http://www.interscience.wiley.com/jpages/0038-0644;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www3.interscience.wiley.com/journalfinder.html",
acknowledgement = ack-nhfb,
fjournal = "Software---Practice and Experience",
journal-URL = "http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1097-024X",
onlinedate = "Dec 23 2009 8:58AM",
}
@Book{Schmitt:2010:CC,
author = "Christopher Schmitt",
title = "{CSS} cookbook",
publisher = pub-ORA,
address = pub-ORA:adr,
edition = "Third",
pages = "xxiv + 702",
year = "2010",
ISBN = "0-596-15593-X (paperback)",
ISBN-13 = "978-0-596-15593-3 (paperback)",
LCCN = "TK5105.888 .S3524 2010",
bibdate = "Wed Jul 28 09:08:49 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
z3950.loc.gov:7090/Voyager",
note = "Foreword by Dan Cederholm.",
acknowledgement = ack-nhfb,
remark = "Updated for Firefox 3, IE 8, and Chrome.",
subject = "Cascading style sheets; Web sites; Design; Cascading
Style Sheets 2.1; Cascading Style Sheets",
}
@Article{Silvasti:2010:ELX,
author = "P. Silvasti and S. Sippu and E. Soisalon-Soininen",
title = "Evaluating Linear {XPath} Expressions by
Pattern-Matching Automata",
journal = j-J-UCS,
volume = "16",
number = "5",
pages = "833--??",
month = "????",
year = "2010",
CODEN = "????",
ISSN = "0948-6968",
ISSN-L = "0948-6968",
bibdate = "Wed Aug 25 21:53:00 MDT 2010",
bibsource = "http://www.jucs.org/jucs;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
URL = "http://www.jucs.org/jucs_16_5/evaluating_linear_xpath_expressions",
acknowledgement = ack-nhfb,
fjournal = "J.UCS: Journal of Universal Computer Science",
journal-URL = "http://www.jucs.org/jucs",
}
@Article{Stamerjohanns:2010:TLC,
author = "Heinrich Stamerjohanns and Michael Kohlhase and Deyan
Ginev and Catalin David and Bruce Miller",
title = "Transforming Large Collections of Scientific
Publications to {XML}",
journal = j-MATH-COMPUT-SCI,
volume = "3",
number = "3",
pages = "299--307",
month = may,
year = "2010",
CODEN = "????",
ISSN = "1661-8270 (print), 1661-8289 (electronic)",
ISSN-L = "1661-8270",
bibdate = "Sun Aug 22 09:02:18 MDT 2010",
bibsource = "http://springerlink.metapress.com/openurl.asp?genre=issue&issn=1661-8270&volume=3&issue=3;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
URL = "http://www.springerlink.com/openurl.asp?genre=article&issn=1661-8270&volume=3&issue=3&spage=299",
abstract = "We describe an experiment transforming large
collections of {\LaTeX} documents to more
machine-understandable representations. Concretely, we
are translating the collection of scientific
publications of the Cornell e-Print Archive ({ar$ \chi
$}iv) using {\LaTeX{}ML}, a {\LaTeX} to XML converter
currently under development. While the long-term goal
is a large body of scientific documents available for
semantic analysis, search indexing and other
experimentation, the immediate goals are tools for
creating such corpora. The first task of our arXMLiv
project is to develop {\LaTeX{}ML} bindings for the
(thousands of) {\LaTeX} classes and packages used in
the {ar$ \chi $}iv collection, as well as methods for
coping with the eccentricities that {\TeX} encourages.
We have created a distributed build system that runs
{\LaTeX{}ML} over the collection, in part or entirely,
while collecting statistics about missing bindings and
other errors. This guides debugging and development
efforts, leading to iterative improvements in both the
tools and the quality of the converted corpus. The
build system thus serves as both a production
conversion engine and software test harness. We have
now processed the complete {ar$ \chi $}iv collection
through 2006 consisting of more than 400,000 documents
(a complete run is a processor-year-size undertaking),
continuously improving our success rate. We are now
able to convert more than 90\% of these documents to
XHTML $+$ MathML. We consider over 60\% to be
successes, converted with no or minor warnings. While
the remaining 30\% can also be converted, their quality
is doubtful, due to unsupported macros or conversion
errors.",
acknowledgement = ack-nhfb,
fjournal = "Mathematics in Computer Science",
journal-URL = "http://www.springerlink.com/content/1661-8270/",
}
@Book{Stark:2010:BIA,
author = "Jonathan Stark",
title = "Building {iPhone} apps with {HTML}, {CSS}, and
{JavaScript}: Making {App Store} apps without
{Objective-C} or {Cocoa}",
publisher = pub-ORA-MEDIA,
address = pub-ORA-MEDIA:adr,
pages = "xv + 166",
year = "2010",
ISBN = "1-4493-8023-9, 0-596-80578-0",
ISBN-13 = "978-1-4493-8023-6, 978-0-596-80578-4",
LCCN = "????",
bibdate = "Wed Jul 28 09:12:55 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
z3950.bibsys.no:2100/BIBSYS",
acknowledgement = ack-nhfb,
subject = "Cascading Style Sheets; HTML (document markup
language); computer software; development; iPhone
(Smartphone); programming; JavaScript (computer program
language)",
}
@Article{Tagarelli:2010:SCX,
author = "Andrea Tagarelli and Sergio Greco",
title = "Semantic clustering of {XML} documents",
journal = j-TOIS,
volume = "28",
number = "1",
pages = "3:1--3:??",
month = jan,
year = "2010",
CODEN = "ATISET",
ISSN = "1046-8188",
ISSN-L = "0734-2047",
bibdate = "Mon Mar 15 12:37:04 MDT 2010",
bibsource = "http://www.acm.org/pubs/contents/journals/tois/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
acknowledgement = ack-nhfb,
articleno = "3",
fjournal = "ACM Transactions on Information Systems",
}
@Article{TenCate:2010:TCL,
author = "Balder {Ten Cate} and Luc Segoufin",
title = "Transitive closure logic, and nested tree walking
automata, and {Xpath}",
journal = j-J-ACM,
volume = "57",
number = "3",
pages = "18:1--18:??",
month = mar,
year = "2010",
CODEN = "JACOAH",
DOI = "https://doi.org/10.1145/1706591.1706598",
ISSN = "0004-5411",
ISSN-L = "0004-5411",
bibdate = "Thu Mar 25 09:08:48 MDT 2010",
bibsource = "http://portal.acm.org/;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
abstract = "We study FO(MTC), first-order logic with monadic
transitive closure, a logical formalism in between FO
and MSO on trees. We characterize the expressive power
of FO(MTC) in terms of nested tree-walking automata.
Using the latter, we show that FO(MTC) is strictly less
expressive than MSO, solving an open problem. We also
present a temporal logic on trees that is expressively
complete for FO(MTC), in the form of an extension of
the XML document navigation language XPath with two
operators: the Kleene star for taking the transitive
closure of path expressions, and a subtree
relativisation operator, allowing one to restrict
attention to a specific subtree while evaluating a
subexpression. We show that the expressive power of
this XPath dialect equals that of FO(MTC) for Boolean,
unary and binary queries. We also investigate the
complexity of the automata model as well as the XPath
dialect. We show that query evaluation be done in
polynomial time (combined complexity), but that
emptiness (or, satisfiability) is 2ExpTime-complete.",
acknowledgement = ack-nhfb,
articleno = "18",
fjournal = "Journal of the ACM",
journal-URL = "http://portal.acm.org/browse_dl.cfm?idx=J401",
keywords = "Transitive closure logic; tree automata; XPath",
}
@Article{Vaughan-Nichols:2010:WHR,
author = "Steven J. Vaughan-Nichols",
title = "Will {HTML 5} Restandardize the {Web}?",
journal = j-COMPUTER,
volume = "43",
number = "4",
pages = "13--15",
month = apr,
year = "2010",
CODEN = "CPTRB4",
DOI = "https://doi.org/10.1109/MC.2010.119",
ISSN = "0018-9162 (print), 1558-0814 (electronic)",
ISSN-L = "0018-9162",
bibdate = "Wed May 12 22:57:42 MDT 2010",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
acknowledgement = ack-nhfb,
fjournal = "Computer",
journal-URL = "http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=2",
}
@Article{Kohlhase:2012:SOM,
author = "Michael Kohlhase and Florian Rabe",
title = "Semantics of {OpenMath} and {MathML 3}",
journal = j-MATH-COMPUT-SCI,
volume = "6",
number = "3",
pages = "235--260",
month = sep,
year = "2012",
CODEN = "????",
DOI = "https://doi.org/10.1007/s11786-012-0113-x",
ISSN = "1661-8270 (print), 1661-8289 (electronic)",
ISSN-L = "1661-8270",
bibdate = "Tue Nov 6 10:16:26 MST 2012",
bibsource = "http://springerlink.metapress.com/openurl.asp?genre=issue&issn=1661-8270&volume=6&issue=3;
http://www.math.utah.edu/pub/tex/bib/math-comput-sci.bib;
http://www.math.utah.edu/pub/tex/bib/sgml2010.bib",
URL = "http://www.springerlink.com/openurl.asp?genre=article&issn=1661-8270&volume=6&issue=3&spage=235",
acknowledgement = ack-nhfb,
fjournal = "Mathematics in Computer Science",
journal-URL = "http://www.springerlink.com/content/1661-8270/",
}
@Book{Pozrikidis:2013:XSC,
author = "C. Pozrikidis",
title = "{XML} in scientific computing",
publisher = pub-CRC,
address = pub-CRC:adr,
pages = "xv + 243 pages",
year = "2013",
ISBN = "1-4665-1227-X (hardback)",
ISBN-13 = "978-1-4665-1227-6 (hardback)",
LCCN = "Q183.9 .P69 2013",
bibdate = "Fri Nov 16 06:32:54 MST 2012",
bibsource = "http://www.math.utah.edu/pub/tex/bib/sgml2010.bib;
http://www.math.utah.edu/pub/tex/bib/super.bib;
z3950.loc.gov:7090/Voyager",
series = "Chapman and Hall/CRC numerical analysis and scientific
computing series",
acknowledgement = ack-nhfb,
subject = "XML (Document markup language); Science; Data
processing; Numerical analysis; COMPUTERS / Internet /
General.; MATHEMATICS / General.; MATHEMATICS / Number
Systems.",
}
