2026-05-13T18:05:54Z https://lib.jucs.org/oai.php

10.3217/jucs-000-00 1994-11-15 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1994-11-15 1994-11-15 1994 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 0 1 2 1994 10.3217/jucs-000-00 https://lib.jucs.org/article/27061/ https://lib.jucs.org/article/27061/download/pdf/ https://lib.jucs.org/article/27061/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-000-00-0003 1994-11-15 jucs

AT&T Bell Laboratories, author Odlyzko, Andrew 1994-11-15 1994-11-15 1994 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 0 3 53 1994 10.3217/jucs-000-00-0003 https://lib.jucs.org/article/27062/ https://lib.jucs.org/article/27062/download/pdf/ https://lib.jucs.org/article/27062/download/xml/ text/html en_US Journal of Universal Computer Science Tragic Loss or Good Riddance? The Impending Demise of Traditional Scholarly Journals Research Article

10.3217/jucs-000-00-0054 1994-11-15 jucs

10.3217/jucs-000-00-0109 1994-11-15 jucs

University of Auckland, New Zealand, New Zealand author Calude, Cristian IICM, Graz University of Technology, Austria author Maurer, Hermann University of Turku, Finland author Salomaa, Arto 1994-11-15 1994-11-15 1994 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 0 109 116 1994 10.3217/jucs-000-00-0109 https://lib.jucs.org/article/27066/ https://lib.jucs.org/article/27066/download/pdf/ https://lib.jucs.org/article/27066/download/xml/ text/html en_US Journal of Universal Computer Science Journal of Universal Computer Science Research Article

10.3217/jucs-000-00-0117 1994-11-15 jucs

IICM, Graz University of Technology, Austria author Maurer, Hermann IICM, Graz University of Technology, Austria author Schmaranz, Klaus 1994-11-15 1994-11-15 1994 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 0 117 126 1994 10.3217/jucs-000-00-0117 https://lib.jucs.org/article/27067/ https://lib.jucs.org/article/27067/download/pdf/ https://lib.jucs.org/article/27067/download/xml/ In this paper we first discuss briefly why electronic journals today have a rather moderate success. We then describe J.UCS - the Journal of Universal Computer Science - an electronic journal that is the prototype for electronic publishing in the future. Using Hyper-G for distribution it provides all search and navigation mechanisms of large scale hypermedia systems and therefore makes it easy to locate interesting articles. Readers can perform variable scope searches to find papers, then they can browse them on screen either in hypertext mode or in high quality PostScript mode, or they can get high quality PostScript documents for printing. Even PostScript documents provide full hyperlink support when reading them on screen. Articles in J.UCS can be accessed very fast using a wide net of servers distributed all over the world. J.UCS also supports annotations to existing articles informing the readers of new research results or errors. Writing articles for J.UCS is very easy using PostScript as the main submission format, even standard hyperlinks such as literature references are generated automatically. We close this paper with a short comparison of J.UCS to other electronic journals and with an outlook on future developments. text/html en_US Journal of Universal Computer Science J.UCS Hyper-G electronic publishing electronic journals J.UCS - The Next Generation in Electronic Journal Publishing Research Article

10.3217/jucs-000-00-0127 1994-11-15 jucs

IICM, Graz University of Technology, Austria author Andrews, Keith IICM, Graz University of Technology, Austria author Kappe, Frank IICM, Graz University of Technology, Austria author Maurer, Hermann IICM, Graz University of Technology, Austria author Schmaranz, Klaus 1994-11-15 1994-11-15 1994 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 0 127 136 1994 10.3217/jucs-000-00-0127 https://lib.jucs.org/article/27074/ https://lib.jucs.org/article/27074/download/pdf/ https://lib.jucs.org/article/27074/download/xml/ In this paper we claim that the navigational and structural tools currently available on the Internet are not sufficient to fully exploit the tremendous power of the largest information and communication ressource mankind has ever had. We contend that current hypermedia systems and its most prominent specimen WWW do not have enough functionality to provide the power that is needed. We explain important features that are absent, claim that "second generation" hypermedia systems incorporating such features are essential and mention a first such second generation hypermedia system called Hyper-G, which is just becoming available and is starting to be used for a wide variety of applications. text/html en_US Journal of Universal Computer Science On Second Generation Hypermedia Systems Research Article

10.3217/jucs-000-00-0137 1994-11-15 jucs

Hypermedia Unit, Department of Computer Science, University of Auckland, New Zealand author Lennon, Jennifer IICM, Graz University of Technology, Austria author Maurer, Hermann 1994-11-15 1994-11-15 1994 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 0 137 143 1994 10.3217/jucs-000-00-0137 https://lib.jucs.org/article/27075/ https://lib.jucs.org/article/27075/download/pdf/ https://lib.jucs.org/article/27075/download/xml/ In the first part of this paper we argue that the terms "multimedia" and "hypermedia" need redefining to reflect latest developments in converging technology. We propose new forms of "interactive" and "annotated" movies, to be created using advanced digital techniques. In the second half of the paper we suggest that some of the problems that users of Internet are currently experiencing are due to "first generation" systems, but that "second generation" answers have already emerged. text/html en_US Journal of Universal Computer Science Converging technology multimedia hypermedia interactive and annotated movies Internet Hyper-G. You Believe You Know What Multimedia is? And What Internet Will Do For You? Well ... Think Again! Research Article

10.3217/jucs-001-01 1995-01-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-01-28 1995-01-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 1 1 1 1995 10.3217/jucs-001-01 https://lib.jucs.org/article/27076/ https://lib.jucs.org/article/27076/download/pdf/ https://lib.jucs.org/article/27076/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-01-0002 1995-01-28 jucs

Department of Computer Science, The University of Auckland, Auckland, New Zealand author Fenwick, Peter 1995-01-28 1995-01-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 1 2 22 1995 10.3217/jucs-001-01-0002 https://lib.jucs.org/article/27077/ https://lib.jucs.org/article/27077/download/pdf/ https://lib.jucs.org/article/27077/download/xml/ High-radix division, developing several quotient bits per clock, is usually limited by the difficulty of generating accurate high-radix quotient digits. This paper describes techniques which allow quotient digits to be inaccurate, but then refine the result. We thereby obtain dividers with slightly reduced performance, but with much simplified logic. For example, a nominal radix-64 divider can generate an average of 4.5 to 5.5 quotient bits per cycle with quite simple digit estimation logic. The paper investigates the technique for radices of 8, 16, 64 and 256, including various qualities of digit estimation, and operation with restricted sets of divisor multiples. text/html en_US Journal of Universal Computer Science Division high radix approximate digit estimates High-radix Division with Approximate Quotient-digit Estimation Research Article

10.3217/jucs-001-01-0023 1995-01-28 jucs

Department of Computer Science, University of Turku, Finland author Leppänen, Ville 1995-01-28 1995-01-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 1 23 34 1995 10.3217/jucs-001-01-0023 https://lib.jucs.org/article/27078/ https://lib.jucs.org/article/27078/download/pdf/ https://lib.jucs.org/article/27078/download/xml/ We show how to implement an -processor EREW PRAM workoptimally on a 2-dimensional n-sided mesh of trees, consisting of n processors, n memory modules, and nodes. Similarly, we prove that an -processor EREW PRAM can be implemented work-optimally on a 3-dimensional n-sided mesh of trees. By the work-optimality of implementations we mean that the expected routing time of PRAM memory requests is per simulated PRAM processor with high probability. Experiments show that on relatively small and the cost per simulated PRAM processor is 1.5-2.5 in the 2-dimensional case, and 2-3 in the 3-dimensional case. If at each step at most 1/3'th of the PRAM processors make a reference to the shared memory, then the simulation cost is approximately 1. We also compare our work-optimal simulations to those proposed for coated meshes. text/html en_US Journal of Universal Computer Science EREW mesh of trees shared memory simulation work-optimal randomized coated mesh. On Implementing EREW Work-Optimally on Mesh of Trees Research Article

10.3217/jucs-001-01-0035 1995-01-28 jucs

Computer Science Department, University of Auckland, Auckland, New Zealand author Flinn, Bill IICM, Graz University of Technology, Austria author Maurer, Hermann 1995-01-28 1995-01-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 1 35 47 1995 10.3217/jucs-001-01-0035 https://lib.jucs.org/article/27080/ https://lib.jucs.org/article/27080/download/pdf/ https://lib.jucs.org/article/27080/download/xml/ In this paper we make a first attempt at systematically investigating levels of anonymity required in networked computer systems: we feel it is often overlooked that beyond such obvious cases as identified by means of a password or anonymous use there are many other levels of anonymity, identification and authenticity necessary in various applications. text/html en_US Journal of Universal Computer Science security anonymous use access control authentication big brother Levels of Anonymity Research Article

10.3217/jucs-001-01-0048 1995-01-28 jucs

University of Auckland, Auckland, New Zealand author Calude, Cristian S. https://orcid.org/0000-0002-8711-6799 1995-01-28 1995-01-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 1 48 66 1995 10.3217/jucs-001-01-0048 https://lib.jucs.org/article/27082/ https://lib.jucs.org/article/27082/download/pdf/ https://lib.jucs.org/article/27082/download/xml/ Chaitin s algorithmic definition of random strings - based on the complexity induced by self-delimiting computers - is critically discussed. One shows that Chaitin s model satisfy many natural requirements related to randomness, so it can be considered as an adequate model for finite random objects. It is a better model than the original (Kolmogorov) proposal. Finally, some open problems will be discussed. text/html en_US Journal of Universal Computer Science Blank-endmarker complexity Chaitin (self-delimiting) complexity random strings. What Is a Random String? Research Article

10.3217/jucs-001-01-0067 1995-01-28 jucs

Institute of Mathematics of the Romanian Academy, Bucharest, Romania author Paun, Gheorghe University of Leiden, Department of Computer Science, Netherlands author Rozenberg, Grzegorz Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland author Salomaa, Arto 1995-01-28 1995-01-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 1 67 82 1995 10.3217/jucs-001-01-0067 https://lib.jucs.org/article/27088/ https://lib.jucs.org/article/27088/download/pdf/ https://lib.jucs.org/article/27088/download/xml/ We consider generative mechanisms producing languages by starting from a finite set of words and shuffling the current words with words in given sets, depending on certain conditions. Namely, regular and finite sets are given for controlling the shuffling: strings are shuffled only to strings in associated sets. Six classes of such grammars are considered, with the shuffling being done on a left most position, on a prefix, arbitrarily, globally, in parallel, or using a maximal selector. Most of the corresponding six families of languages, obtained for finite, respectively for regular selection, are found to be incomparable. The relations of these families with Chomsky language families are briefly investigated. text/html en_US Journal of Universal Computer Science Shuffle operation Chomsky grammars L Systems Grammars Based on the Shuffle Operation Research Article

10.3217/jucs-001-02 1995-02-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-02-28 1995-02-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 83 83 1995 10.3217/jucs-001-02 https://lib.jucs.org/article/27095/ https://lib.jucs.org/article/27095/download/pdf/ https://lib.jucs.org/article/27095/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-02-0084 1995-02-28 jucs

IICM, Graz University of Technology, Austria author Kappe, Frank 1995-02-28 1995-02-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 84 104 1995 10.3217/jucs-001-02-0084 https://lib.jucs.org/article/27096/ https://lib.jucs.org/article/27096/download/pdf/ https://lib.jucs.org/article/27096/download/xml/ One of the problems that we experience with today's most widespread Internet Information Systems (like WWW or Gopher) is the lack of support for maintaining referential integrity. Whenever a resource is (re)moved, dangling references from other resources may occur.This paper presents a scalable architecture for automatic maintenance of referential integrity in large (thousands of servers) distributed information systems. A central feature of the proposed architecture is the p-flood algorithm, which is a scalable, robust, prioritizable, probabilistic server-server protocol for efficient distribution of update information to a large collection of servers.The p-flood algorithm is now implemented in the Hyper-G system, but may in principle also be implemented as an add-on for existing WWW and Gopher servers.Keywords: Hypertext, Link Consistency, Distributed Information System, Internet, Gopher, WWW, Hyper-G, Scalability, p-flood. text/html en_US Journal of Universal Computer Science Hypertext Link Consistency Distributed Information System Internet Gopher WWW Hyper-G Scalability p-flood A Scalable Architecture for Maintaining Referential Integrity in Distributed Information Systems Research Article

