Digital Symposium Collection 2000  

 
 
 
 
 
 

 
















Moshe Y. Vardi

Rewriting of Regular Expressions and Regular Path Queries

Publications

Note: Links lead to the DBLP on the Web.

Moshe Y. Vardi

150 Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi: Query Processing using Views for Regular Path Queries with Inverse. PODS 2000 : 0-

149 Moshe Y. Vardi: Probabilistic Linear-Time Model Checking: An Overview of the Automata-Theoretic Approach. ARTS 1999 : 265-276

148 Orna Kupferman , Moshe Y. Vardi: Model Checking of Safety Properties. CAV 1999 : 172-183

147 Marco Daniele , Fausto Giunchiglia , Moshe Y. Vardi: Improved Automata Generation for Linear Temporal Logic. CAV 1999 : 249-260

146 Orna Kupferman , Moshe Y. Vardi: Robust Satisfaction. CONCUR 1999 : 383-398

145 Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi: Rewriting of Regular Expressions and Regular Path Queries. PODS 1999 : 194-204

144 Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi: Rewriting of Regular Path Queries. SEBD 1999 : 213-224

143 Orna Kupferman , Moshe Y. Vardi: The Weakness of Self-Complementation. STACS 1999 : 437-447

142 Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi: Query Answering Using Views for Data Integration over the Web. WebDB (Informal Proceedings) 1999 : 73-78

141 Kenneth A. Ross , Surajit Chaudhuri , Gösta Grahne , H. V. Jagadish , Jan Van den Bussche , Moshe Y. Vardi: Reminiscences on Influential Papers. SIGMOD Record 28 (4): 39-41 (1999)

140 Moshe Y. Vardi: Sometimes and Not Never Re-revisited: On Branching Versus Linear Time. CONCUR 1998 : 1-17

139 Rajeev Alur , Thomas A. Henzinger , Orna Kupferman , Moshe Y. Vardi: Alternating Refinement Relations. CONCUR 1998 : 163-178

138 Ron van der Meyden , Moshe Y. Vardi: Synthesis from Knowledge-Based Specifications (Extended Abstract). CONCUR 1998 : 34-49

137 Kathi Fisler , Moshe Y. Vardi: Bisimulation Minimization in an Automata-Theoretic Verification Framework. FMCAD 1998 : 115-132

136 Moshe Y. Vardi: Reasoning about The Past with Two-Way Automata. ICALP 1998 : 628-641

135 Moshe Y. Vardi: Linear vs. Branching Time: A Complexity-Theoretic Perspective. LICS 1998 : 394-405

134 Orna Kupferman , Moshe Y. Vardi: Freedom, Weakness, and Determinism: From Linear-Time to Branching-Time. LICS 1998 : 81-92

133 Phokion G. Kolaitis , Moshe Y. Vardi: Conjunctive-Query Containment and Constraint Satisfaction. PODS 1998 : 205-213

132 Joan Feigenbaum , Sampath Kannan , Moshe Y. Vardi, M. Viswanathan : Complexity of Problems on Graphs Represented as OBDDs (Extended Abstract). STACS 1998 : 216-226

131 Orna Kupferman , Moshe Y. Vardi: Weak Alternating Automata and Tree Automata Emptiness. STOC 1998 : 224-233

130 Moshe Y. Vardi: Alternating Automata: Unifying Truth and Validity Checking for Temporal Logics. CADE 1997 : 191-206

129 Neil Immerman , Moshe Y. Vardi: Model Checking and Transitive-Closure Logic. CAV 1997 : 291-302

128 Orna Kupferman , Moshe Y. Vardi: Model Checking Revisited. CAV 1997 : 36-47

127 David Harel , Orna Kupferman , Moshe Y. Vardi: On the Complexity of Verifying Concurrent Transition Systems. CONCUR 1997 : 258-272

126 Moshe Y. Vardi: Verification of Open Systems. FSTTCS 1997 : 250-266

125 Kousha Etessami , Moshe Y. Vardi, Thomas Wilke : First-Order Logic with Two Variables and Unary Temporal Logic. LICS 1997 : 228-235

124 Ronald Fagin , Joseph Y. Halpern , Yoram Moses , Moshe Y. Vardi: Knowledge-Based Programs. Distributed Computing 10 (4): 199-225 (1997)

123 Serge Abiteboul , Moshe Y. Vardi, Victor Vianu : Fixpoint Logics, Relational Machines, and Computational Complexity. JACM 44 (1): 30-56 (1997)

122 Surajit Chaudhuri , Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. JCSS 54 (1): 61-78 (1997)

