1,721,008 research outputs found
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
A typing theory for flow networks (part I)
Full text linkA flow network N is a capacited finite directed graph, with multiple sources (or input arcs) and multiple sinks (or output arcs). A flow f in N is feasible if it satisfies the usual flow-conservation condition at every node and lower-bound/upper-bound capacity constraints at every arc. We develop an algebraic theory of feasible flows in such networks with several beneficial consequences.
We define and prove the correctness of an algorithm to infer, from a given flow network N, an algebraic characterization T of all assignments f of values to the input and output arcs of N that can be extended to feasible flows g. We call such a characterization T a principal typing for N, as there are other typings which are only valid for N because they define subsets of all input-output assignments f that can be extended to feasible flows g. A typing for N turns out to define a bounded convex polyhedral set (or polytope) in the n-dimensional vector space over real numbers where n is the total number of input and output arcs in N. We then establish necessary and sufficient conditions for an arbitrary typing to be a principal typing for some flow network.
Based on these necessary and sufficient conditions, we define operations on typings that preserve their principality (to be typings for flow networks), and examine the implications for a typing theory of flow networks. These also support a divide-and-conquer approach to the design and analysis of flow-network algorithms.National Science Foundation (CCF-0820138
Algebraic characterizations of flow-network typings
Full text linkA flow network N is a capacited finite directed graph, with multiple input ports/arcs and multiple output ports/arcs. A flow f in N assigns a non-negative real number to every arc and is feasible if it satisfies flow conservation at every node and respects lower-bound/upper-bound capacities at every arc. We develop an algebraic theory of feasible flows in such networks with several beneficial consequences.
We define algorithms to infer, from a given flow network N, an algebraic classification, which we call a typing for N, of all assignments f_0 of values to the input and output arcs of N that can be extended to a feasible flow f. We then establish necessary and sufficient conditions on an arbitrary typing T guaranteeing that T is a valid typing for some flow network N. Based on these necessary and sufficient conditions, we define operations on typings that preserve their validity (to be typings for flow networks), and examine the implications for a typing theory of flow networks.National Science Foundation (CCF-0820138
The syntax and semantics of a domain-specific language for flow-network design
Full text linkFlow networks are inductively defined, assembled from small components to produce arbitrarily large ones, with interchangeable functionally-equivalent parts. We carry out this induction formally using a domain-specific language (DSL). Associated with our DSL are a semantics and a typing theory. The latter gives rise to a system of formal annotations that enforce desirable properties of flow networks as invariants across their interfaces. A prerequisite for a typing theory is a formal semantics, i.e., a rigorous characterization of flows that are safe (or just feasible in this report) for the network, possibly restricted to satisfy additional efficiency or safety requirements. We give a detailed presentation of a denotational semantics only, but also point out the elements that an equivalent operational semantics must include.National Science Foundation (CNS-0952145, CCF-0820138, CSR-0720604, CNS-1012798, EFRI-0735974
Lightweight Formal Methods for the Development of High-Assurance Networking Systems
Full text linkWe survey several of the research efforts pursued by the iBench and snBench projects in the CS Department at Boston University over the last half dozen years. These activities use ideas and methodologies inspired by recent developments in other parts of computer science -- particularly in formal methods and in the foundations of programming languages -- but now specifically applied to the certification of safety-critical networking systems. This is research jointly led by Azer Bestavros and Assaf Kfoury with the participation of Adam Bradley, Andrei Lapets, and Michael Ocean
Personal reflections on the role of mathematical logic in computer science
Full text linkAccepted manuscrip
A compositional approach to the max-flow problem
Full text linkAlthough written as a friendly rejoinder to two negative reviews of a 10-page extended abstract, entitled “A Compositional Approach to Network Algorithms,” itself based on a report by the same title [3], this report is intended to be a gentler and more informal addendum to its precursor.Partially supported by NSF awards CCF-0820138 and CNS-1135722
A domain-specific language for the incremental and modular design of large-scale verifiably-safe flow networks
Full text linkFlow networks are inductively defined, assembled from small networks or modules to produce arbitrarily large ones, with interchangeable functionally-equivalent parts. We carry out this induction formally using a domain-specific language (DSL). Associated with our DSL is a typing system (or static semantics), a system of formal annotations that enforce desirable properties of flow networks as invariants across their interfaces. A prerequisite for a type theory is a formal semantics, i.e., a rigorous definition of the entities that qualify as feasible flows through the networks, possibly restricted to satisfy additional efficiency or safety requirements. We carry out this in two ways, as a denotational semantics and as an operational (or reduction) semantics
- …