10.3217/jucs-001-02-0105 1995-02-28 jucs

Technical University Wien, Institute for Computer Languages, Vienna, Austria author Freund, Rudolf Institute of Mathematics of the Romanian Academy, Bucharest, Romania author Paun, Gheorghe 1995-02-28 1995-02-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 105 130 1995 10.3217/jucs-001-02-0105 https://lib.jucs.org/article/27099/ https://lib.jucs.org/article/27099/download/pdf/ https://lib.jucs.org/article/27099/download/xml/ We prove that grammar systems with (prescribed or free) teams (of constant size at least two or arbitrary size) working as long as they can do, characterize the family of languages generated by (context-free) matrix grammars with appearance checking; in this way, the results in [Paun, Rozenberg 1994] are completed and improved. text/html en_US Journal of Universal Computer Science Formal languages grammar systems teams A Variant of Team Cooperation in Grammar Systems Research Article

10.3217/jucs-001-02-0131 1995-02-28 jucs

Department of Mathematics University of Turku and Turku Centre for Computer Science (TUCS), Turku, Finland author Honkala, Juha Institut fuer Algebra und Diskrete Mathematik, Technische Universität Wien, Vienna, Austria author Kuich, Werner 1995-02-28 1995-02-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 131 135 1995 10.3217/jucs-001-02-0131 https://lib.jucs.org/article/27100/ https://lib.jucs.org/article/27100/download/pdf/ https://lib.jucs.org/article/27100/download/xml/ We show that nonzero axioms add to the generative capacity of Lindenmayerian series generating systems. On the other hand, if nonzero axioms are allowed, nonterminals do not, provided that only quasiregular series are considered. text/html en_US Journal of Universal Computer Science On Four Classes of Lindenmayerian Power Series Research Article

10.3217/jucs-001-02-0136 1995-02-28 jucs

The University of Wollongong, Wollongong, Australia author Seberry, Jennifer The University of Wollongong, Wollongong, Australia author Zhang, Xian-Mo Monash University, Melbourne, Australia author Zheng, Yuliang 1995-02-28 1995-02-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 136 150 1995 10.3217/jucs-001-02-0136 https://lib.jucs.org/article/27101/ https://lib.jucs.org/article/27101/download/pdf/ https://lib.jucs.org/article/27101/download/xml/ The connections among the various nonlinearity criteria is currently an important topic in the area of designing and analyzing cryptographic functions. In this paper we show a quantitative relationship between propagation characteristics and nonlinearity, two critical indicators of the cryptographic strength of a Boolean function. We also present a tight lower bound on the nonlinearity of a cryptographic function that has propagation characteristics. text/html en_US Journal of Universal Computer Science Cryptography Boolean functions Encryption functions Nonlinearity Propagation Characteristics SAC S-boxes The Relationship Between Propagation Characteristics and Nonlinearity of Cryptographic Functions Research Article

10.3217/jucs-001-02-0151 1995-02-28 jucs

Odessa State University, Ukraine author Bulitko, Vadim 1995-02-28 1995-02-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 151 154 1995 10.3217/jucs-001-02-0151 https://lib.jucs.org/article/27102/ https://lib.jucs.org/article/27102/download/pdf/ https://lib.jucs.org/article/27102/download/xml/ The paper contains completeness criterions for pseudosimple sets. Those criterions are constructed using effectivization of the definitions as well as extensionally bounded functions. text/html en_US Journal of Universal Computer Science Completeness Pseudosimple set Effectivization Extensionally bounded function On Completeness of Pseudosimple Sets Research Article

10.3217/jucs-001-03 1995-03-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-03-28 1995-03-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 155 155 1995 10.3217/jucs-001-03 https://lib.jucs.org/article/27103/ https://lib.jucs.org/article/27103/download/pdf/ https://lib.jucs.org/article/27103/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-03-0156 1995-03-28 jucs

U. S. Air Force Armstrong Laboratory, Brooks Air Force Base, Texas, United States of America author Carlson, Patricia Command Technologies, Inc., San Antonio, Texas, United States of America author Larralde, Veronica 1995-03-28 1995-03-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 156 161 1995 10.3217/jucs-001-03-0156 https://lib.jucs.org/article/27104/ https://lib.jucs.org/article/27104/download/pdf/ https://lib.jucs.org/article/27104/download/xml/ When driven by simple models of information processing, reading instruction focuses on basic decoding skills centering on words and sentences. Factoring in advanced cognitive studies adds at least two more dimensions. First, readers must learn a collection of strategies for constructing meaning from text. Second, and most importantly, readers must develop enough situational awareness to diagnose a text and know which strategy to deploy. Teaching intellectual crafts that involve not only base-line performative skills but also a repertoire of problem-solving heuristics, and the metacognitive maturity to orchestrate multi-leveled activities, works well in a master-apprentice model. However, one-on-one instruction is far too labor-intensive to be commonplace in the teaching of reading. This paper describes a computerized learning environment for teaching the conceptual patterns of critical literacy. While the full implementation of the software treats both reading and writing, this paper covers only the reading aspects of R-WISE (Reading and Writing in a Supportive Environment). text/html en_US Journal of Universal Computer Science Combining Concept Mapping and Adaptive Advice to Teach Reading Comprehension Research Article

10.3217/jucs-001-03-0162 1995-03-28 jucs

Lab. LIP, Ecole Normale Superieure de Lyon, France author Daumas, Marc Lab. LIP, Ecole Normale Superieure de Lyon, France author Mazenc, Christophe Lab. LIP, Ecole Normale Superieure de Lyon, France author Merrheim, Xavier CNRS, Lab. LIP, Ecole Normale Superieure de Lyon, France author Muller, Jean-Michel 1995-03-28 1995-03-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 162 175 1995 10.3217/jucs-001-03-0162 https://lib.jucs.org/article/27105/ https://lib.jucs.org/article/27105/download/pdf/ https://lib.jucs.org/article/27105/download/xml/ A new range reduction algorithm, called ModularRange Reduction (MRR), briefly introduced by the authors in [Daumas et al. 1994] is deeply analyzed. It is used to reduce the arguments to exponential and trigonometric function algorithms to be within the small range for which the algorithms are valid. MRR reduces the arguments quickly and accurately. A fast hardwired implementation of MRR operates in time (log(n)), where n is the number of bits of the binary input value. For example, with MRR it becomes possible to compute the sine and cosine of a very large number accurately. Web propose two possible architectures implementing this algorithm. text/html en_US Journal of Universal Computer Science Computer Arithmetic Elementary Functions Range Reduction Modular Range Reduction Research Article

10.3217/jucs-001-03-0176 1995-03-28 jucs

The University of Auckland, Auckland, New Zealand author Doran, R. 1995-03-28 1995-03-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 176 194 1995 10.3217/jucs-001-03-0176 https://lib.jucs.org/article/27106/ https://lib.jucs.org/article/27106/download/pdf/ https://lib.jucs.org/article/27106/download/xml/ This surveys algorithms and circuits for integer division in special cases. These include division by constants, small divisors, exact divisors, and cases where the divisor and the number base have a special relationship. The related operation of remainder is also covered. Various prior techniques are treated in a common framework. Worked examples are provided together with examples of practical application. text/html en_US Journal of Universal Computer Science Special Cases of Division Research Article

10.3217/jucs-001-03-0195 1995-03-28 jucs

Alberta Research Council, Calgary, Canada author Gutwin, Carl Alberta Research Council, Calgary, Canada author Jones, Marlene Gemini Learning Systems Inc., Calgary, Canada author Brackett, Patrick Alberta Research Council, Calgary, Canada author Adolphe, Kim 1995-03-28 1995-03-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 195 200 1995 10.3217/jucs-001-03-0195 https://lib.jucs.org/article/27109/ https://lib.jucs.org/article/27109/download/pdf/ https://lib.jucs.org/article/27109/download/xml/ Intelligent Tutoring Systems (ITS) have proven to be effective tools for teaching and training. However, ITSs have not become common in industrial and organisational settings, in part because their complexity has proven difficult to manage outside of the research lab. Minimalist ITSs are an attempt to bridge the gap between research and practical application, they simplify research techniques while striving to maintain as much pedagogic intelligence as possible. This paper describes one such system, SWIFT, that is an example of how a minimalist ITS can be delivered as a commercial product. We outline some of the issues facing designers of a minimalist system, and describe the ways that research techniques have been incorporated into four modules of SWIFT: adaptive testing, course planning, guidance, and diagnosis. text/html en_US Journal of Universal Computer Science Bringing ITS to the Marketplace: A Successful Experiment in Minimalist Design Research Article

10.3217/jucs-001-03-0201 1995-03-28 jucs

Institut für Theoretische Physik, University of Technology Vienna, Vienna, Austria author Svozil, Karl 1995-03-28 1995-03-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 201 204 1995 10.3217/jucs-001-03-0201 https://lib.jucs.org/article/27112/ https://lib.jucs.org/article/27112/download/pdf/ https://lib.jucs.org/article/27112/download/xml/ The classical halting probability introduced by Chaitin is generalized to quantum computations. (The quantum omega was invented in a meeting of G. Chaitin, A. Zeilinger and the author (K. S.) in a Viennese coffee house (Cafe Braeunerhof) in January 1991. Thus, the group should be credited for the original invention, whereas any blame should remain with the author.) text/html en_US Journal of Universal Computer Science Halting Probability Amplitude of Quantum Computers Research Article

10.3217/jucs-001-04 1995-04-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-04-28 1995-04-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 205 205 1995 10.3217/jucs-001-04 https://lib.jucs.org/article/27113/ https://lib.jucs.org/article/27113/download/pdf/ https://lib.jucs.org/article/27113/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-04-0206 1995-04-28 jucs

IICM, Graz University of Technology, Austria author Andrews, Keith IICM, Graz University of Technology, Austria author Kappe, Frank IICM, Graz University of Technology, Austria author Maurer, Hermann 1995-04-28 1995-04-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 206 220 1995 10.3217/jucs-001-04-0206 https://lib.jucs.org/article/27114/ https://lib.jucs.org/article/27114/download/pdf/ https://lib.jucs.org/article/27114/download/xml/ As the Internet continues to experience exponential rates of growth, attention is shifting away from mainstream network services such as electronic mail and file transfer to more interactive information services. Current network information systems, whilst extremely successful, run into problems of fragmentation, consistency, scalability, and loss of orientation.The development of 'second generation' network information systems such as Hyper-G can help overcome these limitations. Of particular note are Hyper-Gs tightly-coupled structuring, linking, and search facilities, its projection of a seamless information space across server boundaries with respect to each of these facilities, and its support for multiple languages. The Harmony client for Hyper-G utilises two and three-dimensional visualisations of the information space and couples location feedback to search and link browsing operations, in order to reduce the likelihood of disorientation. This paper presents a comprehensive overview of Hyper-G and Harmony. text/html en_US Journal of Universal Computer Science Hypermedia information system information visualisation graphical interaction Internet The Hyper-G Network Information System Research Article

10.3217/jucs-001-04-0221 1995-04-28 jucs

CERN, author Cailliau, R. 1995-04-28 1995-04-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 221 231 1995 10.3217/jucs-001-04-0221 https://lib.jucs.org/article/27115/ https://lib.jucs.org/article/27115/download/pdf/ https://lib.jucs.org/article/27115/download/xml/ The World-Wide Web is the most talked-about distributed information system today. This paper does not touch on its workings, it tries to give a brief history and outlines the feelings provoked by the explosive adoption in all circles of WWW as the first vehicle on the Global Information Infrastructure. text/html en_US Journal of Universal Computer Science WWW World-Wide Web History SGML cultural Aspects Society. About WWW Research Article

10.3217/jucs-001-04-0232 1995-04-28 jucs

