12127321
Micro-macro stack systems: a new frontier of elementary decidability for sequential systems
We define the class of micro-macro stack graphs, a new class of graphs modeling infinite-state sequential systems with a decidable model-checking problem. Micro-macro stack graphs are the configuration graphs of stack automata whose states are partitioned into micro and macro states. Nodes of the graph are configurations of the stack automaton where the state is a macro state. Edges of the graph correspond to the sequence of micro steps that the automaton makes between macro states. We prove that this class strictly contains the class of prefix-recognizable graphs. We give a direct automata-theoretic algorithm for model checking /spl mu/-calculus formulas over micro-macro stack graphs.
7297261
Algorithmic Knowledge
The standard model of knowledge in multi-agent systems suffers from what has been called the logical omniscience problem: agents know all tautologies, and know all the logical consequences of their knowledge. For many types of analysis, this turns out not to be a problem. Knowledge is viewed as being ascribed by the system designer to the agents; agents are not assumed to compute their knowledge in any way, nor is it assumed that they can necessarily answer questions based on their knowledge. Nevertheless, in many applications that we are interested in, agents need to act on their knowledge. In such applications, an externally ascribed notion of knowledge is insufficient: clearly an agent can base his actions only on what he explicitly knows. Furthermore, an agent that has to act on his knowledge has to be able to compute this knowledge; we do need to take into account the algorithms available to the agent, as well as the "effort" required to compute knowledge. In this paper, we show how the standard model can be modified in a natural way to take the computational aspects of knowledge into account.
15615893
The Implication and Finite Implication Problems for Typed Template Dependencies
Abstract The class of typed template dependencies is a class of data dependencies that includes embedded multivalued and join dependencies. It is shown that the implication and the finite implication problems for this class are unsolvable. An immediate corollary is that this class has no formal system for finite implication. It is also shown how to construct a finite set of typed template dependencies whose implication and finite implication problems are unsolvable. The class of projected join dependencies is a proper subclass of the above class, and it generalizes slightly embedded join dependencies. It is shown that the implication and the finite implication problems for this class are also unsolvable. An immediate corollary is that this class has no universe-bounded formal system for either implication or finite implication.
5982472
µ-Calculus Synthesis
In system synthesis, we transform a specification into a system that is guaranteed to satisfy the specification. When the system is open, it interacts with an environment via input and output signals and its behavior depends on this interaction. An open system should satisfy its specification in all possible environments. In addition to the input signals that the system can read, an environment can also have internal signals that the system cannot read. In the above setting, of synthesis with incomplete information, we should transform a specification that refers to both readable and unreadable signals into a system whose behavior depends only on the readable signals. In this work we solve the problem of synthesis with incomplete information for specifications in µ-calculus. Since many properties of systems are naturally specified by means of fixed points, the µ-calculus is an expressive and important specification language. Our results and technique generalize and simplify previous work on synthesis. In particular, we prove that the problem of µ-calculus synthesis with incomplete information is EXPTIME-complete. Thus, it is not harder than the satisfiability or the synthesis problems for this logic.
27242289
Model Checking of Safety Properties
Of special interest in formal verification are safety properties, which assert that the system always stays within some allowed region.A computation that violates a general linear property reaches a bad cycle, which witnesses the violation of the property. Accordingly, current methods and tools for model checking of linear properties are based on a search for bad cycles. A symbolic implementation of such a search involves the calculation of a nested fixed-point expression over the system's state space, and is often very difficult. Every computation that violates a safety property has a finite prefix along which the property is violated. We use this fact in order to base model checking of safety properties on a search for finite bad prefixes. Such a search can be performed using a simple forward or backward symbolic reachability check. A naive methodology that is based on such a search involves a construction of an automaton (or a tableau) that is doubly exponential in the property.We present an analysis of safety properties that enables us to prevent the doubly-exponential blow up and to use the same automaton used for model checking of general properties, replacing the search for bad cycles by a search for bad prefixes.
42250709
educational response to offshore outsourcing
William Aspray School of Informatics Indiana University Bloomington, IN 47408-3912 waspray@indiana.edu A. Frank Mayadas Alfred P. Sloan Foundation 630 Fifth Avenue, Ste. 2550 New York, NY 10111 mayadas@sloan.org Moshe Y. Vardi Dept. of Computer Science Rice University, P.O. Box 1892 Houston, TX 77251-1892 vardi@cs.rice.edu Stuart H. Zweben Dept. of Computer Science and Engineering Ohio State University Columbus, OH 43210 zweben@cse.ohio-state.edu
12481186
0-1 laws and decision problems for fragments of second-order logic
Fragments of existential second-order logic are investigated in which the patterns of first order quantifiers are restricted. The focus is on the class Sigma /sub 1//sup 1/ (Ackermann) of existential second-order sentences in which the first-order part belongs to the Ackermann class, i.e. it contains at most one universal first-order quantifier. All properties expressible by Sigma /sub 1//sup 1/ (Ackermann) sentences are NP-computable, and there are natural NP-complete properties, such as satisfiability, that are expressible by such sentences. It is established that the 0-1 law holds for the class Sigma /sub 1//sup 1/ (Ackermann), and it is shown that the associated decision problem is NEXPTIME-complete. It is also shown that the 0-1 law fails for other fragments of existential second-order logic in which first-order part belongs to certain prefix classes with an unsolvable decision problem.<<ETX>>
34835758
0-1 Laws and Decision Problems for Fragments of Second-Order Logic
Fragments of existential second-order logic are investigated in which the patterns of first order quantifiers are restricted. The focus is on the class Sigma /sub 1//sup 1/ (Ackermann) of existential second-order sentences in which the first-order part belongs to the Ackermann class, i.e. it contains at most one universal first-order quantifier. All properties expressible by Sigma /sub 1//sup 1/ (Ackermann) sentences are NP-computable, and there are natural NP-complete properties, such as satisfiability, that are expressible by such sentences. It is established that the 0-1 law holds for the class Sigma /sub 1//sup 1/ (Ackermann), and it is shown that the associated decision problem is NEXPTIME-complete. It is also shown that the 0-1 law fails for other fragments of existential second-order logic in which first-order part belongs to certain prefix classes with an unsolvable decision problem. >