Linear parallel processing machines I
Von Kunze, M
99 GENERAL AND MISCELLANEOUS//MATHEMATICS, COMPUTING, AND INFORMATION SCIENCE; PARALLEL PROCESSING; PROGRAMMING LANGUAGES; ALGORITHMS; AUTOMATION; MATHEMATICAL LOGIC; PROGRAMMING; 990200* - Mathematics & Computers
As is well-known, non-context-free grammars for generating formal languages happen to be of a certain intrinsic computational power that presents serious difficulties to efficient parsing algorithms as well as for the development of an algebraic theory of contextsensitive languages. In this paper a framework is given for the investigation of the computational power of formal grammars, in order to start a thorough analysis of grammars consisting of derivation rules of the form aB ..-->.. A/sub 1/ ... A /sub n/ b/sub 1/...b /sub m/ . These grammars may be thought of as automata by means of parallel processing, if one considers the variables as operators acting on the terminals while reading them right-to-left. This kind of automata and their 2-dimensional programming language prove to be useful by allowing a concise linear-time algorithm for integer multiplication. Linear parallel processing machines (LP-machines) which are, in their general form, equivalent to Turing machines, include finite automata and pushdown automata (with states encoded) as special cases. Bounded LP-machines yield deterministic accepting automata for nondeterministic contextfree languages, and they define an interesting class of contextsensitive languages. A characterization of this class in terms of generating grammars is established by using derivation trees with crossings as a helpful tool. From the algebraic point of view, deterministic LP-machines are effectively represented semigroups with distinguished subsets. Concerning the dualism between generating and accepting devices of formal languages within the algebraic setting, the concept of accepting automata turns out to reduce essentially to embeddability in an effectively represented extension monoid, even in the classical cases.
Institut fur Theoretische Informatik, Technische Hochschule Darmstadt, Alexanderstr. 24, 6100 Darmstadt
Germany
1984-01-01
German
Journal Article
Journal Name: Elektron. Informationsverarb. Kybern.; (German Democratic Republic); Journal Volume: 20:1
Medium: X; Size: Pages: 9-39
https://doi.org/
Journal ID: CODEN: EIVKA
EDB-85-129071
2010-05-11
5508976