Springer-Verlag Heidelberg, author Götze, Dietrich 1995-04-28 1995-04-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 232 234 1995 10.3217/jucs-001-04-0232 https://lib.jucs.org/article/27116/ https://lib.jucs.org/article/27116/download/pdf/ https://lib.jucs.org/article/27116/download/xml/ Publishing the results of scientific research is the basis of the advancement of science, technology and medicine. text/html en_US Journal of Universal Computer Science Electronic Publishing Research Article

10.3217/jucs-001-04-0235 1995-04-28 jucs

University of Minnesota, United States of America author Mccahill, Mark University of Minnesota, United States of America author Anklesaria, Farhad 1995-04-28 1995-04-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 235 246 1995 10.3217/jucs-001-04-0235 https://lib.jucs.org/article/27118/ https://lib.jucs.org/article/27118/download/pdf/ https://lib.jucs.org/article/27118/download/xml/ How the Internet Gopher system has evolved since its first released in 1991 and how Internet Gopher relates to other popular Internet information systems. Current problems and future directions for the Internet Gopher system. text/html en_US Journal of Universal Computer Science Distributed Information Systems Internet Gopher Gopher+ Evolution of Internet Gopher Research Article

10.3217/jucs-001-04-0247 1995-04-28 jucs

JOANNEUM Research - IHM, Graz, Austria author Mülner, Helmut 1995-04-28 1995-04-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 247 250 1995 10.3217/jucs-001-04-0247 https://lib.jucs.org/article/27122/ https://lib.jucs.org/article/27122/download/pdf/ https://lib.jucs.org/article/27122/download/xml/ WAIS (Wide Area Information Servers), a development of Thinking Machine Corporation, turned out to be one of the main search engines in connection with the World Wide Web (WWW). This article gives a short overview of WAIS, its history, its basics and some connected developments. text/html en_US Journal of Universal Computer Science WAIS and Information Retrieval on the Internet Research Article

10.3217/jucs-001-05 1995-05-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-05-28 1995-05-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 251 251 1995 10.3217/jucs-001-05 https://lib.jucs.org/article/27123/ https://lib.jucs.org/article/27123/download/pdf/ https://lib.jucs.org/article/27123/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-05-0252 1995-05-28 jucs

Computer and Automation Institute of the Hungarian Academy of Sciences, Budapest, Hungary author Csuhaj-Varju, Erzsebet Institute of Mathematics of the Romanian Academy, Bucharest, Romania author Paun, Gheorghe Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland author Salomaa, Arto 1995-05-28 1995-05-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 252 268 1995 10.3217/jucs-001-05-0252 https://lib.jucs.org/article/27124/ https://lib.jucs.org/article/27124/download/pdf/ https://lib.jucs.org/article/27124/download/xml/ We investigate the generative capacity of the so-called conditional tabled eco-grammar systems (CTEG). They are a variant of ecogrammar systems, generative mechanisms recently introduced as models of the interplay between environment and agents in eco-systems. In particular, we compare the power of CTEG systems with that of programmed and of random context T0L systems and with that of ET0L systems. CTEG systems with one agent only (and without extended symbols) are found to be surprisingly powerful (they can generate non-ET0L languages). Representation theorems for ET0L and for recursively enumerable languages in terms of CTEG languages are also presented. 1.) Research supported by the Academy of Finland, Project 11281 text/html en_US Journal of Universal Computer Science Grammar systems L systems Artificial Life Conditional Tabled Eco-Grammar Systems Research Article

10.3217/jucs-001-05-0269 1995-05-28 jucs

Departement Computerwetenschappen, Katholieke Universiteit Leuven, Belgium author Duval, Erik Departement Computerwetenschappen, K.U.Leuven Celestijnenlaan 200 A, Heverlee, Belgium author Olivié, Henk Audio-Visual Service, University College London, England and Katholieke Universiteit Leuven, Belgium author Hanlon, Piers Audio-Visual Service, University College London, England and Katholieke Universiteit Leuven, Belgium author Jameson, David 1995-05-28 1995-05-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 269 291 1995 10.3217/jucs-001-05-0269 https://lib.jucs.org/article/27125/ https://lib.jucs.org/article/27125/download/pdf/ https://lib.jucs.org/article/27125/download/xml/ In this paper, we present HOME, a new environment for distributed hypermedia. We mainly concentrate on the server side, and provide access to World-Wide Web clients through a gateway mechanism. Data and metadata are strictly separated in the distributed HOME server. The architecture is based on a layered approach with separate layers for raw data, multimedia characteristics and hypermedia structure. We briefly present some of the implementation aspects and emphasise distinctive characteristics of HOME. We conclude with a comparison with related research and our plans for the future. text/html en_US Journal of Universal Computer Science HOME distributed hypermedia networked multimedia image store navigation query HOME: An Environment for Hypermedia Objects Research Article

10.3217/jucs-001-05-0292 1995-05-28 jucs

Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland author Mateescu, Alexandru Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland author Salomaa, Arto Mathematics Department, University of Turku, Turku, Finland author Salomaa, Kai Department of Computer Science, The University of Western Ontario, London, Ontario, Canada author Yu, Sheng 1995-05-28 1995-05-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 292 311 1995 10.3217/jucs-001-05-0292 https://lib.jucs.org/article/27126/ https://lib.jucs.org/article/27126/download/pdf/ https://lib.jucs.org/article/27126/download/xml/ Many fuzzy automaton models have been introduced in the past. Here, we discuss two basic finite fuzzy automaton models, the Mealy and Moore types, for lexical analysis. We show that there is a remarkable difference between the two types. We consider that the latter is a suitable model for implementing lexical analysers. Various properties of fuzzy regular languages are reviewed and studied. A fuzzy lexical analyzer generator (FLEX) is proposed. 1.) The work reported here has been supported by the Natural Sciences and Engineering Research Council of Canada grants OGP0041630 and the Project 11281 of the Academy of Finland. text/html en_US Journal of Universal Computer Science Lexical Analysis with a Simple Finite-Fuzzy-Automaton Model Research Article

10.3217/jucs-001-05-0312 1995-05-28 jucs

HyperMedia Unit and Department of Political Studies University of Auckland, New Zealand author Shearer, Jenny Institute for Applied Computer Science I, University of Hagen, Germany author Vermeer, Arnould 1995-05-28 1995-05-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 312 319 1995 10.3217/jucs-001-05-0312 https://lib.jucs.org/article/27127/ https://lib.jucs.org/article/27127/download/pdf/ https://lib.jucs.org/article/27127/download/xml/ The attempt by Unisys to obtain royalties from the Lempel Zev Welch Graphics Interchange Format specification through Compuserve has wide implications for the Internet. Increased activity in the US software patents area is likely to result in damage to progress of the software arts and the Internet, and to generate upscaled protest from Internet users. The LZW GIF case highlights the Internet culture in favour of free and unfettered development. Clarification of this important principle will have a major effect on the future of the Internet. text/html en_US Journal of Universal Computer Science Software patents debate Internet Compuserve Unisys LZW GIF Software Patents and The Internet Research Article

10.3217/jucs-001-05-0320 1995-05-28 jucs

The University of Wollongong, Wollongong, Australia author Zhang, Xian-Mo Monash University, Melbourne, Australia author Zheng, Yuliang 1995-05-28 1995-05-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 320 337 1995 10.3217/jucs-001-05-0320 https://lib.jucs.org/article/27128/ https://lib.jucs.org/article/27128/download/pdf/ https://lib.jucs.org/article/27128/download/xml/ We show that some widely accepted criteria for cryptographic functions, including the strict avalanche criterion (SAC) and the propagation criterion, have various limitations in capturing properties of vital importance to cryptographic algorithms, and propose a new criterion called GAC to measure the global avalanche characteristics of cryptographic functions. We also introduce two indicators related to the new criterion, one forecasts the sum-of-squares while the other the absolute avalanche characterist- ics of a function. Lower and upper bounds on the two indicators are derived, and two methods are presented to construct cryptographic functions that achieve nearly optimal global avalanche characteristics. text/html en_US Journal of Universal Computer Science GAC - the Criterion for Global Avalanche Characteristics of Cryptographic Functions Research Article

10.3217/jucs-001-06 1995-06-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-06-28 1995-06-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 338 338 1995 10.3217/jucs-001-06 https://lib.jucs.org/article/27129/ https://lib.jucs.org/article/27129/download/pdf/ https://lib.jucs.org/article/27129/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-06-0339 1995-06-28 jucs

Computer Science Dept., Manchester University, Manchester, United Kingdom author Banach, Richard Computer Science Dept., P. J. Safárik University, Kosice, Slovakia author Balázs, J. Computer Science Dept., University of Cyprus, Nicosia, Cyprus author Papadopoulos, George 1995-06-28 1995-06-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 339 398 1995 10.3217/jucs-001-06-0339 https://lib.jucs.org/article/27130/ https://lib.jucs.org/article/27130/download/pdf/ https://lib.jucs.org/article/27130/download/xml/ A translation of the pi-calculus into the MONSTR graph rewriting language is described and proved correct. The translation illustrates the heavy cost in practice of faithfully implementing the communication primitive of the pi-calculus and similar process calculi. It also illustrates the convenience of representing an evolving network of communicating agents directly within a graph manipulation formalism, both because the necessity to use delicate notions of bound variables and of scopes is avoided, and also because the standard model of graphs in set theory automatically yields a useful semantics for the process calculus. The correctness proof illustrates many features typically encountered in reasoning about graph rewriting systems, and particularly how serialisation techniques can be used to reorder an arbitrary execution into one having stated desirable properties. text/html en_US Journal of Universal Computer Science Concurrency Pi-Calculus Term Graph Rewriting MONSTR Process Networks Simulation Serialisability. A Translation of the Pi-Calculus Into MONSTR Research Article

10.3217/jucs-001-06-0399 1995-06-28 jucs

Institute for Applied Information Processing and Communications, Graz University of Technology, Graz, Austria author Klauser, Artur Institute for Applied Information Processing and Communications, Graz University of Technology, Graz, Austria author Posch, Reinhard 1995-06-28 1995-06-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 399 409 1995 10.3217/jucs-001-06-0399 https://lib.jucs.org/article/27131/ https://lib.jucs.org/article/27131/download/pdf/ https://lib.jucs.org/article/27131/download/xml/ Changing relative performance of processors, networks, and disks makes it necessary to reconsider algorithms using these three resources. As networks get faster and less congested topologies emerge, it becomes important to use network resources more aggressively to obtain good performance. Substitution of local disk accesses by accesses to remote memory can lead to better balanced resource usage and thus to faster systems. In this work we address the issue of file caching in a networked file system configuration. Distributed block-level in-memory caches are considered. We show that carefully constructed distributed concepts can lead to lower server load and better overall system performance than centralized concepts. Oversimplification, although aimed at gaining performance for single components, may deteriorate overall performance as a result of unbalanced resource usage. text/html en_US Journal of Universal Computer Science networked file systems distributed file caches load balancing file system performance Distributed Caching in Networked File Systems Research Article

10.3217/jucs-001-06-0410 1995-06-28 jucs

Department of Computer Science, University of Auckland, Auckland, New Zealand author Lennon, Jennifer Institute for Applied Computer Science I, University of Hagen, Germany author Vermeer, Arnould 1995-06-28 1995-06-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 410 422 1995 10.3217/jucs-001-06-0410 https://lib.jucs.org/article/27132/ https://lib.jucs.org/article/27132/download/pdf/ https://lib.jucs.org/article/27132/download/xml/ Much of the confusion that surrounds electronic personal assistants arises from the open-ended complexity of their development. In this paper we categorise some of their more common uses before suggesting several thought-provoking extensions. text/html en_US Journal of Universal Computer Science Electronic assistants electronic agents message pads searches prediction programming by example voice commands. From Personal Computer to Personal Assistant Research Article

10.3217/jucs-001-06-0423 1995-06-28 jucs

