Abstract A case study comparison is made of four declarative programming languages: Miranda, Miranda is a trademark of Research Software Ltd. Fp, Equations and Prolog. The case study is used as a vehicle to assess both expressiveness and performance aspects of these languages. In expressive power, Miranda is judged to be superior, Equations and Prolog are rated about even in second place, and Fp is judged least expressive. Performance was quite poor for all the available implementations. Reasons for this are explored and the implications are discussed.

Two formal models of string patterns are introduced. One is based on an idealization of patterns as systems of set equations, and the other is based on an abstract procedure model of a pattern. Each model is then shown to yield certain insights and in particular is used to explore an operation not commonly considered in conjunction with string patterns. These two new pattern operations are (set) complementation and reversal of cursor direction. Each is shown to have a dramatic effect on both the expressive power and the complexity of patterns in which they are included. These pattern operations may in turn be regarded as extensions to the usual formal language definition mechanisms (i.e., grammars and equation systems), and our results interpreted in terms of formal language description.

Abstract The presentation of an abstract data type by a series of equational axioms has become an accepted specification mechanism. Verifying the correctness of such specifications has been recognized as a problem troubling their use. A means is presented for experimenting with a directly executable version of the axioms without having to choose representations for the data structures or describe algorithms for the operations.

There is a wide range of applications for string processing and SNOBOL4 (Griswold, et al. [1971]) has come to be the most widely implemented and accepted language for such applications. No doubt one of the principle reasons for this acceptance is the data structure around which the language is organized, the string pattern. This structure together with the associated pattern matching process provide great flexibility. Nevertheless it has been widely recognized in informal terms that the pattern matching process is often grossly inefficient (Ripley & Griswold [1975], Dewar & McCann [1977]) and that the pattern structure is notoriously difficult to explain and use (Ripley & Griswold [1975], Stewart [1975]). Each of these areas of difficulty relates to such things as two modes of operation (quick-full scan), problems with left-recursion, heuristics in the scan, etc. Some difficulties are inherent with string patterns but many are not; we feel the developments described here help to clarify this situation.In section 2 we describe the formal model upon which we base this work. This allows the careful analysis of the variety of sets of strings which may be specified by the patterns which we admit and deduction to be made concerning the possibility/impossibility of algorithms of interest. With SNOBOL4 it has been the case that the careful definition of the meaning of a pattern is in terms of the actions taken by the pattern matching algorithm. This has led to the incorporation of idiosyncrasies of a particular algorithm into the understanding of the pattern structure. This seems akin to using a compiler as the definition of a programming language and we believe it is important to future progress to have other alternatives.In section 3 we point out that the worst-case execution time of the usual SNOBOL pattern matching algorithm is exponential in the length of the subject string, even on some quite simple patterns. We then present an algorithm whose worst-case time is polynomial and that operates on patterns which include a true set complement operator. As side benefits we find that the algorithm is not multi-modal and correctly handles the null string as an alternative and left-recursion.In order to conserve space we will assume throughout this paper that the reader is familiar with the idea of a string pattern in the sense that it is described in Griswold et al. [1971]. Also it is probably necessary that the reader have some general knowledge of the formal languages area.

article Free Access Share on 𝒮-Semigroups of Automata Authors: A. C. Fleck Department of Computer Science, The University of Iowa, Iowa City, Iowa Department of Computer Science, The University of Iowa, Iowa City, IowaView Profile , S. T. Hedetniemi Department of Computer Science, The University of Iowa, Iowa City, Iowa Department of Computer Science, The University of Iowa, Iowa City, IowaView Profile , R. H. Oehmke Department of Mathematics, The University of Iowa, Iowa City, Iowa Department of Mathematics, The University of Iowa, Iowa City, IowaView Profile Authors Info & Claims Journal of the ACMVolume 19Issue 1Jan. 1972 pp 3–10https://doi.org/10.1145/321679.321681Published:01 January 1972Publication History 6citation314DownloadsMetricsTotal Citations6Total Downloads314Last 12 Months9Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The algebraic properties of automata are investigated.The automorphism group of an automaton and a certain associated semigroup are the devices used ir~ the study.Some relationships among various structures of the automaton, its group and semigroup are noted.

This paper persues a discussion of certain algebraic properties of automata and their relationship to the structure (i.e., properties of the next state function) of automata. The device which is used for this study is the association of a group with each automaton. We introduce functions on automata and study the group of an automaton, a representation for the group elements and the direct product of automata. Finally, for a certain class of automata a necessary and sufficient condition, in terms of the group of the automaton, is given for insuring that an automaton can be represented as a direct product.