title: Open Access to Monopoly Cable Platforms Versus Direct Access To Competitive International Telecommunications Satellite Facilities: A Study In Contrasts

abstract: In 1999, the FCC authorized direct access to INTELSAT, allowing INTELSAT's U.S. customers and competitors to bypass INTELSAT's U.S. retail affiliate (COMSAT), and to take satellite capacity at wholesale prices directly from INTELSAT. This policy was modeled in many respects on the access and unbundling requirements applicable to domestic incumbent local exchange carriers (ILECs) under the Telecommunications Act of 1996. At the same time, incumbent domestic cable TV system operators have not been required to provide wholesale open access to competitive Internet Service Providers (ISPs) seeking to provide residential broadband Internet service through existing proprietary cable facilities. Yet the policy arguments favoring open access to incumbent domestic cable systems appear to be stronger than those favoring direct access to INTELSAT. For example, it may be fairly debated whether entrenched cable system operators are now positioned to unfairly leverage their dominance in the multichannel video programming distribution (MVPD) market to thwart competition in the broadband ISP market, as some cable open access advocates assert. In contrast, it is clear that no analogous issues of tying were implicated by INTELSAT in 1999, when its position in the international telecommunications market was substantially nondominant and, in any event, it had no new product to tie to its established offerings. Similarly, while it may be debated whether or not a cable plant is a bottleneck facility that gatekeeps broadband Internet for many residential users, it is beyond cavil that INTELSAT in 1999 controlled virtually no such bottleneck facilities.


title: Competition and Globalization Brazilian Telecommunications Policy at Crossroads

abstract: The current pattern of competition in the Brazilian telecommunications market was defined by a regulatory reform implemented in the second half of the nineties. The telecommunications regulatory reform discussed in the paper promoted the privatization of Telebras System and fostered competition in the Brazilian market under the stricted supervision of the new regulator Anatel. Notwithstanding, the regulatory Brazilian scheme is at a crossroads. From 2002 on an open market approach will be implemented in telecom arena. We analyse the main aspects of those change, from the firms perspective and also in a broad scenario under influence of the World Trade Organization system


title: Assessing the Effectiveness of Section 271 Five Years After the Telecommunications Act of 1996

abstract: A major goal of the Telecommunications Act of 1996 is to promote competition in both the local exchange and long distance wireline markets. In section 271 Congress permitted the Bell Operating Companies (BOCs) to enter the long distance market only if they demonstrate to the FCC that they have complied with the market-opening requirements of section 251. This paper examines the logic behind section 271, to determine if it is a reasonable means of achieving increased competition in both the local and long distance markets, given the technical characteristics of the industry and the legal and informational constraints on regulators who must ensure compliance. It also provides an update on the extent of competitive entry in the local exchange market five years after enactment of the Act. In this paper we examine a variety of schemes for ensuring BOC compliance that Congress could have used. Given the characteristics of the industry and the limitations on regulators' ability to observe BOC's efforts, we determine that the use of a prize such as BOC entry into long distance is a superior incentive mechanism. We further determine that conditioning a BOC's long distance entry on its demonstrating compliance with section 251 is a logical method of protecting the long distance market against a BOC discriminating against long distance competitors once it has gained entry. The statistical evidence we look at, using data we have collected on ILEC lines sold to CLECs for POTS services, appears to confirm that section 271 has thus far been effective in ensuring compliance.


title: CyberCampaigns and Canadian Politics: Still Waiting?

abstract: The early election call in the fall of 2000 provided the perfect opportunity to study the impact the Internet has had on election campaigning in Canada. With the explosion of use the Net has seen since the 1997 general election, Canadian federal parties stood at the threshold of a new age in election campaigning. Pundits such as Rheingold (1993) have argued that the Internet will provide citizens with a way to bypass traditional media and gain unmediated access to each parties political message as well as providing a forum for citizens to engage the parties, and each other in deliberative debate. Through a longitudinal analysis of party web pages and telephone interviews with party staffers, we analyze the role the Internet played in the election campaigns of Canada's federal parties. Our findings indicate that the parties are still focusing on providing online features that talk at the voter instead of engaging them in any type of meaningful discourse. Most of these sites were exceptionally similar in their structure and in the type of content they provided. Generally, these sites served as digital archives for campaign material created with other media in mind and despite the multimedia capabilities of the Internet, these sites tended to be overwhelmingly text oriented. In line with Stromer-Galley's (2000) discussion of why candidates in the U.S. avoid online interaction, we also argue that little incentive exists to motivate parties to engage in any meaningful interaction with voters online.


title: 'Negotiated Liberalization': Stakeholder Politics and Communication Sector Reform in South Africa

abstract: The paper examines the South African transition from apartheid to democracy through the lens of the reform of the communication sector. Through a set of participatory stakeholder consultative processes, the institutions of broadcasting, telecommunications, print press, and state information agency underwent reform in a process I refer to as 'negotiated liberalization.'


title: The Influence of Policy Regimes on the Development and Social Implications of Privacy Enhancing Technologies

abstract: As privacy issues have gained social salience, entrepreneurs have begun to offer privacy enhancing technologies (PETs) and the U.S. has begun to enact privacy legislation. But "privacy" is an ambiguous notion. In the liberal tradition, it is an individualistic value protecting citizens from intrusion into a realm of autonomy. A feminist critique suggests that the social utility of privacy is to exclude certain issues from the public realm. Sociologists suggest that privacy is about identity management, while political economists suggest that the most salient privacy issue is the use of personal information to normalize and rationalize populations according to the needs of capital. While PETs have been developed for use by individual consumers, recently developers are focusing on the business to business market, where demand is stoked by the existence of new privacy regulations. These new laws tend to operationalize privacy in terms of "personally identifiable information." The new generation of PETs reflect and reify that definition. This, in turn, has implications for the everyday understandings of privacy and the constitution of identity and social life. In particular, this socio-technical practice may strengthen the ability of data holders to rationalize populations and create self-serving social categories. At the same time, they may permit individuals to negotiate these categories outside of panoptic vision. They may also encourage public discussion and awareness of these created social categories.


title: ICANN as Regulator

abstract: This paper tells the story leading to ICANN's selection of seven new Internet top level domains in November 2000. In implementing proposals to expand the name space, ICANN adopted an approach far different from Jon Postel's lightweight proposals. ICANN staff, in setting the ground rules for considering new gTLDs, emphasized that only a few applicants would be allowed in, and imposed strict threshold requirements. Staff determined that the Board should pick TLDs by looking at all relevant aspects of every proposal, and deciding which ones presented the best overall combination of a variety of incommensurable factors. Aspects of the resulting process were predictable: Anyone familiar with the FCC comparative hearing process for broadcast licenses can attest that this sort of ad hoc comparison is necessarily subjective, lending itself to arbitrariness and biased application. Yet the process had advantages that appealed to ICANN decision-makers. The Board members would be free to take their best shots, in a situationally sensitive manner, at advancing the policies they thought important. The approach allowed ICANN to maintain the greatest degree of control. The end result, though, was a process stunning in its arbitrariness, a bad parody of fact-bound, situationally sensitive (rather than rules-based) decision-making.


title: Comparison of Wireless Standards-Setting --United States Versus Europe

abstract: When decisions about developing standards are left to individual firms, there are many advantages including a flexible response to market evolution, accommodation to rapid technology change, and avoidance of costly coordination. However, the market process does not necessarily lead to compatible standards, especially when there is no clear market dominator. Standards Institutions generally facilitate better communication among market participants, which may discourage early and/or primitive incompatible standards to emerge in the market. However, expenditures on institutional standards-setting can lead to diminishing returns, or even be counter-productive because institutional standards usually take longer to produce and are slower to respond to technology development. Government agencies can specify compulsory standards to avoid incompatibility. In addition, governments can tie their policy on standardization closely with their industrial, trade, and/or regulatory policies. However, many exogenous factors handicap a government's effective involvement. Government often fails to respond to the dynamics of technology development and consumer demand, and to pick up the "right technology". This study first discusses why two different models have emerged in the two regions. It then examines outcomes and implications of the two models, including impacts on domestic service deployment, global trade competition, technology innovations, and strategies of multinational corporations. The goal is to conduct an empirical comparison between the two contrasting models.


title: Best Effort versus Spectrum Markets: Best Effort versus Spectrum Markets: The Cases of European MVNOs and (Ultra)Wideband Unlicensed Services

abstract: This paper compares two models for delivering broadband wireless services: best effort vs. QoS guaranteed services. The 'best effort' services we refer to in this paper are more commonly known as unlicensed wireless services, while the 'Quality of Service guaranteed' services are more commonly referred to as traditional landline telephony, as well as cellular telephone services of either the second or third generation. This paper highlights the differing 'market' versus 'engineering' philosophies implicit in alternative wireless service architectures.


title: The Next Frontier for Openness: Wireless Communications

