Weak alternating automata and tree automata emptiness

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Weak alternating automata and tree automata emptiness

Full text

Pdf (1.37 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 224 - 233

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Orna Kupferman	EECS Department, UC Berkeley, Berkeley CA
Moshe Y. Vardi	Department of Computer Science, Rice University, Houston, TX

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 46, Citation Count: 8

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276748 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ALW89	Martín Abadi , Leslie Lamport , Pierre Wolper, Realizable and Unrealizable Specifications of Reactive Systems, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.1-17, July 11-15, 1989
	BL80	J.A. Brzozowski and E. Leiss. Finite automata and sequential networks. Theoretical Computer Science, 10:19-35, 1950.
	Büc62	J.R. Biichi. On a decision method in restricted aceend order arithmetic. In Prec. Internat. Conor. Loglc, Afethod and Philos. Set. 1960, pages 1-12, Stanford, 1962. Stanford University Press.
	BVW94	Orna Bernholtz , Moshe Y. Vardi , Pierre Wolper, An Automata-Theoretic Approach to Branching-Time Model Checking (Extended Abstract), Proceedings of the 6th International Conference on Computer Aided Verification, p.142-155, June 21-23, 1994
	CKS81	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	DH94	Doron Drusinsky , David Harel, On the power of bounded concurrency I: finite automata, Journal of the ACM (JACM), v.41 n.3, p.517-539, May 1994 [doi>10.1145/176584.176587]
	EJ88	E.A. Emerson and/3. Jutla. The complexity of tree automata and logics of programs. In Prec. ~9th IEEE Symposium on Foundations of Computer Science, pages 368-377, White Plains, October 1988.
	EJ91	E. A. Emerson , C. S. Jutla, Tree automata, Mu-Calculus and determinacy, Proceedings of the 32nd annual symposium on Foundations of computer science, p.368-377, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185392]
	EJS93	E. Allen Emerson , Charanjit S. Jutla , A. Prasad Sistla, On Model-Checking for Fragments of µ-Calculus, Proceedings of the 5th International Conference on Computer Aided Verification, p.385-396, June 28-July 01, 1993
	EL86	E.A, Emerson and O.-L. Let. Efficient model check- Ing In fragments of the proposoitional Mu-calculns. In Proc, lot Symposium on Logic in Computer Science, pages 267-278, Cambridge, June 1986.
	ES84	A.E. Emerson and A.P. Sis,Is. Deciding full branching time logics. In. formation and Control, 61(3):175-201, 1984.
	HR72	R. Hossley and C.W. Rackoff. The emptiness problem for automata on infinite trees. In Prec. 13th iEEE Syrup, on Switching and Automata Theory, pages 121- 124, 1972,
	Koz83	D, Kozen. Results on the propositional p-calculus. Theoretical Computer Science, 27:333-354, 1983.
	Kur94	Robert P. Kurshan, Computer-aided verification of coordinating processes: the automata-theoretic approach, Princeton University Press, Princeton, NJ, 1994
	KV97	Orna Kupferman , Moshe Vardi, Weak Alternating Automata Are Not That Weak, Proceedings of the Fifth Israel Symposium on the Theory of Computing Systems (ISTCS '97), p.147, June 17-19, 1997
	KV98	O. Kupferman , M. Y. Vardi, Freedom, Weakness, and Determinism: From Linear-Time to Branching-Time, Proceedings of the 13th Annual IEEE Symposium on Logic in Computer Science, p.81, June 21-24, 1998
	Lin88	P A Lindsay, Alternation and &ohgr;-type Turing acceptors, Theoretical Computer Science, v.43 n.1, p.107-115, July 1986
	McN66	R, McNaughton. Testing and generating infinite sequences by a Finite automaton. In.formation and Controlt 9:521-530, 1966.
	MH84	S. Miyano and T. Hayashi. Alternating finite automata on w-words. Theoretical Computer Science, 32:321- 330, 1984.
	Mic88	M, Michel, Complementation is more difficult with automata on infinite words, CNET, Paris, 1988.
	Mos84	A,W, Moatowsld, Regular expressions for infinite trees and a standard form of automata. In Computation Theory, volume 208 of Lecture Notes in Computer Science, pages 157-168. Springer-Verlag, 1984.
	MS87	David, E. Muller , Paul, E. Schupp, Alternating automata on infinite trees, Theoretical Computer Science, v.54 n.2-3, p.267-276, Oct. 1987 [doi>10.1016/0304-3975(87)90133-2]
	MSS86	D E Muller , A Saoudi , P E Schupp, Alternating automata, the weak monadic theory of the tree, and its complexity, International Colloquium on Automata, Languages and Programming on Automata, languages and programming, p.275-283, September 1986, Rennes, France
	Niw88	D. Niwinski. Fixed-points vs. infinite generation. In Prec. 3rd Symposium on Logic in Computer Science, 1988.
	PR89	A. Pnueli , R. Rosner, On the synthesis of a reactive module, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.179-190, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75293]
	Rab69	M.O. Rabin. Decidability of second order theories and automata on infinite trees. Transaction of the A~IS, 141:1-35,1969.
	Rab72	Michael Oser Rabin, Automata on Infinite Objects and Church's Problem, American Mathematical Society, Boston, MA, 1972
	Saf88	S. Safra. On the complexity of u,.automata. In Prec. 29th IEEE Symposium on Foundations of Computer Science, pages 319-327, White Plains, October 1988.
	Saf92	Shmuel Safra, Exponential determinization for &ohgr;-automata with strong-fairness acceptance condition (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.275-282, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129739]
	Tho90	Wolfgang Thomas, Automata on infinite objects, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
	Tho97	Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
	Var94	Moshe Y. Vardi, Nontraditional Applications of Automata Theory, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.575-597, April 19-22, 1994
	Var96	Moshe Y. Vardi, An automata-theoretic approach to linear temporal logic, Proceedings of the VIII Banff Higher order workshop conference on Logics for concurrency : structure versus automata: structure versus automata, p.238-266, April 1996, Banff, Canada
	Var97	Moshe Y. Vardi, Alternating Automata: Unifying Truth and Validity Checking for Temporal Logics, Proceedings of the 14th International Conference on Automated Deduction, p.191-206, July 13-17, 1997
	VS85	M Y Vardi , L Stockmeyer, Improved upper and lower bounds for modal logics of programs, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.240-251, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22173]
	VW86	M.Y. Verdi and P. Wolper. An automata-theoretic approach to automatic program verification. In Pr0c. First Symposium on Logic in Computer Science, pages 322-331, Cambridge, June 1986.
	VW94	Moshe Y. Vardi , Pierre Wolper, Reasoning about infinite computations, Information and Computation, v.115 n.1, p.1-37, Nov. 15, 1994 [doi>10.1006/inco.1994.1092]

