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

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 0(0): 1-2 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1994 Editorial text/html info:doi:10.3217/jucs-000-00 https://doi.org/10.3217/jucs-000-00 https://lib.jucs.org/article/27061/ https://lib.jucs.org/article/27061/download/pdf/ en

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

Tragic Loss or Good Riddance? The Impending Demise of Traditional Scholarly Journals Odlyzko,Andrew JUCS - Journal of Universal Computer Science 0(0): 3-53 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1994 Research Article text/html info:doi:10.3217/jucs-000-00-0003 https://doi.org/10.3217/jucs-000-00-0003 https://lib.jucs.org/article/27062/ https://lib.jucs.org/article/27062/download/pdf/ en

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

Applications and Impact of Hypermedia Systems: An Overview Lennon,Jennifer Maurer,Hermann multimedia hypermedia Internet Hyper-G hyperlinks collections converging technology e-mail libraries electronic publishing kiosks CSCW conferencing life-long learning electronic lecture room CAI electronic personal assistant. JUCS - Journal of Universal Computer Science 0(0): 54-107 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1994 Research Article text/html info:doi:10.3217/jucs-000-00-0054 https://doi.org/10.3217/jucs-000-00-0054 https://lib.jucs.org/article/27063/ https://lib.jucs.org/article/27063/download/pdf/ en

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

Journal of Universal Computer Science Calude,Cristian Maurer,Hermann Salomaa,Arto JUCS - Journal of Universal Computer Science 0(0): 109-116 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1994 Research Article text/html info:doi:10.3217/jucs-000-00-0109 https://doi.org/10.3217/jucs-000-00-0109 https://lib.jucs.org/article/27066/ https://lib.jucs.org/article/27066/download/pdf/ en

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

J.UCS - The Next Generation in Electronic Journal Publishing Maurer,Hermann Schmaranz,Klaus J.UCS Hyper-G electronic publishing electronic journals JUCS - Journal of Universal Computer Science 0(0): 117-126 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1994 Research Article text/html info:doi:10.3217/jucs-000-00-0117 https://doi.org/10.3217/jucs-000-00-0117 https://lib.jucs.org/article/27067/ https://lib.jucs.org/article/27067/download/pdf/ en

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

On Second Generation Hypermedia Systems Andrews,Keith Kappe,Frank Maurer,Hermann Schmaranz,Klaus JUCS - Journal of Universal Computer Science 0(0): 127-136 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1994 Research Article text/html info:doi:10.3217/jucs-000-00-0127 https://doi.org/10.3217/jucs-000-00-0127 https://lib.jucs.org/article/27074/ https://lib.jucs.org/article/27074/download/pdf/ en

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

You Believe You Know What Multimedia is? And What Internet Will Do For You? Well ... Think Again! Lennon,Jennifer Maurer,Hermann Converging technology multimedia hypermedia interactive and annotated movies Internet Hyper-G. JUCS - Journal of Universal Computer Science 0(0): 137-143 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1994 Research Article text/html info:doi:10.3217/jucs-000-00-0137 https://doi.org/10.3217/jucs-000-00-0137 https://lib.jucs.org/article/27075/ https://lib.jucs.org/article/27075/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(1): 1-1 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-01 https://doi.org/10.3217/jucs-001-01 https://lib.jucs.org/article/27076/ https://lib.jucs.org/article/27076/download/pdf/ en

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

High-radix Division with Approximate Quotient-digit Estimation Fenwick,Peter Division high radix approximate digit estimates JUCS - Journal of Universal Computer Science 1(1): 2-22 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-01-0002 https://doi.org/10.3217/jucs-001-01-0002 https://lib.jucs.org/article/27077/ https://lib.jucs.org/article/27077/download/pdf/ en

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

On Implementing EREW Work-Optimally on Mesh of Trees Leppänen,Ville EREW mesh of trees shared memory simulation work-optimal randomized coated mesh. JUCS - Journal of Universal Computer Science 1(1): 23-34 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-01-0023 https://doi.org/10.3217/jucs-001-01-0023 https://lib.jucs.org/article/27078/ https://lib.jucs.org/article/27078/download/pdf/ en

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

Levels of Anonymity Flinn,Bill Maurer,Hermann security anonymous use access control authentication big brother JUCS - Journal of Universal Computer Science 1(1): 35-47 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-01-0035 https://doi.org/10.3217/jucs-001-01-0035 https://lib.jucs.org/article/27080/ https://lib.jucs.org/article/27080/download/pdf/ en

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

What Is a Random String? Calude,Cristian S. Blank-endmarker complexity Chaitin (self-delimiting) complexity random strings. JUCS - Journal of Universal Computer Science 1(1): 48-66 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-01-0048 https://doi.org/10.3217/jucs-001-01-0048 https://lib.jucs.org/article/27082/ https://lib.jucs.org/article/27082/download/pdf/ en

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