abstract: For wireless communications, the FCC has fostered competition rather than openness. This has permitted the emergence of vertically integrated end-to-end providers, creating problems of reduced hardware innovation, software applications, user choice, and content access. To deal with these emerging issues and create multi-level forms of competition, one policy is likely to suffice: a Carterfone for wireless, coupled with more unlicensed spectrum.


title: Leveraging Software, Advocating Ideology: Free Software and Open Source

abstract: This paper uses the software program Linux and the discourse around it in order to examine how software programs can be used to articulate and defend social and economic positions. Although I do not use the term "expression" in a strict legal sense, I claim that in order to make policy decisions involving software, it is important to understand how the functionality of software is expressive. Another way to state this is that software programs like Linux are socially meaningful through functionality and talk about functionality. In section I, I review some recent legal scholarship about software and explain why understanding how embedded technical expression works is important given the increasingly large role of software in governance. In section II, I explore software construction as a combination of social and technical practices. In section III, I describe some examples of meaning-making around the software program Linux. In section IV I conclude with a short description of why such analyses are important.


title: Universal Service in times of Reform: Affordability and accessibility of telecommunication services in Latin America

abstract: By surveying the universal service policies in six Latin American countries, this study explores the evolution of the concept during the rollout of the telecommunication reform in the last decade. Country profiles and a set of universal service indicators provide a frame for discussing issues of accessibility and affordability of telephone service in the region. This study found that the reconfiguration of national networks fostered by liberalization policies offered risks and opportunities to achieve universal service goals. The diversification of access points and services enhanced users choices but price rebalancing and lack of Universal Service Obligations (USO) to target groups with special needs depressed the demand and threatened to exclude significant parts of the population. The situation requires the reformulation of USO incorporating all technological solutions existing in the market, and factors from the consumer-demand accounting for the urban-rural continuum, and different social and economic strata. This study identifies the emergence of a second generation of USO targeting some of these needs. However, more competition and special tariff plans for the poor need to be incorporated to the options available in the market.


title: Standards and Intellectual Property Rights in the Age of Global Communication - A Review of the International Standardization of Third-Generation Mobile System

abstract: When the European Telecommunications Standards Institute (ETSI) selected a radio access technology based on Wideband Code-Division Multiple Access (WCDMA), sponsored by European telecommunications equipment manufactures Ericsson and Nokia, for its third-generation wireless communications system, a bitter dispute developed between ETSI and Qualcommm Inc. Qualcomm threatened to withhold its intellectual property on the CDMA technology unless the Europeans agreed to make the radio access technology backward compatible with cdmaOne, Qualcomm's favored version of CDMA. A dispute over intellectual property rights over key CDMA techniques also erupted between Ericsson and Qualcomm and both filed patent infringement in US Court. The dispute halted the standards activity and has troubled operators worldwide as well as the International Telecommunications Union (ITU).


title: Bigger May Not Be Better: An Empirical Analysis of Optimal Membership Rules in Peer-To-Peer Networks

abstract: Peer to peer networks will become an increasingly important distribution channel for consumer information goods and may play a role in the distribution of information within corporations. Our research analyzes optimal membership rules for these networks in light of positive and negative externalities additional users impose on the network. Using a dataset gathered from the six largest OpenNap-based networks, we find that users impose a positive network externality based on the desirability of the content they provide and a negative network externality based on demands they place on the network. Further we find that the marginal value of additional users is declining and the marginal cost is increasing in the number of current users. This suggests that multiple small networks may serve user communities more efficiently than single monolithic networks and that network operators may wish to specialize in their content and restrict membership based on capacity constraints and user content desirability.


title: Is Patent Law Technology Specific?

abstract: Although patent law purports to cover all manner of technologies, we have noticed recent divergence in the standards applied to biotechnology and to software patents: the Federal Circuit has applied a very permissive standard of obviousness in biotechnology, but a highly restrictive disclosure requirement. The opposite holds true for software patents, which seems to us exactly contrary to sound policy for either industry. These patent standards are grounded in the legal fiction of the "person having ordinary skill in the art" or PHOSITA. We discuss the appropriateness of the PHOSITA standard, concluding that it properly lends flexibility to the patent system. We then discuss the difficulty of applying this standard in different industries, offering suggestions as to how it might be modified to avoid the problems seen in biotechnology and software patents.


title: Spectrum auctions, pricing and network expansion in wireless telecommunications

abstract: This paper examines the effects of licensing conditions, in particular of spectrum fees, on the pricing and diffusion of mobile communications services. Seemingly exorbitant sums paid for 3G licenses in the UK, Germany in 2000 and similarly high fees paid by U.S. carriers in the re-auctioning of PCS licenses early in 2001 raised concerns as to the impacts of the market entry regime on the mobile communications market. The evidence from the GSM and PCS markets reviewed in this paper suggests that market entry fees do indeed influence the subsequent development of the market. We discuss three potential transmission channels by which license fees can influence the price and quantity of service sold in a wireless market: an increase in average cost, an increase in incremental costs, and impacts of sunk costs on the emerging market structure. From this conceptual debate, an empirical model is developed and tested using cross-sectional data for the residential mobile voice market. We utilize a structural equation approach, modeling the supply and demand relationships subject to the constraint that supply equals demand. The results confirm the existence of a positive effect of license fees on the cost of supply. However, we also find that higher market concentration has a positive effect on the overall supply in the market, perhaps supporting a Schumpeterian view that a certain degree of market concentration facilitates efficiency.


title: The Role of Institutions in the Design of Communication Technologies

abstract: Communication technologies contain embedded values that affect our society's fundamental values, such as privacy, freedom of speech, and the protection of intellectual property. Researchers have shown the design of technologies is not autonomous but shaped by conflicting social groups. Consequently, communication technologies contain different values when designed by different social groups. Continuing in this vein, we show that the institutions where communication technologies are designed and developed are an important source of the values of communication technologies. We use the term code to collectively refer to the hardware and software of communication technologies. Institutions differ in their motivations, structure, and susceptibility to external influences. First, we focus on the political, economic, social, and legal influences during the development of code. The institutional reactions to these influences are embodied in code. Second, we focus on the decision-making issues in the review process for code. This process determines the code's content and affects the dissemination of code through the decision whether to publicly release the code. We found these factors vary by institution. As a result, institutions differ in the values that they incorporate into code or communications technologies.


title: Efficient Choice, Inefficient Democracy? The Implications of Cable and Internet Access for Political Knowledge and Voter Turnout

abstract: This paper explains why, despite a marked increase in available political information on cable television and the Internet, citizens' levels of political knowledge have, at best, remained stagnant (Delli Carpini & Keeter, 1996). Since the availability of entertainment content has increased too, the effect of new media on knowledge and vote likelihood should be determined by people's relative preferences for entertainment and information. Access to new media should increase knowledge and vote likelihood among people who prefer news. At the same time, it is hypothesized to have a negative effect on knowledge and turnout for people who prefer entertainment content. Hypotheses are tested by building a measure of Relative Entertainment Preference (REP) from existing NES and Pew survey data. Results support the predicted interaction effect of media environment (cable and/or Internet access) and motivation (REP) on political knowledge and turnout. In particular, people who prefer entertainment to news and have access to cable television and the Internet are less knowledgeable and less likely to vote than any other group of people.


title: Quality of service monitoring: Performance metrics across proprietary content domains

abstract: We propose a quality of service (QoS) monitoring program for broadband access to measure the impact of proprietary network spaces. Our paper surveys other QoS policy initiatives, including those in the airline, and wireless and wireline telephone industries, to situate broadband in the context of other markets undergoing regulatory devolution. We illustrate how network architecture can create impediments to open communications, and how QoS monitoring can detect such effects. We present data from a field test of QoS-monitoring software now in development. We suggest QoS metrics to gauge whether information "walled gardens" represent a real threat for dividing the Internet into proprietary spaces. To demonstrate our proposal, we are placing our software on the computers of a sample of broadband subscribers. The software periodically conducts a battery of tests that assess the quality of connections from the subscriber's computer to various content sites. Any systematic differences in connection quality between affiliated and non-affiliated content sites would warrant research into the behavioral implications of those differences. QoS monitoring is timely because the potential for the Internet to break into a loose network of proprietary content domains appears stronger than ever. Recent court rulings and policy statements suggest a growing trend towards relaxed scrutiny of mergers and the easing or elimination of content ownership rules. This policy environment could lead to a market with a small number of large, vertically integrated network operators, each pushing its proprietary content on subscribers.


title: Elusive Threats: Security Weaknesses of Commercial Cellular Networks

abstract: Commercial cellular telecommunications networks are routinely used as key means of voice and data transport by both businesses and the Public. Despite advances in encryption and other security measures, these commercial cellular networks remain extremely vulnerable to malicious attacks and the loss of user and data privacy and integrity. Such losses can result not only in mere inconvenience, but in serious corporate and national security breaches. Because of the potentially catastrophic nature of such security breaches, it behooves cellular network operators, distributors, and users to explore these network risk areas and mitigate them to the extent that current resources allow.


title: Digital Arroyos: An Examination of State Policy and Regulated Market Boundaries in Constructing Rural Internet Access

