1,720,995 research outputs found
Algebraic Aspects of Families of Fuzzy Languages
Get PDFWe study operations on fuzzy languages such as union, concatenation, Kleene , intersection with regular fuzzy languages, and several kinds of (iterated) fuzzy substitution. Then we consider families of fuzzy languages, closed under a fixed collection of these operations, which results in the concept of full Abstract Family of Fuzzy Languages or full AFFL. This algebraic structure is the fuzzy counterpart of the notion of full Abstract Family of Languages that has been encountered frequently in investigating families of crisp (i.e., non-fuzzy) languages. Some simpler and more complicated algebraic structures (such as full substitution-closed AFFL, full super-AFFL, full hyper-AFFL) will be considered as well. In the second part of the paper we focus our attention to full AFFL's closed under iterated parallel fuzzy substitution, where the iterating process is prescribed by given crisp control languages. Proceeding inductively over the family of these control languages, yields an infinite sequence of full AFFL-structures with increasingly stronger closure properties
Review of "G. Paun & G. Rozenberg, Prescribed teams of grammars. Acta Inform. 31 (1994) 525-537"
No full textA Characterization of ET0L and EDT0L Languages
Get PDFThere exists a PT0L language such that the following holds. A language is an ET0L language if and only if there exists a mapping induced by an a-NGSM (nondeterministic generalized sequential machine with accepting states) such that . There exists an infinite collection of EPDT0L languages () such that the family EDT0L is characterized in the following way. A language is an EDT0L language if and only if there exists , a homomorphism and a regular language such that
Complexity Aspects of Iterated Rewriting:A Survey
Get PDFWe present an overview of results on the complexity of the membership problem for families of languages generated by several types of generalized grammars. In particular, we consider generalized grammars based on context-independent rewriting, i.e., grammars consisting of a finite number of (non)deterministic substitutions, and on iterated context-dependent rewriting , i.e., grammars composed of a finite number of transductions. We give some conditions on the classes of these substitutions and transductions that guarantee the solvability of this membership problem within certain time and space bounds. As consequences we obtain additional closure properties of some time- and space-bounded complexity classes
A Simple Discrete System with Chaotic Behavior
Get PDFWe discuss the behavior of a particular discrete system, viz. Post's system of tag with alphabet , deletion number , and rules: , . As initial strings we consider all strings of length less than or equal to 15 as well as all ``worst case'' inputs of the form with
An Alternative Formulation of Cocke-Younger-Kasami's Algorithm
Get PDFWe provide a reformulation of Cocke-Younger-Kasami's algorithm for recognizing context-free languages in which there are no references either to indices of table entries or to the length of the input string. Some top-down analogues of this functional approach are discussed as well
Fibonacci-like Differential Equations with a Polynomial Non-Homogeneous Part
Get PDFWe investigate non-homogeneous linear differential equations of the form where is either a polynomial or a factorial polynomial in . We express the solution of these differential equations in terms of the coefficients of , in the initial conditions, and in the solution of the corresponding homogeneous differential equation with
Time and Space Complexity of Inside-Out Macro Languages
No full textStarting from Fischer's IO Standard Form Theorem we show that for each inside-out (or IO-) macro language , there is a -free IO-macro grammar with the following property: for each in , there is a derivation of of length at most linear in the length of . Then we construct a nondeterministic log-space bounded auxiliary pushdown automaton which accepts in polynomial time. Therefore the IO-macro languages are (many-one) log-space reducible to the context-free languages. Consequently, the membership problem for IO-macro languages can be solved deterministically in polynomial time and in space
Review of "G. File: Machines for attribute grammars, Inform. and Control 69 (1986) 41-124"
Get PDFAn attribute grammar is a context-free grammar in which the occurrences of nonterminals in the productions are provided with certain variables, called attributes, over some semantic domain. In addition to each production of this context-free grammar G, so-called semantic rules are given in order to compute the value of the attributes. Each attribute grammar induces a (string-) translation, i.e. a set of pairs (w; s), where w is a sentence of L(G) with derivation tree T and s is the value of some designated attribute of the root of T. This value of s can be computed by applying the semantic rules recursively [cf. D. E. Knuth, Math. Systems Theory 2 (1968), no. 2, 127{145; RZhMat 1971:11 B923; correction, ibid. 5 (1971), no. 1, 95{96; RZhMat 1971:11 B923]. Another translation, called tree-translation, induced by an attribute grammar consists of all pairs (T; s). In the paper under review two types of machines are introduced to characterize these translations, viz., the temporary [resp. permanent] register tree pushdown transducer. Roughly speaking, they are pushdown transducers extended with registers to compute the values of the attributes. These machines dene the same class of string-translations as attribute grammars, but with respect to three-translations they are more powerful than attribute grammars. Finally, an extended model of attribute grammar is introduced which denes the same class of tree-translations as these machines
Review of "G. Paun & G. Rozenberg, Prescribed teams of grammars. Acta Inform. 31 (1994) 525-537"
Get PDF- …
