The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We consider a language of typed λ-expressions with primitives including nondeterministic choice operators. Starting from the natural idea that a first order nondeterministic procedure should define a one-many function, we give a reduction system in which ground arguments are shared, in order to avoid some unnatural consequences due to unrestricted application of the copy-rule. This is achieved by...
A word w is called repetitive if it contains two consecutive equal factors ; otherwise w is nonrepetitive. Thus the word abacacb is repetitive, and abcacbabcbac is nonrepetitive. There is no nonrepetitive word of length 4 over a two letter alphabet ; on the contrary, there exist infinite nonrepetitive words over a three letter alphabet. Most of the explicitly known infinite nonrepetitive words are...
Hierarchies of abstract data types are specified by axioms which are positive formulas consisting of universally and existentially quantified disjunctions and conjunctions of equations. Necessary and sufficient conditions for the existence of terminal algebras are investigated. Furthermore, some advantages of disjunctions and existential quantifiers within the laws are discussed and the usefulness...
We generalize Ginsburg and Rose's characterization of g-s-m mappings to the broader family of so-called subsequential functions, introduced by M.P.Schützenberger
A controlled rewriting system over an alphabet X is a finite set of rules vi → wi (l⩽i⩽n) with vi , wi in X* such that |vi|<|wi| , each rule being associated with a regular language Ri ... X*. Given such a system, f ⇒ g means that f=αviβ and g=αwiβ for some i, α in Ri , β in X*. The system is said to be injective if and only if f ⇒ g ⇐ f′ implies f=f′. Controlled rewriting systems are a special...
Both (operational or denotational) semantics and type theories for λ-calculus induce in a natural way equivalence relations between terms. The aim of the present paper is to show that in some cases the semantic and functional equivalences coincide.
An algorithm is presented which implements mutual exclusion for a system of n processes by means of protocol-controled communication on a (n + const.)-valued shared buffer. The algorithm uses a generalized test-and-set instruction, and schedules processes into their critical sections on a first-come, first-serve basis. The method can be extended to accomodate any queueing discipline defined as a function...
The paper gives another understanding of the two-level grammar formalism: any two-level grammar can be splitted into two parts — a context-free "syntax" and an equational "semantics". It has been shown that in the case of a repetition-free and regular based two-level grammar one can always solve the equations assigned to each derivation of the resulting CF grammar. This suggests...
A common tool for proving the termination of programs is the well-founded set, a set ordered in such a way as to admit no infinite descending sequences. The basic approach is to find a termination function that maps the values of the program variables into some well-founded set, such that the value of the termination function is continually reduced throughout the computation. All too often, the termination...
This paper discusses the problem of factoring program proofs into a proof of correctness of an abstract algorithm followed by a proof of correct implementation at the concrete level. The problem of showing that diagrams commute is simplified by the introduction of a set of abstract entities that define constraints on the abstract operations. Correctness at the concrete level is then shown by exhibiting...
The family of G-trivial languages is investigated. This family is a generalization of L-trivial and R-trivial languages, a relationship analogous to the one between generalized definite languages and the definite and reverse definite languages. Characterizations of G-trivial languages are given in terms of their syntactic monoids, various congruence relations, and the (finite) automata which recognize...
This paper investigates some of the underlying axioms allowing the fixpoint-semantics approach to hold for tree-like recursion schemes. The notions of scheme and interpretation are generalized. The axioms satisfied by "algebraic theories" are shown to be adequate for the definition of the notion of an interpretation. It is also shown that in order to provide the semantics of arbitrary finite...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.