Wyniki wyszukiwania - BazTech

1

Word Matrix Rewriting Systems

Bisht Raj Kishor, Nishida Taishin Yasunobu, Yamamoto Kouhei

Fundamenta Informaticae

|

2019

|

Vol. 166, nr 3

199--226

EN

We introduce word matrices and word matrix rewriting systems. A word matrix over an alphabet ∑ of k letters is a k × n rectangular matrix with entries of nonnegative integers. A word matrix represents a set of words. The i-th row corresponds to the i-th letter in ∑ (thus the letters in ∑ are ordered as a1, . . . , ak). Each column vector represents a set of words which have the vector as the Parikh vector. The word matrix represents the concatenation of all sets represented by column vectors. A word matrix rewriting system consists of a set of rewriting rules which rewrite word matrices and an initial word matrix (the axiom). A word matrix rewriting system generates a set of word matrices by iterated applications of rules to the axiom and generates a language which is the union of all sets represented by the matrices. A word matrix rewriting system is a kind of (restricted) parallel rewriting system with scattered context dependency and hence can generate non-context-free languages, e.g., {anbncn | 1 ≤ n}. We define variants of word matrix rewriting systems and show an infinite hierarchy among them. Some language theoretical problems, including relations among Chomsky hierarchy, closure properties, and decision properties, are considered.

2

Enumeration of words in context-free languages using Haskell

Wieczorek W.

Studia Informatica

|

2017

|

Vol. 38, nr 1B

5--17

EN

The cross-section enumeration problem is to list all words of length n in a language L in lexicographic order. We present the Haskell implementation of an algorithm for the cross-section enumeration problem for any language defined by a context-free grammar without unit productions and without λ-productions.

PL

Jednym z rozważanych problemów kombinatorycznych jest wyliczenie w porządku leksykograficznym wszystkich słów o długości n należących do pewnego języka L. W niniejszym artykule zaprezentowano algorytm – wraz ze stosownym kodem w języku Haskell – służący do takiego wyliczania. Zakładamy, że język L zdefiniowany jest za pomocą gramatyki bezkontekstowej bez produkcji jednostkowych i bez λ-produkcji.

3

Filtrations of Formal Languages by Arithmetic Progressions

Mousavi H., Shallit J.

Fundamenta Informaticae

|

2013

|

Vol. 123, nr 2

135--142

EN

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL’s that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness.

4

Nonterminal Complexity of Some Operations on Context-Free Languages

Dassow J., Stiebe R.

Fundamenta Informaticae

|

2008

|

Vol. 83, nr 1-2

35-49

EN

We investigate context-free languages with respect to the measure Var of descriptional complexity, which gives the minimal number of nonterminals necessary to generate a language. More specifically, we consider the behaviour of this measure with respect to language-theoretic operations. For given numbers c1,c2,... ,cn and an n-ary operation t on languages, we discuss the range of Var(t(L1,L2,... , Ln)) where, for 1 ≤ i ≥ n, Li is a context-free language with Var(Li)=ci. The operations under discussion are the six AFL-operations: union, concatenation, Kleene-closure, homomorphisms, inverse homomorphisms and intersections by regular sets.

5

On Winning Conditions of High Borel Complexity in Pushdown Games

Finkel O.

Fundamenta Informaticae

|

2005

|

Vol. 66, nr 3

277--298

EN

In a recent paper [19,20] Serre has presented some decidable winning conditions [...] of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs. We answer in this paper several questions which were raised by Serre in [19,20]. We study classes \mathbbCn(A), defined in [20], and show that these classes are included in the class of non-ambiguous context free w-languages. Moreover from the study of a larger class \mathbbCln(A) we infer that the complements of languages in \mathbbCn(A) are also non-ambiguous context free w-languages. We conclude the study of classes \mathbbCn(A) by showing that they are neither closed under union nor under intersection. We prove also that there exists pushdown games, equipped with winning conditions in the form [...], where the winning sets are not deterministic context free languages, giving examples of winning sets which are non-deterministic non-ambiguous context free languages, inherently ambiguous context free languages, or even non context free languages.

6

Contextual Grammars with Uniform Sets of Trajectories

Okhotin A., Salomaa K.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

341-351

EN

A uniform contextual grammar with contexts shuffled along trajectories uses the same set of trajectories for each context. We prove that when the alphabet has at least two symbols, the non-uniform contextual grammars with trajectories are strictly more powerful than the uniform variant. For unary alphabets the generative power of the two variants coincides, and the same is true for grammars where the sets of trajectories are regular or context-free.

7

On a construction of context-free gramma

Martinek P.

Fundamenta Informaticae

|

2000

|

Vol. 44, Nr 3

245-264

EN

The grammatical inference problem is solved for the class of context-free languages. A context-free language is supposed to be given by means of all its strings. Considering all strings of length bounded by k, context-free grammars G(j,k) with 1 < j < k are constructed. A continual increasing of the index k leads to an infinite sequence. It is proved that G(j,k) are equivalent for all j > j(o), k > k(o) with some positive integers j(o), k(o). Moreover, the equivalences among these grammars can be recognized on the basis of involved nonterminals and productions only.