121 Orna Kupferman , Moshe Y. Vardi: Verification of Fair Transisiton Systems. CAV 1996 : 372-382

120 Orna Kupferman , Moshe Y. Vardi: Module Checking. CAV 1996 : 75-86

119 Thomas A. Henzinger , Orna Kupferman , Moshe Y. Vardi: A Space-Efficient On-the-fly Algorithm for Real-Time Model Checking. CONCUR 1996 : 514-529

118 Surajit Chaudhuri , Ashok K. Chandra , Umeshwar Dayal , Jim Gray , Michael Stonebraker , Gio Wiederhold , Moshe Y. Vardi: Database Research: Lead, Follow, or Get Out of the Way? - Panel Abstract. ICDE 1996 : 190

117 Orna Kupferman , Shmuel Safra , Moshe Y. Vardi: Relating Word and Tree Automata. LICS 1996 : 322-332

116 Phokion G. Kolaitis , Moshe Y. Vardi: On the Expressive Power of Variable-Confined Logics. LICS 1996 : 348-359

115 Serge Abiteboul , Gabriel M. Kuper , Christos H. Papadimitriou , Moshe Y. Vardi: In Memoriam: Paris C. Kanellakis. PODS 1996 : 79

114 Serge Abiteboul , Gabriel M. Kuper , Harry G. Mairson , Alexander A. Shvartsman , Moshe Y. Vardi: In Memoriam Paris C. Kanellakis. Computing Surveys 28 (1): 3-15 (1996)

113 Moshe Y. Vardi: In Memoriam: Paris C. Kanellakis (1953-1995). Information and Computation 127 (2): 65 (1996)

112 Moshe Y. Vardi: An Automata-Theoretic Approach to Fair Realizability and Synthesis. CAV 1995 : 267-278

111 Orna Kupferman , Moshe Y. Vardi: On the Complexity of Branching Modular Model Checking (Extended Abstract). CONCUR 1995 : 408-422

110 Moshe Y. Vardi: Alternating Automata and Program Verification. Computer Science Today 1995 : 471-485

109 Moshe Y. Vardi: On the Complexity of Modular Model Checking. LICS 1995 : 101-111

108 Ronald Fagin , Joseph Y. Halpern , Yoram Moses , Moshe Y. Vardi: Knowledge-Based Programs. PODC 1995 : 153-163

107 Moshe Y. Vardi: On the Complexity of Bounded-Variable Queries. PODS 1995 : 266-276

106 Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi: A Nonstandard Approach to the Logical Omniscience Problem. Artificial Intelligence 79 (2): 203-240 (1995)

105 Ronald Fagin , Larry J. Stockmeyer , Moshe Y. Vardi: On Monadic NP vs. Monadic co-NP. Information and Computation 120 (1): 78-92 (1995)

104 Phokion G. Kolaitis , Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. JCSS 51 (1): 110-134 (1995)

103 Gerd G. Hillebrand , Paris C. Kanellakis , Harry G. Mairson , Moshe Y. Vardi: Undecidable Boundedness Problems for Datalog Programs. JLP 25 (2): 163-190 (1995)

102 Serge Abiteboul , Moshe Y. Vardi, Victor Vianu : Computing with Infinitary Logic. TCS 149 (1): 101-128 (1995)

101 Ronald Fagin , Joseph Y. Halpern , Yoram Moses , Moshe Y. Vardi: An Operational Semantics for Knowledge Bases. AAAI, Vol. 2 1994 : 1142-1147

100 Orna Bernholtz , Moshe Y. Vardi, Pierre Wolper : An Automata-Theoretic Approach to Branching-Time Model Checking (Extended Abstract). CAV 1994 : 142-155

99 Surajit Chaudhuri , Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994 : 107-116

98 Moshe Y. Vardi: Nontraditional Applications of Automata Theory. TACS 1994 : 575-597

97 Moshe Y. Vardi, Pierre Wolper : Reasoning About Infinite Computations. Information and Computation 115 (1): 1-37 (1994)

96 Alexander Aiken , Dexter Kozen , Moshe Y. Vardi, Edward L. Wimmers : The Complexity of Set Constraints. CSL 1993 : 1-17

95 Surajit Chaudhuri , Moshe Y. Vardi: Optimization of Real Conjunctive Queries. PODS 1993 : 59-70

94 Rajeev Alur , Thomas A. Henzinger , Moshe Y. Vardi: Parametric Real-time Reasoning. STOC 1993 : 592-601

93 Tomás Feder , Moshe Y. Vardi: Monotone Monadic SNP and Constraint Satisfaction. STOC 1993 : 612-622

