Fundamenta Informaticae - Volume 5, issue 3-4

Article Type: Other

DOI: 10.3233/FI-1982-53-401

Citation: Fundamenta Informaticae, vol. 5, no. 3-4, pp. i-vi, 1982

Authors: Fischetti, Enrico | Smaldone, Roberto

Article Type: Research Article

Abstract: Operator precedence parsers suffer the disadvantage of parsing invalid as well valid strings. This problem is scrutinized in relation to previous papers of Henderson and Levy (3) and Williams (4) and a parsing algorithm is put forward, capable of parsing a large class of operator precedence grammars.

Keywords: formal languages, operator precedence grammars

DOI: 10.3233/FI-1982-53-402

Citation: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 247-260, 1982

Authors: Mundici, Daniele

Article Type: Research Article

Abstract: In this paper we investigate the length ‖ χ ‖ of the shortest interpolant of a valid implication φ → ψ in terms of ‖ φ ‖ + ‖ ψ ‖ , both in sentential and in first-order logic. In the case of sentential logic, we give a precise exponential upper bound for ‖ χ ‖ . We also show that the information about the growth of ‖ χ ‖ has some implications for computation theory. In the case of first-order logic we exhibit a very short …valid implication whose interpolants are all impossibly long. Show more

Keywords: Valid implication, logical circuit, interpolant, delay complexity

DOI: 10.3233/FI-1982-53-403

Citation: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 261-278, 1982

Authors: Pettorossi, Alberto

Article Type: Research Article

Abstract: In this paper we consider combinators as tree transducers: this approach is based on the one-to-one correspondence between terms of Combinatory Logic and trees, and on the fact that combinators may be considered as transformers of terms. Since combinators are terms themselves, we will deal with trees as objects to be transformed and tree transformers as well. Methods for defining and studying tree rewriting systems inside Combinatory Weak Reduction Systems and Weak Combinatory Logic are also analyzed and particular attention is devoted to the problem of finiteness and infinity of the generated tree languages (here defined). This implies the study …of the termination of the rewriting process (i.e. reduction) for combinators. Show more

Keywords: Combinatory Logic, Combinatory Weak Reduction Systems, Tree Languages, Tree Transducers, Termination, Rewriting Systems, Type Free Languages

DOI: 10.3233/FI-1982-53-404

Citation: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 279-299, 1982

Authors: Kramosil, Ivan

Article Type: Research Article

Abstract: In this paper we investigate the Monte-Carlo method for estimation of the unknown probability of a random event on the ground of relative frequencies and under the condition that random sampling is replaced by a deterministic side input producing binary sequences of high algorithmic complexity. It is proved that if this complexity exceeds a treshold value, the sequences may be used in the Monte-Carlo methods instead of random samples as the obtained estimates converge to the estimated probability when the length of these binary sequences increases.

Keywords: Monte-Carlo methods, random sampling, statistical estimates, pseudo-random numbers, universal Turing machine, binary strings, algorithmic complexity

DOI: 10.3233/FI-1982-53-405

Citation: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 301-312, 1982

Authors: Urzyczyn, Paweł

Article Type: Research Article

Abstract: We show an example of a first-order complete theory T, with no locally finite models and such that every program schema, total over a model of T, is strongly equivalent in that model to a loop-free schema. For this purpose we consider the notion of an algorithmically prime model, what enables us to formulate an analogue to Ryll-Nardzewski Theorem.

Keywords: program schemas, algorithmically trivial and algorithmically prime structures, eds-complete theories

DOI: 10.3233/FI-1982-53-406

Citation: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 313-318, 1982

Authors: Imieliński, Tomasz

Article Type: Research Article

Abstract: In the paper properties of en extension of a query language for incomplete information systems by a new descriptor “known(i)” are examined. Introducing a new descriptor “known(i)” allows to distinguish the objects about which our knowledge is complete, and increases the descriptive power of the language. It is shown that every query (term) is equivalent to a term in a simpler canonical form. Completeness results are presented.

Keywords: query languages, incomplete information, data bases

DOI: 10.3233/FI-1982-53-407

Citation: Fundamenta Informaticae, vol. 5, no. 3-4, pp. 319-342, 1982