Jodrey School of Computer Science, Acadia University, Canada author Tomek, Ivan 1995-06-28 1995-06-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 423 434 1995 10.3217/jucs-001-06-0423 https://lib.jucs.org/article/27133/ https://lib.jucs.org/article/27133/download/pdf/ https://lib.jucs.org/article/27133/download/xml/ We present two examples of microworlds built into the Smalltalk environment for the purpose of teaching the main concepts of object oriented programming (OOP) and of the Smalltalk programming language. Thee distinguishing features of our microworlds are that each of them presents the student with a sequence of environments. These environments introduce one OOP concept after another, and disclose the Smalltalk environment and language in a step-by-step fashion. The starting environment does not require any programming and does not encourage the user to use Smalltalk tools, the last environment must be programmed in Smalltalk and discloses the major Smalltalk tools. The intended use of our microworlds is for the introductory part of a course on OOP, to be followed by a detailed presentation of the language. An extension of the presented approach would make the method suitable for teaching basics of computer programming in a computer literacy course. text/html en_US Journal of Universal Computer Science Microworld object oriented programming progressive disclosure Smalltalk teaching object oriented programming computer literacy. Microworlds For Teaching Concepts of Object Oriented Programming Research Article

10.3217/jucs-001-07 1995-07-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann Laboratoire LMI, Université de Provence, Marseille, France author Bajard, Jean-Claude Ecole des Mines de Saint-Etienne, SIMADE, Saint-Etienne, France author Michelucci, Dominique Ecole des Mines de Saint-Etienne, SIMADE, Saint-Etienne, France author Moreau, Jean-Michel CNRS, Laboratoire LIP, ENS Lyon, Lyon, France author Muller, Jean-Michel 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 435 438 1995 10.3217/jucs-001-07 https://lib.jucs.org/article/27136/ https://lib.jucs.org/article/27136/download/pdf/ https://lib.jucs.org/article/27136/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-07-0439 1995-07-28 jucs

Advanced Micro Devices, United States of America author Lynch, Thomas University of Texas at Austin, United States of America author Schulte, Michael 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 439 453 1995 10.3217/jucs-001-07-0439 https://lib.jucs.org/article/27137/ https://lib.jucs.org/article/27137/download/pdf/ https://lib.jucs.org/article/27137/download/xml/ The result of a simple floating-point computation can be in great error, even though no error is signaled, no coding mistakes are in the program, and the computer hardware is functioning correctly. This paper proposes a set of instructions appropriate for a general purpose microprocessor that can be used to improve the credibility and accuracy of numerical computations. Such instructions provide direct hardware support for monitoring events which may threaten computational integrity, implementing floating-point data types of arbitrary precision, and repeating calculations with greater precision. These useful features are obtained by the efficient implementation of high radix on-line arithmetic. The prevalence of super-scalar and VLIW processors makes this approach especially attractive. text/html en_US Journal of Universal Computer Science High-radix on-line arithmetic precision accurate reliable credible super-scaler VLIW. A High Radix On-line Arithmetic for Credible and Accurate Computing Research Article

10.3217/jucs-001-07-0454 1995-07-28 jucs

Laboratoire MASI-IBP, URA-818 du CNRS, Université Pierre et Marie Curie, 4 place Jussieu, Paris, France author Asserrhine, Jalil Laboratoire MASI-IBP, URA-818 du CNRS, Université Pierre et Marie Curie, 4 place Jussieu, Paris, France author Chesneaux, Jean-Marie Laboratoire MASI-IBP, URA-818 du CNRS, Université Pierre et Marie Curie, 4 place Jussieu, Paris, France author Lamotte, Jean-Luc 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 454 468 1995 10.3217/jucs-001-07-0454 https://lib.jucs.org/article/27138/ https://lib.jucs.org/article/27138/download/pdf/ https://lib.jucs.org/article/27138/download/xml/ Numerical validation of computed results in scientific computation is always an essential problem as well on sequential architecture as on parallel architecture. The probabilistic approach is the only one that allows to estimate the round-off error propagation of the floating point arithmetic on computers. We begin by recalling the basics of the CESTAC method (Controle et Estimation Stochastique des Arrondis de Calculs). Then, the use of the CADNA software (Control of Accuracy and Debugging For Numerical Applications) is presented for numerical validation on sequential architecture. On parallel architecture, we present two solutions for the control of round-off errors. The first one is the combination of CADNA and the PVM library. This solution allows to control round-off errors of parallel codes with the same architecture. It does not need more processors than the classical parallel code. The second solution is represented by the RAPP prototype. In this approach, the CESTAC method is directly parallelized. It works both on sequential and parallel programs. The essential difference is that this solution requires more processors than the classical codes. These different approaches are tested on sequential and parallel programs of multiplication of matrices. text/html en_US Journal of Universal Computer Science Estimation of Round-off Errors on Several Computers Architectures Research Article

10.3217/jucs-001-07-0469 1995-07-28 jucs

Université Pierre et Marie Curie, France author Jézéquel, Fabienne 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 469 483 1995 10.3217/jucs-001-07-0469 https://lib.jucs.org/article/27140/ https://lib.jucs.org/article/27140/download/pdf/ https://lib.jucs.org/article/27140/download/xml/ The effect of round-off errors on the numerical solution of the heat equation by finite differences can be theoretically determined by computing the mean error at each time step. The floating point error propagation is then theoretically time linear. The experimental simulations agree with this result for the towards zero rounding arithmetic. However the results are not so good for the rounding to the nearest artihmetic. The theoretical formulas provide an approximation of the experimental round-off errors. In these formulas the mean value of the assignment operator is used, and consequently, their reliability depends on the arithmetic used. text/html en_US Journal of Universal Computer Science Floating point arithmetic numerical error propagation partial differential equations finite difference methods Round-off Error Propagation in the Solution of the Heat Equation by finite Differences Research Article

10.3217/jucs-001-07-0484 1995-07-28 jucs

Dept. of Mathematics and Computer Science, Odense University, Odense, Denmark author Kornerup, Peter Dept. of Computer Science and Engineering, Southern Methodist University, Dallas, TX, United States of America author Matula, David 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 484 503 1995 10.3217/jucs-001-07-0484 https://lib.jucs.org/article/27141/ https://lib.jucs.org/article/27141/download/pdf/ https://lib.jucs.org/article/27141/download/xml/ A binary representation of the rationals derived from their continued fraction expansions is described and analysed. The concepts "adjacency", "mediant" and "convergent" from the literature on Farey fractions and continued fractions are suitably extended to provide a foundation for this new binary representation system. Worst case representation-induced precision loss for any real number by a fixed length representable number of the system is shown to be at most 19% of bit word length, with no precision loss whatsoever induced in the representation of any reasonably sized rational number. The representation is supported by a computer arithmetic system implementing exact rational and approximate real computations in an on-line fashion. text/html en_US Journal of Universal Computer Science Computer arithmetic continued fractions lexicographic number systems number theory rational numbers. LCF: A Lexicographic Binary Representation of the Rationals Research Article

10.3217/jucs-001-07-0504 1995-07-28 jucs

Functional Programming Group, Department of Computer Science, Manchester University, Manchester, United Kingdom author Lester, David 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 504 513 1995 10.3217/jucs-001-07-0504 https://lib.jucs.org/article/27143/ https://lib.jucs.org/article/27143/download/pdf/ https://lib.jucs.org/article/27143/download/xml/ In this paper we investigate an extension to Vuillemin's work on continued fraction arithmetic [Vuillemin 87, Vuillemin 88, Vuillemin 90], that permits it to evaluate the standard statistical distribution functions. By this we mean: the normal distribution, the -distribution, the t-distribution, and, in particular, the F-distribution. The underlying representation of non-rational computable real numbers is also as continued fractions, in the style of Vuillemin. This permits arbitrary accuracy over a range of values. The number of terms of a continued fraction that are used by the implementation is dynamically controlled by the accuracy demanded of the final answer. The use of a modern lazy functional language - Haskell - has considerably eased the programming task. Two features are of note. Firstly, the type-class structure allows one to augment the varieties of numbers supported by the language. Secondly, the laziness inherent in the Haskell's semantics, makes it very straightforward to dynamically control the accuracy of the intermediate evaluations. text/html en_US Journal of Universal Computer Science Exact Statistics and Continued Fractions Research Article

10.3217/jucs-001-07-0514 1995-07-28 jucs

Bulgarian Academy of Sciences, Bulgaria author Markov, Svetoslav 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 514 526 1995 10.3217/jucs-001-07-0514 https://lib.jucs.org/article/27145/ https://lib.jucs.org/article/27145/download/pdf/ https://lib.jucs.org/article/27145/download/xml/ We discuss two closely related interval arithmetic systems: i) the of directed (generalized) intervals studied by E. Kaucher, and ii) the syste intervals together with the outer and inner interval operations. A relation two systems becomes feasible due to introduction of special notations and a normal form of directed intervals. As an application, it has been shown that interval systems can be used for the computation of tight inner and outer in of ranges of functions and consequently for the development of software for computation of ranges of functions. text/html en_US Journal of Universal Computer Science computer arithmetic error analysis interval algebraic manipulation On Directed Interval Arithmetic and its Applications Research Article

10.3217/jucs-001-07-0527 1995-07-28 jucs

Dept. of Mathematics and Computer Science, Odense University, Odense, Denmark author Nielsen, Asger Dept. of Mathematics and Computer Science, Odense University, Odense, Denmark author Kornerup, Peter 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 527 547 1995 10.3217/jucs-001-07-0527 https://lib.jucs.org/article/27146/ https://lib.jucs.org/article/27146/download/pdf/ https://lib.jucs.org/article/27146/download/xml/ We develop a formal account of digit serial number representations by describing them as strings from a language. A prefix of a string represents an int erval approximating a number by enclosure. Standard on-line representations are shown to be a special case of the general digit serial representations. Matrices are introd uced as representations of intervals and a finite-state transducer is used for mapping str ings into intervals. Homographic and bi-homographic functions are used for representing basi c arithmetic operations on digit serial numbers, and finally a digit serial represen tation of floating point numbers is introduced. 1.) This work has been supported by The Danish Research Councils under the grant no.5.21.08.02. text/html en_US Journal of Universal Computer Science Computer Arithmetic On-line Computation Number Representations Redundant Digit sets Continued Fractions Intervals MSB-First Digit Serial Arithmetic Research Article

10.3217/jucs-001-07-0548 1995-07-28 jucs

LIMI, Université de Bretagne Occidentale, Brest, France author Pavec, Raymond 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 548 559 1995 10.3217/jucs-001-07-0548 https://lib.jucs.org/article/27147/ https://lib.jucs.org/article/27147/download/pdf/ https://lib.jucs.org/article/27147/download/xml/ Three algorithms providing rigourous bounds for the eigenvalues of a real matrix are presented. The first is an implementation of the bisection algorithm for a symmetric tridiagonal matrix using IEEE floating-point arithmetic. The two others use interval arithmetic with directed rounding and are deduced from the Jacobi method for a symmetric matrix and the Jacobi-like method of Eberlein for an unsymmetric matrix. text/html en_US Journal of Universal Computer Science Some Algorithms Providing Rigorous Bounds for the Eigenvalues of a Matrix Research Article

10.3217/jucs-001-07-0560 1995-07-28 jucs

Bulgarian Academy of Sciences, Bulgaria author Popova, Evgenija 1995-07-28 1995-07-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 560 569 1995 10.3217/jucs-001-07-0560 https://lib.jucs.org/article/27148/ https://lib.jucs.org/article/27148/download/pdf/ https://lib.jucs.org/article/27148/download/xml/ IEEE floating-point arithmetic standards 754 and 854 reflect the present state of the art in designing and implementing floating-point arithmetic units. A formalism applied to a standard non-trapping mode floating-point system shows incorrectness of some numeric and non-numeric results. A software emulation of decimal floating-point computer arithmetic supporting an enhanced set of exception symbols is reported. Some implementation details, discussion of some open questions about utility and consistency of the implemented arithmetic with the IEEE Standards are provided. The potential benefit for computations with infinite symbolic elements is outlined. text/html en_US Journal of Universal Computer Science computer arithmetic implementation IEEE standards exception handling On a Formally Correct Implementation of IEEE Computer Arithmetic Research Article

