Fundamenta Informaticae - Volume 8, issue 2

Article Type: Other

DOI: 10.3233/FI-1985-8201

Citation: Fundamenta Informaticae, vol. 8, no. 2, pp. i-vi, 1985

Authors: Păun, Gheorghe

Article Type: Research Article

Abstract: One defines a class of contextual grammars “intermediate” between the conditional contextual grammars and the contextual grammars with bounded choice (the addition of each context depends on a prefix and a suffix of the current string which belong to a given pair of languages associated with this context). The paper investigates the generative capacity of these grammars compared to other contextual language families and with families in Chomsky hierarchy.

Keywords: Chomsky grammars, Marcus contextual grammars

DOI: 10.3233/FI-1985-8202

Citation: Fundamenta Informaticae, vol. 8, no. 2, pp. 151-161, 1985

Authors: Dańko, Wiktor

Article Type: Research Article

Abstract: In the paper the following problem stated by Tajtslin in 1979 is investigated: Let A = ⟨ A; f1 , …, fn ; r1 , …, rm ⟩ be a structure. Are there functions f′ 1 , …, f′ p and relations r′ 1 , …, r′ q definable in A by means of algorithms such that every function relation definable over A by an algorithm is first-order definable in A + = ⟨ A; f1 , …, fn , f′ 1 …, …, f′ p ; r1 , …, rm , r′ 1 , …, r′ q ⟩? Show more

Keywords: algorithms, programmability, logics of programs, algorithmic definability

DOI: 10.3233/FI-1985-8203

Citation: Fundamenta Informaticae, vol. 8, no. 2, pp. 163-197, 1985

Authors: Wiweger, Antoni

Article Type: Research Article

Abstract: Concepts of category theory are applied to the investigation of some relations between automata and abstract games. The notion of a coloured automaton introduced in this paper provides a framework for a unified treatment of automata and abstract games. Both games and automata can be viewed as special cases of this general notion. A coloured automaton is defined to be a Mealy automaton with the additional structure of a coloured graph on the set of inputs. Various categories of coloured automata, automata, and games are described. It is shown that some forgetful functors between these categories have left adjoints, and …explicit constructions of these adjoints are given. The main result is Theorem 5.5 which describes a construction of a free abstract game over a coloured automaton satisfying some additional conditions. Show more

Keywords: automaton, coloured automaton, coloured qraph, abstract game, category, free pair, adjoint functor

DOI: 10.3233/FI-1985-8204

Citation: Fundamenta Informaticae, vol. 8, no. 2, pp. 199-224, 1985

Authors: Jacopini, Giuseppe | Venturini Zilli, Marisa

Article Type: Research Article

Abstract: This paper, a revised version of the one [4] presented at the Logic Colloquium ’82, concerns closed unsolvable λ -terms, named easy , which are terms such that they can be consistently equated to arbitrary closed ones. Some general results are obtained, mainly sufficient or necessary conditions for proving that an unsolvable λ -term is easy.

Keywords: lambda calculus, unsolvable terms, easy terms, extension of a theory

DOI: 10.3233/FI-1985-8205

Citation: Fundamenta Informaticae, vol. 8, no. 2, pp. 225-233, 1985

Authors: Ostravský, Jan

Article Type: Research Article

Abstract: In this paper we solve inference problem for languages on two particular classes BC , BS . For any language (V,L) ∈ Bj , j ∈ {s,c}, and any natural number i, we define a grammar Gj i (V,L) in an effective way. We prove that (V,L) ∈ Bj iff there exists a natural number i0 such that Gj i (V,L) = Gj i0 (V,L) for any i ⩾ i0 ; the grammar Gj i0 (V,L) generates (V,L).

Keywords: special generalized grammar, special grammar, language generated by the (generalized) special grammar, norms, monotone productions or c-productions, context-free productions or s-productions, special grammar with s-productions, special grammar with c-productions, languages of the classes BC and BS, reducing operator, fragment of the language, relation Ti(V,L), relation Tji(V,L), special grammar Gji(V,L)

DOI: 10.3233/FI-1985-8206

Citation: Fundamenta Informaticae, vol. 8, no. 2, pp. 235-252, 1985

Authors: Wong, S.K.M. | Ziarko, Wojciech

Article Type: Research Article

Abstract: In information retrieval, it is common to model index terms and documents as vectors in a suitably defined vector space. The main difficulty with this approach is that the explicit representation of term vectors is not known a priori. For this reason, the vector space model adopted by Salton for the SMART system treats the terms as a set of orthogonal vectors. In such a model it is often necessary to adopt a separate, corrective procedure to take into account the correlations between terms. In this paper, we propose a systematic method (the generalized vector space model) to compute term …correlations directly from automatic indexing scheme. We also demonstrate how such correlations can be included with minimal modification in the existing vector based information retrieval systems. Show more

Keywords: information retrieval, vector space models

DOI: 10.3233/FI-1985-8207

Citation: Fundamenta Informaticae, vol. 8, no. 2, pp. 253-267, 1985