92 Ronald Fagin , Larry J. Stockmeyer , Moshe Y. Vardi: On Monadic NP vs. Monadic co-NP (Extended Abstract). Structure in Complexity Theory Conference 1993 : 19-30

91 Haim Gaifman , Harry G. Mairson , Yehoshua Sagiv , Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. JACM 40 (3): 683-713 (1993)

90 Raghu Ramakrishnan , Yehoshua Sagiv , Jeffrey D. Ullman , Moshe Y. Vardi: Logical Query Optimization by Proff-Tree Transformation. JCSS 47 (1): 222-248 (1993)

89 Gabriel M. Kuper , Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model. TCS 116 (1&2): 33-57 (1993)

88 Gabriel M. Kuper , Moshe Y. Vardi: The Logical Data Model. TODS 18 (3): 379-413 (1993)

87 Phokion G. Kolaitis , Moshe Y. Vardi: Infinitary Logic for Computer Science. ICALP 1992 : 450-473

86 Serge Abiteboul , Moshe Y. Vardi, Victor Vianu : Computing with Infinitary Logic. ICDT 1992 : 113-123

85 Phokion G. Kolaitis , Moshe Y. Vardi: Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory. LICS 1992 : 46-57

84 Surajit Chaudhuri , Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992 : 55-66

83 Serge Abiteboul , Moshe Y. Vardi, Victor Vianu : Fixpoint Logics, Relational Machines, and Computational Complexity. Structure in Complexity Theory Conference 1992 : 156-168

82 Moshe Y. Vardi: Automata Theory for Database Theoreticans. Theoretical Studies in Computer Science 1992 : 153-180

81 Phokion G. Kolaitis , Moshe Y. Vardi: Infinitary Logics and 0-1 Laws. Information and Computation 98 (2): 258-294 (1992)

80 Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi: What Can Machines Know? On the Properties of Knowledge in Distributed Systems. JACM 39 (2): 328-376 (1992)

79 Joseph Y. Halpern , Moshe Y. Vardi: Model Checking vs. Theorem Proving: A Manifesto. KR 1991 : 325-334

78 Thom W. Frühwirth , Ehud Y. Shapiro , Moshe Y. Vardi, Eyal Yardeni : Logic Programs as Types for Logic Programs. LICS 1991 : 300-309

77 Gerd G. Hillebrand , Paris C. Kanellakis , Harry G. Mairson , Moshe Y. Vardi: Tools for Datalog Boundedness. PODS 1991 : 1-12

76 Moshe Y. Vardi: Verification of Concurrent Programs: The Automata-Theoretic Framework. Annals of Pure and Applied Logic 51 (1-2): 79-98 (1991)

75 Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi: A Model-Theoretic Analysis of Knowledge. JACM 38 (2): 382-428 (1991)

74 Moshe Y. Vardi: Database Logic Programming. JLP 10 (1/2/3&4): 179-180 (1991)

73 Moshe Y. Vardi: Global Optimization Problems for Database Logic Programs. ICLP 1990 : 767-771

72 Phokion G. Kolaitis , Moshe Y. Vardi: 0-1 Laws for Infinitary Logics (Preliminary Report). LICS 1990 : 156-167

71 David Harel , Roni Rosner , Moshe Y. Vardi: On the Power of Bounded Concurrency~III: Reasoning About Programs (Preliminary Report). LICS 1990 : 478-488

70 Phokion G. Kolaitis , Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990 : 61-71

69 Moshe Y. Vardi: Endmarkers can Make a Difference. IPL 35 (3): 145-148 (1990)

68 Phokion G. Kolaitis , Moshe Y. Vardi: 0-1 Laws and Decision Problems for Fragments of Second-Order Logic. Information and Computation 87 (1/2): 301-337 (1990)

67 Stavros S. Cosmadakis , Paris C. Kanellakis , Moshe Y. Vardi: Polynomial-Time Implication Problems for Unary Inclusion Dependencies. JACM 37 (1): 15-46 (1990)

66 Moshe Y. Vardi: On the Complexity of Epistemic Reasoning. LICS 1989 : 243-252

65 Yehoshua Sagiv , Moshe Y. Vardi: Safety of Datalog Queries over Infinite Databases. PODS 1989 : 160-171

64 Raghu Ramakrishnan , Yehoshua Sagiv , Jeffrey D. Ullman , Moshe Y. Vardi: Proof-Tree Transformation Theorems and Their Applications. PODS 1989 : 172-181

63 Moshe Y. Vardi: Automata Theory for Database Theoreticans. PODS 1989 : 83-92