Grammars Based on the Shuffle Operation Paun,Gheorghe Rozenberg,Grzegorz Salomaa,Arto Shuffle operation Chomsky grammars L Systems JUCS - Journal of Universal Computer Science 1(1): 67-82 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-01-0067 https://doi.org/10.3217/jucs-001-01-0067 https://lib.jucs.org/article/27088/ https://lib.jucs.org/article/27088/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(2): 83-83 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-02 https://doi.org/10.3217/jucs-001-02 https://lib.jucs.org/article/27095/ https://lib.jucs.org/article/27095/download/pdf/ en

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

A Scalable Architecture for Maintaining Referential Integrity in Distributed Information Systems Kappe,Frank Hypertext Link Consistency Distributed Information System Internet Gopher WWW Hyper-G Scalability p-flood JUCS - Journal of Universal Computer Science 1(2): 84-104 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-02-0084 https://doi.org/10.3217/jucs-001-02-0084 https://lib.jucs.org/article/27096/ https://lib.jucs.org/article/27096/download/pdf/ en

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

A Variant of Team Cooperation in Grammar Systems Freund,Rudolf Paun,Gheorghe Formal languages grammar systems teams JUCS - Journal of Universal Computer Science 1(2): 105-130 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-02-0105 https://doi.org/10.3217/jucs-001-02-0105 https://lib.jucs.org/article/27099/ https://lib.jucs.org/article/27099/download/pdf/ en

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

On Four Classes of Lindenmayerian Power Series Honkala,Juha Kuich,Werner JUCS - Journal of Universal Computer Science 1(2): 131-135 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-02-0131 https://doi.org/10.3217/jucs-001-02-0131 https://lib.jucs.org/article/27100/ https://lib.jucs.org/article/27100/download/pdf/ en

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

The Relationship Between Propagation Characteristics and Nonlinearity of Cryptographic Functions Seberry,Jennifer Zhang,Xian-Mo Zheng,Yuliang Cryptography Boolean functions Encryption functions Nonlinearity Propagation Characteristics SAC S-boxes JUCS - Journal of Universal Computer Science 1(2): 136-150 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-02-0136 https://doi.org/10.3217/jucs-001-02-0136 https://lib.jucs.org/article/27101/ https://lib.jucs.org/article/27101/download/pdf/ en

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

On Completeness of Pseudosimple Sets Bulitko,Vadim Completeness Pseudosimple set Effectivization Extensionally bounded function JUCS - Journal of Universal Computer Science 1(2): 151-154 The paper contains completeness criterions for pseudosimple sets. Those criterions are constructed using effectivization of the definitions as well as extensionally bounded functions. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-02-0151 https://doi.org/10.3217/jucs-001-02-0151 https://lib.jucs.org/article/27102/ https://lib.jucs.org/article/27102/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(3): 155-155 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-03 https://doi.org/10.3217/jucs-001-03 https://lib.jucs.org/article/27103/ https://lib.jucs.org/article/27103/download/pdf/ en

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

Combining Concept Mapping and Adaptive Advice to Teach Reading Comprehension Carlson,Patricia Larralde,Veronica JUCS - Journal of Universal Computer Science 1(3): 156-161 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). info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-03-0156 https://doi.org/10.3217/jucs-001-03-0156 https://lib.jucs.org/article/27104/ https://lib.jucs.org/article/27104/download/pdf/ en

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

Modular Range Reduction Daumas,Marc Mazenc,Christophe Merrheim,Xavier Muller,Jean-Michel Computer Arithmetic Elementary Functions Range Reduction JUCS - Journal of Universal Computer Science 1(3): 162-175 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-03-0162 https://doi.org/10.3217/jucs-001-03-0162 https://lib.jucs.org/article/27105/ https://lib.jucs.org/article/27105/download/pdf/ en

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

Special Cases of Division Doran,R. JUCS - Journal of Universal Computer Science 1(3): 176-194 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-03-0176 https://doi.org/10.3217/jucs-001-03-0176 https://lib.jucs.org/article/27106/ https://lib.jucs.org/article/27106/download/pdf/ en

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

Bringing ITS to the Marketplace: A Successful Experiment in Minimalist Design Gutwin,Carl Jones,Marlene Brackett,Patrick Adolphe,Kim JUCS - Journal of Universal Computer Science 1(3): 195-200 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-03-0195 https://doi.org/10.3217/jucs-001-03-0195 https://lib.jucs.org/article/27109/ https://lib.jucs.org/article/27109/download/pdf/ en

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

