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.
It is known, that over 1-dimensional strings, the expressive power of 2-way multihead (non) deterministic automata and (non) deterministic Transitive Closure formulas is (non) deterministic log space [Ib73, Im88]. However, the subset of formulas needed to simulate exactly k heads is unknown. It is also unknown if the automata and formulas have the same expressive power over more general structures...
We provide a mathematical specification of an extension of Warren's Abstract Machine for executing Prolog to type-constraint logic programming and prove its correctness. In this paper, we keep the notion of types and dynamic type constraints rather abstract to allow applications to different constraint formalisms like Prolog III or CLP(R). This generality permits us to introduce modular extensions...
In this paper we develop a model checking algorithm which is fast in the size of the system. The class of system models we consider are safe persistent Petri nets; the logic is S4, i.e. prepositional logic with a ‘some time’ operator. Our algorithm does not require to construct any transition system: We reduce the model checking problem to the problem of computing certain Parikh vectors,...
The paper indicates how the validity of a fixed first order formula in any finite structure can be checked by realistic local memory parallel computers.
A notion of abstract computational procedure is introduced here which meets the criteria for computation over ADTs, for the general theory of such presented in Part I of this paper. This is provided by a form of generalized recursion theory (g.r.t.) which uses schemata for explicit definition, conditional definition and least fixed point (LFP) recursion in partial functions and functionals of type...
A subsystem of Kripke-Platek set theory proof-theoretically equivalent to primitive recursive arithmetic is isolated; Aczel's (relative) consistency argument for the Anti-Foundation Axiom is adapted to a (related) weak setting; and the logical complexity of the largest bisimulation is investigated.
The cutting plane proof system for proving the unsatisfiability of propositional formulas in conjunctive normalform is based on a natural representation of formulas as systems of integer inequalities. We define a restriction of this system, the cutting plane system with bounded degree of falsity, and show the results: This system p-simulates resolution and has polynomial size proofs for the pigeonhole...
Denotational semantics is the usual mathematical semantics for functional programming languages. It is higher order (H.O.) in the sense that the semantic domain D includes [D → D] as a subdomain. On the other hand, the usual declarative semantics for logic programs is first order (F.O.) and given by the least Herbrand model. In this paper, we take a restricted kind of H.O. conditional rewriting...
We present Ehrenfeucht-Fraïssé games for transitive closure logic (FO + TC) and for quantifier classes in (FO + TC). With this method we investigate the fine structure of positive transitive closure logic (FO + pos TC), and identify an infinite quantifier hierarchy inside (FO + pos TC), formed by interleaving universal quantifiers and TC-operators. It is also shown that transitive closure logic...
The SAT-Problem fot boolean formulas in conjunctive normal form often arises in the area of artificial intelligence, its solution is known as mechanical theorem proving. Most mechanical theorem provers perform this by using a variant of the resolution principle. The time and space complexity of resolution strongly depends on the class of formulas. Horn formulas, where each clause may contain at most...
We define the class of syntactically safe queries in first order languages with function symbols. We prove using ideas from model theory that every model independent query is equivalent to a safe query. This answers a question raised by Topor in [Topor 1987].
We explore connections between polyhedral projection and inference in propositional logic. We formulate the problem of drawing all inferences that contain a restricted set of atoms (i.e., all inferences that pertain to a given question) as a logical projection problem. We show that polyhedral projection partially solves this problem and in particular derives precisely those inferences that can be...
This work investigates a 3-valued semantics, where the third value has the intention ”unimportant” or ”insignificant”. If ”true” and ”unimportant” are the distinguished values, then we can define a tautology in this logics also as follows: a formula is a tautology iff every subformula, which arises by elimination of propositional variables, is a classical tautology. So our system is stable against...
An approach for proving termination of well-moded logic programs is given by transforming a given logic program into a term rewriting system. It is proved that the termination of the derived rewriting system implies the termination of the corresponding logic program for well-moded queries under any selection rule implied by the given modings. The approach is mechanizable using termination orderings...
This is an effort towards an abstract presentation of the formal properties of the way we tend to jump to conclusions from less than fully convincing information. In [6], such properties were presented as families of binary relations between propositional formulas, i.e., built out of preexisting propositional logic. Though the family of cumulative relations is easily amenable to an abstract presentation...
We extend Kozen's theory KA of Kleene Algebra to axiomatize parts of the equational theory of context-free languages, using a least fixed-point operator μ instead of Kleene's iteration operator*. Although the equational theory of context-free languages is not recursively axiomatizable, there are natural axioms for subtheories $$KAF \subseteq KAR \subseteq KAG$$ : respectively, these make...
We introduce an algebraic framework for the equational specification of algebras of types and combinators. A categorical semantics for type specifications is given based on cofibrations of categories of algebras. It is shown that each equational type specification admits an initial model semantics, and we present complete inference systems for type assignments and equations.
Let [0,1] be the real unit interval. A Schauder hat is a Λ-shaped function h:[0,1] → [0,1] whose four pieces are given by linear polynomials with integral coefficients. Rose and Rosser gave an effective method to represent every Schauder hat by a sentence in the infinite-valued calculus of Lukasiewicz. We give an effective method to reduce every sentence ψ with one variable, to an equivalent sentence...
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.