62 Shmuel Safra , Moshe Y. Vardi: On omega-Automata and Temporal Logic (Preliminary Report). STOC 1989 : 127-137

61 Moshe Y. Vardi: A Note on the Reduction of Two-Way Automata to One-Way Automata. IPL 30 (5): 261-264 (1989)

60 Joseph Y. Halpern , Moshe Y. Vardi: The Complexity of Reasoning about Knowledge and Time. I. Lower Bounds. JCSS 38 (1): 195-237 (1989)

59 Gabriel M. Kuper , Moshe Y. Vardi: On the Complexity of Queries in the Logical Data Model (Extended Abstract). ICDT 1988 : 267-280

58 Phokion G. Kolaitis , Moshe Y. Vardi: 0-1 Laws and Decision Problems for Fragments of Second-Order Logic. LICS 1988 : 2-11

57 Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988 : 341-351

56 Jeffrey D. Ullman , Moshe Y. Vardi: The Complexity of Ordering Subgoals. PODS 1988 : 74-81

55 Moshe Y. Vardi: A Temporal Fixpoint Calculus. POPL 1988 : 250-259

54 Moshe Y. Vardi: Database Logic Programming, Deductive Databases, and Expert Database Systems. SIGMOD Conference 1988 : 7

53 Stavros S. Cosmadakis , Haim Gaifman , Paris C. Kanellakis , Moshe Y. Vardi: Decidable Optimization Problems for Database Logic Programs (Preliminary Report). STOC 1988 : 477-490

52 Joseph Y. Halpern , Moshe Y. Vardi: Reasoning about Knowledge and Time in Asynchronous Systems. STOC 1988 : 53-65

51 Moshe Y. Vardi: The Universal-Relation Data Model for Logic Independence. IEEE Software 5 (2): 80-85 (1988)

50 Moshe Y. Vardi: Response to a Letter to the Editor. IEEE Software 5 (4): 4-6 (1988)

49 Haim Gaifman , Harry G. Mairson , Yehoshua Sagiv , Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987 : 106-115

48 Moshe Y. Vardi: Verification of Concurrent Programs: The Automata-Theoretic Framework. LICS 1987 : 167-176

47 Phokion G. Kolaitis , Moshe Y. Vardi: The Decision Problem for the Probabilities of Higher-Order Properties. STOC 1987 : 425-435

46 A. Prasad Sistla , Moshe Y. Vardi, Pierre Wolper : The Complementation Problem for Büchi Automata with Appplications to Temporal Logic. TCS 49 : 217-237 (1987)

45 Ronald Fagi , Joseph Y. Halpern , Moshe Y. Vardi: What Can Machines Know? On the Epistemic Properties of Machines. AAAI, Vol. 1 1986 : 428-435

44 Moshe Y. Vardi, Pierre Wolper : An Automata-Theoretic Approach to Automatic Program Verification (Preliminary Report). LICS 1986 : 332-344

43 Moshe Y. Vardi: On the Integrity of Databases with Incomplete Information. PODS 1986 : 252-266

42 Constantin Courcoubetis , Moshe Y. Vardi, Pierre Wolper : Reasoning about Fair Concurrent Programs. STOC 1986 : 283-294

41 Joseph Y. Halpern , Moshe Y. Vardi: The Complexity of Reasoning about Knowledge and Time: Extended Abstract. STOC 1986 : 304-315

40 Johann A. Makowsky , Moshe Y. Vardi: On the Expressive Power of Data Dependencies. Acta Informatica 23 (3): 231-244 (1986)

39 Ronald Fagin , Gabriel M. Kuper , Jeffrey D. Ullman , Moshe Y. Vardi: Updating Logical Databases. Advances in Computing Research 3 : 1-18 (1986)

38 Marc H. Graham , Alberto O. Mendelzon , Moshe Y. Vardi: Notions of Dependency Satisfaction. JACM 33 (1): 105-129 (1986)

37 Moshe Y. Vardi, Pierre Wolper : Automata-Theoretic Techniques for Modal Logics of Programs. JCSS 32 (2): 183-221 (1986)

36 Moshe Y. Vardi: Querying Logical Databases. JCSS 33 (2): 142-160 (1986)

35 Moshe Y. Vardi: Automatic Verification of Probabilistic Concurrent Finite-State Programs. FOCS 1985 : 327-338

34 A. Prasad Sistla , Moshe Y. Vardi, Pierre Wolper : The Complementation Problem for Büchi Automata with Applications to Temporal Logic (Extended Abstract). ICALP 1985 : 465-474

33 Moshe Y. Vardi: A Model-Theoretic Analysis of Monotonic Knowledge. IJCAI 1985 : 509-512