CITED BY 8

	Thomas A. Henzinger , Orna Kupferman , Sriram K. Rajamani, Fair simulation, Information and Computation, v.173 n.1, p.64-81, February 25, 2002
	Orna Kupferman , Moshe Y. Vardi , Pierre Wolper, An automata-theoretic approach to branching-time model checking, Journal of the ACM (JACM), v.47 n.2, p.312-360, March 2000
	Orna Kupferman , Moshe Y. Vardi, Weak alternating automata are not that weak, ACM Transactions on Computational Logic (TOCL), v.2 n.3, p.408-429, July 2001
	Erich Grädel , Wolfgang Thomas , Thomas Wilke, Literature, Automata logics, and infinite games: a guide to current research, Springer-Verlag New York, Inc., New York, NY, 2002
	Yonit Kesten , Nir Piterman , Amir Pnueli, Bridging the gap between fair simulation and trace inclusion, Information and Computation, v.200 n.1, p.35-61, 1 July 2005
	Martin Lange, The alternation hierarchy in fixpoint logic with chop is strict too, Information and Computation, v.204 n.9, p.1346-1367, September 2006
	Naiyong Jin , Chengjie Shen , Jun Chen , Taoyong Ni, Engineering of An Assertion-based PSLSimple-Verilog Dynamic Verifier by Alternating Automata, Electronic Notes in Theoretical Computer Science (ENTCS), 207, p.153-169, April, 2008
	Florian Horn, Dicing on the Streett, Information Processing Letters, v.104 n.1, p.1-9, September, 2007