306,338 research outputs found
C-tree systolic automata
No full textA new type of systolic automaton is introduced, its structural properties, such as homogeneity and stability, are investigated and the class of languages accepted by these automata is studied. This class of languages, in the nondeterministic case, contains a large subclass of the Lindenmayer EPT0L languages. A characterization of the defined model is also given in terms of sequential machines
Coding for a long silence
No full textWe determine the exact exponential asymptotics of the maximum number of n-length binary strings any two of which differ in the following strong sense: there must be a coordinate in which one of them has a 1 in correspondence with a predetermined position within a "long run" of zeros in the other string. We discuss some generalizations and implications of this result
Synchronized Bottom-up Tree Automata and L-Systems.
No full textIn this paper a new type of bottom-up tree automaton, c a l l e d synchronized
bottom-up tree automaton, is considered. This automaton processes a
tree in a bottom-up way and one level at a time. Moreover, more than one
t r a n s i t i o n function i s allowed, but only one o~ them at a time can be
applied t o nodes at the same level of a tree.
The tree language recognized by these automata are t h e images, under
projection, of the set o f derivation t r e e s of EPTOL languages
Going Beyond Counting First Authors in Author Co-citation Analysis
No full textThe 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
Systolic Y-tree automata: closure properties and decision problemsFundamentals of Computation Theory
No full textClasses of Y-trees are defined so that closure properties hold for families of languages accepted by deterministic [or nondeterministic] systolic automata over a Y-tree T, called , if and, in some cases, only if the underlying Y-tree T is in the class. Results of the same type are proved also for decision problems. Moreover a new nonacceptability criterion for is given and used to prove some non closure properties
A Kleene-like charachterization of languages accepted by Systolic Binary Tree Automata.
No full textWe present a Kleen-like characterization of the class of languages accepted by systolic binary tree automata, L(SBTA). This characterization uses union, intersection, restricted concatenation, restricted concatenation closure, and finite substitution closure. The restrictions we impose on the operator of concatenation are purely in terms of the length of the words to be concatenated. (C) 1994 Academic Press, Inc
Hierarchies of Primitive Recursive Wordsequence Functions: Comparisons and Decision Problems.
No full textAbstractIn this paper we consider wordsequence functions, i.e., functions of the type ƒ: Σ∗′ → Σ∗‵ where Σ is a finite alphabet and r ⩾ 0, s > 0. By starting with finite sets of basic functions and by taking the closure with respect to composition, cylindrification and iteration, we give some characterizations of primitive recursive wordsequence functions. We define some hierarchies of length ω2 of these functions by bounding the number of successive compositions and the depth of the nested iterations in the definitions of the functions. In such a manner we obtain refinements of the Axt, Grzegorczyk and Meyer and Ritchie generalized hierarchies of length ω of primitive recursive wordfunctions defined by Von Henke, Indermark and Weihrauch (1972).We consider Loop programs on words (see Ausiello and Moscarini (1976)) by allowing more than one output register, and we prove that the class of functions computed by these programs coincides with the class of primitive recursive wordsequence functions. The hierarchies of functions induce some hierarchies of programs.For the case of functions ƒ: Σ∗′ → Σ∗, our hierarchies are compared with the Axt et al. generalized hierarchies.We also compare our hierarchies with storage hierarchies, and we analyze the power of the Loop programs as acceptors.Finally, we state some decidability results for the considered classes
- …