Halting Probability Amplitude of Quantum Computers Svozil,Karl JUCS - Journal of Universal Computer Science 1(3): 201-204 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.) info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-03-0201 https://doi.org/10.3217/jucs-001-03-0201 https://lib.jucs.org/article/27112/ https://lib.jucs.org/article/27112/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(4): 205-205 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-04 https://doi.org/10.3217/jucs-001-04 https://lib.jucs.org/article/27113/ https://lib.jucs.org/article/27113/download/pdf/ en

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

The Hyper-G Network Information System Andrews,Keith Kappe,Frank Maurer,Hermann Hypermedia information system information visualisation graphical interaction Internet JUCS - Journal of Universal Computer Science 1(4): 206-220 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-04-0206 https://doi.org/10.3217/jucs-001-04-0206 https://lib.jucs.org/article/27114/ https://lib.jucs.org/article/27114/download/pdf/ en

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

About WWW Cailliau,R. WWW World-Wide Web History SGML cultural Aspects Society. JUCS - Journal of Universal Computer Science 1(4): 221-231 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-04-0221 https://doi.org/10.3217/jucs-001-04-0221 https://lib.jucs.org/article/27115/ https://lib.jucs.org/article/27115/download/pdf/ en

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

Electronic Publishing Götze,Dietrich JUCS - Journal of Universal Computer Science 1(4): 232-234 Publishing the results of scientific research is the basis of the advancement of science, technology and medicine. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-04-0232 https://doi.org/10.3217/jucs-001-04-0232 https://lib.jucs.org/article/27116/ https://lib.jucs.org/article/27116/download/pdf/ en

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

Evolution of Internet Gopher Mccahill,Mark Anklesaria,Farhad Distributed Information Systems Internet Gopher Gopher+ JUCS - Journal of Universal Computer Science 1(4): 235-246 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-04-0235 https://doi.org/10.3217/jucs-001-04-0235 https://lib.jucs.org/article/27118/ https://lib.jucs.org/article/27118/download/pdf/ en

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

WAIS and Information Retrieval on the Internet Mülner,Helmut JUCS - Journal of Universal Computer Science 1(4): 247-250 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-04-0247 https://doi.org/10.3217/jucs-001-04-0247 https://lib.jucs.org/article/27122/ https://lib.jucs.org/article/27122/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(5): 251-251 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-05 https://doi.org/10.3217/jucs-001-05 https://lib.jucs.org/article/27123/ https://lib.jucs.org/article/27123/download/pdf/ en

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

Conditional Tabled Eco-Grammar Systems Csuhaj-Varju,Erzsebet Paun,Gheorghe Salomaa,Arto Grammar systems L systems Artificial Life JUCS - Journal of Universal Computer Science 1(5): 252-268 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 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-05-0252 https://doi.org/10.3217/jucs-001-05-0252 https://lib.jucs.org/article/27124/ https://lib.jucs.org/article/27124/download/pdf/ en

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

HOME: An Environment for Hypermedia Objects Duval,Erik Olivié,Henk Hanlon,Piers Jameson,David HOME distributed hypermedia networked multimedia image store navigation query JUCS - Journal of Universal Computer Science 1(5): 269-291 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-05-0269 https://doi.org/10.3217/jucs-001-05-0269 https://lib.jucs.org/article/27125/ https://lib.jucs.org/article/27125/download/pdf/ en

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

Lexical Analysis with a Simple Finite-Fuzzy-Automaton Model Mateescu,Alexandru Salomaa,Arto Salomaa,Kai Yu,Sheng JUCS - Journal of Universal Computer Science 1(5): 292-311 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-05-0292 https://doi.org/10.3217/jucs-001-05-0292 https://lib.jucs.org/article/27126/ https://lib.jucs.org/article/27126/download/pdf/ en

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

Software Patents and The Internet Shearer,Jenny Vermeer,Arnould Software patents debate Internet Compuserve Unisys LZW GIF JUCS - Journal of Universal Computer Science 1(5): 312-319 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-05-0312 https://doi.org/10.3217/jucs-001-05-0312 https://lib.jucs.org/article/27127/ https://lib.jucs.org/article/27127/download/pdf/ en

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

GAC - the Criterion for Global Avalanche Characteristics of Cryptographic Functions Zhang,Xian-Mo Zheng,Yuliang JUCS - Journal of Universal Computer Science 1(5): 320-337 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-05-0320 https://doi.org/10.3217/jucs-001-05-0320 https://lib.jucs.org/article/27128/ https://lib.jucs.org/article/27128/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(6): 338-338 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-06 https://doi.org/10.3217/jucs-001-06 https://lib.jucs.org/article/27129/ https://lib.jucs.org/article/27129/download/pdf/ en

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

