Fundamenta Informaticae - Volume 99, issue 4

Authors: Bergstra, Jan A. | Middelburg, Cornelis A.

Article Type: Research Article

Abstract: We take a process component as a pair of an interface and a behaviour. We study the composition of interacting process components in the setting of process algebra. We formalize the interfaces of interacting process components by means of an interface group. An interesting feature of the interface group is that it allows for distinguishing between expectations and promises in interfaces of process components. This distinction comes into play in case components with both client …and server behaviour are involved. Show more

Keywords: interface group, process component, process algebra

DOI: 10.3233/FI-2010-254

Citation: Fundamenta Informaticae, vol. 99, no. 4, pp. 355-382, 2010

Authors: Bloom, Stephen L. | Ésik, Zoltan

Article Type: Research Article

Abstract: An algebraic tree T is one determined by a finite system of fixed point equations. The frontier Fr(T ) of an algebraic tree T is linearly ordered by the lexicographic order <ℓ If (Fr(T) <ℓ) is well-ordered, its order type is an algebraic ordinal. We prove that the algebraic ordinals are exactly the ordinals less than ω^{&omega;} ^{&omega;} .

DOI: 10.3233/FI-2010-255

Citation: Fundamenta Informaticae, vol. 99, no. 4, pp. 383-407, 2010

Authors: Deorowicz, Sebastian

Article Type: Research Article

Abstract: The problem of finding a constrained longest common subsequence (CLCS) for the sequences A and B with respect to the sequence P was introduced recently. Its goal is to find a longest subsequence C of A and B such that P is a subsequence of C. Most of the algorithms solving the CLCS problem are based on dynamic programming. Bit-parallelism is a technique of using single bits in a machine word for concurrent computation. We propose the first bit-parallel …algorithm computing a CLCS and/or its length which outperforms the other known algorithms in terms of speed. Show more

Keywords: constrained longest common subsequence, longest common subsequence, dynamic programming, bit-parallel algorithm

DOI: 10.3233/FI-2010-256

Citation: Fundamenta Informaticae, vol. 99, no. 4, pp. 409-433, 2010

Authors: De Mol, Liesbeth

Article Type: Research Article

Abstract: In this paper a detailed proofwill be given of the solvability of the halting and reachability problem for binary 2-tag systems.

Keywords: v-Tag systems, halting problem, reachability problem, non-universality

DOI: 10.3233/FI-2010-257

Citation: Fundamenta Informaticae, vol. 99, no. 4, pp. 435-471, 2010

Authors: Masopust, Tomáš

Article Type: Research Article

Abstract: Scattered context grammars with three nonterminals are known to be computationally complete. So far, however, it was an open problem whether the number of parallel productions can be bounded along with three nonterminals. In this paper, we prove that every recursively enumerable language is generated by a scattered context grammar with three nonterminals and five parallel productions, each of which simultaneously rewrites no more than nine nonterminals.

Keywords: Scattered context grammars, parallel productions, descriptional complexity, generative power

DOI: 10.3233/FI-2010-258

Citation: Fundamenta Informaticae, vol. 99, no. 4, pp. 473-480, 2010