Wyniki wyszukiwania - BazTech

1

Generative Capacity of Contextual Grammars with Subregular Selection Languages

Truthe Bianca

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 1-2

123--150

EN

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.

2

Unavoidable Sets, Prefix Graphs and Regularity of Circular Splicing Languages

Bonizzoni Paola, De Felice Clelia, Zaccagnino Rocco, Zizza Rosalba

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

81--95

EN

Circular splicing systems are a mathematical model, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A, an initial set I of circular words, and a set R of rules. A circular splicing language is a language generated by a circular splicing system. An open problem is to characterize regular circular splicing languages and the corresponding circular splicing systems. In this framework an important role is played by unavoidable sets. These sets have been considered in several contexts. In particular, Ehrenfeucht, Haussler and Rozenberg (1983) proved the following generalization of a famous Higman’s theorem: the quasi-order induced by insertions of words from a fixed finite set is a well-quasi-order if and only if the finite set is unavoidable. In this paper we survey the known relations between unavoidable sets and regular circular languages. Motivated by these connections we give an alternative and simpler proof of the Ehrenfeucht, Haussler and Rozenberg result. Our proof is strongly based on a known characterization of unavoidable sets in terms of graphs associated with them.

3

On the Density of Regular Languages

Koga Toshihiro

Fundamenta Informaticae

|

2019

|

Vol. 168, nr 1

45--49

EN

Let ∑ be an alphabet which has at least two symbols. The density of L ⊆ ∑* is defined as D(L) := limn |L ∩ ∑n|/|∑n| ∈ [0, 1], provided that the limit exists. In 2015, R. Sin’ya has discovered an interesting relation between regular languages and their densities: If L ⊆ ∑* is a regular language, then D(L) = 0 if and only if there exists s ∈ ∑* such that ∑*s∑* ∩ L = Ø. In this paper, we give a simple proof of this theorem, obtaining it as a simple consequence of the pumping lemma for regular languages.

4

Development of a flexible Mizar tokenizer and parser for information retrieval system

Nakasho Kazuhisa

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

77--80

EN

In this paper, we explain the development of a new Mizar tokenizer and parser program as a component of a search system that works on the Mizar Mathematical Library. The existing Mizar tokenizer and parser can handle only an article as a whole written in the Mizar language, however, the newly developed program can deal with a snippet of a Mizar article. In particular, since it is possible to handle a snippet of an article without specifying a vocabulary section of an environment part, it is expected that user input efforts will be greatly reduced.

5

State Complexity of Multiple Catenations

Caron P., Luque J.-G., Patrou B.

Fundamenta Informaticae

|

2018

|

Vol. 160, nr 3

255--279

EN

We improve some results relative to the state complexity of the multiple catenations described by Gao and Yu. In particular we nearly divide by 2 the size of the alphabet needed for witnesses. We also give some refinements to the algebraic expression of the state complexity, which is especially complex with this operation. We obtain these results by using peculiar DFAs defined by Brzozowski.

6

Two-Dimensional Limited Context Restarting Automata

Krtek L., Mráz F.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

309--340

EN

Motivated by possible machine learning of picture languages, we introduce a new twodimensional automaton called two-dimensional limited context restarting automaton. Our model is a simplification of the two-dimensional restarting tiling automaton, from which it differs in that it does not require to scan input pictures in a fixed order. We show that the two-dimensional limited context restarting automaton is equally powerful as the two-dimensional sgraffito automaton. Moreover, the correctness preserving version of the new model, while still being nondeterministic, is equivalent to the deterministic sgraffito automaton. However, the property of being correctness preserving is not even semi-decidable for two-dimensional limited context restarting automata.

7

Strongly Limited Automata

Pighizzini G.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

369--392

EN

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. When d ≥2, these devices characterize the class of context-free languages. In this paper we consider restricted versions of these models which we call strongly limited automata, where rewrites, head reversals, and state changes are allowed only at certain points of the computation. Those restrictions are inspired by a simple algorithm for accepting Dyck languages on 2-limited automata. We prove that the models so defined are still able to recognize all context-free languages. We also consider descriptional complexity aspects. We prove that there are polynomial transformations of context-free grammars and pushdown automata into strongly limited automata and vice versa.

8

Reversible Queue Automata

Kutrib M., Malcher A., Wendlandt M.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

341--368

EN

