1,721,049 research outputs found
Chomsky Hierarchies of Pattern Languages
No full textWe consider languages of patterns of any type in the Chomsky hierarchy. Two hierarchies of language families which are "parallel" with the Chomsky hierarchy are obtained, , one when using "pure" variables, and one when using transformations
On the Power of Pictorial Languages
No full textWe continue the study of pictorial languages as formalized in Ref. 1 (based on the operations of shifting and superposing elementary pictures). If the pixels are superposed without composing their colors, then we produce only recursive languages. When the colors of the superposed pixels can be composed, then any array grammar can be simulated (hence, all recursively enumerable languages can be obtained). Bidimensional pictorial frameworks with a nonrecursive membership problem are obtained in the restricted case when (1) we do not allow the superposition of nontransparent pixels, excepting the fact that (2) for each color there is a complementary color, which, superposed on the original one, leads to a transparent pixel
Grammars Working on Layered Strings
No full textWe consider first an operation with strings and languages suggested by superposed windows on the computer screen (as well as by cryptographic systems of Richelieu type): we assume that the strings contain usual symbols as well as a transparent symbol. Superposing two strings (justified to left), we produce a new string consisting of the symbols visible from above. This operation is investigated as an abstract operation on strings, then it is used in building a variant of grammar systems with the component grammars working on the layers of an array of strings. Each grammar can rewrite only symbols in its layer which are visible from above. The language generated in this way consists of strings of the visible symbols, produced at the end of a derivation. The power of several variants of these generative mechanisms is investigated for the case of two layered strings. When a matrix-like control on the work of the component grammars is considered, then a characterization of recursively enumerable languages is obtained
Pattern Control on Derivation in Context-Free Rewriting
No full textStarting from a grammatical approach to the task of producing variations of given music themes, where the patterns of the obtained themes are prescribed in advance, we define grammars with the derivation controlled by patterns. Usual context-free grammars and pure context-free grammars are considered, with various types of control: with patterns associated to each rule or only checking the last word in a derivation, with one pattern in each case or with several patterns which have to be simultaneously observed, etc. Mainly the generative power of the obtained grammars is examined. Some open problems naturally occurring in this framework are mentioned. (An intriguing one concerns the question whether or not the hierarchy of languages obtained as simultaneous interpretations of n patterns is infinite; we have only found that two patterns are stronger than one.
Membrane Systems with Promoters/Inhibitors
No full textThe computational model of membrane computing (formalized through membrane systems, also called P systems) is based on the way that biological membranes define compartments, each having its set of molecules and (enzymes enhancing) reactions, with compartments communicating through the transport of molecules through membranes. In this paper we augment the basic model of membrane systems with promoters and inhibitors, which formalize the reaction enhancing and reaction prohibiting roles of various substances (molecules) present in cells. We formalize such membrane systems with promoters/inhibitors and investigate their basic properties. In particular we establish universality results, i.e., we provide characterizations of recursively enumerable sets (of vectors of natural numbers) using these systems. It turns out that systems with promoters/inhibitors achieve universal computations without using the standard “auxiliary” features of membrane systems, for instance, without using catalysts
Successful Visual Human-Computer Interaction is Undecidable
No full textWe propose a model of visual interactive computing and define a family of visual languages which abstract some of its features. We prove that the problem whether or not successful communications exist is not decidable. (A human-computer communication by means of a visual language is successful when all human commands, in the form of pictures composed of icons, are correctly interpreted and answered by the computer.) The proof makes use of a codification of the Post Correspondence Problem by means of icons and pictures. This result warns about possible limitations of a purely algorithmic treatment of interactive computing via visual language
Splicing Normalization and Regularity
No full textSeries in Discrete Mathematics and Theoretical Computer Science, Vol. 15, London, 200
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
