Fundamenta Informaticae - Volume 112, issue 2-3

Authors: Bordihn, Henning | Freund, Rudolf | Hirvensalo, Mika | Holzer, Markus | Kutrib, Martin | Otto, Friedrich

Article Type: Research Article

DOI: 10.3233/FI-2011-582

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. i-ii, 2011

Authors: Bianchi, Maria Paola | Mereghetti, Carlo | Palano, Beatrice | Pighizzini, Giovanni

Article Type: Research Article

Abstract: We investigate and compare the descriptional power of unary probabilistic and nondeterministic automata (pfa's and nfa's, respectively). We show the existence of a family of languages hard for pfa's in the following sense: For any positive integer d, there exists a unary d-cyclic language such that any pfa accepting it requires d states, as the smallest deterministic automaton. On the other hand, we prove that there exist infinitely many languages having pfa's which from one side do not match a known optimal state lower bound and, on the other side, they are smaller than nfa's which, in turn, are smaller …than deterministic automata. Show more

Keywords: probabilistic automata, nondeterministic automata, descriptional complexity, unary languages

DOI: 10.3233/FI-2011-583

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 119-135, 2011

Authors: Csuhaj-Varjú, Erzsébet | Masopust, Tomáš | Vaszil, György

Article Type: Research Article

Abstract: We introduce and investigate blackhole pushdown automata, variants of pushdown automata, where a string can always be pushed to the pushdown, but only a given depth of the pushdown content is remembered (the rest of the pushdown content is either canceled or becomes inaccessible). We also study blackhole variants of regulated pushdown automata, where the automaton in some distinguished states checks the form of its pushdown content against a given control language. We present characterizations of several language families in terms of these constructs.

Keywords: Pushdown automaton, regulation, computational power

DOI: 10.3233/FI-2011-584

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 137-156, 2011

Authors: Dassow, Jürgen | Truthe, Bianca

Article Type: Research Article

Abstract: In this paper, we study networks of evolutionary processors where the filters are chosen as special regular sets. We consider networks where all the filters belong to a set of languages that are accepted by deterministic finite automata with a fixed number of states. We show that if the number of states is bounded by two, then every recursively enumerable language can be generated by such a network. If the number of states is bounded by one, then not all regular languages but non-context-free languages can be generated.

Keywords: Evolutionary processors, language generating networks, state complexity

DOI: 10.3233/FI-2011-585

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 157-170, 2011

Authors: Huschenbett, Martin

Article Type: Research Article

Abstract: We study weighted trace automata with weights in strong bimonoids. Traces form a generalization of words that allow to model concurrency; strong bimonoids are algebraic structures that can be regarded as “semirings without distributivity”. A very important example for the latter are bounded lattices, especially non-distributive ones. We show that if both operations of the bimonoid are locally finite, then the classes of recognizable and mc-rational trace series coincide and, in general, are properly contained in the class of c-rational series. Moreover, if, in addition, in the bimonoid the addition is idempotent and the multiplication is commutative, then all three …classes coincide. Show more

Keywords: weighted automata, concurrency, multi-valued logics, traces, formal power series

DOI: 10.3233/FI-2011-586

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 171-191, 2011

Authors: Jurdziński, Tomasz

Article Type: Research Article

Abstract: Growing context-sensitive grammars were introduced in 1986 as a restricted variant of context-sensitive grammars, where all productions are length increasing. Several interesting properties of these grammars have been shown since then, including polynomial time complexity of the membership problem and machine model characterizations. Various characterizations of the model, efficient recognition algorithm and the properties of its deterministic variant (possessing a characterization by string-rewriting systems) justify the practical value. Moreover, as pointed out by McNaughton in 1999, growing context-sensitive grammars complement the Chomsky hierarchy in a very natural way. This article reviews results on this topic and proposes some open problems.

Keywords: Chomsky hierarchy, growing grammars, length-reducing automata

DOI: 10.3233/FI-2011-587

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 193-217, 2011

Authors: Leupold, Peter | Otto, Friedrich

Article Type: Research Article

Abstract: We study the McNaughton families of languages that are specified by four different variants of monadic string-rewriting systems: strictly monadic systems, monadic systems, inverse context-free systems, and generalized monadic systems. In the general case these four variants yield the same McNaughton family of languages, which coincides with the class of context-free languages. In the case of confluent systems, however, we obtain two McNaughton families by showing that special rules, that is, rules with empty right-hand side, are not needed. This implies that in this situation strictly monadic systems are as expressive as monadic systems, and inverse context-free systems are as …expressive as generalized monadic systems. The McNaughton family defined by the former systems is contained in the McNaughton family that is defined by the latter systems, and this inclusion is proper if and only if the former family is not closed under inverse alphabetic morphisms. Finally, we show that the latter family is a proper subclass of the class of deterministic context-free languages. Show more

DOI: 10.3233/FI-2011-588

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 219-238, 2011

Authors: Maletti, Andreas

Article Type: Research Article

Abstract: In this second part of the survey, we present the application of weighted extended top-down tree transducers in machine translation, which is the automatic translation of natural language texts. We present several formal properties that are relevant to machine translation and evaluate the weighted extended top-down tree transducer along those criteria. In addition, we demonstrate how to extract rules for an extended top-down tree transducer from existing linguistic data and how to obtain suitable rule weights automatically from similar information. Overall, the aim of the survey is twofold. It should provide a synopsis that illustrates how theory (tree transducers) and …practice (machine translation) interact on this particular example. Secondly, it presents a uniform and simplified treatment of the rule extraction and training algorithms that is accessible to the nonexpert. Additional details can be found in the original results that are referenced throughout the text. Show more

DOI: 10.3233/FI-2011-589

Citation: Fundamenta Informaticae, vol. 112, no. 2-3, pp. 239-261, 2011