A Translation of the Pi-Calculus Into MONSTR Banach,Richard Balázs,J. Papadopoulos,George Concurrency Pi-Calculus Term Graph Rewriting MONSTR Process Networks Simulation Serialisability. JUCS - Journal of Universal Computer Science 1(6): 339-398 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-06-0339 https://doi.org/10.3217/jucs-001-06-0339 https://lib.jucs.org/article/27130/ https://lib.jucs.org/article/27130/download/pdf/ en

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

Distributed Caching in Networked File Systems Klauser,Artur Posch,Reinhard networked file systems distributed file caches load balancing file system performance JUCS - Journal of Universal Computer Science 1(6): 399-409 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-06-0399 https://doi.org/10.3217/jucs-001-06-0399 https://lib.jucs.org/article/27131/ https://lib.jucs.org/article/27131/download/pdf/ en

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

From Personal Computer to Personal Assistant Lennon,Jennifer Vermeer,Arnould Electronic assistants electronic agents message pads searches prediction programming by example voice commands. JUCS - Journal of Universal Computer Science 1(6): 410-422 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-06-0410 https://doi.org/10.3217/jucs-001-06-0410 https://lib.jucs.org/article/27132/ https://lib.jucs.org/article/27132/download/pdf/ en

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

Microworlds For Teaching Concepts of Object Oriented Programming Tomek,Ivan Microworld object oriented programming progressive disclosure Smalltalk teaching object oriented programming computer literacy. JUCS - Journal of Universal Computer Science 1(6): 423-434 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-06-0423 https://doi.org/10.3217/jucs-001-06-0423 https://lib.jucs.org/article/27133/ https://lib.jucs.org/article/27133/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann Bajard,Jean-Claude Michelucci,Dominique Moreau,Jean-Michel Muller,Jean-Michel JUCS - Journal of Universal Computer Science 1(7): 435-438 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-07 https://doi.org/10.3217/jucs-001-07 https://lib.jucs.org/article/27136/ https://lib.jucs.org/article/27136/download/pdf/ en

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

A High Radix On-line Arithmetic for Credible and Accurate Computing Lynch,Thomas Schulte,Michael High-radix on-line arithmetic precision accurate reliable credible super-scaler VLIW. JUCS - Journal of Universal Computer Science 1(7): 439-453 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0439 https://doi.org/10.3217/jucs-001-07-0439 https://lib.jucs.org/article/27137/ https://lib.jucs.org/article/27137/download/pdf/ en

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

Estimation of Round-off Errors on Several Computers Architectures Asserrhine,Jalil Chesneaux,Jean-Marie Lamotte,Jean-Luc JUCS - Journal of Universal Computer Science 1(7): 454-468 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0454 https://doi.org/10.3217/jucs-001-07-0454 https://lib.jucs.org/article/27138/ https://lib.jucs.org/article/27138/download/pdf/ en

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

Round-off Error Propagation in the Solution of the Heat Equation by finite Differences Jézéquel,Fabienne Floating point arithmetic numerical error propagation partial differential equations finite difference methods JUCS - Journal of Universal Computer Science 1(7): 469-483 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0469 https://doi.org/10.3217/jucs-001-07-0469 https://lib.jucs.org/article/27140/ https://lib.jucs.org/article/27140/download/pdf/ en

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

LCF: A Lexicographic Binary Representation of the Rationals Kornerup,Peter Matula,David Computer arithmetic continued fractions lexicographic number systems number theory rational numbers. JUCS - Journal of Universal Computer Science 1(7): 484-503 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0484 https://doi.org/10.3217/jucs-001-07-0484 https://lib.jucs.org/article/27141/ https://lib.jucs.org/article/27141/download/pdf/ en

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

Exact Statistics and Continued Fractions Lester,David JUCS - Journal of Universal Computer Science 1(7): 504-513 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0504 https://doi.org/10.3217/jucs-001-07-0504 https://lib.jucs.org/article/27143/ https://lib.jucs.org/article/27143/download/pdf/ en

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

On Directed Interval Arithmetic and its Applications Markov,Svetoslav computer arithmetic error analysis interval algebraic manipulation JUCS - Journal of Universal Computer Science 1(7): 514-526 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0514 https://doi.org/10.3217/jucs-001-07-0514 https://lib.jucs.org/article/27145/ https://lib.jucs.org/article/27145/download/pdf/ en

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

MSB-First Digit Serial Arithmetic Nielsen,Asger Kornerup,Peter Computer Arithmetic On-line Computation Number Representations Redundant Digit sets Continued Fractions Intervals JUCS - Journal of Universal Computer Science 1(7): 527-547 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0527 https://doi.org/10.3217/jucs-001-07-0527 https://lib.jucs.org/article/27146/ https://lib.jucs.org/article/27146/download/pdf/ en

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