10.3217/jucs-001-08 1995-08-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-08-28 1995-08-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 570 570 1995 10.3217/jucs-001-08 https://lib.jucs.org/article/27150/ https://lib.jucs.org/article/27150/download/pdf/ https://lib.jucs.org/article/27150/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-08-0571 1995-08-28 jucs

Rose-Hulman Institute of Technology, author Carlson, Patricia 1995-08-28 1995-08-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 571 590 1995 10.3217/jucs-001-08-0571 https://lib.jucs.org/article/27151/ https://lib.jucs.org/article/27151/download/pdf/ https://lib.jucs.org/article/27151/download/xml/ This paper describes a work-in-progress: a computerized learning environment for teaching the conceptual patterns of scientific reasoning. BROCA (Basic Research, Observations, Critical Analysis) is theory-driven, combining two very powerful conceptual models of thinking. The first -- drawn from cognitive psychology and information theory -- focuses on the mental manipulations by which data becomes information and information becomes knowledge. The second theoretical construct comes from rhetoric and describes the intellectual activities carried out in prewriting, drafting, and revision by an expert writing. As an interactive "cognitive tool," BROCA provides scaffolding (through visual algorithms and adaptive prompting) to help a fledgling thinker practice the robust patterns of scientific reasoning. text/html en_US Journal of Universal Computer Science Computers and Education Computer Uses in Education BROCA : A Computerized Environment for Mediating Scientific Reasoning through Writing Research Article

10.3217/jucs-001-08-0591 1995-08-28 jucs

Department of Computer Science, The University of Auckland, Auckland, New Zealand author Fenwick, Peter 1995-08-28 1995-08-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 591 602 1995 10.3217/jucs-001-08-0591 https://lib.jucs.org/article/27152/ https://lib.jucs.org/article/27152/download/pdf/ https://lib.jucs.org/article/27152/download/xml/ We describe a novel text compressor which combines Ziv-Lempel compression and arithmetic coding with a form of vector quantisation. The resulting compressor resembles an LZ-77 compressor, but with no explicit phrase lengths or coding for literans. An examination of the limitations on its performance leads to some predictions of the limits of LZ-77 compression in general, showing that the LZ-77 text compression technique is already very close to the limits of its performance. text/html en_US Journal of Universal Computer Science text compression LZ-77 arithmetic coding vector quantisation Differential Ziv-Lempel Text Compression Research Article

10.3217/jucs-001-08-0603 1995-08-28 jucs

University of Bucharest, Faculty of Mathematics, Romania, Bucharest, Romania author Panaitopol, Laurentiu University of Bucharest, Bucharest, Romania author Ştefănescu, Doru 1995-08-28 1995-08-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 603 613 1995 10.3217/jucs-001-08-0603 https://lib.jucs.org/article/27153/ https://lib.jucs.org/article/27153/download/pdf/ https://lib.jucs.org/article/27153/download/xml/ We describe new methods for the estimation of the bounds of the coefficients of proper divisors of integer polynomials in one variable. There exist classes of poly-nomials for which our estimates are better than those obtained using the polynomial measure or the 2-weighted norm. text/html en_US Journal of Universal Computer Science Bounds for Heights of Integer Polynomial Factors Research Article

10.3217/jucs-001-08-0614 1995-08-28 jucs

Institute for Computer Graphics, Technical University of Graz, Graz, Austria author Pinz, Axel Institute for Computer Graphics, Technical University of Graz, Graz, Austria author Prantl, Manfred Institute for Computer Graphics, Technical University of Graz, Graz, Austria author Ganster, Harald 1995-08-28 1995-08-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 614 631 1995 10.3217/jucs-001-08-0614 https://lib.jucs.org/article/27154/ https://lib.jucs.org/article/27154/download/pdf/ https://lib.jucs.org/article/27154/download/xml/ We describe a robust method for spatial registration, which relies on the coarse correspondence of structures extracted from images, avoiding the establishment of point correspondences. These structures (tokens) are points, chains, polygons and regions at the level of intermediate symbolic representation (ISR). The algorithm recovers conformal transformations (4 affine parameters), so that 2-dimensional scenes as well as planar structures in 3D scenes can be handled. The affine transformation between two different tokensets is found by minimization of an exponentially decreasing distance function. As long as the tokensets are kept sparse, the method is very robust against a broad variety of common disturbances (e.g. incomplete segmentations, missing tokens, partial overlap). The performance of the algorithm is demonstrated using simple 2D shapes, medical, and remote sensing satellite images. The complexity of the algorithm is quadratic on the number of affine parameters. text/html en_US Journal of Universal Computer Science Affine Matching Spatial Registration Information Fusion Image Understanding A Robust Affine Matching Algorithm Using an Exponentially Decreasing Distance Function Research Article

10.3217/jucs-001-09 1995-09-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-09-28 1995-09-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 632 632 1995 10.3217/jucs-001-09 https://lib.jucs.org/article/27157/ https://lib.jucs.org/article/27157/download/pdf/ https://lib.jucs.org/article/27157/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-09-0633 1995-09-28 jucs

Indian Institute of Technology, Madras, India, Madras, India author Aranha, R. F. M. Indian Institute of Technology, Madras, India, Madras, India author Rangan, C. 1995-09-28 1995-09-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 633 651 1995 10.3217/jucs-001-09-0633 https://lib.jucs.org/article/27158/ https://lib.jucs.org/article/27158/download/pdf/ https://lib.jucs.org/article/27158/download/xml/ Given a biconnected network G with n nodes and a specific edge (r, s) of G, the st-numbering problem asks for an assignment of integers to the nodes satisfying the following condition: r is assigned the number 1 and s is assigned the number n and all other nodes are assigned numbers in such a way that every node (other than r and s) has a neighbour with smaller st-number and a neighbour with larger st-number. Since st-numbering exists iff G is biconnected, it serves as a powerful "local characterization" of the "global" property of the network. We present an efficient O(e) message complexity and O(n) time complexity algorithm for st-numbering a biconnected graph. text/html en_US Journal of Universal Computer Science Distributed graph algorithms st-numbering biconnected graph An Efficient Distributed Algorithm For st-numbering the Vertices of a Biconnected Graph Research Article

10.3217/jucs-001-09-0652 1995-09-28 jucs

Department of Mathematics University of Turku and Turku Centre for Computer Science (TUCS), Turku, Finland author Honkala, Juha 1995-09-28 1995-09-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 652 657 1995 10.3217/jucs-001-09-0652 https://lib.jucs.org/article/27163/ https://lib.jucs.org/article/27163/download/pdf/ https://lib.jucs.org/article/27163/download/xml/ We show that it is decidable, given a number system N, whether or not there is an unambiguous number system equivalent to N. text/html en_US Journal of Universal Computer Science A Decision Method for the Unambiguity of Sets Defined by Number Systems Research Article

10.3217/jucs-001-09-0658 1995-09-28 jucs

Institut National Polytechnique de Grenoble, France author Wang, Dongming 1995-09-28 1995-09-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 658 673 1995 10.3217/jucs-001-09-0658 https://lib.jucs.org/article/27164/ https://lib.jucs.org/article/27164/download/pdf/ https://lib.jucs.org/article/27164/download/xml/ A zero decomposition algorithm is presented and used to devise a method for proving theorems automatically in differential geometry and mechanics. The method has been implemented and its practical efficiency is demonstrated by several non-trivial examples including Bertrand s theorem, Schell s theorem and Kepler-Newton s laws. text/html en_US Journal of Universal Computer Science Differential geometry mechanics polynomial elimination theorem proving triangular system zero decomposition A Method for Proving Theorems in Differential Geometry and Mechanics Research Article

10.3217/jucs-001-10 1995-10-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-10-28 1995-10-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 674 674 1995 10.3217/jucs-001-10 https://lib.jucs.org/article/27165/ https://lib.jucs.org/article/27165/download/pdf/ https://lib.jucs.org/article/27165/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-10-0675 1995-10-28 jucs

Department of Computer Science, University of South Carolina, Columbia, SC, United States of America author Ii., Karel Iterated Systems, Inc., Atlanta, GA, United States of America author Kari, Jarkko 1995-10-28 1995-10-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 675 686 1995 10.3217/jucs-001-10-0675 https://lib.jucs.org/article/27167/ https://lib.jucs.org/article/27167/download/pdf/ https://lib.jucs.org/article/27167/download/xml/ We introduce Wang cubes with colored faces that are a generalization of Wang tiles with colored edges. We show that there exists an aperiodic set of 21 Wang cubes, that is, a set for which there exists a tiling of the whole space with matching unit cubes but there exists no periodic tiling. We use the aperiodic set of 13 Wang tiles recently obtained by the first author using the new method developed by the second. Our method can be used to construct an aperiodic set of n-dimensional cubes for any n 3. text/html en_US Journal of Universal Computer Science discrete mathematics automata theory aperiodic tilings Wang tiles Wang cubes sequential machines An Aperiodic Set of Wang Cubes Research Article

10.3217/jucs-001-10-0687 1995-10-28 jucs

Departement Computerwetenschappen, Katholieke Universiteit Leuven, Belgium author Duval, Erik Departement Computerwetenschappen, K.U.Leuven Celestijnenlaan 200 A, Heverlee, Belgium author Olivié, Henk IICM, Graz University of Technology, Graz, Austria author Scherbakov, Nick 1995-10-28 1995-10-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 687 705 1995 10.3217/jucs-001-10-0687 https://lib.jucs.org/article/27170/ https://lib.jucs.org/article/27170/download/pdf/ https://lib.jucs.org/article/27170/download/xml/ We propose a new hypermedia data model, called CHM for Contained HyperMedia. Our model is based on set-oriented data structuring, with a strong emphasis on automatic maintenance of link integrity. In this paper, the CHM model is presented in detail: both data structuring, navigational facilities and authoring support are presented. We will also explain how we have integrated support for the CHM model in Home, our Hypermedia Object Management Environment, publicly accessible through the World-Wide Web. text/html en_US Journal of Universal Computer Science hypermedia data modeling automatic link maintenance Contained Hypermedia Research Article

10.3217/jucs-001-10-0706 1995-10-28 jucs

University of Freiburg, Germany author Ottmann, Thomas Institut fuer Informatik, Universitaet Freiburg, Germany author Bacher, Ch. 1995-10-28 1995-10-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 706 717 1995 10.3217/jucs-001-10-0706 https://lib.jucs.org/article/27174/ https://lib.jucs.org/article/27174/download/pdf/ https://lib.jucs.org/article/27174/download/xml/ We report about a new way of producing hypermedia documents for supporting teaching at universities. A computer held lecture is automatically converted into the core of a multimedia document and linked together with papers, textbooks, animations and simulations. As an electronic substitute of the blackboard we have used the whiteboard wb of the Mbone toolset and have transmitted the lecture also to remote locations. Our experiments demonstrate that classroom lecturing, distance teaching, and the production of educational hypermedia can be successfully integrated. text/html en_US Journal of Universal Computer Science electronic courseware hypermedia whiteboard distance teaching Authoring on the Fly Research Article

10.3217/jucs-001-11 1995-11-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-11-28 1995-11-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 718 718 1995 10.3217/jucs-001-11 https://lib.jucs.org/article/27179/ https://lib.jucs.org/article/27179/download/pdf/ https://lib.jucs.org/article/27179/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-11-0719 1995-11-28 jucs

