Search

This paper contains a discussion of striking similarities between influential philosophical concepts of the past and the approaches currently employed in selected areas of computer science. In particular, works of the Pythagoreans, Plato, Abelard, Ash'arites, Malebranche and Berkeley are presented and contrasted with such computer science ideas as digital computers, object-oriented programming, the modelling of an object's actions and causality in virtual environments, and 3D graphics rendering. The intention of this paper is to provoke the computer science community to go off the beaten path in order to find inspiration for the development of new approaches in software engineering., Author(s): Wojciech Tylman [sup.1] Author Affiliations: (Aff1) 0000 0004 0620 0652, grid.412284.9, Department of Microelectronics and Computer Science, Lódz University of Technology, , Lódz, Poland Introduction Today's computer science is [...]

This paper sheds light on the shift that is taking place from the practice of 'coding', namely developing programs as conventional in the software community, to the practice of 'curing', an activity that has emerged in the last few years in Deep Learning (DL) and that amounts to curing the data regime to which a DL model is exposed during training. Initially, the curing paradigm is illustrated by means of a study-case on autonomous vehicles. Subsequently, the shift from coding to curing is analysed taking into consideration the epistemological notions, central in the philosophy of computer science, of function, implementation, and correctness. First, it is illustrated how, in the curing paradigm, the functions performed by the trained model depend much more on dataset curation rather than on the model algorithms which, in contrast with the coding paradigm, do not comply with requested specifications. Second, it is highlighted how DL models cannot be considered implementations according to any of the available definitions of implementation that follow an intentional theory of functions. Finally, it is argued that DL models cannot be evaluated in terms of their correctness but rather in their experimental computational validity., Author(s): Nicola Angius [sup.1], Alessio Plebe [sup.1] Author Affiliations: (1) grid.10438.3e, 0000 0001 2178 8421, Department of Cognitive Science, University of Messina, , Messina, Italy Introduction Let us loosely use [...]

How can we be certain that software is reliable? Is there any method that can verify the correctness of software for all cases of interest? Computer scientists and software engineers have informally assumed that there is no fully general solution to the verification problem. In this paper, we survey approaches to the problem of software verification and offer a new proof for why there can be no general solution., Author(s): John Symons [sup.1], Jack K. Horner [sup.1] [sup.2] Author Affiliations: (1) grid.266515.3, 0000 0001 2106 0692, Department of Philosophy, University of Kansas, , Wescoe Hall 1445 Jayhawk Blvd, 66045-7590, [...]

This paper provides a review of Raymond Turner's book Computational Artefacts. Towards a Philosophy of Computer Science. Focus is made on the definition of program correctness as the twofold problem of evaluating whether both the symbolic program and the physical implementation satisfy a set of specifications. The review stresses how these are not two separate problems. First, it is highlighted how formal proofs of correctness need to rely on the analysis of physical computational processes. Secondly, it is underlined how software testing requires considering the formal relations holding between the specifications and the symbolic program. Such a mutual dependency between formal and empirical program verification methods is finally shown to influence the debate on the epistemological status of computer science., Author(s): Nicola Angius [sup.1] Author Affiliations: (1) grid.11450.31, 0000 0001 2097 9138, Department of History, Human Sciences, and Education, University of Sassari, , Sassari, Italy Raymond Turner's book Computational Artefacts. [...]

Byline: Birte Lonneker-Rodman (1) Keywords: Agreement; Annotation; Conceptual information; Evaluation; Lexical information; Mapping; Metaphor; Resource creation Abstract: This paper concerns metaphor resource creation. It provides an account of methods used, problems discovered, and insights gained at the Hamburg Metaphor Database project, intended to inform similar resource creation initiatives, as well as future metaphor processing algorithms. After introducing the project, the theoretical underpinnings that motivate the subdivision of represented information into a conceptual and a lexical level are laid out. The acquisition of metaphor attestations from electronic corpora is explained, and annotation practices as well as database contents are evaluated. The paper concludes with an overview of related projects and an outline of possible future work. Author Affiliation: (1) International Computer Science Institute, 1947 Center Street, Suite 600, Berkeley, CA, 94704, USA Article History: Registration Date: 02/09/2008 Received Date: 12/09/2007 Accepted Date: 02/09/2008 Online Date: 01/10/2008