Some Algorithms Providing Rigorous Bounds for the Eigenvalues of a Matrix Pavec,Raymond JUCS - Journal of Universal Computer Science 1(7): 548-559 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0548 https://doi.org/10.3217/jucs-001-07-0548 https://lib.jucs.org/article/27147/ https://lib.jucs.org/article/27147/download/pdf/ en

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

On a Formally Correct Implementation of IEEE Computer Arithmetic Popova,Evgenija computer arithmetic implementation IEEE standards exception handling JUCS - Journal of Universal Computer Science 1(7): 560-569 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-07-0560 https://doi.org/10.3217/jucs-001-07-0560 https://lib.jucs.org/article/27148/ https://lib.jucs.org/article/27148/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(8): 570-570 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-08 https://doi.org/10.3217/jucs-001-08 https://lib.jucs.org/article/27150/ https://lib.jucs.org/article/27150/download/pdf/ en

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

BROCA : A Computerized Environment for Mediating Scientific Reasoning through Writing Carlson,Patricia Computers and Education Computer Uses in Education JUCS - Journal of Universal Computer Science 1(8): 571-590 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-08-0571 https://doi.org/10.3217/jucs-001-08-0571 https://lib.jucs.org/article/27151/ https://lib.jucs.org/article/27151/download/pdf/ en

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

Differential Ziv-Lempel Text Compression Fenwick,Peter text compression LZ-77 arithmetic coding vector quantisation JUCS - Journal of Universal Computer Science 1(8): 591-602 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-08-0591 https://doi.org/10.3217/jucs-001-08-0591 https://lib.jucs.org/article/27152/ https://lib.jucs.org/article/27152/download/pdf/ en

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

Bounds for Heights of Integer Polynomial Factors Panaitopol,Laurentiu Ştefănescu,Doru JUCS - Journal of Universal Computer Science 1(8): 603-613 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-08-0603 https://doi.org/10.3217/jucs-001-08-0603 https://lib.jucs.org/article/27153/ https://lib.jucs.org/article/27153/download/pdf/ en

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

A Robust Affine Matching Algorithm Using an Exponentially Decreasing Distance Function Pinz,Axel Prantl,Manfred Ganster,Harald Affine Matching Spatial Registration Information Fusion Image Understanding JUCS - Journal of Universal Computer Science 1(8): 614-631 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-08-0614 https://doi.org/10.3217/jucs-001-08-0614 https://lib.jucs.org/article/27154/ https://lib.jucs.org/article/27154/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(9): 632-632 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-09 https://doi.org/10.3217/jucs-001-09 https://lib.jucs.org/article/27157/ https://lib.jucs.org/article/27157/download/pdf/ en

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

An Efficient Distributed Algorithm For st-numbering the Vertices of a Biconnected Graph Aranha,R. F. M. Rangan,C. Distributed graph algorithms st-numbering biconnected graph JUCS - Journal of Universal Computer Science 1(9): 633-651 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-09-0633 https://doi.org/10.3217/jucs-001-09-0633 https://lib.jucs.org/article/27158/ https://lib.jucs.org/article/27158/download/pdf/ en

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

A Decision Method for the Unambiguity of Sets Defined by Number Systems Honkala,Juha JUCS - Journal of Universal Computer Science 1(9): 652-657 We show that it is decidable, given a number system N, whether or not there is an unambiguous number system equivalent to N. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-09-0652 https://doi.org/10.3217/jucs-001-09-0652 https://lib.jucs.org/article/27163/ https://lib.jucs.org/article/27163/download/pdf/ en

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

A Method for Proving Theorems in Differential Geometry and Mechanics Wang,Dongming Differential geometry mechanics polynomial elimination theorem proving triangular system zero decomposition JUCS - Journal of Universal Computer Science 1(9): 658-673 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-09-0658 https://doi.org/10.3217/jucs-001-09-0658 https://lib.jucs.org/article/27164/ https://lib.jucs.org/article/27164/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(10): 674-674 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-10 https://doi.org/10.3217/jucs-001-10 https://lib.jucs.org/article/27165/ https://lib.jucs.org/article/27165/download/pdf/ en

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

An Aperiodic Set of Wang Cubes Ii.,Karel Kari,Jarkko discrete mathematics automata theory aperiodic tilings Wang tiles Wang cubes sequential machines JUCS - Journal of Universal Computer Science 1(10): 675-686 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-10-0675 https://doi.org/10.3217/jucs-001-10-0675 https://lib.jucs.org/article/27167/ https://lib.jucs.org/article/27167/download/pdf/ en

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