32 Moshe Y. Vardi: Querying Logical Databases. PODS 1985 : 57-65

31 Gabriel M. Kuper , Moshe Y. Vardi: On the Expressive Power of the Logical Data Model (Preliminary Report). SIGMOD Conference 1985 : 180-187

30 Moshe Y. Vardi, Larry J. Stockmeyer : Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report. STOC 1985 : 240-251

29 Ronald Fagin , Moshe Y. Vardi: An Internal Semantics for Modal Logic: Preliminary Report. STOC 1985 : 305-315

28 Ashok K. Chandra , Moshe Y. Vardi: The Implication Problem for Functional and Inclusion Dependencies is Undecidable. SIAM J. Comput. 14 (3): 671-677 (1985)

27 Catriel Beeri , Moshe Y. Vardi: Formal Systems for Join Dependencies. TCS 38 : 99-116 (1985)

26 Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi: A Model-Theoretic Analysis of Knowledge: Preliminary Report. FOCS 1984 : 268-278

25 Ronald Fagin , Moshe Y. Vardi: The Theory of Data Dependencies - An Overview. ICALP 1984 : 1-22

24 Gabriel M. Kuper , Jeffrey D. Ullman , Moshe Y. Vardi: On the Equivalence of Logical Databases. PODS 1984 : 221-228

23 Marc H. Graham , Moshe Y. Vardi: On the Complexity and Axiomatizability of Consistent Database States. PODS 1984 : 281-289

22 Gabriel M. Kuper , Moshe Y. Vardi: A New Approach to Database Logic. PODS 1984 : 86-96

21 Moshe Y. Vardi, Pierre Wolper : Automata Theoretic Techniques for Modal Logics of Programs (Extended Abstract). STOC 1984 : 446-456

20 Moshe Y. Vardi: A Note on Lossless Database Decompositions. Information Processing Letters 18 (5): 257-260 (1984)

19 Catriel Beeri , Moshe Y. Vardi: On Acyclic Database Decompositions. Information and Control 61 (2): 75-84 (1984)

18 Catriel Beeri , Moshe Y. Vardi: A Proof Procedure for Data Dependencies. JACM 31 (4): 718-741 (1984)

17 Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. JCSS 28 (1): 3-28 (1984)

16 Catriel Beeri , Moshe Y. Vardi: Formal Systems for Tuple and Equality Generating Dependencies. SIAM J. Comput. 13 (1): 76-98 (1984)

15 David Maier , Jeffrey D. Ullman , Moshe Y. Vardi: On the Foundations of the Universal Relation Model. TODS 9 (2): 283-308 (1984)

14 Pierre Wolper , Moshe Y. Vardi, A. Prasad Sistla : Reasoning about Infinite Computation Paths (Extended Abstract). FOCS 1983 : 185-194

13 David Maier , Jeffrey D. Ullman , Moshe Y. Vardi: The Revenge of the JD. PODS 1983 : 279-287

12 Ronald Fagin , Jeffrey D. Ullman , Moshe Y. Vardi: On the Semantics of Updates in Databases. PODS 1983 : 352-365

11 Paris C. Kanellakis , Stavros S. Cosmadakis , Moshe Y. Vardi: Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract). STOC 1983 : 264-277

10 Moshe Y. Vardi: Inferring Multivalued Dependencies From Functional and Join Dependencies. Acta Informatica 19 : 305-324 (1983)

9 Ronald Fagin , Moshe Y. Vardi: Armstrong Databases for Functional and Inclusion Dependencies. IPL 16 (1): 13-19 (1983)

8 Moshe Y. Vardi: On Decomposition of Relational Databases. FOCS 1982 : 176-185

7 Moshe Y. Vardi: The Implication and Finite Implication Problems for Typed Template Dependencies. PODS 1982 : 230-238

6 Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982 : 137-146

5 Moshe Y. Vardi: Global Decision Problems for Relational Databases. FOCS 1981 : 198-202

4 Catriel Beeri , Moshe Y. Vardi: The Implication Problem for Data Dependencies. ICALP 1981 : 73-85

3 Moshe Y. Vardi: The Decision Problem for Database Dependencies. Information Processing Letters 12 (5): 251-254 (1981)

2 Catriel Beeri , Moshe Y. Vardi: A Note on Decompositions of Relational Databases. SIGMOD Record 12 (1): 33-37 (1981)

1 Catriel Beeri , Moshe Y. Vardi: On the Properties of Join Dependencies. Advances in Data Base Theory 1979 : 25-71



























Copyright(C) 2000 ACM