IFIG Research Report

Dauerhafte URI für die Sammlung

jlupub.ub.uni-giessen.de/handle/jlupub/7512

Bis 1996 unter dem Titel: Bericht / Arbeitsgruppe Informatik

URN: urn:nbn:de:hebis:26-opus-12462

Suchen

Gerade angezeigt 1 - 20 von 57

Existential second-order logic over strings
(1997) Eiter, Thomas; Gottlob, Georg; Gurevich, Yuri
Existential secondorder logic (ESO) and monadic secondorder logic (MSO) have attracted much interest in logic and computer science. ESO is a much more expressive logic over word structures than MSO. However, little was known about the relationship between MSO and syntactic fragments of ESO. We shed light on this issue by completely characterizing this relationship for the prefix classes of ESO over strings, (i.e., finite word structures). Moreover, we determine the complexity of model checking over strings, for all ESOprefix classes. Let ESO(Q) denote the prefix class containing all sentences of the shape 9RQ' where R is a list of predicate variables, Q is a firstorder quantifier prefix from the prefix set Q, and ' is quantifier free. We show that ESO(9 \Lambda 89 \Lambda ) and ESO(9 \Lambda 88) are the maximal standard ESOprefix classes contained in MSO, thus expressing only regular languages. We further prove the following dichotomy theorem: An ESO prefixclass either expresses only regular languages (and is thus in MSO), or it expresses some NPcomplete languages. We also give a precise characterization of those ESOprefix classes which are equivalent to MSO over strings, and of the ESOprefix classes which are closed under complementation on strings.
Enhancing symbolic model checking by AI techniques
(1997) Buccafurri, Francesco; Eiter, Thomas; Gottlob, Georg; Leone, Nicola
Comparisons of different cellular devices and the investigation of their computing power can be made in terms of their capabilities to timeconstruct and timecompute functions. Timeconstruction means that a distinguished cell has to enter distinguished states exactly at the time steps f(1); f(2); : : :, whereas timecomputation requires the distinguished cell to enter a distinguished state firstly at time step f(n), where n is the length of the input. Here the family of functions which are timeconstructible by a twoway unbounded cellular space (F(CS)) is characterized in terms of functions which are timecomputable by one of the simplest cellular devices, a oneway bounded cellular automaton (C (OCA)). Conceptually, timeconstructible functions have to be strictly increasing. Regarding that restriction the reverse characterization is shown, too. Some results concerning the structure of F(CS) and C(OCA) and their relation to formal language recognition are established.
Probalistic and truth-functional many-valued logic programming
(1998) Lukasiewicz, Thomas
We introduce probabilistic manyvalued logic programs in which the implication connective is interpreted as material implication. We show that probabilistic many-valued logic programming is computationally more complex than classical logic programming. More precisely, some deduction problems that are Pcomplete for classical logic programs are shown to be coNPcomplete for probabilistic manyvalued logic programs. We then focus on manyvalued logic programming in Pr*n as an approximation of probabilistic manyvalued logic programming. Surprisingly, manyvalued logic programs in Pr*n have both a probabilistic semantics in probabilities over a set of possible worlds and a truthfunctional semantics in the finitevalued Lukasiewicz logics Ln. Moreover, manyvalued logic programming in Pr*n has a model and fixpoint characterization, a proof theory, and computational properties that are very similar to those of classical logic programming. We especially introduce the proof theory of manyvalued logic programming in Pr*n and show its soundness and completeness.
Decision lists and related Boolean functions
(1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, Kazuhisa
We consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1decision lists has interesting relationships to independently defined classes such as disguised Horn functions, readonce functions, nested differences of concepts, threshold functions, and 2monotonic functions. In particular, 1decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.
On time reduction and simulation in cellular spaces
(1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
We prove a generalized and corrected version of the time reduction theorem for cellular spaces. One basic tool for investigations in this field is the concept of simulation between systems of automata. We propose a general formal definition of the intuitive concept and relate it to the notions which appear in the literature.
On interacting automata with limited nondeterminism
(1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
Oneway and twoway cellular language acceptors with restricted non determinism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to realtime, lineartime and unrestrictedtime computations. A speedup result that allows any lineartime computation to be spedup to realtime is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic language families and [Epsilon]free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions.
Computing intersections of Horn theories for reasoning with models
(1998) Eiter, Thomas; Ibaraki, Toshihide; Makino, Kazuhisa
Modelbased reasoning has been proposed as an alternative form of representing and accessing logical knowledge bases. In this approach, a knowledge base is represented by a set of characteristic models. In this paper, we consider computational issues when combining logical knowledge bases, which are represented by their characteristic models; in particular, we study taking their logical intersection. We present loworder polynomial time algorithms or prove intractability for the major computation problems in the context of knowledge bases which are Horn theories. In particular, we show that a model of the intersection \Sigma of Horn theories \Sigma 1 ; : : : ; \Sigma l, represented by their characteristic models, can be found in linear time, and that some characteristic model of \Sigma can be found in polynomial time. Moreover, we present an algorithm which enumerates the models of \Sigma with polynomial delay. The analogous problem for the characteristic models is proved to be intractable, even if the possible exponential size of the output is taken into account. Furthermore, we show that approximate computation of the set of characteristic models is difficult as well. Nonetheless, we show that deduction from \Sigma is possible for a large class of queries in polynomial time, while abduction turns out to be intractable. We also consider an extension of Horn theories, and prove negative results for the basic questions, indicating that an extension of the positive results beyond Horn theories is not immediate.
Heterogeneous active agents
(1998) Eiter, Thomas; Subrahmanian, V.S; Pick, George
Over the years, many different agent programming languages have been proposed. In this paper, we propose a concept called Agent Programs using which, the way an agent should act in various situations can be declaratively specified by the creator of that agent. Agent Programs may be built on top of arbitrary pieces of software code and may be used to specify what an agent is obliged to do, what an agent may do, and what an agent may not do. In this paper, we define several successively more sophisticated and epistemically satisfying declarative semantics for agent programs, and study the computation price to be paid (in terms of complexity) for such epistemic desiderata. We further show that agent programs cleanly extend well understood semantics for logic programs, and thus are clearly linked to existing results on logic programming and nonmonotonic reasoning. Last, but not least, we have built a simulation of a Supply Chain application in terms of our theory, building on top of commercial software systems such as Microsoft Access and ESRI's MapObject.
One guess one-way cellular arrays
(1998) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
Oneway cellular automata with restricted nondeterminism are investigated. The number of allowed nondeterministic state transitions is limited to a constant. It is shown that a limit to exactly one step does not decrease the language accepting capabilities. We prove a speedup result that allows any lineartime computation to be spedup to realtime. Some relationships to deterministic arrays are considered. Finally we prove several closure properties of the realtime languages.
A first-order representation of stable models
(1998) Eiter, Thomas; Lu, James; Subrahmanian, V.S
Turi (1991) introduced the important notion of a constrained atom: an atom with associated equality and disequality constraints on its arguments. A set of constrained atoms is a constrained interpretation. We investigate how nonground representations of both the stable model semantics and the wellfounded semantics may be obtained through Turi's approach. The practical implication of this is that the wellfounded model (or the set of stable models) may be partially precomputed at compiletime, resulting in the association of each predicate symbol in the program to a constrained atom. Algorithms to create such models are presented, both for the well founded case, and the case of stable models. Query processing reduces to checking whether each atom in the query is true in a stable model (resp. wellfounded model). This amounts to showing the atom is an instance of one of some constrained atom whose associated constraint is solvable. Various related complexity results are explored, and the impacts of these results are discussed from the point of view of implementing systems that incorporate the stable and wellfounded semantics.
Preferred answer sets for extended logic programs
(1998) Brewka, Gerd; Eiter, Thomas
In this paper, we address the issue of how Gelfond and Lifschitz's answer set semantics for extended logic programs can be suitably modified to handle prioritized programs. In such programs an ordering on the program rules is used to express preferences. We show how this ordering can be used to define preferred answer sets and thus to increase the set of consequences of a program. We define a strong and a weak notion of preferred answer sets. The first takes preferences more seriously, while the second guarantees the existence of a preferred answer set for programs possessing at least one answer set. Adding priorities to rules is not new, and has been explored in different contexts. However, we show that many approaches to priority handling, most of which are inherited from closely related formalisms like default logic, are not suitable and fail on intuitive examples. Our approach, which obeys abstract, general principles that any approach to prioritized knowledge representation should satisfy, handles them in the expected way. Moreover, we investigate the complexity of our approach. It appears that strong preference on answer sets does not add on the complexity of the principal reasoning tasks, and weak preference leads only to a mild increase in complexity.
Iterative arrays with small time bounds
(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
An iterative arrays is a line of interconnected interacting finite automata. One distinguished automaton, the communication cell, is connected to the outside world and fetches the input serially symbol by symbol. Sometimes in the literature this model is referred to as cellular automaton with sequential input mode. We investigate deterministic iterative arrays (IA) with small time bounds between real-time and linear-time. It is shown that there exists an infinite dense hierarchy of strictly included complexity classes in that range. The result closes the last gap in the time hierarchy of IAs.
On tally languages and generalized interacting automata
(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
Devices of interconnected parallel acting sequential automata are investigated from a language theoretic point of view. Starting with the wellknown result that each tally language acceptable by a classical oneway cellular automaton (OCA) in realtime has to be a regular language we will answer the three natural questions 'How much time do we have to provide?' 'How much power do we have to plug in the single cells (i.e., how complex has a single cell to be)?' and 'How can we modify the mode of operation (i.e., how much nondeterminism do we have to add)?' in order to accept nonregular tally languages. We show the surprising result that for some classes of generalized interacting automata parallelism does not lead to more accepting power than obtained by a single sequential cell. Adding a wee bit of nondeterminism an infinite hierarchy of unary language families can be shown by allowing more and more nondeterminism.
Real-time language recognition by alternating cellular automata
(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
The capabilities of alternating cellular automata (ACA) to accept formal languages are investigated. Several notions of alternation in cellular automata have been proposed. Here we study socalled nonuniform ACAs. Our considerations center on space bounded realtime computations. In particular, we prove that there is no difference in acceptance power regardless whether oneway or twoway communication lines are provided. Moreover, the relations between realtime ACAs and deterministic (CA) and nondeterministic (NCA) cellular automata are investigated. It is proved that even the realtime ACAs gain exponential speedup against nondeterministic NCAs. Comparing ACAs with deterministic CAs it is shown that realtime ACAs are strictly more powerful than realtime CAs.
Iterative arrays with limited nondeterministic communication cell
(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
Iterative arrays with restricted nondeterminism are investigated. Non-determinism is provided for the distinguished communication cell only. All the other cells are deterministic ones. Moreover, the number of allowed nondeterministic state transitions is limited dependent on the length of the input. It is shown that the limit can be reduced by a constant factor without affecting the language accepting capabilities, but for sublogarithmic limits there exists a infinite hierarchy of properly included realtime language families. Finally we prove several closure properties of these families.
Iterative arrays with a wee bit alternation
(1999) Buchholz, Thomas; Klein, Andreas; Kutrib, Martin
An iterative array is a line of interconnected interacting finite automata. One distinguished automaton, the communication cell, is connected to the outside world and fetches the input serially symbol by symbol. We are investigating iterative arrays with an alternating communication cell. All the other automata are deterministic. The number of alternating state transitions is regarded as a limited resource which depends on the length of the input. We center our attention to realtime computations and compare alternating IAs with nondeterministic IAs. By proving that the language families of the latter are not closed under complement for sublogarithmic limits it is shown that alternation is strictly more powerful than nondeterminism. Moreover, for these limits there exist infinite hierarchies of properly included alternating language families. It is shown that these families are closed under boolean operations.
Probalistic logic programming under maximum entropy
(1999) Lukasiewicz, Thomas; Kern-Isberner, Gabriele
In this paper, we focus on the combination of probabilistic logic programming with the principle of maximum entropy. We start by defining probabilistic queries to probabilistic logic programs and their answer substitutions under maximum entropy. We then present an efficient linear programming characterization for the problem of deciding whether a probabilistic logic program is satisfiable. Finally, and as a main result of this paper, we introduce an efficient technique for approximative probabilistic logic programming under maximum entropy. This technique reduces the original entropy maximization task to solving a modified and relatively small optimization problem.
Automata arrays and context-free languages
(1999) Kutrib, Martin
From a biological point of view automata arrays have been employed by John von Neumann in order to solve the logical problem of nontrivial self-reproduction. From a computer scientific point of view they are a model for massively parallel computing systems. Here we are dealing with automata arrays as acceptors for formal languages. Our focus of investigations concerns their capabilities to accept the classical linguistic languages. While there are simple relations to the regular and context-sensitive ones here we shed some light on the relations to the context-free languages and some of their important subfamilies. CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1
Fault tolerant parallel pattern recognition
(2000) Kutrib, Martin; Löwe, Jan-Thomas
The general capabilities of fault tolerant computations in one-way and two-way linear cellular arrays are investigated in terms of pattern recognition. The defective processing elements (cells) that cause the misoperations are assumed to behave as follows. Dependent on the result of a self-diagnosis they store their working state locally such that it becomes visible to the neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. Arrays with static defects run the self-diagnosis once before the actual computation. Subsequently no more defects may occur.In case of dynamic defects cells may fail during the computation. We center our attention to patterns that are recognizable very fast, i.e. in real-time, but almost all results can be generalized to arbitrary recognition times in a straightforward manner. It is shown that fault tolerant recognition capabilities of two-way arrays with static defects are characterizable by intact one-way arrays and that one-way arrays are fault tolerant per se. For arrays with dynamic defects it is proved that the failures can be compensated as long as the number of adjacent defective cells is bounded. Arbitrary large defective regions (and thus fault tolerant computations) lead to a dramatically decrease of computing power. The recognizable patterns are those of a single processing element, the regular ones. CR Subject Classification (1998): F.1, F.4.3, B.6.1, E.1, B.8.1, C.4
Deterministic Turing machines in the range between real-time and linear-time
(2000) Klein, Andreas; Kutrib, Martin
Deterministic k-tape and multitape Turing machines with one-way, two-way and without a separated input tape are considered. We investigate the classes of languages acceptable by such devices with time bounds of the form n + r(n) where r E o(n) is a sublinear function. It is shown that there exist infinite time hierarchies of separated complexity classes in that range. For these classes weak closure properties are proved. Finally, it is shown that similar results are valid for several types of acceptors with the same time bounds. CR Subject Classification (1998): F.1.3, F.1.1, F.4.3

Suchen

Auflistung IFIG Research Report nach Erscheinungsdatum

Treffer pro Seite

Sortieroptionen