Fundamenta Informaticae - Volume 64, issue 1-4

Authors: Davidson, Michael | Ilie, Lucian

Article Type: Research Article

Abstract: We consider the data compression using antidictionaries and give algorithms for faster compression and decompression. While the original method of Crochemore et al. uses finite transducers with ε-moves, we (de)compress using ε-free transducers. This is provably faster, assuming data non-negligibly compressible, but we have to consider the overhead due to building the new ma-chines. In general, they can be quadratic in size compared to the ones allowing ε-moves; we prove this bound optimal as it is …reached for de Bruijn words. However, in practice, the size of the ε-free machines turns out to be close to the size of the ones allowing ε-moves and therefore we can achieve significantly faster (de)compression. We show our results for the files in Calgary corpus. Show more

Keywords: Text compression, antidictionaries, finite transducers, ε-free transducers, de Bruijn words

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 119-134, 2005

Authors: Dinu, Liviu P.

Article Type: Research Article

Abstract: In this paper we introduce a metric for measuring the similarity between two classifications which differ by their constitutive elements. Our measure is inspired from natural language and genomics where the most important information is carried by the first part of the unit. We extend the measure to words and to rooted (un)labelled general trees. We use this metric to analyze the syllabic similarity of Romance languages.

Keywords: Rank distance, similarities, tree-to-tree distance, computing with words, classifications, similarity of Romance languages

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 135-149, 2005

Authors: Dömösi, Pál | Kudlek, Manfred

Article Type: Research Article

Abstract: Using well-known characterizations of regular languages, on the basis of known iteration lemmas, new iteration lemmas for regular languages are given.

Keywords: Regular language, finite automaton, pumping lemma

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 151-157, 2005

Authors: Fernau, Henning | Freund, Rudolf | Holzer, Markus

Article Type: Research Article

Abstract: The main result proved in this paper shows that the natural embedding of any recursively enumerable one-dimensional array language in the two-dimensional space can be characterized by the projection of a two-dimensional array language generated by a contextual array grammar working in the t-mode and with norm one. Moreover, we show that any recursively enumerable one – dimensional array language can even be characterized by the projection of a two-dimensional array language generated by a contextual …array grammar working in the t-mode where in the selectors of the contextual array productions only the ability to distinguish between blank and non-blank positions is necessary; in that case, the norm of the two-dimensional contextual array grammar working in the -mode cannot be bounded. Show more

Keywords: Arrays, array grammars, contextual grammars, shape

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 159-170, 2005

Authors: Gramatovici, Radu | Manea, Florin

Article Type: Research Article

Abstract: We extend the result from [8] by giving also a concrete polynomial parsing algorithm for a class of languages generated by a variant of contextual grammars, namely local internal contextual grammars with context-free choice.

Keywords: Contextual grammar, parsing, polynomial complexity

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 171-183, 2005

Authors: Head, Tom

Article Type: Research Article

Abstract: The evolution of life on our planet is briefly reviewed emphasizing the roles played by light and language. Life and language are regarded as a single interlocking system which light has stimulated to serve as an organ of cosmic awareness. Light first rewarded life with energy. Light then stimulated life to grow upward from the surface of our planet. Life is now integrating into itself detailed knowledge of the cosmos by decoding the vast store of …information contained in celestial light. Show more

Keywords: Light & life, astrobiology, cosmos, awareness

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 185-189, 2005

Authors: Ipate, Florentin | Bălănescu, Tudor

Article Type: Research Article

Abstract: The paper formalizes two types of refinement for finite state machines: OR refinement and p-OR refinement. For each such type of refinement, it shows that, if the implementation is also constructed through a process of refinement, then the application of Chow's W test generation method can be distributed into smaller chunks, thus diminishing the effort devoted to testing and the size of the final test set.

Keywords: Finite state machines, testing, test generation, verification, W-method

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 191-203, 2005

Authors: Ipate, Florentin | Holcombe, Mike

Article Type: Research Article

Abstract: One of the strengths of using a stream X-machine to specify a system is that, under certain well defined conditions, it is possible to produce a test set that is guaranteed to determine the correctness of the implementation. This testing method assumes that the processing functions are correctly implemented, therefore it only tests the integration of the processing functions implementations into the system implementation. This paper uses a case study to illustrate how this method can …be extended so that it will no longer require the implementations of the processing functions to be proved correct before the actual system testing can take place. Instead, the testing of the processing functions is performed along with the integration testing. Show more

Keywords: Testing, test generation, verification, stream X-machines, finite state machines

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 205-216, 2005

Authors: Jurdziński, Tomasz | Otto, Friedrich | Mráz, František | Plátek, Martin

Article Type: Research Article

Abstract: It is known that for (right-) monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right-left-monotone. Moreover, we present a transformation of this kind of restarting automata into contextual grammars with regular selection.

Keywords: Contextual grammars, restarting automata, right-left monotonicity

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 217-228, 2005

Authors: Kappes, Martin

Article Type: Research Article

Abstract: Bracketed contextual grammars are a variant of Marcus' contextual grammars with an induced Dyck-structure to control the derivation process and to provide derivation trees. Many variants of bracketed contextual grammars have been proposed in literature. In this paper, we study the relationship between various mechanisms in such grammars, in particular the number of brackets, the used selector languages, and the ability to introduce more than a single pair of brackets in a derivation step, with respect …to the generative capacity of the resulting models. Show more

Keywords: Contextual grammars, bracketed contextual grammars

Citation: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 229-239, 2005