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.
In this article we study the time complexity of the recognition problem for some “moderate” extensions of context-free grammars or pushdown automata. It is well known that, for a given context-free grammar G, the recognition problem “x ∈ L(G)” can be decided in 0(|x|)3 steps by a suitable algorithm. How do extensions behave in this respect? In particular, do they admit recognition algorithms whose...
A useful approach to the design and description of complex data management systems is the decomposition of a system into a hierarchically organized collection of levels. In such a system, transaction management is distributed among the levels. This paper presents the fundamental theory of multi-level concurrency control and recovery. A model for the computation of multi-level transactions is introduced...
In this paper we study the implication and the finite implication problems for data dependencies. When all dependencies are total the problems are equivalent and solvable but are NP-hard, i.e., probably computationally intractable. For non-total dependencies the implication problem is unsolvable, and the finite implication problem is not even partially solvable. Thus, there can be no formal system...
Languages for models of nested relations and complex objects have been attracting considerable attention recently. Some of these languages are algebraic, others are calculus based, some are logic programming oriented. This paper describes these languages and surveys recent results about the expressive power of these languages. The emphasis is on completeness issues. The expressive power of the languages...
In this paper we describe an architecture that provides for automating and monitoring the flow of control and document over the Internet among different organizations, thereby creating a platform necessary to describe higher order processes involving several organizations and companies. The higher order process is designed through a graphical user interface and is executed through cooperating agents...
One of the central concepts supported by object-oriented databases is isa relationship. Its intuitive simplicity is deceptive. In reality, this term denotes several concepts, such as subtyping, subset relationships, and inheritance of structure and/or behavior. Each of these is non-trivial, and their interaction may be quite subtle. This paper deals with subtyping and its properties, in the context...
In this paper Valiant's decision procedure for equivalence of deterministic finite-turn pushdown machines is improved upon. The improved equivalence test is: Given two mahcines, one constructs a pushdown machine that simulates them simultaneously and accepts a string iff it is accepted by exactly one of them. The given machines are equivalent iff the simulating pda accepts the empty language. The...
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.