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.
The method of well founded structures for proving termination of programs is extended to concurrent programs. The more complicated case is when a program terminates only for fair executions. Different versions of fairness are introduced: Impartiality, Fairness and Justice, and Methods for proving their termination are presented.
It is proved that a natural generalization of chess to an n×n board is complete in exponential time. This implies that there exist chess-positions on an n×n chess-board for which the problem of determining who can win from that position requires an amount of time which is at least exponential in n.
Let E be the set of all simple arithmetic expressions of the form E(x)=xT1...Tk, where x is a nonnegative integer variable and each Ti is a multiplication or integer division by a positive integer constant. We investigate the complexity of the inequivalence and the bounded inequivalence problems for expressions in E. (The bounded inequivalence problem is the problem of deciding for arbitrary expressions...
A string y is in C(x), the commutative image of a string x, if y is a permutation of the symbols in x. A language L is Parikh-bounded if L contains a bounded language B and all x in L have a corresponding y in B such that x is in C(y). The central result in this paper is that if L is context-free it is also Parikh-bounded. Parikh's theorem follows as a corollary. If L is not bounded but is a Parikh-bounded...
The notion of the Parikh mapping is generalized by considering numbers of occurrences of segments of a fixed length instead of considering numbers of letters (i.e. segments of length one) only as is done in connection with the Parikh mappings. It is easily seen that the families of regular and context-free languages make difference with respect to these generalized Parikh mappings. On the other hand,...
The paper has two parts. In Part I, we shall present Chomsky-Schützenberger theorems for the families of context-sensitive (CS)and recursive-enumerable (RE) languages. The results are obtained by generalizing the construction of the Dyck set from a "content-free" one to a "content-sensitive" one. Also presented are fixed-point characterization theorems for CS and...
We define a method for mechanically constructing verification condition generators from a useful class of Hoare logics. Any verification condition generator constructed by our method is shown to be sound and deduction-complete with respect to the associated Hoare logic. The method has been implemented.
Consider the connection between denotational semantics for a language with goto statements and flow diagrams for programs in such a language. The main point of interest is that the denotational semantics uses a recursively defined environment to give the meaning of labels, while a flow diagram merely has a jump to the appropriate program point. A simple reduction called “indirection elimination” strips...
There exist many equivalence decision algorithms for classes of grammars, program schemes, transducers which follow the general pattern of the Korenjak-Hopcroft algorithm for deciding the equivalence of simple deterministic grammars. An axiomatic framework is presented which points out the essence of the Korenjak-Hopcroft algorithm and applies to numerous situations.
We give a sufficient condition for proving strong termination in Combinatory Logic and Rewriting Systems which solves an open problem [Böh 77]. We also compare, in the context of general rewriting systems, the power of that condition and other known methods, as the recursive path orderings and simplification orderings, presenting original results. A new technique for proving strong termination,...
Limitations, such as right-linearity, on the form of rules in a term-rewriting system are shown to restrict the class of derivations that must be considered when determining whether or not the system terminates for all inputs. These restricted derivations, termed "chains", are obtained by attempting to apply rules to the final terms of derivations that issue from the left-hand side of rules...
We provide four semantics for a small programming language involving unbounded (but countable) nondeterminism. These comprise an operational one, two denotational ones based on the Egli-Milner and Smyth orders, respectively, and a weakest precondition semantics. Their equivalence is proved. We also introduce a Hoare-like proof system for total correctness and show its soundness and completeness in...
We exhibit a large class of machines with polynomial time decidable containment and equivalence problems. The machines in the class accept more than the regular sets. We know of no other class (different from the finite-state acceptors) for which the containment and equivalence problems have been shown polynomially decidable. We also discuss the complexity of other decision problems.
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.