Byline: Antoine Doucet (1), Helena Ahonen-Myka (2) Keywords: Multiword expressions; Document retrieval; Endogenous resources Abstract: In this paper, we address the problem of the exploitation of text phrases in a multilingual context. We propose a technique to benefit from multi-word units in adhoc document retrieval, whatever the language of the document collection. We present principles to optimize the performance improvement obtained through this approach. The work is validated through retrieval experiments conducted on Chinese, Japanese, Korean and English. Author Affiliation: (1) Department of Computer Science, University of Caen, Caen, France (2) Department of Computer Science, University of Helsinki, Helsinki, Finland Article History: Registration Date: 02/09/2009 Online Date: 03/10/2009

Byline: Helena Medeiros Caseli (1), Carlos Ramisch (2), Maria Gracas Volpe Nunes (3), Aline Villavicencio (2,4) Keywords: Automatic identification; Word alignment; Machine translation; Terminology; Multiword expressions; Lexical acquisition; Statistical methods Abstract: Due to idiosyncrasies in their syntax, semantics or frequency, Multiword Expressions (MWEs) have received special attention from the NLP community, as the methods and techniques developed for the treatment of simplex words are not necessarily suitable for them. This is certainly the case for the automatic acquisition of MWEs from corpora. A lot of effort has been directed to the task of automatically identifying them, with considerable success. In this paper, we propose an approach for the identification of MWEs in a multilingual context, as a by-product of a word alignment process, that not only deals with the identification of possible MWE candidates, but also associates some multiword expressions with semantics. The results obtained indicate the feasibility and low costs in terms of tools and resources demanded by this approach, which could, for example, facilitate and speed up lexicographic work. Author Affiliation: (1) NILC, Department of Computer Science, Federal University of Sao Carlos, Sao Carlos, Brazil (2) Institute of Informatics, Federal University of Rio Grande do Sul, Porto Alegre, Brazil (3) NILC, ICMC, University of Sao Paulo, Sao Carlos, Brazil (4) Department of Computer Science, University of Bath, Bath, UK Article History: Registration Date: 17/07/2009 Received Date: 20/11/2007 Accepted Date: 14/07/2009 Online Date: 14/08/2009

Byline: Donghong Ji (1), Shiju Zhao (2), Guozheng Xiao (3) Keywords: Term extraction; Term weighting; Maximal marginal relevance; Document re-ranking; Information retrieval Abstract: In this paper, we address the problem of document re-ranking in information retrieval, which is usually conducted after initial retrieval to improve rankings of relevant documents. To deal with this problem, we propose a method which automatically constructs a term resource specific to the document collection and then applies the resource to document re-ranking. The term resource includes a list of terms extracted from the documents as well as their weighting and correlations computed after initial retrieval. The term weighting based on local and global distribution ensures the re-ranking not sensitive to different choices of pseudo relevance, while the term correlation helps avoid any bias to certain specific concept embedded in queries. Experiments with NTCIR3 data show that the approach can not only improve performance of initial retrieval, but also make significant contribution to standard query expansion. Author Affiliation: (1) Department of Computer Science, Center for Study of Language Information, Wuhan University, 430072, Wuhan, China (2) Department of Chinese Language and Literature, Wuhan University, 430072, Wuhan, China (3) Center for Study of Language Information, Wuhan University, 430072, Wuhan, China Article History: Registration Date: 03/10/2009 Online Date: 13/11/2009 Article note: First author is supported by NSF (60773011), NSF(90820005), and first two authors are supported by Wuhan University 985 Project (985yk004).

Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove complexity bounds for these types of problems is based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization problems over the boolean hypercube via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS-based certificates remain valid: First, for polynomials, which are nonnegative over the n-variate boolean hypercube with constraints of degree d there exists a SONC certificate of degree at most [Formula omitted]. Second, if there exists a degree d SONC certificate for nonnegativity of a polynomial over the boolean hypercube, then there also exists a short degree d SONC certificate that includes at most [Formula omitted] nonnegative circuit polynomials. Moreover, we prove that, in opposite to SOS, the SONC cone is not closed under taking affine transformation of variables and that for SONC there does not exist an equivalent to Putinar's Positivstellensatz for SOS. We discuss these results from both the algebraic and the optimization perspective., Author(s): Mareike Dressler [sup.1], Adam Kurpisz [sup.2], Timo de Wolff [sup.3] Author Affiliations: (1) grid.266100.3, 0000 0001 2107 4242, Department of Mathematics, University of California, San Diego, , 9500 Gilman [...]