IICM, Graz University of Technology, Austria author Maurer, Hermann The University of Auckland, Auckland, New Zealand author Lennon, Jennifer 1995-11-28 1995-11-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 719 727 1995 10.3217/jucs-001-11-0719 https://lib.jucs.org/article/27180/ https://lib.jucs.org/article/27180/download/pdf/ https://lib.jucs.org/article/27180/download/xml/ For 30 years repeated attempts have been made to use computers to support the teaching and learning process, albeit with only moderate success. Whenever major attempts failed, some seemingly convincing reasons were presented the for less than satisfactory results. In the early days cost or even lack of suitable equipment was blamed, after colour graphics computers started to be widespread, production costs of interactive and graphically appealing material were considered the main culprits, when modern multimedia authoring techniques did not change the situation either, the lack of personalized feed-back, of network support and the difficulty of producing high quality simulations were seen as main obstacles. With networks now offering excellent multimedia presentation and communication facilities the final breakthrough of computers as ultimate teaching and learning tool is (once more) predicted. And once more results will be disappointing if one crucial component is again overlooked: good courseware must give both guidance to students but also provide a rich variety of background material whenever such is needed. It is the main claim of this paper that the advent of sizeable digital libraries provides one of the most significant chances for computer based training ever. We will argue that such libraries not only allow the efficient production of courseware but also provide the extensive background reservoir of material needed in many situations. text/html en_US Journal of Universal Computer Science Digital libraries electronic libraries learning support teaching support instructional technology CAI CBT Digital Libraries as Learning and Teaching Support Research Article

10.3217/jucs-001-11-0728 1995-11-28 jucs

IAIK, Graz University of Technology, Austria author Mayerwieser, Wolfgang IAIK, Graz University of Technology, Austria author Posch, Karl Institute for Applied Information Processing and Communications, Graz University of Technology, Graz, Austria author Posch, Reinhard IAIK, Graz University of Technology, Austria author Schindler, Volker 1995-11-28 1995-11-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 728 743 1995 10.3217/jucs-001-11-0728 https://lib.jucs.org/article/27185/ https://lib.jucs.org/article/27185/download/pdf/ https://lib.jucs.org/article/27185/download/xml/ High speed devices for public key cryptography are of emerging interest. For this reason, the crypto chip was designed. It is an architecture capable of performing fast RSA encryption and other cryptographic algorithms based on modulo multiplication. Besides the modulo multiplication algorithm called FastMM, the reasons for its high computation speed are the As Parallel As Possible (APAP) architecture, as well as the high operation frequency. The crypto chip also contains on-chip RAM and a special-purpose control logic, enabling special features like encrypted key loading. However, this control mechanism influences to some extend testability of the MM data path which is the heart of the chip. For this reason, the crypto chip has been designed to be able to evaluate the behaviour of the pure MM data path. In the following, we describe the strategies used with the crypto chip for testing the MM data path under realistical conditions. In this context, analyzing control signal flow turns out to be the key action.This work has been sponsored as part of the project Nr. P9384PHY "Sichere Kommunikation bei hohen Geschwindigkeiten" by the Austrian Science Foundation. text/html en_US Journal of Universal Computer Science high speed multipliers hardware algorithms design for testability public key cryptography Testing a High-Speed Data Path The Design of the RSAb Crypto Chip Research Article

10.3217/jucs-001-11-0744 1995-11-28 jucs

author Pam, Andrew Institute for Applied Computer Science I, University of Hagen, Germany author Vermeer, Arnould 1995-11-28 1995-11-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 744 750 1995 10.3217/jucs-001-11-0744 https://lib.jucs.org/article/27188/ https://lib.jucs.org/article/27188/download/pdf/ https://lib.jucs.org/article/27188/download/xml/ In this paper we attempt to compare features of WWW and Hyper-G, the first fully operable networked multimedia system that goes much beyond WWW and incorporates many features first proposed in Xanadu and later partially tested in systems such as Intermedia. text/html en_US Journal of Universal Computer Science Hypermedia Hyper-G WWW Xanadu networked information systems Internet A Comparison of WWW and Hyper-G Research Article

10.3217/jucs-001-12 1995-12-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1995-12-28 1995-12-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 751 751 1995 10.3217/jucs-001-12 https://lib.jucs.org/article/27190/ https://lib.jucs.org/article/27190/download/pdf/ https://lib.jucs.org/article/27190/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-001-12-0752 1995-12-28 jucs

Institute for Theoretical Computer Science, Graz University of Technology, Graz, Austria author Aichholzer, Oswin Graz University of Technology, Graz, Austria author Aurenhammer, Franz Institut für Informatik, Freie Universität Berlin, Berlin, Germany author Alberts, David Institut für Informatik, Freie Universität Berlin, Berlin, Germany author Gärtner, Bernd 1995-12-28 1995-12-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 752 761 1995 10.3217/jucs-001-12-0752 https://lib.jucs.org/article/27191/ https://lib.jucs.org/article/27191/download/pdf/ https://lib.jucs.org/article/27191/download/xml/ A new internal structure for simple polygons, the straight skeleton, is introduced and discussed. It is composed of pieces of angular bisectores which partition the interior of a given n-gon P in a tree-like fashion into n monotone polygons. Its straight-line structure and its lower combinatorial complexity may make the straight skeleton preferable to the widely used medial axis of a polygon. As a seemingly unrelated application, the straight skeleton provides a canonical way of constructing a polygonal roof above a general layout of ground walls. text/html en_US Journal of Universal Computer Science Simple polygon angular bisectors internal skeleton roof construction A Novel Type of Skeleton for Polygons Research Article

10.3217/jucs-001-12-0762 1995-12-28 jucs

Rank Xerox Research Centre, Meylan, France author Andreoli, Jean-Marc Rank Xerox Research Centre, Meylan, France author Borghoff, Uwe Rank Xerox Research Centre, Meylan, France author Pareschi, Remo Institut fuer Informatik, Technische Universitaet Muenchen, Muenchen, Germany author Schlichter, Johann 1995-12-28 1995-12-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 762 789 1995 10.3217/jucs-001-12-0762 https://lib.jucs.org/article/27192/ https://lib.jucs.org/article/27192/download/pdf/ https://lib.jucs.org/article/27192/download/xml/ We propose constraints as the appropriate computational constructs for the design of agents with the task of selecting, merging and managing electronic information coming from such services as Internet access, digital libraries, E-mail, or on-line information repositories. Specifically, we introduce the framework of Constraint-Based Knowledge Brokers, which are concurrent agents that use so-called signed feature constraints to represent partially specified information and can flexibly cooperate in the management of distributed knowledge. We illustrate our approach by several examples, and we define application scenarios based on related technology such as Telescript and workflow management systems. text/html en_US Journal of Universal Computer Science multiagent coordination agent-interaction distributed problem solving signed feature constraints negotiation cooperation strategies. Constraint Agents for the Information Age Research Article

10.3217/jucs-001-12-0790 1995-12-28 jucs

Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland author Mateescu, Alexandru Institute of Mathematics of the Romanian Academy, Bucharest, Romania author Paun, Gheorghe University of Leiden, Department of Computer Science, Netherlands author Rozenberg, Grzegorz Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland author Salomaa, Arto 1995-12-28 1995-12-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 790 810 1995 10.3217/jucs-001-12-0790 https://lib.jucs.org/article/27197/ https://lib.jucs.org/article/27197/download/pdf/ https://lib.jucs.org/article/27197/download/xml/ An n-dimensional vector of natural numbers is said to be prime if the greatest common divisor of its components is one. A word is said to be Parikh prime if its Parikh vector is prime. The languages of Parikh prime and of Parikh non-prime words are investigated (they are neither semilinear nor slender, hence are not context-free or D0L languages, both of them can be generated by matrix grammars with appearance checking). Marking in the plane the points identified by prime (2-dimensional) vectors, interesting patterns of non-marked ("free") points appear (they are similar to the territories in the game of GO). The shape of such possible territories is investigated (with an exhaustive analysis of tro-, tetro-, pento- and hexominoes). Some open problems are formulated (both concerning the mentioned languages and the "GO territories theory"). 1.) Research supported by the Academy of Finland, project 11281, and the ESPRIT Basic Research Working Group ASMICS II. text/html en_US Journal of Universal Computer Science formal languages context free languages L-systems Parikh mapping word problems Parikh Prime Words and GO-like Territories Research Article

10.3217/jucs-001-12-0811 1995-12-28 jucs

ITI, Graz University of Technology, Austria author Platzner, Marco ITI, Graz University of Technology, Austria author Rinner, Bernhard ITI, Graz University of Technology, Austria author Weiss, Reinhold 1995-12-28 1995-12-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 811 820 1995 10.3217/jucs-001-12-0811 https://lib.jucs.org/article/27198/ https://lib.jucs.org/article/27198/download/pdf/ https://lib.jucs.org/article/27198/download/xml/ Constraint satisfaction is very common in many artificial intelligence applications. This paper presents results from parallelizing constraint satisfaction in a special application --- the algorithm for qualitative simulation QSim [Kuipers 94]. A parallel-agent based strategy (PAB) is used to solve the constraint satisfaction problem (CSP). Two essential steps of PAB are studied in more detail to achieve a good performance of the parallel algorithm. Partitioning heuristics to generate independent parts of the overall search space are investigated. Sequential CSP algorithms are compared in order to reveal the most efficient one for QSim. The evaluation of these heuristics and algorithms is based on runtime measurements using CSPs traced from QSim. These runtimes allow a best- and worst-case estimation of the expected speedup of the parallel algorithms. The comparison of sequential CSP algorithms leads to following strategy for solving partitioned problems. Less complex problems are solved with simple backtracking, and more complex models are solved with graph-directed backjumping (GBJ). text/html en_US Journal of Universal Computer Science Parallel constraint satisfaction QSim distributed AI Exploiting Parallelism in Constraint Satisfaction for Qualitative Simulation Research Article

10.3217/jucs-001-12-0821 1995-12-28 jucs

author Stefanescu, Calina 1995-12-28 1995-12-28 1995 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 1 821 827 1995 10.3217/jucs-001-12-0821 https://lib.jucs.org/article/27200/ https://lib.jucs.org/article/27200/download/pdf/ https://lib.jucs.org/article/27200/download/xml/ We describe a Markov process which models the sequential allocation for two adjacent tables coexisting in memory by growing towards each other. The tables are expected to fill at the same rate, random deletions and insertions are allowed. 1.) 1991 Mathematics Subject Classification. Primary 60J20, Secondary 62M05, 68P05. text/html en_US Journal of Universal Computer Science A Markov Process for Sequential Allocation Research Article

10.3217/jucs-002-01 1996-01-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1996-01-28 1996-01-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 1 1 1 1996 10.3217/jucs-002-01 https://lib.jucs.org/article/27202/ https://lib.jucs.org/article/27202/download/pdf/ https://lib.jucs.org/article/27202/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-002-01-0002 1996-01-28 jucs

Computer Science Department, Technion, Haifa, Israel author Brit, Hagit Computer Science Department, Technion, Haifa, Israel author Moran, Shlomo 1996-01-28 1996-01-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 1 2 19 1996 10.3217/jucs-002-01-0002 https://lib.jucs.org/article/27203/ https://lib.jucs.org/article/27203/download/pdf/ https://lib.jucs.org/article/27203/download/xml/ In this paper we define and study public data structures, which are concurrent data structures in the shared memory environment, which enable access to an unknown (and possibly infinite) set of identical processes. Specific cases of such data structures (like counting networks and concurrent counters) have been studied recently, and such data structures seem to model concurrent systems like client-server applications, in which the identities of the clients, and sometimes also their number, are not known apriori. Specifically, we study the relation between wait-free and bounded wait-free public data structures - the former guarantees that every operation performed on the data structure always terminates, regardless of the relative speed of the processes, the latter guarantees that every such operation is terminated within a fixed number of steps. We present an example of a public data structure which is wait-free but not bounded wait-free, and then we show that if all the concurrent objects of the data structure are periodic, then wait-freedom implies bounded wait-freedom. text/html en_US Journal of Universal Computer Science Wait-Freedom vs. Bounded Wait Freedom in Public Data Structures Research Article

10.3217/jucs-002-01-0020 1996-01-28 jucs

