OpenRaiser/Intern-Atlas huggingface dataset:
Abstract versus Concrete Computation on Metric Partial Algebras
Venue: arXiv cs.LO 2001
Year: 2001

A model of computation is abstract if, when applied to any algebra, the resulting programs for computable functions and sets on that algebra are invariant under isomorphisms, and hence do not depend on a representation for the algebra. Otherwise it is concrete. Intuitively, concrete models depend on the implementation of the algebra. The difference is particularly striking in the case of topological partial algebras, and notably in algebras over the reals. We investigate the relationship between abstract and concrete models of partial metric algebras. In the course of this investigation, interesting aspects of continuity, extensionality and non-determinism are uncovered.
Parallel Computing on a PC Cluster
Venue: arXiv cs.DC 2001
Year: 2001

The tremendous advance in computer technology in the past decade has made it possible to achieve the performance of a supercomputer on a very small budget. We have built a multi-CPU cluster of Pentium PC capable of parallel computations using the Message Passing Interface (MPI). We will discuss the configuration, performance, and application of the cluster to our work in physics.
The Role of Incentives for Opening Monopoly Markets: Comparing GTE and BOC Cooperation with Local Entrants
Venue: arXiv cs.CY 2001
Year: 2001

While the 1996 Telecommunications Act requires all incumbent local telephone companies to cooperate with local entrants, section 271 of the Act provides the Bell companies (but not GTE) additional incentives to cooperate. Using an original data set, I compare the negotiations of AT&T, as a local entrant, with GTE and with the Bell companies in states where both operate. My results suggest that the differential incentives matter: The Bells accommodate entry more than does GTE, as evidenced in quicker agreements, less litigation, and more favorable prices offered for network access. Consistent with this, there is more entry into Bell territories
Communication Complexity and Secure Function Evaluation
Venue: arXiv cs.CR 2001
Year: 2001

