Fundamenta Informaticae - Volume 180, issue 1-2

Authors: Hirvensalo, Mika | Mráz, František | Průša, Daniel

Article Type: Other

DOI: 10.3233/FI-2021-2031

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. v-vi, 2021

Authors: Fernau, Henning | Kutrib, Martin | Wendlandt, Matthias

Article Type: Research Article

Abstract: We study the computational and descriptional complexity of self-verifying pushdown automata (SVPDA) and self-verifying realtime queue automata (SVRQA). A self-verifying automaton is a nondeterministic device whose nondeterminism is symmetric in the following sense. Each computation path can give one of the answers yes , no , or do not know . For every input word, at least one computation path must give either the answer yes or no , and the answers given must not be contradictory. We show that SVPDA and SVRQA are automata characterizations of so-called complementation kernels, that is, context-free or realtime nondeterministic queue automaton languages …whose complement is also context free or accepted by a realtime nondeterministic queue automaton. So, the families of languages accepted by SVPDA and SVRQA are strictly between the families of deterministic and nondeterministic languages. Closure properties and various decidability problems are considered. For example, it is shown that it is not semidecidable whether a given SVPDA or SVRQA can be made self-verifying. Moreover, we study descriptional complexity aspects of these machines. It turns out that the size trade-offs between nondeterministic and self-verifying as well as between self-verifying and deterministic automata are non-recursive. That is, one can choose an arbitrarily large recursive function f , but the gain in economy of description eventually exceeds f when changing from the former system to the latter. Show more

DOI: 10.3233/FI-2021-2032

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 1-28, 2021

Authors: Holzer, Markus | Kutrib, Martin | Otto, Friedrich

Article Type: Research Article

Abstract: A two-sided extension of strictly locally testable languages is presented. In order to determine membership within a two-sided strictly locally testable language, the input must be scanned from both ends simultaneously, whereby it is synchronously checked that the factors read are correlated with respect to a given binary relation. The class of two-sided strictly locally testable languages is shown to be a proper subclass of the even linear languages that is incomparable to the regular languages with respect to inclusion. Furthermore, closure properties of the class of two-sided strictly locally testable languages and decision problems are studied. Finally, it is …shown that two-sided strictly k -testable languages are learnable in the limit from positive data. Show more

DOI: 10.3233/FI-2021-2033

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 29-51, 2021

Authors: Malcher, Andreas

Article Type: Research Article

Abstract: Insertion systems or insertion grammars are a generative formalism in which words can only be generated by starting with some axioms and by iteratively inserting strings subject to certain contexts of a fixed maximal length. It is known that languages generated by such systems are always context sensitive and that the corresponding language classes are incomparable with the regular languages. On the other hand, it is possible to generate non-semilinear languages with systems having contexts of length two. Here, we study decidability questions for insertion systems. On the one hand, it can be seen that emptiness and universality are decidable. …Moreover, the fixed membership problem is solvable in deterministic polynomial time. On the other hand, the usually studied decidability questions such as, for example, finiteness, inclusion, equivalence, regularity, inclusion in a regular language, and inclusion of a regular language turn out to be undecidable. Interestingly, the latter undecidability results can be carried over to other models which are basically able to handle the mechanism of inserting strings depending on contexts. In particular, new undecidability results are obtained for pure grammars, restarting automata, clearing restarting automata, and forgetting automata. Show more

Keywords: Insertion systems, decidability questions, pure grammars, clearing restarting automata, restarting automata, forgetting automata

DOI: 10.3233/FI-2021-2034

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 53-76, 2021

Authors: Otto, Friedrich

Article Type: Research Article

Abstract: A complete taxonomy is presented for restarting automata without auxiliary symbols. In this taxonomy, the language classes that are accepted by deterministic and nondeterministic, monotone, weakly monotone, and non-monotone, shrinking and length-reducing restarting automata are compared to each other with respect to inclusion. As it turns out, the 45 types of restarting automata considered yield 29 different classes of languages. By presenting a collection of rather simple example languages, it is shown that, for any two of these language classes ℒ1 and ℒ2 , the class ℒ1 is a subclass of ℒ2 if and only if ℒ1 …is defined by a type of restarting automaton that is a restriction of a type of restarting automaton that defines the class ℒ2 . Show more

DOI: 10.3233/FI-2021-2035

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 77-101, 2021

Authors: Pighizzini, Giovanni | Prigioniero, Luca

Article Type: Research Article

Abstract: Non-self-embedding grammars are a subclass of context-free grammars which only generate regular languages. The size costs of the conversion of non-self-embedding grammars into equivalent finite automata are studied, by proving optimal bounds for the number of states of nondeterministic and deterministic automata equivalent to given non-self-embedding grammars. In particular, each non-self-embedding grammar of size s can be converted into an equivalent nondeterministic automaton which has an exponential size in s and into an equivalent deterministic automaton which has a double exponential size in s. These costs are shown to be optimal. Moreover, they do not change if the …larger class of quasi-non-self-embedding grammars, which still generate only regular languages, is considered. In the case of letter bounded languages, the cost of the conversion of non-self-embedding grammars and quasi-non-self-embedding grammars into deterministic automata reduces to an exponential of a polynomial in s . Show more

Keywords: Context-free grammars, Descriptional complexity, Bounded languages

DOI: 10.3233/FI-2021-2036

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 103-122, 2021

Authors: Truthe, Bianca

Article Type: Research Article

Abstract: A contextual grammar is a language generating mechanism inspired by generating sentences in natural languages. An existing string can be extended to a new string of the language by adjoining a context before and behind the string or by inserting it into the string around some subword. The first mode is called external derivation whereas the second mode is called internal derivation. If conditions are given, around which words which contexts can be adjoined, we speak about contextual grammars with selection. We give an overview about the generative capacity of contextual grammars (working externally or internally) where the selection languages …belong to subregular language classes. All languages generated by contextual grammars where all selection languages are elements of a certain subregular language family form again a language family. We compare such families which are based on finite, monoidal, nilpotent, combinational, definite, suffix-closed, ordered, commutative, circular, non-counting, power-separating, or union-free languages, or based on languages defined by restrictions regarding the descriptional complexity. Show more

Keywords: Contextual grammars, subregular language families, formal languages, generative power

DOI: 10.3233/FI-2021-2037

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 123-150, 2021

Authors: Wang, Qichao

Article Type: Research Article

Abstract: Weighted restarting automata have been introduced to study quantitative aspects of computations of restarting automata. In earlier works we studied the classes of functions and relations that are computed by weighted restarting automata. Here we use them to define classes of formal languages by restricting the weight associated to a given input word through an additional requirement. In this way, weighted restarting automata can be used as language acceptors. First, we show that by using the notion of acceptance relative to the tropical semiring, we can avoid the use of auxiliary symbols. Furthermore, a certain type of word-weighted restarting automata …turns out to be equivalent to non-forgetting restarting automata, and another class of languages accepted by word-weighted restarting automata is shown to be closed under the operation of intersection. This is the first result that shows that a class of languages defined in terms of a quite general class of restarting automata is closed under intersection. Finally, we prove that the restarting automata that are allowed to use auxiliary symbols in a rewrite step, and to keep on reading after performing a rewrite step can be simulated by regular-weighted restarting automata that cannot do this. Show more

Keywords: weighted restarting automata, non-forgetting restarting automata, semiring, relative acceptance condition, closure properties

DOI: 10.3233/FI-2021-2038

Citation: Fundamenta Informaticae, vol. 180, no. 1-2, pp. 151-177, 2021