Contained Hypermedia Duval,Erik Olivié,Henk Scherbakov,Nick hypermedia data modeling automatic link maintenance JUCS - Journal of Universal Computer Science 1(10): 687-705 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-10-0687 https://doi.org/10.3217/jucs-001-10-0687 https://lib.jucs.org/article/27170/ https://lib.jucs.org/article/27170/download/pdf/ en

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

Authoring on the Fly Ottmann,Thomas Bacher,Ch. electronic courseware hypermedia whiteboard distance teaching JUCS - Journal of Universal Computer Science 1(10): 706-717 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-10-0706 https://doi.org/10.3217/jucs-001-10-0706 https://lib.jucs.org/article/27174/ https://lib.jucs.org/article/27174/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(11): 718-718 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-11 https://doi.org/10.3217/jucs-001-11 https://lib.jucs.org/article/27179/ https://lib.jucs.org/article/27179/download/pdf/ en

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

Digital Libraries as Learning and Teaching Support Maurer,Hermann Lennon,Jennifer Digital libraries electronic libraries learning support teaching support instructional technology CAI CBT JUCS - Journal of Universal Computer Science 1(11): 719-727 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-11-0719 https://doi.org/10.3217/jucs-001-11-0719 https://lib.jucs.org/article/27180/ https://lib.jucs.org/article/27180/download/pdf/ en

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

Testing a High-Speed Data Path The Design of the RSAb Crypto Chip Mayerwieser,Wolfgang Posch,Karl Posch,Reinhard Schindler,Volker high speed multipliers hardware algorithms design for testability public key cryptography JUCS - Journal of Universal Computer Science 1(11): 728-743 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-11-0728 https://doi.org/10.3217/jucs-001-11-0728 https://lib.jucs.org/article/27185/ https://lib.jucs.org/article/27185/download/pdf/ en

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

A Comparison of WWW and Hyper-G Pam,Andrew Vermeer,Arnould Hypermedia Hyper-G WWW Xanadu networked information systems Internet JUCS - Journal of Universal Computer Science 1(11): 744-750 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-11-0744 https://doi.org/10.3217/jucs-001-11-0744 https://lib.jucs.org/article/27188/ https://lib.jucs.org/article/27188/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 1(12): 751-751 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Editorial text/html info:doi:10.3217/jucs-001-12 https://doi.org/10.3217/jucs-001-12 https://lib.jucs.org/article/27190/ https://lib.jucs.org/article/27190/download/pdf/ en

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

A Novel Type of Skeleton for Polygons Aichholzer,Oswin Aurenhammer,Franz Alberts,David Gärtner,Bernd Simple polygon angular bisectors internal skeleton roof construction JUCS - Journal of Universal Computer Science 1(12): 752-761 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-12-0752 https://doi.org/10.3217/jucs-001-12-0752 https://lib.jucs.org/article/27191/ https://lib.jucs.org/article/27191/download/pdf/ en

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

Constraint Agents for the Information Age Andreoli,Jean-Marc Borghoff,Uwe Pareschi,Remo Schlichter,Johann multiagent coordination agent-interaction distributed problem solving signed feature constraints negotiation cooperation strategies. JUCS - Journal of Universal Computer Science 1(12): 762-789 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-12-0762 https://doi.org/10.3217/jucs-001-12-0762 https://lib.jucs.org/article/27192/ https://lib.jucs.org/article/27192/download/pdf/ en

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

Parikh Prime Words and GO-like Territories Mateescu,Alexandru Paun,Gheorghe Rozenberg,Grzegorz Salomaa,Arto formal languages context free languages L-systems Parikh mapping word problems JUCS - Journal of Universal Computer Science 1(12): 790-810 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-12-0790 https://doi.org/10.3217/jucs-001-12-0790 https://lib.jucs.org/article/27197/ https://lib.jucs.org/article/27197/download/pdf/ en

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

Exploiting Parallelism in Constraint Satisfaction for Qualitative Simulation Platzner,Marco Rinner,Bernhard Weiss,Reinhold Parallel constraint satisfaction QSim distributed AI JUCS - Journal of Universal Computer Science 1(12): 811-820 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). info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-12-0811 https://doi.org/10.3217/jucs-001-12-0811 https://lib.jucs.org/article/27198/ https://lib.jucs.org/article/27198/download/pdf/ en

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

A Markov Process for Sequential Allocation Stefanescu,Calina JUCS - Journal of Universal Computer Science 1(12): 821-827 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1995 Research Article text/html info:doi:10.3217/jucs-001-12-0821 https://doi.org/10.3217/jucs-001-12-0821 https://lib.jucs.org/article/27200/ https://lib.jucs.org/article/27200/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 2(1): 1-1 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Editorial text/html info:doi:10.3217/jucs-002-01 https://doi.org/10.3217/jucs-002-01 https://lib.jucs.org/article/27202/ https://lib.jucs.org/article/27202/download/pdf/ en

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