Deterministic finite automata equipped with the storage medium of a queue are investigated towards their ability to perform reversible computations, that is, computations in which every occurring configuration has exactly one successor and exactly one predecessor. A first result is that any queue automaton can be simulated by a reversible one. So, reversible queue automata are as powerful as Turing machines. Therefore it is of natural interest to impose time restrictions to queue automata. Here we consider quasi realtime and realtime computations. It is shown that every reversible quasi realtime queue automaton can be sped up to realtime. On the other hand, under realtime conditions reversible queue automata are less powerful than general queue automata. Furthermore, we exhibit a lower bound of ...[formula] time steps for realtime queue automata witness languages to be accepted by any equivalent reversible queue automaton. We study the closure properties of reversible realtime queue automata and obtain similar results as for reversible deterministic pushdown automata. Finally, we investigate decidability questions and obtain that all commonly studied questions such as emptiness, finiteness, or equivalence are not semidecidable for reversible realtime queue automata. Furthermore, it is not semidecidable whether an arbitrary given realtime queue automaton is reversible.

9

On the Computational Complexity of Partial Word Automata Problems

Holzer M., Jakobi S., Wendlandt M.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

267--289

EN

We consider the computational complexity of problems related to partial word automata. Roughly speaking, a partial word is a word in which some positions are unspecified and a partial word automaton is a finite automaton that accepts a partial word language-here the unspecified positions in the word are represented by a "hole" symbol ◊ . A partial word language L' can be transformed into an ordinary language L by using a ◊-substitution. In particular, we investigate the complexity of the compression or minimization problem for partial word automata, which is known to be NP-hard. We improve on the previously known complexity on this problem, by showing PSPACE-completeness. In fact, it turns out that almost all problems related to partial word automata, such as, e.g., equivalence and universality, are already PSPACE- complete. Moreover, we also study these problems under the further restriction that the involved automata accept only finite languages. In this case, the complexities of the studied problems drop from PSPACE-completeness down to coNP-hardness and containment in ∑P2 depending on the problem investigated.

10

Distinguishability Operations and Closures

Câmpeanu C., Moreira N., Reis R.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

243--266

EN

Given a language L, we study the language of words D(L), that distinguish between pairs of different left quotients of L. We characterize this distinguishability operation, show that its iteration has always a fixed point, and we generalize this result to operations derived from closure operators and Boolean operators. For the case of regular languages, we give an upper bound for the state complexity of the distinguishability operation, and prove its tightness. We show that the set of minimal words that can be used to distinguish between different left quotients of a regular language L has at most n - 1 elements, where n is the state complexity of L, and we also study the properties of its iteration. We generalize the results for the languages of words that distinguish between pairs of different right quotients and two-sided quotients of a language L.

11

Expressibility of many-valued linguistics constructions

Frankowski S.

Journal of Applied Computer Science

|

2015

|

Vol. 23, nr 2

7--19

EN

The main problem of this paper is a comparison between different kinds of many-valued and two valued linguistics constructions. We are trying to approximate probabilistic grammars by using ones which contain rational numbers only. Moreover, it is shown that probabilistic grammar can be simulated by regularly controlled grammar.

12

On the Power of Accepting Networks of Evolutionary Processors with Special Topologies and Random Context Filters

Dassow J., Manea F., Truthe B.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

1--35

EN

In this paper, we approach the problemof accepting all recursively enumerable languages by accepting networks of evolutionary processors (ANEPs, for short) with a fixed architecture. More precisely, we show that every recursively enumerable language can be accepted by an ANEP with an underlying graph in the form of a star with 13 nodes or by an ANEP with an underlying grid with 13 × 4 = 52 nodes as well as by ANEPs having underlying graphs in the form of a chain, a ring, or a wheel with 29 nodes each. In all these cases, the size and form as well as the general working strategy of the constructed networks do not depend on the accepted language; only the rewriting rules and the filters associated to each node of the networks depend on this language. Noteworthy is also the fact that the filtering process is implemented using random context conditions only. Our results answer problems which were left open in a paper published by J. Dassow and F. Manea at the conference on Descriptional Complexity of Formal Systems (DCFS) 2010 and improve a result published by B. Truthe at the conference on Non-Classical Models of Automata and Applications (NCMA) 2013.

13

Limited Automata and Context-Free Languages

Pighizzini G., Pisoni A.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

157--176

EN

Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2- limited automata coincides with the class of deterministic context-free languages.

14

A Formal Language Model of DNA Polymerase Enzymatic Activity

Enaganti S. K., Kari L., Kopecki S.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

179--192

EN

