Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Nonterminal Complexity of Some Operations on Context-Free Languages

Dassow J., Stiebe R.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

35-49

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.

Blind Counter Automata on w-Words

Fernau H., Stiebe R.

Fundamenta Informaticae

2008

Vol. 83, nr 1-2

51-64

This paper generalizes the concept of blind multicounter languages to infinite words. We introduce two different acceptance modes of blind multicounter machines on w-words, called synchrononous and asynchronous acceptance. These acceptance modes are compared with each other and with families of w-languages of the form L=[formula], where Ui, Vi are finitary blind multicounter languages.

Valences in Lindenmayer systems

Fernau H., Stiebe R.

Fundamenta Informaticae

2001

Vol. 45, nr 4

329-358

We investigate four variants of valence regulations incorporated in (limited) Lindenmayer systems, focussing on hierarchical relations and closure properties. Strong connections to well-known families of languages obtained by regulated rewriting are established. We prove several new results on valence transducers and valence generalized sequential machines (gsm). In this way, we can show new properties of ET0L languages, namely the non-closure under quasiintersection, valence gsm mappings and intersection with regular valence languages. Moreover, we solve a question marked as open in by proving that the uniformly k-limited ET0L languages form a full semi-AFL for all k > 1.