Wait-Freedom vs. Bounded Wait Freedom in Public Data Structures Brit,Hagit Moran,Shlomo JUCS - Journal of Universal Computer Science 2(1): 2-19 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-01-0002 https://doi.org/10.3217/jucs-002-01-0002 https://lib.jucs.org/article/27203/ https://lib.jucs.org/article/27203/download/pdf/ en

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

LAN Access Over ISDN Pucher,Franz Leitold,Herbert Posch,Reinhard JUCS - Journal of Universal Computer Science 2(1): 20-33 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-01-0020 https://doi.org/10.3217/jucs-002-01-0020 https://lib.jucs.org/article/27205/ https://lib.jucs.org/article/27205/download/pdf/ en

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

The Dortmund Family of Hypermedia Models - Concepts and their Application Tochtermann,Klaus Dittrich,Gisbert hypermedia hypermedia model hypermedia system hypermedia structuring JUCS - Journal of Universal Computer Science 2(1): 34-56 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-01-0034 https://doi.org/10.3217/jucs-002-01-0034 https://lib.jucs.org/article/27206/ https://lib.jucs.org/article/27206/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 2(2): 57-58 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Editorial text/html info:doi:10.3217/jucs-002-02 https://doi.org/10.3217/jucs-002-02 https://lib.jucs.org/article/27209/ https://lib.jucs.org/article/27209/download/pdf/ en

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

Curve Fitting and Interpolation of Biological Data Under Uncertainties Markov,Svetoslav Akyildiz,Y. Interpolation least squares approximation verification model validation algebraic manipulations computer algebra systems enzyme kinetics uncertainties interval arithmetic JUCS - Journal of Universal Computer Science 2(2): 59-69 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-02-0058 https://doi.org/10.3217/jucs-002-02-0058 https://lib.jucs.org/article/27210/ https://lib.jucs.org/article/27210/download/pdf/ en

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

Inexact Information Systems and its Application to Approximate Reasoning Andreeva,Plamena Linguistic approach fuzzy implication fuzzy quantifier fuzzy number approximate reasoning information system. JUCS - Journal of Universal Computer Science 2(2): 70-76 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-02-0070 https://doi.org/10.3217/jucs-002-02-0070 https://lib.jucs.org/article/27214/ https://lib.jucs.org/article/27214/download/pdf/ en

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

Dedicated Hardware for Biological Sequence Comparison Lavenier,Dominique Hardware Biological Sequence Comparison DNA FPGA VLSI JUCS - Journal of Universal Computer Science 2(2): 77-86 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-02-0077 https://doi.org/10.3217/jucs-002-02-0077 https://lib.jucs.org/article/27219/ https://lib.jucs.org/article/27219/download/pdf/ en

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

On the Scalability of Molecular Computational Solutions to NP Problems Dónaill,Dónall A. Mac Molecular Computation DNA NP-problem JUCS - Journal of Universal Computer Science 2(2): 87-95 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 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-02-0087 https://doi.org/10.3217/jucs-002-02-0087 https://lib.jucs.org/article/27220/ https://lib.jucs.org/article/27220/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 2(3): 96-96 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Editorial text/html info:doi:10.3217/jucs-002-03 https://doi.org/10.3217/jucs-002-03 https://lib.jucs.org/article/27222/ https://lib.jucs.org/article/27222/download/pdf/ en

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

An Optimal Parallel Algorithm for Learning DFA Balcázar,José Díaz,Josep Gavaldà,Ricard Watanabe,Osamu computational learning theory query learning membership query equivalence query DFA optimal parallel learning JUCS - Journal of Universal Computer Science 2(3): 97-112 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). info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-03-0097 https://doi.org/10.3217/jucs-002-03-0097 https://lib.jucs.org/article/27223/ https://lib.jucs.org/article/27223/download/pdf/ en

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

Government, Cryptography, and the Right to Privacy Shearer,Jenny Gutmann,Peter JUCS - Journal of Universal Computer Science 2(3): 113-146 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-03-0113 https://doi.org/10.3217/jucs-002-03-0113 https://lib.jucs.org/article/27225/ https://lib.jucs.org/article/27225/download/pdf/ en

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

On the Difficulty of Constructing Cryptographically Strong Substitution Boxes Zhang,Xian-Mo Zheng,Yuliang cryptography differential attack linear attack permutations substitution boxes (S-boxes) JUCS - Journal of Universal Computer Science 2(3): 147-162 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-03-0147 https://doi.org/10.3217/jucs-002-03-0147 https://lib.jucs.org/article/27228/ https://lib.jucs.org/article/27228/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann JUCS - Journal of Universal Computer Science 2(4): 163-163 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Editorial text/html info:doi:10.3217/jucs-002-04 https://doi.org/10.3217/jucs-002-04 https://lib.jucs.org/article/27230/ https://lib.jucs.org/article/27230/download/pdf/ en

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

