1,721,168 research outputs found
Essays on concepts, formalisms, and tools : [a collection of papers dedicated to Leo A. M. Verbeek]
No full textComplexity 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
Programming Language Concepts:The Lambda Calculus Approach
Get PDFThe Lambda Calculus is a formal system, originally intended as a tool in the foundation of mathematics, but mainly used to study the concepts of algorithm and effective computability. Recently, the Lambda Calculus and related systems acquire attention from Computer Science for another reason too: several important programming language concepts can be explained elegantly and can be studied successfully in the framework of the Lambda Calculi. We show this mainly by means of examples. We address ourselves to interested computer scientists who have no prior knowledge of the Lambda Calculus. The concepts discussed include: parameterization, definitions, recursion, elementary and composite data types, typing, abstract types, control of visibility and life-time, and modules
On Covers and Left-Corner Parses
Get PDFA transformation is defined which is a modification of a classic transformation on context-free grammars. By means of this transformation, a proof is presented of the fact that any cycle-free context-free grammar can be left-to-left-corner covered by a non-left-recursive grammar. The proof method is based on the idea to transform the characteristic grammar associated with the simple syntax-directed translation scheme which defines the left-corner parse of the strings generated by the input grammar of the scheme. It is shown that the transformation yields an LL(k) grammar if and only if it is applied to an LC(k) grammar. Finally, some ideas are presented to extend the theory of covers to the semantical covering of attribute grammars
A Representation Principle for Sets and Functions
Get PDFWe present a representation principle for sets and functions, essentially meaning that sets and functions do exist in two different ways: as intuitive objects and as mathematical objects. In this paper some aspects of the relationship between these two ways are investigated. The principle has consequences for the concept of λ-calculus model and for the relationship between such models and set theory
Program Generation through Symbolic Processing
Get PDFComputer algebra systems can be useful when attempting to automatize mathematics. One can use these facilities to assist in the construction of programs for numerical purposes, i.e., to assist in making the problem dependent parts of the software needed to solve a problem numerically. We discuss aspects of the symbolic-numeric interface required to accomplish this. Special attention is given to program generation aspects and to code optimization
Nonterminal Separating Macro Grammars
Get PDFWe extend the concept of nonterminal separating (or NTS) context-free grammar to nonterminal separating -macro grammar where the mode of derivation is equal to "unrestricted". "outside-in' or "inside-out". Then we show some (partial) characterization results for these NTS -macro grammars
From mechanical to theoretical:Aspects of the origins of Theoretical Computer Science
Get PDFSome aspects of the prehistory and the background of Theoretical Computer Science are discussed. We consider the introduction of notations to describe dynamic processes, the change to the algorithmic specification of problems and the attempts to develop programs to make programming easier. The impact of Chomsky's theory of generative grammar, its reception and its relationship with the BNF-description are discussed. Observations on formal language theory and its development into Theoretical Computer Science conclude this (sketchy) survey
- …
