Fundamenta Informaticae - Volume 81, issue 4

Authors: Bedregal, Benjamín René Callejas

Article Type: Research Article

Abstract: By explicit nondeterminism degree of a pushdown automata we mean the maximal number of choices in the transitions of the automata. In this paper we will prove that each pushdown automaton has an equivalent pushdown automaton with degree 1 of explicit nondeterminism, which implies that λ-moves in pda are sufficient to simulate nondeterminism. Moreover, from this normal form (i.e. pda with degree 1 of explicit nondeterminism) we can measure the amount of (implicit) nondeterminism. This measure …will be used to determine a countable infinite hierarchy of contextfree language subclasses, whose bottom is the class of deterministic context-free languages and the top is the class of context-free languages. Show more

Keywords: Pushdown automata, amount of nondeterminism, λ-moves, hierarchy, implicit and explicit nondeterminism

Citation: Fundamenta Informaticae, vol. 81, no. 4, pp. 367-377, 2007

Authors: Diaconescu, Denisa | Georgescu, George

Article Type: Research Article

Abstract: We introduce tense LM_n -algebras and tense MV-algebras as algebraic structures for some tense many-valued logics. A representation theorem for tense LM_n -algebras is proved and the polynomial equivalence between tense LM_3 -algebras (resp. tense LM_4 -algebras) and tense MV_3 -algebras (resp. tense MV_4 -algebras) is established. We study the pairs of dually-conjugated operations on MV-algebras and we use their properties in order to investigate how the axioms of tense …operators are preserved by the Dedekind-MacNeille completion of an Archimedean MV-algebra. A tense many-valued propositional calculus is developed and a completeness theorem is proved. Show more

Keywords: tense Łukasiewicz-Moisil algebra, tense MV-algebra, tense Moisil logic

Citation: Fundamenta Informaticae, vol. 81, no. 4, pp. 379-408, 2007

Authors: Fernández-Camacho, María-Inés | Sánchez-Couso, José-Ramón

Article Type: Research Article

Abstract: We give a generic framework to analyze the average-case running time for computing the so called recurrent properties for pairs of binary search trees. Recurrent properties are algorithms that operate on pairs of trees testing some characteristic on nodes by performing a preorder traversal on both trees. Analysis of recurrent properties using the probability model associated with randomly grown binary search trees leads to wave equations. We use a "normalized" integral equation as a pattern to …model a specific wave equation and investigate the asymptotic behavior of its solution. This methodology is applied to some particular cases of recurrent properties like testing equality, detecting direct occurrences and clashes or pattern matching. Show more

Keywords: Average case analysis, generating function, binary search tree, singularity analysis, integral equation, asymptotic expansion

Citation: Fundamenta Informaticae, vol. 81, no. 4, pp. 409-439, 2007

Authors: Han, Yo-Sub | Wood, Derick

Article Type: Research Article

Abstract: A string x is an outfix of a string y if there is a string w such that x_1 wx_2 = y and x = x_1 x_2 . A set X of strings is outfix-free if no string in X is an outfix of any other string in X. Based on the properties of outfix strings, we develop a polynomial-time algorithm that determines outfix-freeness of regular languages. Note that outfix-free regular languages are always …finite. We consider two cases: 1) a language is given as a finite set of strings and 2) a language is given by a finite-state automaton. Furthermore, we investigate the prime outfix-free decomposition of outfixfree regular languages and design a linear-time algorithm that computes prime outfix-free decomposition for outfix-free regular languages. We also demonstrate the uniqueness of prime outfix-free decomposition. Show more

Keywords: regular languages, outfix-freeness, prime decomposition

Citation: Fundamenta Informaticae, vol. 81, no. 4, pp. 441-457, 2007

Authors: Manea, Florin | Ploscaru, Călina

Article Type: Research Article

Abstract: In this paper we propose a generalization of the Assignment Problem. First, we describe an algorithm, based on network flow techniques, that obtains just one solution of the approached problem; further, we develop an algorithm that is able to find all the solutions. Finally, we discuss how this general form of the Assignment Problem can be applied in solving the Rank Aggregation Problem, in the case of rankings with ties.

Keywords: Assignment Problem, network flow, ranking, Rank Aggregation Problem

Citation: Fundamenta Informaticae, vol. 81, no. 4, pp. 459-471, 2007

Authors: Marciniec, Jacek

Article Type: Research Article

Abstract: In this paperwe explain how to derive learnability of some classes of categorial languages as a consequence of the a property that have unifiable infinite sets of types, namely unification compactness. At first we present an alternate (with respect to [6]) proof of learnability of rigid languages, that introduces our method. Then we prove learnability of the class of semi-rigid languages, which lies in between (learnable) class of rigid languages and (not learnable) class of optimal …(as defined by Kanazawa in [6]) languages. Show more

Keywords: categorial grammar, unification, learnability

Citation: Fundamenta Informaticae, vol. 81, no. 4, pp. 473-484, 2007

Authors: Schott, René | Spehner, Jean-Claude

Article Type: Research Article

Abstract: The starting definitions of araucarias given in [1] contain some mistakes. We give here new definitions which replace Definitions 2.2, 2.3 and 2.4, Theorem 2.1 and Corollary 2.1. The rest of the paper is based on the characterization of araucarias given in Theorem 1.1 and remains true with these corrections.

Citation: Fundamenta Informaticae, vol. 81, no. 4, pp. 485-490, 2007