The Circuit SAT problem for a circuit with at most one satisfying assignment is considered. An algorithm running in time O([2.sup..374589m]) is presented, where m is the number of internal gates of the circuit. In order to make the exposition self-contained, an algorithm for the general case of Circuit SAT with running time O([2.sup..389667m]) obtained by Savinov in his master thesis is described. Bibliography: 13 titles., 1. INTRODUCTION The Boolean circuit satisfiability problem (Circuit SAT), along with its particular case of satisfiability of a Boolean formula in CNF (SAT), are among the central problems of theoretical [...]

I critically review Raymond Turner's Computational Artifacts - Towards a Philosophy of Computer Science by placing beside his position a rather different one, according to which computer science is a branch of, and is therefore subsumed by, immaterial formal logic., Author(s): Selmer Bringsjord [sup.1] [sup.2] [sup.3] [sup.4] Author Affiliations: (1) grid.33647.35, 0000 0001 2160 9198, Rensselaer AI & Reasoning (RAIR) Laboratory, Rensselaer Polytechnic Institute (RPI), , 12180, Troy, NY, USA [...]

Turner (2018 (See CR52)) argues that computer programs must have purposes, that implementation is not a kind of semantics, and that computers might need to understand what they do. I respectfully disagree: Computer programs need not have purposes, implementation is a kind of semantic interpretation, and neither human computers nor computing machines need to understand what they do., Author(s): William J. Rapaport [sup.1] [sup.2] [sup.3] [sup.4] Author Affiliations: (1) grid.273335.3, 0000 0004 1936 9887, Department of Computer Science and Engineering, University at Buffalo - The State University of [...]

One might poetically muse that computers have the essence both of logic and machines. Through the case of the history of Separation Logic, we explore how this assertion is more than idle poetry. Separation Logic works because it merges the software engineer's conceptual model of a program's manipulation of computer memory with the logical model that interprets what sentences in the logic are true, and because it has a proof theory which aids in the crucial problem of scaling the reasoning task. Scalability is a central problem, and some would even say the central problem, in appli- cations of logic in computer science. Separation Logic is an interesting case because of its widespread success in verification tools. For these two senses of model-the engineering/conceptual and the logical-to merge in a genuine sense, each must maintain their norms of use from their home disciplines. When this occurs, both the logic and engineering benefit greatly. Seeking this intersection of two different senses of model provides a strategy for how computer scientists and logicians may be successful. Furthermore, the history of Separation Logic for analysing programs provides a novel case for philosophers of science of how software engineers and computer scientists develop models and the components of such models. We provide three contributions: an exploration of the extent of models merging that is necessary for success in computer science; an introduction to the technical details of Separation Logic, which can be used for reasoning about other exhaustible resources; and an introduction to (a subset of) the problems, process, and results of computer scientists for those outside the field., Author(s): David Pym [sup.1] , Jonathan M. Spring [sup.1] , Peter O'Hearn [sup.1] Author Affiliations: (Aff1) 0000000121901201, grid.83440.3b, Computer Science, University College London, , Gower Street, WC1E 6BT, London, UK [...]

Very large databases are a major opportunity for science and data analytics is a remarkable new field of investigation in computer science. The effectiveness of these tools is used to support a 'philosophy' against the scientific method as developed throughout history. According to this view, computer-discovered correlations should replace understanding and guide prediction and action. Consequently, there will be no need to give scientific meaning to phenomena, by proposing, say, causal relations, since regularities in very large databases are enough: 'with enough data, the numbers speak for themselves'. The 'end of science' is proclaimed. Using classical results from ergodic theory, Ramsey theory and algorithmic information theory, we show that this 'philosophy' is wrong. For example, we prove that very large databases have to contain arbitrary correlations. These correlations appear only due to the size, not the nature, of data. They can be found in 'randomly' generated, large enough databases, which-as we will prove-implies that most correlations are spurious. Too much information tends to behave like very little information. The scientific method can be enriched by computer mining in immense databases, but not replaced by it., Author(s): Cristian S. Calude [sup.1], Giuseppe Longo [sup.2] [sup.3] Author Affiliations: (1) 0000 0004 0372 3343, grid.9654.e, Department of Computer Science, University of Auckland, , Auckland, New Zealand (2) 0000 [...]