We suggest two new methodologies for the design of efficient secure protocols, that differ with respect to their underlying computational models. In one methodology we utilize the communication complexity tree (or branching for f and transform it into a secure protocol. In other words, "any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter". The second methodology uses the circuit computing f, enhanced with look-up tables as its underlying computational model. It is possible to simulate any RAM machine in this model with polylogarithmic blowup. Hence it is possible to start with a computation of f on a RAM machine and transform it into a secure protocol. We show many applications of these new methodologies resulting in protocols efficient either in communication or in computation. In particular, we exemplify a protocol for the "millionaires problem", where two participants want to compare their values but reveal no other information. Our protocol is more efficient than previously known ones in either communication or computation.
Tracing Execution of Software for Design Coverage
Venue: arXiv cs.SE 2001
Year: 2001

Test suites are designed to validate the operation of a system against requirements. One important aspect of a test suite design is to ensure that system operation logic is tested completely. A test suite should drive a system through all abstract states to exercise all possible cases of its operation. This is a difficult task. Code coverage tools support test suite designers by providing the information about which parts of source code are covered during system execution. Unfortunately, code coverage tools produce only source code coverage information. For a test engineer it is often hard to understand what the noncovered parts of the source code do and how they relate to requirements. We propose a generic approach that provides design coverage of the executed software simplifying the development of new test suites. We demonstrate our approach on common design abstractions such as statecharts, activity diagrams, message sequence charts and structure diagrams. We implement the design coverage using Third Eye tracing and trace analysis framework. Using design coverage, test suites could be created faster by focussing on untested design elements.
Integrating Multiple Knowledge Sources for Robust Semantic Parsing
Venue: arXiv cs.CL 2001
Year: 2001

This work explores a new robust approach for Semantic Parsing of unrestricted texts. Our approach considers Semantic Parsing as a Consistent Labelling Problem (CLP), allowing the integration of several knowledge types (syntactic and semantic) obtained from different sources (linguistic and statistic). The current implementation obtains 95% accuracy in model identification and 72% in case-role filling.
Enriching WordNet concepts with topic signatures
Venue: arXiv cs.CL 2001
Year: 2001

This paper explores the possibility of enriching the content of existing ontologies. The overall goal is to overcome the lack of topical links among concepts in WordNet. Each concept is to be associated to a topic signature, i.e., a set of related words with associated weights. The signatures can be automatically constructed from the WWW or from sense-tagged corpora. Both approaches are compared and evaluated on a word sense disambiguation task. The results show that it is possible to construct clean signatures from the WWW using some filtering techniques.
The Building of BODHI, a Bio-diversity Database System
Venue: arXiv cs.DB 2001
Year: 2001

We have recently built a database system called BODHI, intended to store plant bio-diversity information. It is based on an object-oriented modeling approach and is developed completely around public-domain software. The unique feature of BODHI is that it seamlessly integrates diverse types of data, including taxonomic characteristics, spatial distributions, and genetic sequences, thereby spanning the entire range from molecular to organism-level information. A variety of sophisticated indexing strategies are incorporated to efficiently access the various types of data, and a rule-based query processor is employed for optimizing query execution. In this paper, we report on our experiences in building BODHI and on its performance characteristics for a representative set of queries.
Between a rock and a hard place: assessing the application of domestic policy and South Africa's commitments under the WTO'S Basic Telecommunications Agreement
Venue: arXiv cs.CY 2001
Year: 2001

South Africa adopted the GATS Basic Agreement on Telecommunications and the regulatory principles in 1998. Obligations undertaken by South Africa mirrored the framework for the gradual telecommunications reform process that was begun in 1996. In the light of two threatened actions for anti-competitive practices in violation of the Agreement, this paper reviews the nature of the commitments undertaken by South Africa and assesses the country's compliance to date. This paper also seeks to explore the tension that arises between domestic policy reforms and international trade aspirations. It is argued that the dynamic produced through this tension affords domestic governments a mechanism with which to balance the seemingly opposing goals of competition and development. It is further argued that the broad regulatory principles, adopted by all signatories and often criticized for lack of precision, facilitate this fine balancing and affords domestic governments an opportunity to advance sovereign concerns while pursuing international trade ideals.
Geography and the Internet: Is the Internet a Substitute or a Complement for Cities?
Venue: arXiv cs.CY 2001
Year: 2001

By combining persons around the world into a single market, the Internet may serve as a substitute for urban agglomeration. That is, the Internet may level the consumption playing field between large, variety-laden and small, variety-starved markets. However, if local content on the Internet is more prevalent in larger markets, then the Internet may be a complement for urban agglomeration. Characterizing the nature of available content using Media Metrix web page visits by about 13,500 households, we document that substantially more online local content is available in larger markets. Combining this with CPS Internet use data, we find statistically significant direct evidence of both complementarity and substitutability: Individuals are more likely to connect in markets with more local online content; and holding local online content constant, are less likely to connect in larger markets. We also find that individuals connect to overcome local isolation: Blacks are more likely to connect, relative to whites, when they comprise a smaller fraction of local population, making the Internet is a substitute for agglomeration of preference minorities within cities, if not cities themselves. On balance we find that the substitution and complementarity effects offset each other so that the Internet does not promote or discourage agglomeration in larger markets.
Second-Level Digital Divide: Mapping Differences in People's Online Skills
Venue: arXiv cs.CY 2001
Year: 2001

Much of the existing approach to the digital divide suffers from an important limitation. It is based on a binary classification of Internet use by only considering whether someone is or is not an Internet user. To remedy this shortcoming, this project looks at the differences in people's level of skill with respect to finding information online. Findings suggest that people search for content in a myriad of ways and there is a large variance in how long people take to find various types of information online. Data are collected to see how user demographics, users' social support networks, people's experience with the medium, and their autonomy of use influence their level of user sophistication.
Internet Attacks: A Policy Framework for Rules of Engagement
Venue: arXiv cs.CY 2001
Year: 2001

Information technology is redefining national security and the use of force by state and nonstate actors. The use of force over the Internet warrants analysis given recent terrorist attacks. At the same time that information technology empowers states and their commercial enterprises, information technology makes infrastructures supported by computer systems increasingly accessible, interdependent, and more vulnerable to malicious attack. The Computer Security Institute and the FBI jointly estimate that financial losses attributed to malicious attack amounted to $378 million in 2000. International Law clearly permits a state to respond in self-defense when attacked by another state through the Internet, however, such attacks may not always rise to the scope, duration, and intensity threshold of an armed attack that may justify a use of force in self-defense. This paper presents a policy framework to analyze the rules of engagement for Internet attacks. We describe the state of Internet security, incentives for asymmetric warfare, and the development of international law for conflict management and armed conflict. We focus on options for future rules of engagement specific to Information Warfare. We conclude with four policy recommendations for Internet attack rules of engagement: (1) the U.S. should pursue international definitions of "force" and "armed attack" in the Information Warfare context; (2) the U.S. should pursue international cooperation for the joint investigation and prosecution of Internet attacks; (3) the U.S. must balance offensive opportunities against defensive vulnerabilities; and (4) the U.S. should prepare strategic plans now rather than making policy decisions in real-time during an Internet attack.
Policy for access: Framing the question
Venue: arXiv cs.CY 2001
Year: 2001

Five years after the '96 Telecommunications Act, we still find precious little local facilities-based competition. In response there are calls in Congress and even from the FCC for new legislation to "free the Bells." However, the same ideology drove policy, not just five years ago, but also almost twenty years back with the first modern push for "freedom," namely divestiture. How might we frame the question of policy for local access to engender a more fruitful approach? The starting point for this analysis is the network--not bits and bytes, but the human network. With the human network as starting point, the unit of analysis is the community--specifically, the individual in a tension with community. There are two core ideas. The first takes a behavioral approach to the economics--and the relative share between beneficial chaos and order, in economic affairs, becomes explicit. If the first main idea provides a conceptual base for open source, the second core idea distinguishes open source from open design, ie at the information 'frontier' we push forward. The resulting policy frame for access is worked out in the detailed, concrete steps of an extended thought experiment. A small town setting (Concord, Massachusetts) grounds the discussion in the real world. The purpose overall is to stimulate new thinking which may break out of the conundrum where periodic rounds to legislate 'freedom' produce the opposite, recursively. The ultimate aim is better fit between our analytically-driven expectations and economic outcomes.
The Influence of Policy Regimes on the Development and Social Implications of Privacy Enhancing Technologies
Venue: arXiv cs.CY 2001
Year: 2001

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.
The Next Frontier for Openness: Wireless Communications
Venue: arXiv cs.CY 2001
Year: 2001

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.
Standards and Intellectual Property Rights in the Age of Global Communication - A Review of the International Standardization of Third-Generation Mobile System
Venue: arXiv cs.CY 2001
Year: 2001

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).
Digital Arroyos: An Examination of State Policy and Regulated Market Boundaries in Constructing Rural Internet Access
Venue: arXiv cs.CY 2001
Year: 2001

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
Two-way Quantum One-counter Automata
Venue: arXiv cs.CC 2001
Year: 2001

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.
Pushdown Timed Automata: a Binary Reachability Characterization and Safety Verification
Venue: arXiv cs.LO 2001
Year: 2001

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.
ENUM: The Collision of Telephony and DNS Policy
Venue: arXiv cs.GL 2001
Year: 2001

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]
Part-of-Speech Tagging with Two Sequential Transducers
Venue: arXiv cs.CL 2001
Year: 2001

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.
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
Venue: arXiv cs.DM 2001
Year: 2001

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}.