abstract: This focused study on state-level policy and access patterns contributes to a fuller understanding of how these invisible barriers work to structure access and define rural communities. Combining both quantitative and qualitative data, this study examines the role of geo-policy barriers in one of the largest and most rural states in the nation. Expanded Area Service policies are state policies wherein phone customers can expand their local calling area. Because useful Internet access requires a flat-price connection, EAS policies can play a crucial role in connecting citizens to one another. EAS policies (including Texas') tend to vary along five dimensions (community of interest, customer scope, directionality, pricing mechanism and policy scope). EAS policies that rely on regulated market boundaries for definition can generate gross inequities in rural Internet access. Interviews with Internet Service Providers in a case study of 25 rural communities reveals that LATA and exchange boundaries, along with geographically restricted infrastructure investments, curtail service provision in remote areas. A statistical analysis of 1300 telephone exchanges, including 208 rural telephone exchanges in Texas reveals that the farther a community lies from a metropolitan area the less likely they are to have reliable Internet access


title: The Consumer Product Selection Process in an Internet Age: Obstacles to Maximum Effectiveness & Policy Options

abstract: Intermediaries, like real estate agents, Consumer Reports, and Zagats, have long helped buyers to identify their most suitable options. Now, the combination of databases and the Internet enables them to serve consumers dramatically more effectively. This article begins by offering a three-part framework for understanding the evolving forms of selection assistance. It then focuses on numerous potential obstacles that could prevent shoppers from enjoying the full benefits of these developing technologies. While concluding that adjustments to business strategies and the enforcement of existing laws can effectively overcome most of these impediments, the article identifies several areas where proactive government action may be desirable, such as to prevent the emergence of anticompetitive entry barriers.


title: Prospects for Improving Competition in Mobile Roaming

abstract: The ability to make international roaming calls is of increasing importance to customers in Europe. This contrasts with various complaints that retail prices of roaming calls are rigid and excessive. The focus if the paper is on wholesale roaming, which is the prime determinant of retail roaming prices. The paper analyses the structural conditions of wholesale roaming markets that have impaired incentives to competition, namely high combined market share of the two leading GSM 900 operators combined with second mover disadvantages for new entrant GSM 1800 operators, and demand externalities. The paper argues that a number of developments are under way that are likely to modify this situation in the future. With the introduction of SIM over-the-air programming, home mobile operators will be able to direct customers to networks with the lowest charges. As dual mode handsets become ubiquitous and as new entrant GSM 1800 operators reach nationwide coverage, second-mover disadvantages will disappear. Given the relatively small roaming volumes that GSM 1800 operators currently provide, they should have an incentive to lower charges in exchange for preferred roaming status. On the demand side of wholesale roaming markets, it will be the larger GSM 900 operators, and in particular those with a pan-European footprint, that will ask for lower charges in exchange for preferred roaming status. This could discriminate against mobile operators in downstream retail markets that do not have a pan-European footprint and that lack the bargaining power. However, arbitrage by roaming brokers, new entry and wider geographical markets on the retail roaming level will work against this.


title: Digital Color Imaging

abstract: This paper surveys current technology and research in the area of digital color imaging. In order to establish the background and lay down terminology, fundamental concepts of color perception and measurement are first presented us-ing vector-space notation and terminology. Present-day color recording and reproduction systems are reviewed along with the common mathematical models used for representing these devices. Algorithms for processing color images for display and communication are surveyed, and a forecast of research trends is attempted. An extensive bibliography is provided.


title: Computer Security: Competing Concepts

abstract: This paper focuses on a tension we discovered in the philosophical part of our multidisciplinary project on values in web-browser security. Our project draws on the methods and perspectives of empirical social science, computer science, and philosophy to identify values embodied in existing web-browser security and also to prescribe changes to existing systems (in particular, Mozilla) so that values relevant to web-browser systems are better served than presently they are. The tension, which we had not seen explicitly addressed in any other work on computer security, emerged when we set out to extract from the concept of security the set values that ought to guide the shape of web-browser security. We found it impossible to construct an internally consistent set of values until we realized that two robust -- and in places competing -- conceptions of computer security were influencing our thinking. We needed to pry these apart and make a primary commitment to one. One conception of computer security invokes the ordinary meaning of security. According to it, computer security should protect people -- computer users -- against dangers, harms, and threats. Clearly this ordinary conception of security is already informing much of the work and rhetoric surrounding computer security. But another, substantively richer conception, also defines the aims and trajectory of computer security -- computer security as an element of national security. Although, like the ordinary conception, this one is also concerned with protection against threats, its primary subject is the state, not the individual. The two conceptions suggest divergent system-specifications, not for all mechanisms but a significant few.


title: Inventing E-Regulation in the US, EU and East Asia: Conflicting Social Visions of the Internet & the Information Society

abstract: This paper attempts to assess the international approach to Internet policy in the context of distinctive socio-political frameworks evolving in the US, the European Union (EU), and East Asia. The comparative review will develop a set of underlying structural models of the Information Society particular to each region, along with an analysis of their defining characteristics in relation to one another. This examination demonstrates how each region, given its regulatory legacy, has elected a different mix of good and bad socio-political choices in public policy for the Internet. Despite the range and diversity of paths to e-regulation suggested in these choices, none adequately addresses the underlying issue of how to promote an innovative society that is open to broad social participation. The paper evaluates principal weaknesses in these regional models of Internet policy and argues the need for re-conceptualizing the cultural, political and economic approach to the new information space of the Internet.


title: The temporal calculus of conditional objects and conditional events

abstract: We consider the problem of defining conditional objects (a|b), which would allow one to regard the conditional probability Pr(a|b) as a probability of a well-defined event rather than as a shorthand for Pr(ab)/Pr(b). The next issue is to define boolean combinations of conditional objects, and possibly also the operator of further conditioning. These questions have been investigated at least since the times of George Boole, leading to a number of formalisms proposed for conditional objects, mostly of syntactical, proof-theoretic vein. We propose a unifying, semantical approach, in which conditional events are (projections of) Markov chains, definable in the three-valued extension of the past tense fragment of propositional linear time logic, or, equivalently, by three-valued counter-free Moore machines. Thus our conditional objects are indeed stochastic processes, one of the central notions of modern probability theory. Our model fulfills early ideas of Bruno de Finetti and, moreover, as we show in a separate paper, all the previously proposed algebras of conditional events can be isomorphically embedded in our model.


title: Embedding conditional event algebras into temporal calculus of conditionals

abstract: In this paper we prove that all the existing conditional event algebras embed into a three-valued extension of temporal logic of discrete past time, which the authors of this paper have proposed in anothe paper as a general model of conditional events. First of all, we discuss the descriptive incompleteness of the cea's. In this direction, we show that some important notions, like independence of conditional events, cannot be properly addressed in the framework of conditional event algebras, while they can be precisely formulated and analyzed in the temporal setting. We also demonstrate that the embeddings allow one to use Markov chain algorithms (suitable for the temporal calculus) for computing probabilities of complex conditional expressions of the embedded conditional event algebras, and that these algorithms can outperform those previously known.


title: Two-way Quantum One-counter Automata

abstract: After the first treatments of quantum finite state automata by Moore and Crutchfield and by Kondacs and Watrous, a number of papers study the power of quantum finite state automata and their variants. This paper introduces a model of two-way quantum one-counter automata (2Q1CAs), combining the model of two-way quantum finite state automata (2QFAs) by Kondacs and Watrous and the model of one-way quantum one-counter automata (1Q1CAs) by Kravtsev. We give the definition of 2Q1CAs with well-formedness conditions. It is proved that 2Q1CAs are at least as powerful as classical two-way deterministic one-counter automata (2D1CAs), that is, every language L recognizable by 2D1CAs is recognized by 2Q1CAs with no error. It is also shown that several non-context-free languages including {a^n b^{n^2}} and {a^n b^{2^n}} are recognizable by 2Q1CAs with bounded error.


title: Electronic Commerce, Consumer Search and Retailing Cost Reduction

abstract: This paper explains four things in a unified way. First, how e-commerce can generate price equilibria where physical shops either compete with virtual shops for consumers with Internet access, or alternatively, sell only to consumers with no Internet access. Second, how these price equilibria might involve price dispersion on-line. Third, why prices may be higher on-line. Fourth, why established firms can, but need not, be more reluctant than newly created firm to adopt e-commerce. For this purpose we develop a model where e-commerce reduces consumers' search costs, involves trade-offs for consumers, and reduces retailing costs.


title: Variable and Value Ordering When Solving Balanced Academic Curriculum Problems

abstract: In this paper we present the use of Constraint Programming for solving balanced academic curriculum problems. We discuss the important role that heuristics play when solving a problem using a constraint-based approach. We also show how constraint solving techniques allow to very efficiently solve combinatorial optimization problems that are too hard for integer programming techniques.


title: Analyzing Website Choice Using Clickstream Data

abstract: This paper uses clickstream data from Plurimus Corp. (formerly Foveon Corp.) to analyze user choice of Internet portals. It will show that commonly used econometric models for examining grocery scanner data can be applied to clickstream data on advertising-based online markets. Developing a framework to study consumer choices of free websites is an essential step to better understanding user behavior on the Internet. The main data for this study is a clickstream data set consisting of every website visited by 2654 users from December 27 1999 to March 31 2000. Using this data, I construct several variables including search success, time spent searching, and whether a website is an individual's starting page. I also have advertising and media mentions data. This study helps to increase understanding of user behavior on the Internet. It explores some key determinants of website choice and simulates market responses to changes in the online environment. By better understanding website choice, we can better evaluate the implications of policy decisions.


title: Algorithmic Self-Assembly of DNA Tiles and its Application to Cryptanalysis

abstract: The early promises of DNA computing to deliver a massively parallel architecture well-suited to computationally hard problems have so far been largely unkept. Indeed, it is probably fair to say that only toy problems have been addressed experimentally. Recent experimental development on algorithmic self-assembly using DNA tiles seem to offer the most promising path toward a potentially useful application of the DNA computing concept. In this paper, we explore new geometries for algorithmic self-assembly, departing from those previously described in the literature. This enables us to carry out mathematical operations like binary multiplication or cyclic convolution product. We then show how to use the latter operation to implement an attack against the well-known public-key crypto system NTRU.


title: Pushdown Timed Automata: a Binary Reachability Characterization and Safety Verification

abstract: We consider pushdown timed automata (PTAs) that are timed automata (with dense clocks) augmented with a pushdown stack. A configuration of a PTA includes a control state, dense clock values and a stack word. By using the pattern technique, we give a decidable characterization of the binary reachability (i.e., the set of all pairs of configurations such that one can reach the other) of a PTA. Since a timed automaton can be treated as a PTA without the pushdown stack, we can show that the binary reachability of a timed automaton is definable in the additive theory of reals and integers. The results can be used to verify a class of properties containing linear relations over both dense variables and unbounded discrete variables. The properties previously could not be verified using the classic region technique nor expressed by timed temporal logics for timed automata and CTL$^*$ for pushdown systems. The results are also extended to other generalizations of timed automata.


title: The Minimum Expectation Selection Problem

abstract: We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. We assume each distribution has finitely many atoms. Let d be the number of distinct values in the support of the distributions. We show that if d is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.


title: Proceedings of the 6th Annual Workshop of the ERCIM Working Group on Constraints

abstract: Homepage of the workshop proceedings, with links to all individually archived papers


title: A Proposal for Dynamic Access Lists for TCP/IP Packet Filering

abstract: The use of IP filtering to improve system security is well established, and although limited in what it can achieve has proved to be efficient and effective. In the design of a security policy there is always a trade-off between usability and security. Restricting access means that legitimate use of the network is prevented; allowing access means illegitimate use may be allowed. Static access list make finding a balance particularly stark -- we pay the price of decreased security 100% of the time even if the benefit of increased usability is only gained 1% of the time. Dynamic access lists would allow the rules to change for short periods of time, and to allow local changes by non-experts. The network administrator can set basic security guide-lines which allow certain basic services only. All other services are restricted, but users are able to request temporary exceptions in order to allow additional access to the network. These exceptions are granted depending on the privileges of the user. This paper covers the following topics: (1) basic introduction to TCP/IP filtering; (2) semantics for dynamic access lists and; (3) a proposed protocol for allowing dynamic access; and (4) a method for representing access lists so that dynamic update and look-up can be done efficiently performed.


title: The Open Language Archives Community and Asian Language Resources

abstract: The Open Language Archives Community (OLAC) is a new project to build a worldwide system of federated language archives based on the Open Archives Initiative and the Dublin Core Metadata Initiative. This paper aims to disseminate the OLAC vision to the language resources community in Asia, and to show language technologists and linguists how they can document their tools and data in such a way that others can easily discover them. We describe OLAC and the OLAC Metadata Set, then discuss two key issues in the Asian context: language classification and multilingual resource classification.


title: Richer Syntactic Dependencies for Structured Language Modeling

abstract: The paper investigates the use of richer syntactic dependencies in the structured language model (SLM). We present two simple methods of enriching the dependencies in the syntactic parse trees used for intializing the SLM. We evaluate the impact of both methods on the perplexity (PPL) and word-error-rate(WER, N-best rescoring) performance of the SLM. We show that the new model achieves an improvement in PPL and WER over the baseline results reported using the SLM on the UPenn Treebank and Wall Street Journal (WSJ) corpora, respectively.


title: Limits To Certainty in QoS Pricing and Bandwidth

abstract: Advanced services require more reliable bandwidth than currently provided by the Internet Protocol, even with the reliability enhancements provided by TCP. More reliable bandwidth will be provided through QoS (quality of service), as currently discussed widely. Yet QoS has some implications beyond providing ubiquitous access to advance Internet service, which are of interest from a policy perspective. In particular, what are the implications for price of Internet services? Further, how will these changes impact demand and universal service for the Internet. This paper explores the relationship between certainty of bandwidth and certainty of price for Internet services over a statistically shared network and finds that these are mutually exclusive goals.


title: The Increased Need For FCC Merger Review In A Networked World

abstract: Recently, the FCC announced a new standard for review in mergers. Under the new standard, mass media mergers that comply with existing rules will automaticly receive approval, while those that do not will receive a more searching review. Common carrier mergers, however, will continue to receive the 4=part test established in Bell Atlantic/Nynex. The new standard fails to take into account the complexities of the emerging, converged networked world, and is essentially obsolete on arrival. Looking to those areas where Congress has required an additional public interest review of mergers, a pattern emerges. The emergence of vast, vertically integrated networks of content and conduit fit the historic pattern of areas requiring piublic interest review and re-enforce the need for increased, rather than decreased merger review.


title: ENUM: The Collision of Telephony and DNS Policy

abstract: ENUM marks either the convergence or collision of the public telephone network with the Internet. ENUM is an innovation in the domain name system (DNS). It starts with numerical domain names that are used to query DNS name servers. The servers respond with address information found in DNS records. This can be telephone numbers, email addresses, fax numbers, SIP addresses, or other information. The concept is to use a single number in order to obtain a plethora of contact information. By convention, the Internet Engineering Task Force (IETF) ENUM Working Group determined that an ENUM number would be the same numerical string as a telephone number. In addition, the assignee of an ENUM number would be the assignee of that telephone number. But ENUM could work with any numerical string or, in fact, any domain name. The IETF is already working on using E.212 numbers with ENUM. [Abridged]


title: New approach for network monitoring and intrusion detection

abstract: The approach for a network behavior description in terms of numerical time-dependant functions of the protocol parameters is suggested. This provides a basis for application of methods of mathematical and theoretical physics for information flow analysis on network and for extraction of patterns of typical network behavior. The information traffic can be described as a trajectory in multi-dimensional parameter-time space with dimension about 10-12. Based on this study some algorithms for the proposed intrusion detection system are discussed.


title: Structuring Business Metadata in Data Warehouse Systems for Effective Business Support

abstract: Large organizations today are being served by different types of data processing and informations systems, ranging from the operational (OLTP) systems, data warehouse systems, to data mining and business intelligence applications. It is important to create an integrated repository of what these systems contain and do in order to use them collectively and effectively. The repository contains metadata of source systems, data warehouse, and also the business metadata. Decision support and business analysis require extensive and in-depth understanding of business entities, tasks, rules and the environment. The purpose of business metadata is to provide this understanding. Realizing the importance of metadata, many standardization efforts has been initiated to define metadata models. In trying to define an integrated metadata and information systems for a banking application, we discover some important limitations or inadequacies of the business metadata proposals. They relate to providing an integrated and flexible inter-operability and navigation between metadata and data, and to the important issue of systematically handling temporal characteristics and evolution of the metadata itself. In this paper, we study the issue of structuring business metadata so that it can provide a context for business management and decision support when integrated with data warehousing. We define temporal object-oriented business metadata model, and relate it both to the technical metadata and the data warehouse. We also define ways of accessing and navigating metadata in conjunction with data.


title: Alife Model of Evolutionary Emergence of Purposeful Adaptive Behavior

abstract: The process of evolutionary emergence of purposeful adaptive behavior is investigated by means of computer simulations. The model proposed implies that there is an evolving population of simple agents, which have two natural needs: energy and reproduction. Any need is characterized quantitatively by a corresponding motivation. Motivations determine goal-directed behavior of agents. The model demonstrates that purposeful behavior does emerge in the simulated evolutionary processes. Emergence of purposefulness is accompanied by origin of a simple hierarchy in the control system of agents.


title: Mixed-Initiative Interaction = Mixed Computation

abstract: We show that partial evaluation can be usefully viewed as a programming model for realizing mixed-initiative functionality in interactive applications. Mixed-initiative interaction between two participants is one where the parties can take turns at any time to change and steer the flow of interaction. We concentrate on the facet of mixed-initiative referred to as `unsolicited reporting' and demonstrate how out-of-turn interactions by users can be modeled by `jumping ahead' to nested dialogs (via partial evaluation). Our approach permits the view of dialog management systems in terms of their native support for staging and simplifying interactions; we characterize three different voice-based interaction technologies using this viewpoint. In particular, we show that the built-in form interpretation algorithm (FIA) in the VoiceXML dialog management architecture is actually a (well disguised) combination of an interpreter and a partial evaluator.


title: Set Unification

abstract: The unification problem in algebras capable of describing sets has been tackled, directly or indirectly, by many researchers and it finds important applications in various research areas--e.g., deductive databases, theorem proving, static analysis, rapid software prototyping. The various solutions proposed are spread across a large literature. In this paper we provide a uniform presentation of unification of sets, formalizing it at the level of set theory. We address the problem of deciding existence of solutions at an abstract level. This provides also the ability to classify different types of set unification problems. Unification algorithms are uniformly proposed to solve the unification problem in each of such classes. The algorithms presented are partly drawn from the literature--and properly revisited and analyzed--and partly novel proposals. In particular, we present a new goal-driven algorithm for general ACI1 unification and a new simpler algorithm for general (Ab)(Cl) unification.


title: Pretty-Simple Password-Authenticated Key-Exchange Protocol

abstract: We propose pretty simple password-authenticated key-exchange protocol which is based on the difficulty of solving DDH problem. It has the following advantages: (1) Both $y_1$ and $y_2$ in our protocol are independent and thus they can be pre-computed and can be sent independently. This speeds up the protocol. (2) Clients and servers can use almost the same algorithm. This reduces the implementation costs without accepting replay attacks and abuse of entities as oracles.


title: Recognizing When Heuristics Can Approximate Minimum Vertex Covers Is Complete for Parallel Access to NP

abstract: For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r, where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP. To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs for which either of these heuristics can find an optimal solution remains NP-hard.


title: Information retrieval in Current Research Information Systems

abstract: In this paper we describe the requirements for research information systems and problems which arise in the development of such system. Here is shown which problems could be solved by using of knowledge markup technologies. Ontology for Research Information System offered. Architecture for collecting research data and providing access to it is described.


title: Part-of-Speech Tagging with Two Sequential Transducers

abstract: We present a method of constructing and using a cascade consisting of a left- and a right-sequential finite-state transducer (FST), T1 and T2, for part-of-speech (POS) disambiguation. Compared to an HMM, this FST cascade has the advantage of significantly higher processing speed, but at the cost of slightly lower accuracy. Applications such as Information Retrieval, where the speed can be more important than accuracy, could benefit from this approach. In the process of tagging, we first assign every word a unique ambiguity class c_i that can be looked up in a lexicon encoded by a sequential FST. Every c_i is denoted by a single symbol, e.g. [ADJ_NOUN], although it represents a set of alternative tags that a given word can occur with. The sequence of the c_i of all words of one sentence is the input to our FST cascade. It is mapped by T1, from left to right, to a sequence of reduced ambiguity classes r_i. Every r_i is denoted by a single symbol, although it represents a set of alternative tags. Intuitively, T1 eliminates the less likely tags from c_i, thus creating r_i. Finally, T2 maps the sequence of r_i, from right to left, to a sequence of single POS tags t_i. Intuitively, T2 selects the most likely t_i from every r_i. The probabilities of all t_i, r_i, and c_i are used only at compile time, not at run time. They do not (directly) occur in the FSTs, but are "implicitly contained" in their structure.


title: On Equivalence and Canonical Forms in the LF Type Theory

abstract: Decidability of definitional equality and conversion of terms into canonical form play a central role in the meta-theory of a type-theoretic logical framework. Most studies of definitional equality are based on a confluent, strongly-normalizing notion of reduction. Coquand has considered a different approach, directly proving the correctness of a practical equivalance algorithm based on the shape of terms. Neither approach appears to scale well to richer languages with unit types or subtyping, and neither directly addresses the problem of conversion to canonical. In this paper we present a new, type-directed equivalence algorithm for the LF type theory that overcomes the weaknesses of previous approaches. The algorithm is practical, scales to richer languages, and yields a new notion of canonical form sufficient for adequate encodings of logical systems. The algorithm is proved complete by a Kripke-style logical relations argument similar to that suggested by Coquand. Crucially, both the algorithm itself and the logical relations rely only on the shapes of types, ignoring dependencies on terms.


title: How to Commission, Operate and Maintain a Large Future Accelerator Complex from Far Remote

abstract: A study on future large accelerators [1] has considered a facility, which is designed, built and operated by a worldwide collaboration of equal partner institutions, and which is remote from most of these institutions. The full range of operation was considered including commi-ssioning, machine development, maintenance, trouble shooting and repair. Experience from existing accele-rators confirms that most of these activities are already performed 'remotely'. The large high-energy physics ex-periments and astronomy projects, already involve inter-national collaborations of distant institutions. Based on this experience, the prospects for a machine operated remotely from far sites are encouraging. Experts from each laboratory would remain at their home institution but continue to participate in the operation of the machine after construction. Experts are required to be on site only during initial commissioning and for par-ticularly difficult problems. Repairs require an on-site non-expert maintenance crew. Most of the interventions can be made without an expert and many of the rest resolved with remote assistance. There appears to be no technical obstacle to controlling an accelerator from a distance. The major challenge is to solve the complex management and communication problems.


title: Dense point sets have sparse Delaunay triangulations

abstract: The spread of a finite set of points is the ratio between the longest and shortest pairwise distances. We prove that the Delaunay triangulation of any set of n points in R^3 with spread D has complexity O(D^3). This bound is tight in the worst case for all D = O(sqrt{n}). In particular, the Delaunay triangulation of any dense point set has linear complexity. We also generalize this upper bound to regular triangulations of k-ply systems of balls, unions of several dense point sets, and uniform samples of smooth surfaces. On the other hand, for any n and D=O(n), we construct a regular triangulation of complexity Omega(nD) whose n vertices have spread D.


title: Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem

abstract: We consider the problem of computing the second elementary symmetric polynomial S^2_n(X) using depth-three arithmetic circuits of the form "sum of products of linear forms". We consider this problem over several fields and determine EXACTLY the number of multiplication gates required. The lower bounds are proved for inhomogeneous circuits where the linear forms are allowed to have constants; the upper bounds are proved in the homogeneous model. For reals and rationals, the number of multiplication gates required is exactly n-1; in most other cases, it is \ceil{n/2}. This problem is related to the Graham-Pollack theorem in algebraic graph theory. In particular, our results answer the following question of Babai and Frankl: what is the minimum number of complete bipartite graphs required to cover each edge of a complete graph an odd number of times? We show that for infinitely many n, the answer is \ceil{n/2}.


title: A logic-based approach to data integration

abstract: An important aspect of data integration involves answering queries using various resources rather than by accessing database relations. The process of transforming a query from the database relations to the resources is often referred to as query folding or answering queries using views, where the views are the resources. We present a uniform approach that includes as special cases much of the previous work on this subject. Our approach is logic-based using resolution. We deal with integrity constraints, negation, and recursion also within this framework.


title: Inference of termination conditions for numerical loops in Prolog

abstract: We present a new approach to termination analysis of numerical computations in logic programs. Traditional approaches fail to analyse them due to non well-foundedness of the integers. We present a technique that allows overcoming these difficulties. Our approach is based on transforming a program in a way that allows integrating and extending techniques originally developed for analysis of numerical computations in the framework of query-mapping pairs with the well-known framework of acceptability. Such an integration not only contributes to the understanding of termination behaviour of numerical computations, but also allows us to perform a correct analysis of such computations automatically, by extending previous work on a constraint-based approach to termination. Finally, we discuss possible extensions of the technique, including incorporating general term orderings.


title: On termination of meta-programs

abstract: The term {\em meta-programming} refers to the ability of writing programs that have other programs as data and exploit their semantics. The aim of this paper is presenting a methodology allowing us to perform a correct termination analysis for a broad class of practical meta-interpreters, including negation and performing different tasks during the execution. It is based on combining the power of general orderings, used in proving termination of term-rewrite systems and programs, and on the well-known acceptability condition, used in proving termination of logic programs. The methodology establishes a relationship between the ordering needed to prove termination of the interpreted program and the ordering needed to prove termination of the meta-interpreter together with this interpreted program. If such a relationship is established, termination of one of those implies termination of the other one, i.e., the meta-interpreter preserves termination. Among the meta-interpreters that are analysed correctly are a proof trees constructing meta-interpreter, different kinds of tracers and reasoners. To appear without appendix in Theory and Practice of Logic Programming.


title: Efficient algorithms for decision tree cross-validation

abstract: Cross-validation is a useful and generally applicable technique often employed in machine learning, including decision tree induction. An important disadvantage of straightforward implementation of the technique is its computational overhead. In this paper we show that, for decision trees, the computational overhead of cross-validation can be reduced significantly by integrating the cross-validation with the normal decision tree induction process. We discuss how existing decision tree algorithms can be adapted to this aim, and provide an analysis of the speedups these adaptations may yield. The analysis is supported by experimental results.


title: Practical Aspects for a Working Compile Time Garbage Collection System for Mercury

abstract: Compile-time garbage collection (CTGC) is still a very uncommon feature within compilers. In previous work we have developed a compile-time structure reuse system for Mercury, a logic programming language. This system indicates which datastructures can safely be reused at run-time. As preliminary experiments were promising, we have continued this work and have now a working and well performing near-to-ship CTGC-system built into the Melbourne Mercury Compiler (MMC). In this paper we present the multiple design decisions leading to this system, we report the results of using CTGC for a set of benchmarks, including a real-world program, and finally we discuss further possible improvements. Benchmarks show substantial memory savings and a noticeable reduction in execution time.


title: Counting is Easy

abstract: For any fixed $k$, a remarkably simple single-tape Turing machine can simulate $k$ independent counters in real time. Informally, a counter is a storage unit that maintains a single integer (initially 0), incrementing it, decrementing it, or reporting its sign (positive, negative, or zero) on command. Any automaton that responds to each successive command as a counter would is said to simulate a counter. (Only for a sign inquiry is the response of interest, of course. And zeroness is the only real issue, since a simulator can readily use zero detection to keep track of positivity and negativity in finite-state control. In this paper we describe a remarkably simple real-time simulation, based on just five simple rewriting rules, of any fixed number $k$ of independent counters. On a Turing machine with a single, binary work tape, the simulation runs in real time, handling an arbitrary counter command at each step. The space used by the simulation can be held to $(k+\epsilon) \log_2 n$ bits for the first $n$ commands, for any specified $\epsilon > 0$.


title: Two heads are better than two tapes

abstract: We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x'| x \in {0,1}^* and x' is a prefix of x} in real time, although it can do so with three tapes, two two-dimensional tapes, or one two-head tape, or in linear time with just one tape. In particular, this settles the longstanding conjecture that a two-head Turing machine can recognize more languages in real time if its heads are on the same one-dimensional tape than if they are on separate one-dimensional tapes.


title: A New Approach to Formal Language Theory by Kolmogorov Complexity

abstract: We present a new approach to formal language theory using Kolmogorov complexity. The main results presented here are an alternative for pumping lemma(s), a new characterization for regular languages, and a new method to separate deterministic context-free languages and nondeterministic context-free languages. The use of the new `incompressibility arguments' is illustrated by many examples. The approach is also successful at the high end of the Chomsky hierarchy since one can quantify nonrecursiveness in terms of Kolmogorov complexity. (This is a preliminary uncorrected version. The final version is the one published in SIAM J. Comput., 24:2(1995), 398-410.)


title: Towards Solving the Interdisciplinary Language Barrier Problem

abstract: This work aims to make it easier for a specialist in one field to find and explore ideas from another field which may be useful in solving a new problem arising in his practice. It presents a methodology which serves to represent the relationships that exist between concepts, problems, and solution patterns from different fields of human activity in the form of a graph. Our approach is based upon generalization and specialization relationships and problem solving. It is simple enough to be understood quite easily, and general enough to enable coherent integration of concepts and problems from virtually any field. We have built an implementation which uses the World Wide Web as a support to allow navigation between graph nodes and collaborative development of the graph.


title: An Architecture for Security and Privacy in Mobile Communications

abstract: There is much discussion and debate about how to improve the security and privacy of mobile communication systems, both voice and data. Most proposals attempt to provide incremental improvements to systems that are deployed today. Indeed, only incremental improvements are possible, given the regulatory, technological, economic, and historical structure of the telecommunications system. In this paper, we conduct a ``thought experiment'' to redesign the mobile communications system to provide a high level of security and privacy for the users of the system. We discuss the important requirements and how a different architecture might successfully satisfy them. In doing so, we hope to illuminate the possibilities for secure and private systems, as well as explore their real limits.


title: An Overview of Computer security

abstract: As more business activities are being automated and an increasing number of computers are being used to store vital and sensitive information the need for secure computer systems becomes more apparent. These systems can be achieved only through systematic design; they cannot be achieved through haphazard seat-of-the-pants methods.This paper introduces some known threats to the computer security, categorizes the threats, and analyses protection mechanisms and techniques for countering the threats. The threats have been classified more so as definitions and then followed by the classifications of these threats. Also mentioned are the protection mechanisms.


title: EquiX--A Search and Query Language for XML

abstract: EquiX is a search language for XML that combines the power of querying with the simplicity of searching. Requirements for such languages are discussed and it is shown that EquiX meets the necessary criteria. Both a graph-based abstract syntax and a formal concrete syntax are presented for EquiX queries. In addition, the semantics is defined and an evaluation algorithm is presented. The evaluation algorithm is polynomial under combined complexity. EquiX combines pattern matching, quantification and logical expressions to query both the data and meta-data of XML documents. The result of a query in EquiX is a set of XML documents. A DTD describing the result documents is derived automatically from the query.


title: From 2G TO 3G - The Evolution of International Cellular Standards

abstract: The purpose of this paper is to examine the major factors surrouding and contributing to the creation (and success) of Europe's 2nd generation 'GSM' cellular system, and compare and contrast it to key events and recent developments in 3rd generation 'IMT-2000' systems. The objective is to ascertain whether lessons from the development of one system can be applied to the other, and what implications 2G has for the development and assessment of 3G technologies. Among the major themes incorporated into this assessment is the concept of cooperation, and its role in bringing about the collaboration and integration necessary to support the success of an international cellular standard.


title: The Expresso Microarray Experiment Management System: The Functional Genomics of Stress Responses in Loblolly Pine

abstract: Conception, design, and implementation of cDNA microarray experiments present a variety of bioinformatics challenges for biologists and computational scientists. The multiple stages of data acquisition and analysis have motivated the design of Expresso, a system for microarray experiment management. Salient aspects of Expresso include support for clone replication and randomized placement; automatic gridding, extraction of expression data from each spot, and quality monitoring; flexible methods of combining data from individual spots into information about clones and functional categories; and the use of inductive logic programming for higher-level data analysis and mining. The development of Expresso is occurring in parallel with several generations of microarray experiments aimed at elucidating genomic responses to drought stress in loblolly pine seedlings. The current experimental design incorporates 384 pine cDNAs replicated and randomly placed in two specific microarray layouts. We describe the design of Expresso as well as results of analysis with Expresso that suggest the importance of molecular chaperones and membrane transport proteins in mechanisms conferring successful adaptation to long-term drought stress.


title: Multivariant Branching Prediction, Reflection, and Retrospection

abstract: In branching simulation, a novel approach to simulation presented in this paper, a multiplicity of plausible scenarios are concurrently developed and implemented. In conventional simulations of complex systems, there arise from time to time uncertainties as to which of two or more alternatives are more likely to be pursued by the system being simulated. Under these conditions the simulationist makes a judicious choice of one of these alternatives and embeds this choice in the simulation model. By contrast, in the branching approach, two or more of such alternatives (or branches) are included in the model and implemented for concurrent computer solution. The theoretical foundations for branching simulation as a computational process are in the domains of alternating Turing machines, molecular computing, and E-machines. Branching simulations constitute the development of diagrams of scenarios representing significant, alternative flows of events. Logical means for interpretation and investigation of the branching simulation and prediction are provided by the logical theories of possible worlds, which have been formalized by the construction of logical varieties. Under certain conditions, the branching approach can considerably enhance the efficiency of computer simulations and provide more complete insights into the interpretation of predictions based on simulations. As an example, the concepts developed in this paper have been applied to a simulation task that plays an important role in radiology - the noninvasive treatment of brain aneurysms.


title: A Symmetric Strategy in Graph Avoidance Games

abstract: In the graph avoidance game two players alternatingly color edges of a graph G in red and in blue respectively. The player who first creates a monochromatic subgraph isomorphic to a forbidden graph F loses. A symmetric strategy of the second player ensures that, independently of the first player's strategy, the blue and the red subgraph are isomorphic after every round of the game. We address the class of those graphs G that admit a symmetric strategy for all F and discuss relevant graph-theoretic and complexity issues. We also show examples when, though a symmetric strategy on G generally does not exist, it is still available for a particular F.


title: What is the minimal set of fragments that achieves maximal parse accuracy?

abstract: We aim at finding the minimal set of fragments which achieves maximal parse accuracy in Data Oriented Parsing. Experiments with the Penn Wall Street Journal treebank show that counts of almost arbitrary fragments within parse trees are important, leading to improved parse accuracy over previous models tested on this treebank (a precision of 90.8% and a recall of 90.6%). We isolate some dependency relations which previous models neglect but which contribute to higher parse accuracy.


title: Combining semantic and syntactic structure for language modeling

abstract: Structured language models for speech recognition have been shown to remedy the weaknesses of n-gram models. All current structured language models are, however, limited in that they do not take into account dependencies between non-headwords. We show that non-headword dependencies contribute to significantly improved word error rate, and that a data-oriented parsing model trained on semantically and syntactically annotated data can exploit these dependencies. This paper also contains the first DOP model trained by means of a maximum likelihood reestimation procedure, which solves some of the theoretical shortcomings of previous DOP models.


title: Mragyati : A System for Keyword-based Searching in Databases

abstract: The web, through many search engine sites, has popularized the keyword-based search paradigm, where a user can specify a string of keywords and expect to retrieve relevant documents, possibly ranked by their relevance to the query. Since a lot of information is stored in databases (and not as HTML documents), it is important to provide a similar search paradigm for databases, where users can query a database without knowing the database schema and database query languages such as SQL. In this paper, we propose such a database search system, which accepts a free-form query as a collection of keywords, translates it into queries on the database using the database metadata, and presents query results in a well-structured and browsable form. Th eysytem maps keywords onto the database schema and uses inter-relationships (i.e., data semantics) among the referred tables to generate meaningful query results. We also describe our prototype for database search, called Mragyati. Th eapproach proposed here is scalable, as it does not build an in-memory graph of the entire database for searching for relationships among the objects selected by the user's query.


title: Machine Learning in Automated Text Categorization

abstract: The automated categorization (or classification) of texts into predefined categories has witnessed a booming interest in the last ten years, due to the increased availability of documents in digital form and the ensuing need to organize them. In the research community the dominant approach to this problem is based on machine learning techniques: a general inductive process automatically builds a classifier by learning, from a set of preclassified documents, the characteristics of the categories. The advantages of this approach over the knowledge engineering approach (consisting in the manual definition of a classifier by domain experts) are a very good effectiveness, considerable savings in terms of expert manpower, and straightforward portability to different domains. This survey discusses the main approaches to text categorization that fall within the machine learning paradigm. We will discuss in detail issues pertaining to three different problems, namely document representation, classifier construction, and classifier evaluation.


title: Vertex-Unfoldings of Simplicial Manifolds

abstract: We present an algorithm to unfold any triangulated 2-manifold (in particular, any simplicial polyhedron) into a non-overlapping, connected planar layout in linear time. The manifold is cut only along its edges. The resulting layout is connected, but it may have a disconnected interior; the triangles are connected at vertices, but not necessarily joined along edges. We extend our algorithm to establish a similar result for simplicial manifolds of arbitrary dimension.


title: Analytical solution of transient scalar wave and diffusion problems of arbitrary dimensionality and geometry by RBF wavelet series

abstract: This study applies the RBF wavelet series to the evaluation of analytical solutions of linear time-dependent wave and diffusion problems of any dimensionality and geometry. To the best of the author's knowledge, such analytical solutions have never been achieved before. The RBF wavelets can be understood an alternative for multidimensional problems to the standard Fourier series via fundamental and general solutions of partial differential equation. The present RBF wavelets are infinitely differential, compactly supported, orthogonal over different scales and very simple. The rigorous mathematical proof of completeness and convergence is still missing in this study. The present work may open a new window to numerical solution and theoretical analysis of many other high-dimensional time-dependent PDE problems under arbitrary geometry.


title: Probabilistic analysis of a differential equation for linear programming

abstract: In this paper we address the complexity of solving linear programming problems with a set of differential equations that converge to a fixed point that represents the optimal solution. Assuming a probabilistic model, where the inputs are i.i.d. Gaussian variables, we compute the distribution of the convergence rate to the attracting fixed point. Using the framework of Random Matrix Theory, we derive a simple expression for this distribution in the asymptotic limit of large problem size. In this limit, we find that the distribution of the convergence rate is a scaling function, namely it is a function of one variable that is a combination of three parameters: the number of variables, the number of constraints and the convergence rate, rather than a function of these parameters separately. We also estimate numerically the distribution of computation times, namely the time required to reach a vicinity of the attracting fixed point, and find that it is also a scaling function. Using the problem size dependence of the distribution functions, we derive high probability bounds on the convergence rates and on the computation times.

categories: cs.CC cond-mat.stat-mech math-ph math.MP math.OC


title: Generating Multilingual Personalized Descriptions of Museum Exhibits - The M-PIRO Project

abstract: This paper provides an overall presentation of the M-PIRO project. M-PIRO is developing technology that will allow museums to generate automatically textual or spoken descriptions of exhibits for collections available over the Web or in virtual reality environments. The descriptions are generated in several languages from information in a language-independent database and small fragments of text, and they can be tailored according to the backgrounds of the users, their ages, and their previous interaction with the system. An authoring tool allows museum curators to update the system's database and to control the language and content of the resulting descriptions. Although the project is still in progress, a Web-based demonstrator that supports English, Greek and Italian is already available, and it is used throughout the paper to highlight the capabilities of the emerging technology.


title: Teaching Parallel Programming Using Both High-Level and Low-Level Languages

abstract: We discuss the use of both MPI and OpenMP in the teaching of senior undergraduate and junior graduate classes in parallel programming. We briefly introduce the OpenMP standard and discuss why we have chosen to use it in parallel programming classes. Advantages of using OpenMP over message passing methods are discussed. We also include a brief enumeration of some of the drawbacks of using OpenMP and how these drawbacks are being addressed by supplementing OpenMP with additional MPI codes and projects. Several projects given in my class are also described in this paper.


title: Nonorthogonal Polyhedra Built from Rectangles

abstract: We prove that any polyhedron of genus zero or genus one built out of rectangular faces must be an orthogonal polyhedron, but that there are nonorthogonal polyhedra of genus seven all of whose faces are rectangles. This leads to a resolution of a question posed by Biedl, Lubiw, and Sun [BLS99].


title: Selected Topics in Asynchronous Automata

abstract: The paper is concerned with defining the electrical signals and their models. The delays are discussed, the asynchronous automata - which are the models of the asynchronous circuits - and the examples of the clock generator and of the R-S latch are given. We write the equations of the asynchronous automata, which combine the pure delay model and the inertial delay model; the simple gate model and the complex gate model; the fixed, bounded and unbounded delay model. We give the solutions of these equations, which are written on R->{0,1} functions, where R is the time set. The connection between the real time and the discrete time is discussed. The stability, the fundamental mode of operation, the combinational automata, the semi-modularity are defined and characterized. Some connections are suggested with the linear time and the branching time temporal logic of the propositions.


title: An Asynchronous Automata Approach to the Semantics of Temporal Logic

abstract: The paper presents the differential equations that characterize an asynchronous automaton and gives their solution x:R->{0,1}x...x{0,1}. Remarks are made on the connection between the continuous time and the discrete time of the approach. The continuous and the discrete time, the linear and the branching temporal logics have the semantics depending on x and their formulas give the properties of the automaton.


title: The Delay-Insensitivity, the Hazard-Freedom, the Semi-Modularity and the Technical Condition of Good Running of the Discrete Time Asynchronous Automata

abstract: The paper studies some important properties of the asynchronous (=timed) automata: the delay-insensitivity, the hazard-freedom, the semi-modularity and the technical condition of good running. Time is discrete.


title: The Existence of $\omega$-Chains for Transitive Mixed Linear Relations and Its Applications

abstract: We show that it is decidable whether a transitive mixed linear relation has an $\omega$-chain. Using this result, we study a number of liveness verification problems for generalized timed automata within a unified framework. More precisely, we prove that (1) the mixed linear liveness problem for a timed automaton with dense clocks, reversal-bounded counters, and a free counter is decidable, and (2) the Presburger liveness problem for a timed automaton with discrete clocks, reversal-bounded counters, and a pushdown stack is decidable.


title: Applications of the Differential Calculus in the Study of the Timed Automata: the Inertial Delay Buffer

abstract: We write the relations that characterize the simpliest timed automaton, the inertial delay buffer, in two versions: the non-deterministic and the deterministic one, by making use of the derivatives of the R->{0,1} functions.


title: Interfacing the ControlLogix PLC over Ethernet/IP

abstract: The Allen-Bradley ControlLogix line of pro-grammable logic controllers (PLCs) offers several in-terfaces: Ethernet, ControlNet, DeviceNet, RS-232 and others. The ControlLogix Ethernet interface module 1756-ENET uses EtherNet/IP, the ControlNet protocol, encapsulated in Ethernet packages, with specific service codes. A driver for the Experimental Physics and Industrial Control System (EPICS) has been developed that utilizes this EtherNet/IP protocol for controllers running the vxWorks RTOS as well as a Win32 and Unix/Linux test program. Features, per-formance and limitations of this interface are presented.


title: Overview of the Experimental Physics and Industrial Control System (EPICS) Channel Archiver

abstract: The Channel Archiver has been operational for more than two years at Los Alamos National Laboratory and other sites. This paper introduces the available components (data sampling engine, viewers, scripting interface, HTTP/CGI integration and data management), presents updated performance measurements and reviews operational experience with the Channel Archiver.


title: Analysis of Investment Policy in Belarus

abstract: The optimal planning trajectory is analyzed on the basis of the growth model with effectiveness. The saving per capital value has to be rather high initially with smooth decrement in the future years.


title: Integrating LabVIEW into a Distributed Computing Environment

abstract: Being easy to learn and well suited for a self-contained desktop laboratory setup, many casual programmers prefer to use the National Instruments LabVIEW environment to develop their logic. An ActiveX interface is presented that allows integration into a plant-wide distributed environment based on the Experimental Physics and Industrial Control System (EPICS). This paper discusses the design decisions and provides performance information, especially considering requirements for the Spallation Neutron Source (SNS) diagnostics system.


title: L-Fuzzy Valued Inclusion Measure, L-Fuzzy Similarity and L-Fuzzy Distance

abstract: The starting point of this paper is the introduction of a new measure of inclusion of fuzzy set A in fuzzy set B. Previously used inclusion measures take values in the interval [0,1]; the inclusion measure proposed here takes values in a Boolean lattice. In other words, inclusion is viewed as an L-fuzzy valued relation between fuzzy sets. This relation is re exive, antisymmetric and transitive, i.e. it is a fuzzy order relation; in addition it possesess a number of properties which various authors have postulated as axiomatically appropriate for an inclusion measure. We also define an L-fuzzy valued measure of similarity between fuzzy sets and and an L-fuzzy valued distance function between fuzzy sets; these possess properties analogous to the ones of real-valued similarity and distance functions. Keywords: Fuzzy Relations, inclusion measure, subsethood, L-fuzzy sets, similarity, distance, transitivity.


title: The Use of Classifiers in Sequential Inference

abstract: We study the problem of combining the outcomes of several different classifiers in a way that provides a coherent inference that satisfies some constraints. In particular, we develop two general approaches for an important subproblem-identifying phrase structure. The first is a Markovian approach that extends standard HMMs to allow the use of a rich observation structure and of general classifiers to model state-observation dependencies. The second is an extension of constraint satisfaction formalisms. We develop efficient combination algorithms under both models and study them experimentally in the context of shallow parsing.


title: The Relational Database Aspects of Argonne's ATLAS Control System

abstract: The Relational Database Aspects of Argonnes ATLAS Control System Argonnes ATLAS (Argonne Tandem Linac Accelerator System) control system comprises two separate database concepts. The first is the distributed real-time database structure provided by the commercial product Vsystem [1]. The second is a more static relational database archiving system designed by ATLAS personnel using Oracle Rdb [2] and Paradox [3] software. The configuration of the ATLAS facility has presented a unique opportunity to construct a control system relational database that is capable of storing and retrieving complete archived tune-up configurations for the entire accelerator. This capability has been a major factor in allowing the facility to adhere to a rigorous operating schedule. Most recently, a Web-based operator interface to the control systems Oracle Rdb database has been installed. This paper explains the history of the ATLAS database systems, how they interact with each other, the design of the new Web-based operator interface, and future plans.


title: Automated Real-Time Testing (ARTT) for Embedded Control Systems (ECS)

abstract: Developing real-time automated test systems for embedded control systems has been a real problem. Some engineers and scientists have used customized software and hardware as a solution, which can be very expensive and time consuming to develop. We have discovered how to integrate a suite of commercially available off-the-shelf software tools and hardware to develop a scalable test platform that is capable of performing complete black-box testing for a dual-channel real-time Embedded-PLC-based control system (www.aps.anl.gov). We will discuss how the Vali/Test Pro testing methodology was implemented to structure testing for a personnel safety system with large quantities of requirements and test cases. This work was supported by the U.S. Department of Energy, Basic Energy Sciences, under Contract No. W-31-109-Eng-38.


title: Proliferation of SDDS Support for Various Platforms and Languages

abstract: Since Self-Describing Data Sets (SDDS) were first introduced, the source code has been ported to many different operating systems and various languages. SDDS is now available in C, Tcl, Java, Fortran, and Python. All of these versions are supported on Solaris, Linux, and Windows. The C version of SDDS is also supported on VxWorks. With the recent addition of the Java port, SDDS can now be deployed on virtually any operating system. Due to this proliferation, SDDS files serve to link not only a collection of C programs, but programs and scripts in many languages on different operating systems. The platform independent binary feature of SDDS also facilitates portability among operating systems. This paper presents an overview of various benefits of SDDS platform interoperability.


title: Explaining Scenarios for Information Personalization

abstract: Personalization customizes information access. The PIPE ("Personalization is Partial Evaluation") modeling methodology represents interaction with an information space as a program. The program is then specialized to a user's known interests or information seeking activity by the technique of partial evaluation. In this paper, we elaborate PIPE by considering requirements analysis in the personalization lifecycle. We investigate the use of scenarios as a means of identifying and analyzing personalization requirements. As our first result, we show how designing a PIPE representation can be cast as a search within a space of PIPE models, organized along a partial order. This allows us to view the design of a personalization system, itself, as specialized interpretation of an information space. We then exploit the underlying equivalence of explanation-based generalization (EBG) and partial evaluation to realize high-level goals and needs identified in scenarios; in particular, we specialize (personalize) an information space based on the explanation of a user scenario in that information space, just as EBG specializes a theory based on the explanation of an example in that theory. In this approach, personalization becomes the transformation of information spaces to support the explanation of usage scenarios. An example application is described.


title: The Control of a Beamline Over Intranet

abstract: The machines and beamlines controlled by VME industrial networks are very popular in accelerator faculties. Recently new software technology, among of which are Internet/Intranet application, Java language, and distributed calculating environment, changes the control manner rapidly. A program based on DCOM is composed to control of a variable included angle spherical grating monochromator beamline at National Synchrotron Radiation Laboratory (NSRL) in China. The control computer with a residential DCOM program is connected to Intranet by LAN, over which the user-end-operating program located in another computer sends driving beamline units' commands to the control computer. And also a web page coded in Java, published by the WWW service running in the control computer, is simply illustrated how to use web browser to query the states of or to control the beamline units.


title: On the complexity of inducing categorical and quantitative association rules

abstract: Inducing association rules is one of the central tasks in data mining applications. Quantitative association rules induced from databases describe rich and hidden relationships holding within data that can prove useful for various application purposes (e.g., market basket analysis, customer profiling, and others). Even though such association rules are quite widely used in practice, a thorough analysis of the computational complexity of inducing them is missing. This paper intends to provide a contribution in this setting. To this end, we first formally define quantitative association rule mining problems, which entail boolean association rules as a special case, and then analyze their computational complexities, by considering both the standard cases, and a some special interesting case, that is, association rule induction over databases with null values, fixed-size attribute set databases, sparse databases, fixed threshold problems.


title: Abduction with Penalization in Logic Programming

abstract: Abduction, first proposed in the setting of classical logics, has been studied with growing interest in the logic programming area during the last years. In this paper we study {\em abduction with penalization} in logic programming. This form of abductive reasoning, which has not been previously analyzed in logic programming, turns out to represent several relevant problems, including optimization problems, very naturally. We define a formal model for abduction with penalization from logic programs, which extends the abductive framework proposed by Kakas and Mancarella. We show the high expressiveness of this formalism, by encoding a couple of relevant problems, including the well-know Traveling Salesman Problem from optimization theory, in this abductive framework. The resulting encodings are very simple and elegant. We analyze the complexity of the main decisional problems arising in this framework. An interesting result in this course is that ``negation comes for free.'' Indeed, the addition of (even unstratified) negation does not cause any further increase to the complexity of the abductive reasoning tasks (which remains the same as for not-free programs).


title: Sintesi di algoritmi con SKY

abstract: This paper describes the semantics and ideas about SKY, a logic programming language intended in order to specify algorithmic strategies for the evaluation of problems.


title: Intelligent Anticipated Exploration of Web Sites

abstract: In this paper we describe a web search agent, called Global Search Agent (hereafter GSA for short). GSA integrates and enhances several search techniques in order to achieve significant improvements in the user-perceived quality of delivered information as compared to usual web search engines. GSA features intelligent merging of relevant documents from different search engines, anticipated selective exploration and evaluation of links from the current result set, automated derivation of refined queries based on user relevance feedback. System architecture as well as experimental accounts are also illustrated.


title: Quality Control, Testing and Deployment Results in NIF ICCS

abstract: The strategy used to develop the NIF Integrated Computer Control System (ICCS) calls for incremental cycles of construction and formal test to deliver a total of 1 million lines of code. Each incremental release takes four to six months to implement specific functionality and culminates when offline tests conducted in the ICCS Integration and Test Facility verify functional, performance, and interface requirements. Tests are then repeated on line to confirm integrated operation in dedicated laser laboratories or ultimately in the NIF. Test incidents along with other change requests are recorded and tracked to closure by the software change control board (SCCB). Annual independent audits advise management on software process improvements. Extensive experience has been gained by integrating controls in the prototype laser preamplifier laboratory. The control system installed in the preamplifier lab contains five of the ten planned supervisory subsystems and seven of sixteen planned front-end processors (FEPs). Beam alignment, timing, diagnosis and laser pulse amplification up to 20 joules was tested through an automated series of shots. Other laboratories have provided integrated testing of six additional FEPs. Process measurements including earned-value, product size, and defect densities provide software project controls and generate confidence that the control system will be successfully deployed.