IAIK, Graz University of Technology, Austria author Pucher, Franz IAIK, Graz University of Technology, Austria author Leitold, Herbert Institute for Applied Information Processing and Communications, Graz University of Technology, Graz, Austria author Posch, Reinhard 1996-01-28 1996-01-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 1 20 33 1996 10.3217/jucs-002-01-0020 https://lib.jucs.org/article/27205/ https://lib.jucs.org/article/27205/download/pdf/ https://lib.jucs.org/article/27205/download/xml/ This paper describes local area network (LAN) access using public wide area data networks and problems that arise when using integrated services digital network (ISDN) technology [Stallings 90] [Thachenkary 93]. To date mainly modem connections at serial lines with a terminal port have been the standard remote access technique. With ISDN it is foreseen that these modem lines will be replaced rather soon. This is mainly due to the fact that ISDN offers a more adequate bandwidth and is much more consistent from the point of view of access and embedding. This paper demonstrates in the main section a router-based solution for enhanced call management. One of the main advantages is the separation of the strategic module which defines the behavior and thus allows for a number of active connections exceeding the number of ports. It also addresses traffic and access control in the network environment. text/html en_US Journal of Universal Computer Science LAN Access Over ISDN Research Article

10.3217/jucs-002-01-0034 1996-01-28 jucs

University of Dortmund, Department of Computer Science, Dortmund, Germany author Tochtermann, Klaus University of Dortmund, Department of Computer Science, Dortmund, Germany author Dittrich, Gisbert 1996-01-28 1996-01-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 1 34 56 1996 10.3217/jucs-002-01-0034 https://lib.jucs.org/article/27206/ https://lib.jucs.org/article/27206/download/pdf/ https://lib.jucs.org/article/27206/download/xml/ This paper presents the Dortmund Family of Hypermedia Models (DFHM). Existing formal models for hypermedia mostly lack the flexibility and adaptability and, often not more than one existing system conforms to such a model. The DFHM overcomes this drawback by means of optional and alternative data types. The conformance of a hypermedia system to the DFHM can be conditionalised upon one member of the family. The DFHM has been formalised in VDM, but the aim of this paper is to give an informal overview of the main concepts. Therefore, any formalisms are omitted here. The first part of the paper deals with hypermedia fundamentals from a conceptual perspective. Apart from basic concepts, e.g. nodes and links, also structuring concepts, e.g. views, folders and others, are discussed in detail. Some examples are given to convey how models for existing hypermedia systems can be derived from the DFHM. The second part demonstrates the power of these concepts by introducing main features of a hypermedia system that has been developed for the use in educational settings. This hypermedia system bases upon a member of the DFHM. text/html en_US Journal of Universal Computer Science hypermedia hypermedia model hypermedia system hypermedia structuring The Dortmund Family of Hypermedia Models - Concepts and their Application Research Article

10.3217/jucs-002-02 1996-02-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1996-02-28 1996-02-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 57 58 1996 10.3217/jucs-002-02 https://lib.jucs.org/article/27209/ https://lib.jucs.org/article/27209/download/pdf/ https://lib.jucs.org/article/27209/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-002-02-0058 1996-02-28 jucs

Research Group for Mathematical Modelling in Biology, Institute of Biophysics, Bulgarian Academy of Sciences, Sofia, Bulgaria author Markov, Svetoslav Mathematics Department, Bosphorus University, Istanbul, author Akyildiz, Y. 1996-02-28 1996-02-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 59 69 1996 10.3217/jucs-002-02-0058 https://lib.jucs.org/article/27210/ https://lib.jucs.org/article/27210/download/pdf/ https://lib.jucs.org/article/27210/download/xml/ This paper is devoted to the software implementation of two mathematical methods which are often used in biological applications: interpolation and curve fitting in the presence of uncertainties in the input data given in the form of intervals. The methods involve model functions linear in their parameters and are formulated by means of simple expressions in terms of interval arithmetic allowing the computation of verified bounds for the interpolating/approximating functions. The methods are demonstrated for certain classes of nonlinear modelling functions finding applications in biology. A case study involving enzyme-catalysed reaction is considered. The numerical results are performed in the computer algebra system Mathematica, which supports interval-arithmetic computations. text/html en_US Journal of Universal Computer Science Interpolation least squares approximation verification model validation algebraic manipulations computer algebra systems enzyme kinetics uncertainties interval arithmetic Curve Fitting and Interpolation of Biological Data Under Uncertainties Research Article

10.3217/jucs-002-02-0070 1996-02-28 jucs

Institute of Control and System Research, Bulgarian Academy of Sciences, Sofia, Bulgaria author Andreeva, Plamena 1996-02-28 1996-02-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 70 76 1996 10.3217/jucs-002-02-0070 https://lib.jucs.org/article/27214/ https://lib.jucs.org/article/27214/download/pdf/ https://lib.jucs.org/article/27214/download/xml/ The inexact information system is based on linguistic terms which have values lying in the interval [0,1]. Imprecision has advantages, because fuzzy sets avoid the rigidity of conventional mathematical reasoning and computer programming. Fuzzy quantifiers are made explicit by means of fuzzy logic. Many systems, for example, complex biological processes, cannot be programmed in a precise way. With fuzzy sets the implicit quantifiers can be easily translated into machine usable form. This paper discusses a method for the description of fuzzy quantifiers in formal languages. A comparison between approximate reasoning and the method of linear interpolation is made. Inexact information in biological and medical expert systems, and the reliability inferences based on it, are also discussed. text/html en_US Journal of Universal Computer Science Linguistic approach fuzzy implication fuzzy quantifier fuzzy number approximate reasoning information system. Inexact Information Systems and its Application to Approximate Reasoning Research Article

10.3217/jucs-002-02-0077 1996-02-28 jucs

IRISA, Campus de Beaulieu, France author Lavenier, Dominique 1996-02-28 1996-02-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 77 86 1996 10.3217/jucs-002-02-0077 https://lib.jucs.org/article/27219/ https://lib.jucs.org/article/27219/download/pdf/ https://lib.jucs.org/article/27219/download/xml/ Biological sequence comparison is a time consuming task on a Von Neuman computer. The addition of dedicated hardware for parallelizing the comparison algorithms results in a reduction of several orders of magnitude in the execution time. This paper presents and compares different dedicated approaches, based on the parallelization of the algorithms on linear arrays of processors. text/html en_US Journal of Universal Computer Science Hardware Biological Sequence Comparison DNA FPGA VLSI Dedicated Hardware for Biological Sequence Comparison Research Article

10.3217/jucs-002-02-0087 1996-02-28 jucs

Department of Chemistry & Centre for Scientific Computation, Trinity College, University of Dublin, Ireland author Dónaill, Dónall A. Mac 1996-02-28 1996-02-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 87 95 1996 10.3217/jucs-002-02-0087 https://lib.jucs.org/article/27220/ https://lib.jucs.org/article/27220/download/pdf/ https://lib.jucs.org/article/27220/download/xml/ A molecular computational procedure in which manipulation of DNA strands may be harnessed to solve a classical problem in NP - the directed Hamiltonian path problem - was recently proposed [Adleman 1994], [Gifford 1994]. The procedure is in effect a massively parallel chemical analog computer and has a computational capacity corresponding to approximately CPU years on a typical 10 MFLOP workstation. In this paper limitations on the potential scalability of molecular computation are considered. A simple analysis of the time complexity function shows that the potential of molecular systems to increase the size of generally solvable problems in NP is fundamentally limited to . Over the chemically measurable picomolar to molar concentration range the greatest practical increase in problem size is limited to text/html en_US Journal of Universal Computer Science Molecular Computation DNA NP-problem On the Scalability of Molecular Computational Solutions to NP Problems Research Article

10.3217/jucs-002-03 1996-03-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1996-03-28 1996-03-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 96 96 1996 10.3217/jucs-002-03 https://lib.jucs.org/article/27222/ https://lib.jucs.org/article/27222/download/pdf/ https://lib.jucs.org/article/27222/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-002-03-0097 1996-03-28 jucs

Universitat Politècnica de Catalunya, Spain author Balcázar, José Universitat Politècnica de Catalunya, Spain author Díaz, Josep Universitat Politècnica de Catalunya, Spain author Gavaldà, Ricard Tokyo Institute of Technology, Japan author Watanabe, Osamu 1996-03-28 1996-03-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 97 112 1996 10.3217/jucs-002-03-0097 https://lib.jucs.org/article/27223/ https://lib.jucs.org/article/27223/download/pdf/ https://lib.jucs.org/article/27223/download/xml/ Sequential algorithms given by Angluin (1987) and Schapire (1992) learn deterministic finite automata (DFA) exactly from Membership and Equivalence queries. These algorithms are feasible, in the sense that they take time polynomial in n and m, where n is the number of states of the automaton and m is the length of the longest counterexample to an Equivalence query. This paper studies whether parallelism can lead to substantially more efficient algorithms for the problem. We show that no CRCW PRAM machine using a number of processors polynomial in n and m can identify DFA in o(n/log n) time. Furthermore, this lower bound is tight up to constant factors: we develop a CRCW PRAM learning algorithm that uses polynomially many processors and exactly learns DFA in time O(n/log n). text/html en_US Journal of Universal Computer Science computational learning theory query learning membership query equivalence query DFA optimal parallel learning An Optimal Parallel Algorithm for Learning DFA Research Article

10.3217/jucs-002-03-0113 1996-03-28 jucs

HyperMedia Unit, University of Auckland, New Zealand author Shearer, Jenny Computer Science Department, University of Auckland, New Zealand author Gutmann, Peter 1996-03-28 1996-03-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 113 146 1996 10.3217/jucs-002-03-0113 https://lib.jucs.org/article/27225/ https://lib.jucs.org/article/27225/download/pdf/ https://lib.jucs.org/article/27225/download/xml/ The notion of a right to privacy of citizens in their communications is discussed in the context of an international movement by governments towards regulation of cryptography, and consideration of key forfeiture systems in national cryptography use. The authors argue that the right to privacy in communications networks is an issue of major importance, assuring freedom of the individual in national and global communications. Regulation and control of cryptography use on the Internet by national governments may lead to an imbalance in the citizen/government power relationship, with sequelae including unprecedented surveillance of citizens, disruption of international commerce due to lack of powerful cryptography (and lack of standardisation), human rights abuses by less democratic or non-democratic governments, and limiting of the political potential of an Internet global political system. text/html en_US Journal of Universal Computer Science Government, Cryptography, and the Right to Privacy Research Article

10.3217/jucs-002-03-0147 1996-03-28 jucs

The University of Wollongong, Wollongong, Australia author Zhang, Xian-Mo Monash University, Melbourne, Australia author Zheng, Yuliang 1996-03-28 1996-03-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 147 162 1996 10.3217/jucs-002-03-0147 https://lib.jucs.org/article/27228/ https://lib.jucs.org/article/27228/download/pdf/ https://lib.jucs.org/article/27228/download/xml/ Two significant recent advances in cryptanalysis, namely the differential attack put forward by Biham and Shamir [BS91] and the linear attack by Matsui [Mat94a, Mat94b], have had devastating impact on data encryption algorithms. An eminent problem that researchers are facing is to design S-boxes or substitution boxes so that an encryption algorithm that employs the S-boxes is immune to the attacks. In this paper we present evidence indicating that there are many pitfalls on the road to achieve the goal. In particular, we show that certain types of S-boxes which are seemingly very appealing do not exist. We also show that, contrary to previous perception, techniques such as chopping or repeating permutations do not yield cryptographically strong S-boxes. In addition, we reveal an important combinatorial structure associated with certain quadratic permutations, namely, the difference distribution table of each differentially 2-uniform quadratic permutation embodies a Hadamard matrix. As an application of this result, we show that chopping a differentially 2-uniform quadratic permutation results in an S-box that is very prone to the differential cryptanalytic attack. text/html en_US Journal of Universal Computer Science cryptography differential attack linear attack permutations substitution boxes (S-boxes) On the Difficulty of Constructing Cryptographically Strong Substitution Boxes Research Article

10.3217/jucs-002-04 1996-04-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann 1996-04-28 1996-04-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 163 163 1996 10.3217/jucs-002-04 https://lib.jucs.org/article/27230/ https://lib.jucs.org/article/27230/download/pdf/ https://lib.jucs.org/article/27230/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-002-04-0164 1996-04-28 jucs