We propose and investigate a formal language operation inspired by the naturally occurring phenomenon of DNA primer extension by a DNA-template-directed DNA Polymerase enzyme. Given two DNA strings u and v, where the shorter string v (called primer) is Watson-Crick complementary and can thus bind to a substring of the longer string u (called template) the result of the primer extension is a DNA string that is complementary to a suffix of the template which starts at the binding position of the primer. The operation of DNA primer extension can be abstracted as a binary operation on two formal languages: a template language L1 and a primer language L2. We call this language operation L1-directed extension of L2 and study the closure properties of various language classes, including the classes in the Chomsky hierarchy, under directed extension. Furthermore, we answer the question under what conditions can a given language of target strings be generated from a given template language when the primer language is unknown. We use the canonic inverse of directed extension in order to obtain the optimal solution (the minimal primer language) to this question.

15

Clearing Restarting Automata

Černo P., Mráz F.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

17-54

EN

Restarting automata were introduced as a model for analysis by reduction, which is a linguistically motivated method for checking correctness of a sentence. We propose a new restricted version of restarting automata called clearing restarting automata with a very simple definition but simultaneously with interesting properties with respect to their possible applications. The new model can be learned very efficiently from positive examples and its stronger version can be used to learn effectively a large class of languages. We relate the class of languages recognized by clearing restarting automata to the Chomsky hierarchy.

16

5'→3' Watson-Crick AutomataWith Several Runs

Leupold P., Nagy B.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

71-91

EN

5'→3' WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that the expressive power of these automata increases with every additional run that they can make, both for deterministic and non-deterministic machines. This defines two incomparable infinite hierarchies of language classes between the regular and the context-sensitive languages. These hierarchies are complemented with classes defined by several restricted variants of 5'→3' WK-automata like stateless automata. Finally we show that several standard problems are undecidable for languages accepted by 5'→3' WK-automata in only one run, for example the emptiness and the finiteness problems.

17

A Formal Syntax of Natural Languages and the Deductive Grammar

Wang Y.

Fundamenta Informaticae

|

2009

|

Vol. 90, nr 4

353-368

EN

This paper presents a formal syntax framework of natural languages for computational linguistics. The abstract syntax of natural languages, particularly English, and their formal manipulations are described. On the basis of the abstract syntax, a universal language processing model and the deductive grammar of English are developed toward the formalization of Chomsky's universal grammar in linguistics. Comparative analyses of natural and programming languages, as well as the linguistic perception on software engineering, are discussed. A wide range of applications of the deductive grammar of English have been explored in language acquisition, comprehension, generation, and processing in cognitive informatics, computational intelligence, and cognitive computing.

18

On Descriptional Complexity of Partially Parallel Grammars

Masopust T., Meduna A.

Fundamenta Informaticae

|

2008

|

Vol. 87, nr 3-4

407-415

EN

This paper presents some new results concerning the descriptional complexity of partially parallel grammars. Specifically, it proves that every recursively enumerable language is generated (i) by a four-nonterminal scattered context grammar with no more than four non-context-free productions, (ii) by a two-nonterminal multisequential grammar with no more than two selectors, or (iii) by a three-nonterminalmulticontinuous grammar with no more than two selectors.

19

Bag Context Tree Grammars

Drewes F., du Toit C., Ewert S., van der Merwe B., van der Walt A.

Fundamenta Informaticae

|

2008

|

Vol. 86, nr 4

459-480

EN

We introduce bag context as a device for regulated rewriting in tree grammars. Bag context represents information that is not part of a developing tree, but instead evolves separately during a derivation. We present several results. First, we give some normal forms and equivalent formulations for bag context tree grammars. Then we compare bag context tree grammars to their random context counterparts. We show that bag context is strictly more powerful than random context; in doing so, we show that the class of bag context tree languages is the closure of the class of random context tree languages under linear top-down tree transductions. Finally, we consider the structural limitations of bag context tree grammars. We establish a necessary condition for languages generated by bag context tree grammars, and use it to present a tree language that cannot be generated by such a grammar. Moreover, we show that the class of bag context tree languages is incomparable with the class of branching synchronization tree languages.

20

Array Grammars with Contextual Operations

Subramanian K.G., Van Do Long, Chandra P.H., Quyen N.D.

Fundamenta Informaticae

|

2008

|

Vol. 83, nr 4

411-428

EN

In this paper, we consider a class of two-dimensional array grammars, called parallel contextual array grammars, that extend the contextual operations on strings to arrays in a natural way and generate languages of pictures of rectangular arrays. Several classes of these array grammars and the resulting families of picture languages are considered. Necessary conditions for picture languages to be contained in these classes are obtained and the relations between these families are also established.