MONSTR I - Fundamental Issues and the Design of MONSTR Banach,Richard Intermediate Languages Term Graph Rewriting MONSTR Semantic Models JUCS - Journal of Universal Computer Science 2(4): 164-216 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-04-0164 https://doi.org/10.3217/jucs-002-04-0164 https://lib.jucs.org/article/27233/ https://lib.jucs.org/article/27233/download/pdf/ en

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

On Images of Algebraic Series Honkala,Juha JUCS - Journal of Universal Computer Science 2(4): 217-223 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-04-0217 https://doi.org/10.3217/jucs-002-04-0217 https://lib.jucs.org/article/27234/ https://lib.jucs.org/article/27234/download/pdf/ en

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

The Power of Restricted Splicing with Rules from a Regular Language Kari,Lila Paun,Gheorghe Salomaa,Arto DNA recombination splicing systems molecular genetics Chomsky hierarchy regulated rewriting abstract families of languages JUCS - Journal of Universal Computer Science 2(4): 224-240 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-04-0224 https://doi.org/10.3217/jucs-002-04-0224 https://lib.jucs.org/article/27235/ https://lib.jucs.org/article/27235/download/pdf/ en

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

Managing Editor's Column Maurer,Hermann Calude,Cristian S. JUCS - Journal of Universal Computer Science 2(5): 241-244 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Editorial text/html info:doi:10.3217/jucs-002-05 https://doi.org/10.3217/jucs-002-05 https://lib.jucs.org/article/27236/ https://lib.jucs.org/article/27236/download/pdf/ en

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

Introduction To Algorithmic Information Theory Markowsky,George JUCS - Journal of Universal Computer Science 2(5): 245-269 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-05-0245 https://doi.org/10.3217/jucs-002-05-0245 https://lib.jucs.org/article/27237/ https://lib.jucs.org/article/27237/download/pdf/ en

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

The Limits of Mathematics Chaitin,G. JUCS - Journal of Universal Computer Science 2(5): 270-305 info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-05-0270 https://doi.org/10.3217/jucs-002-05-0270 https://lib.jucs.org/article/27238/ https://lib.jucs.org/article/27238/download/pdf/ en

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

Kraft-Chaitin Inequality Revisited Calude,Cristian S. Grozea,Cristian Kraft inequality Kraft-Chaitin inequality prefix-free codes JUCS - Journal of Universal Computer Science 2(5): 306-310 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-05-0306 https://doi.org/10.3217/jucs-002-05-0306 https://lib.jucs.org/article/27239/ https://lib.jucs.org/article/27239/download/pdf/ en

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

Quantum Algorithmic Information Theory Svozil,Karl JUCS - Journal of Universal Computer Science 2(5): 311-346 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-05-0311 https://doi.org/10.3217/jucs-002-05-0311 https://lib.jucs.org/article/27240/ https://lib.jucs.org/article/27240/download/pdf/ en

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

Towards Foundations of Cryptography: Investigation of Perfect Secrecy Jürgensen,H. Robbins,L. cryptography perfect secrecy program-size complexity information theory computational complexity JUCS - Journal of Universal Computer Science 2(5): 347-379 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-05-0347 https://doi.org/10.3217/jucs-002-05-0347 https://lib.jucs.org/article/27242/ https://lib.jucs.org/article/27242/download/pdf/ en

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

Is Finite Precision Arithmetic Useful For Physics ? Chaitin-Chatelin,Françoise JUCS - Journal of Universal Computer Science 2(5): 380-395 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-05-0380 https://doi.org/10.3217/jucs-002-05-0380 https://lib.jucs.org/article/27245/ https://lib.jucs.org/article/27245/download/pdf/ en

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

Polynomials, Constructivity and Randomness Ştefănescu,Doru JUCS - Journal of Universal Computer Science 2(5): 396-409 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. info:eu-repo/semantics/altIdentifier/eissn/0948-6968 info:eu-repo/semantics/altIdentifier/pissn/0948-695X info:eu-repo/semantics/openAccess J.UCS License Journal of Universal Computer Science 1996 Research Article text/html info:doi:10.3217/jucs-002-05-0396 https://doi.org/10.3217/jucs-002-05-0396 https://lib.jucs.org/article/27247/ https://lib.jucs.org/article/27247/download/pdf/ en cGFnZT0xJnNldD1qdWNzJmZyb209JnVudGlsPSZtZXRhZGF0YV9wcmVmaXg9b2FpX2Rj