Computer Science Dept., Manchester University, Manchester, United Kingdom author Banach, Richard 1996-04-28 1996-04-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 164 216 1996 10.3217/jucs-002-04-0164 https://lib.jucs.org/article/27233/ https://lib.jucs.org/article/27233/download/pdf/ https://lib.jucs.org/article/27233/download/xml/ This is the first in a series of papers dealing with the implementation of an extended term graph rewriting model of computation (described by the DACTL language) on a distributed store architecture. In this paper we set out the high level model, and under some simple restrictions, prove an abstract packet store implementation correct modulo garbage. The abstract packet store model is compared to a more realistic and finegrained packet store model, more closely related to the properties of a genuine distributed store architecture, and the differences are used to inspire the definition of the MONSTR sublanguage of DACTL, intended for direct execution on the machine. Various alternative operational semantics for MONSTR are proposed to reflect more closely the finegrained packet store model, and the prospects for establishing correctness are discussed. The detailed treatment of the alternative models, in the context of suitable sublanguages of MONSTR where appropriate, are subjects for subsequent papers. text/html en_US Journal of Universal Computer Science Intermediate Languages Term Graph Rewriting MONSTR Semantic Models MONSTR I - Fundamental Issues and the Design of MONSTR Research Article

10.3217/jucs-002-04-0217 1996-04-28 jucs

Department of Mathematics, University of Turku, Turku, Finland author Honkala, Juha 1996-04-28 1996-04-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 217 223 1996 10.3217/jucs-002-04-0217 https://lib.jucs.org/article/27234/ https://lib.jucs.org/article/27234/download/pdf/ https://lib.jucs.org/article/27234/download/xml/ We show that it is decidable whether or not the set of coefficients of a given Q-algebraic sequence is finite. The same question is undecidable for Q-algebraic series. We consider also prime factors of algebraic series. text/html en_US Journal of Universal Computer Science On Images of Algebraic Series Research Article

10.3217/jucs-002-04-0224 1996-04-28 jucs

Department of Mathematics University of Western Ontario, London, Ontario, Canada author Kari, Lila Institute of Mathematics of the Romanian Academy, Bucharest, Romania author Paun, Gheorghe Academy of Finland and University of Turku, Department of Mathematics, Turku, Finland author Salomaa, Arto 1996-04-28 1996-04-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 224 240 1996 10.3217/jucs-002-04-0224 https://lib.jucs.org/article/27235/ https://lib.jucs.org/article/27235/download/pdf/ https://lib.jucs.org/article/27235/download/xml/ We continue the investigations begun in [11] on the relationships between several variants of the splicing operation and usual operations with formal languages. The splicing operations are defined with respect to arbitrarily large sets of splicing rules, codified as simple languages. The closure properties of families in Chomsky hierarchy are examined in this context. Several surprising results are obtained about the generative or computing power of the splicing operation. Many important open problems are mentioned. text/html en_US Journal of Universal Computer Science DNA recombination splicing systems molecular genetics Chomsky hierarchy regulated rewriting abstract families of languages The Power of Restricted Splicing with Rules from a Regular Language Research Article

10.3217/jucs-002-05 1996-05-28 jucs

Technical University Graz, Graz, Austria author Maurer, Hermann University of Auckland, Auckland, New Zealand author Calude, Cristian S. https://orcid.org/0000-0002-8711-6799 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 241 244 1996 10.3217/jucs-002-05 https://lib.jucs.org/article/27236/ https://lib.jucs.org/article/27236/download/pdf/ https://lib.jucs.org/article/27236/download/xml/ text/html en_US Journal of Universal Computer Science Managing Editor's Column Editorial

10.3217/jucs-002-05-0245 1996-05-28 jucs

Computer Science Department, University of Maine, Orono, ME 04469-5752, United States of America author Markowsky, George 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 245 269 1996 10.3217/jucs-002-05-0245 https://lib.jucs.org/article/27237/ https://lib.jucs.org/article/27237/download/pdf/ https://lib.jucs.org/article/27237/download/xml/ 1.) C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. text/html en_US Journal of Universal Computer Science Introduction To Algorithmic Information Theory Research Article

10.3217/jucs-002-05-0270 1996-05-28 jucs

IBM Research Division, P. O. Box 704, Yorktown Heights, NY 10598, author Chaitin, G. 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 270 305 1996 10.3217/jucs-002-05-0270 https://lib.jucs.org/article/27238/ https://lib.jucs.org/article/27238/download/pdf/ https://lib.jucs.org/article/27238/download/xml/ text/html en_US Journal of Universal Computer Science The Limits of Mathematics Research Article

10.3217/jucs-002-05-0306 1996-05-28 jucs

University of Auckland, Auckland, New Zealand author Calude, Cristian S. https://orcid.org/0000-0002-8711-6799 Faculty of Mathematics, Bucharest University, Bucharest, Romania author Grozea, Cristian 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 306 310 1996 10.3217/jucs-002-05-0306 https://lib.jucs.org/article/27239/ https://lib.jucs.org/article/27239/download/pdf/ https://lib.jucs.org/article/27239/download/xml/ Kraft's inequality [9] is essential for the classical theory of noiseless coding [1, 8]. In algorithmic information theory [5, 7, 2] one needs an extension of Kraft's condition from finite sets to (infinite) recursively enumerable sets. This extension, known as Kraft-Chaitin Theorem, was obtained by Chaitin in his seminal paper [4] (see also, [3, 2]). The aim of this note is to offer a simpler proof of Kraft-Chaitin Theorem based on a new construction of the prefix-free code. 1.) C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. 2.) The work of the first author has been partially supported by Auckland University Research Grant A18/ XXXXX/62090/3414050. text/html en_US Journal of Universal Computer Science Kraft inequality Kraft-Chaitin inequality prefix-free codes Kraft-Chaitin Inequality Revisited Research Article

10.3217/jucs-002-05-0311 1996-05-28 jucs

Institut für Theoretische Physik, University of Technology Vienna, Vienna, Austria author Svozil, Karl 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 311 346 1996 10.3217/jucs-002-05-0311 https://lib.jucs.org/article/27240/ https://lib.jucs.org/article/27240/download/pdf/ https://lib.jucs.org/article/27240/download/xml/ The agenda of quantum algorithmic information theory, ordered `top-down, is the quantum halting amplitude, followed by the quantum algorithmic information content, which in turn requires the theory of quantum computation. The fundamental atoms processed by quantum computation are the quantum bits which are dealt with in quantum information theory. The theory of quantum computation will be based upon a model of universal quantum computer whose elementary unit is a two-port interferometer capable of arbitrary U(2) transformations. Basic to all these considerations is quantum theory, which is most conveniently expressible in Hilbert space. 1.) C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. text/html en_US Journal of Universal Computer Science Quantum Algorithmic Information Theory Research Article

10.3217/jucs-002-05-0347 1996-05-28 jucs

Department of Computer Science, The University of Western Ontario, London, Ontario, Canada author Jürgensen, H. Department of Computer Science, The University of Western Ontario, London, Ontario, Canada author Robbins, L. 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 347 379 1996 10.3217/jucs-002-05-0347 https://lib.jucs.org/article/27242/ https://lib.jucs.org/article/27242/download/pdf/ https://lib.jucs.org/article/27242/download/xml/ In the spirit of Shannon s theory of secrecy systems we analyse several possible natural definitons of the notion of perfect secrecy, these definitions are based on arguments taken from probability theory, information theory, the theory of computational complexity, and the theory of program-size complexity or algorithmic information. It turns out that none of these definitions models the intuitive notion of perfect secrecy completely: Some fail because a cryptographic system with weak keys can be proven to achieve perfect secrecy in their framework, others fail, because a system which, intuitively, achieves perfect secrecy cannot be proven to do so in their framework. To present this analysis we develop a general formal framework in which to express and measure secrecy aspects of information transmission systems. Our analysis leads to a clarification of the intuition which any definition of the notion of perfect secrecy should capture and the conjecture, that such a definition may be impossible, that is, that only secrecy by degrees can be defined rigorously. This analysis also leads to a clarification of what the cryptographic literature refers to as the one-time pad. On the basis of the arguments used for its strength in the literature, one has to distinguish between two quite different systems: the first kind uses randomly chosen strings of some given length, the second kind uses random strings, that is, patternless strings of some given length. The former achieves perfect secrecy in the sense of Shannon, but permits weak keys - like the all-zero key, the latter, while intuitively stronger, does not achieve perfect secrecy in any of the proposed senses. Finally, the analysis exposes the need for a formal, non-operational, but mathematical definition of the notion of weak key. 1.) C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. The research reported in this paper was supported by the Natural Sciences and Engineering Council of Canada, Grant OGP0000243. text/html en_US Journal of Universal Computer Science cryptography perfect secrecy program-size complexity information theory computational complexity Towards Foundations of Cryptography: Investigation of Perfect Secrecy Research Article

10.3217/jucs-002-05-0380 1996-05-28 jucs

CERFACS and CEREMADE, University Paris IX Dauphine, Toulouse, France author Chaitin-Chatelin, Françoise 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 380 395 1996 10.3217/jucs-002-05-0380 https://lib.jucs.org/article/27245/ https://lib.jucs.org/article/27245/download/pdf/ https://lib.jucs.org/article/27245/download/xml/ Both empirical sciences and computations are fundamentally restricted to measurements/computations involving a finite amount of information. These activities deal with the FINITE - some finite precision numbers, coming out from measurements, or from calculations run for some finite amount of time. By way of contrast, as Leibniz expressed it, mathematics is the science of the INFINITE, which contains the concept of continuum. The related concepts of limit points, derivatives and Cantor sets also belong to mathematics, the realm of the infinite, and not to the world of the finite. One is then lead to wonder about the basis for the "unreasonable effectiveness of mathematics in the natural sciences" (Wigner (1960). This puzzling situation gave birth, over the centuries, to a very lively philosophical discussion between mathematicians and physicists. We intend to throw into the debate a few simple examples drawn from practice in numerical analysis as well as in finite precision computations. By means of these examples, we illustrate some aspects of the subtle interplay between the discrete and the continuous, which takes place in Scientific Computing, when solving some equations of Physics.Is Nature better described by discrete or continuous models at its most intimate level, that is below the atomic level? With the theory of quantum physics, it seems that the question has received a significant push towards a discrete space. However one can argue equally that the time variable in Schrödinger's equation is continuous. We will not get involved in the scholarly dispute between the continuous and the discrete. Instead, we will show on simple examples taken from Scientific Computing, the subtlety of the interplay between the continuous and the discrete, which can take place in computations, be it with finite precision or exact arithmetic. 1.) C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. text/html en_US Journal of Universal Computer Science Is Finite Precision Arithmetic Useful For Physics ? Research Article

10.3217/jucs-002-05-0396 1996-05-28 jucs

University of Bucharest, Bucharest, Romania author Ştefănescu, Doru 1996-05-28 1996-05-28 1996 JUCS - Journal of Universal Computer Science 0948-6968 0948-695X 2 396 409 1996 10.3217/jucs-002-05-0396 https://lib.jucs.org/article/27247/ https://lib.jucs.org/article/27247/download/pdf/ https://lib.jucs.org/article/27247/download/xml/ We discuss some effective characterizations of the prime elements in a polynomial ring and polynomial factorization techniques. We emphasize that some factorization methods are probabilistic, their efficiency justifies the experimental trend in mathematics. The possibility of an effective version of Hilbert's irreducibility theorem and the probabilistic techniques of Berlekamp will be also discussed. Finally, bounds on the heights of integer polynomials are used as tools for improving polynomial factorizations. 1 C. Calude (ed.). The Finite, the Unbounded and the Infinite, Proceedings of the Summer School "Chaitin Complexity and Applications", Mangalia, Romania, 27 June - 6 July, 1995. text/html en_US Journal of Universal Computer Science Polynomials, Constructivity and Randomness Research Article cGFnZT0xJnNldD1qdWNzJmZyb209JnVudGlsPSZtZXRhZGF0YV9wcmVmaXg9bW9kcw==