research-article

Subcubic algorithms for recursive state machines

Author:

Swarat ChaudhuriAuthors Info & Claims

POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 159 - 169

https://doi.org/10.1145/1328438.1328460

Published: 07 January 2008 Publication History

Abstract

We show that the reachability problem for recursive state machines (or equivalently, pushdown systems), believed for long to have cubic worst-case complexity, can be solved in slightly subcubic time. All that is necessary for the new bound is a simple adaptation of a known technique. We also show that a better algorithm exists if the input machine does not have infinite recursive loops.

References

[1]

A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Series in Computer Science and Information Processing. Addison-Wesley, 1974.

Digital Library

[2]

R. Alur and M. Yannakakis. Model checking of hierarchical state machines. In 6th ACM Symposium on Foundations of Software Engineering, pages 175--188, 1998.

Digital Library

[3]

R. Alur, M. Benedikt, K. Etessami, P. Godefroid, T. Reps, and M. Yannakakis. Analysis of recursive state machines. ACM Transactions on Programming Languages and Systems, 27(4):786--818, 2005.

Digital Library

[4]

V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev. On economical construction of the transitive closure of an oriented graph. Soviet Mathematics Doklady, 11:1209--1210, 1970. ISSN 0197-6788.

[5]

T. Ball and S. Rajamani. The SLAM toolkit. In 13th International Conference on Computer Aided Verification, pages 260--264, 2001.

Digital Library

[6]

A. Bouajjani, J. Esparza, and O. Maler. Reachability analysis of pushdown automata: Applications to model checking. In 8th International Conference on Concurrency Theory, LNCS 1243, pages 135--150, 1997.

Digital Library

[7]

T. M. Chan. All--pairs shortest paths with real weights in o(n³ log n)) time. In 9th Workshop on Algorithms and Data Structures, pages 318--324, 2005.

Digital Library

[8]

T. M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. In 39th ACM Symposium on Theory of Computing, pages 590--598, 2007.

Digital Library

[9]

J. Eve and R. Kurki-Suonio. On computing the transitive closure of a relation. Acta Informatica, 8:303--314, 1977.

Digital Library

[10]

J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.

Digital Library

[11]

S. Horwitz, T. W. Reps, and D. Binkley. Interprocedural slicing using dependence graphs (with retrospective). In Best of Programming Language Design and Implementation, pages 229--243, 1988.

Digital Library

[12]

S. Horwitz, T. Reps, and M. Sagiv. Demand interprocedural dataflow analysis. In 3rd ACM Symposium on Foundations of Software Engineering, pages 104--115, 1995.

Digital Library

[13]

D. Melski and T. W. Reps. Interconvertibility of a class of set constraints and context-free-language reachability. Theoretical Computer Science, 248(1-2):29--98, 2000.

Digital Library

[14]

P. W. Purdom. A transitive closure algorithm. BIT, 10:76--94, 1970.

Digital Library

[15]

J. Rehof and M. Fahndrich. Type-base flow analysis: from polymorphic subtyping to CFL-reachability. In 28th ACM Symposium on Principles of Programming Languages, pages 54--66, 2001.

Digital Library

[16]

T. Reps. Shape analysis as a generalized path problem. In ACM Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages 1--11, 1995.

Digital Library

[17]

T. Reps. Program analysis via graph reachability. Information and Software Technology, 40(11-12): 701--726, 1998.

[18]

T. Reps, S. Horwitz, and S. Sagiv. Precise interprocedural dataflow analysis via graph reachability. In 22nd ACM Symposium on Principles of Programming Languages, pages 49--61, 1995.

Digital Library

[19]

T. W. Reps, S. Schwoon, and S. Jha. Weighted pushdown systems and their application to interprocedural dataflow analysis. In 10th Static Analysis Symposium, pages 189--213, 2003.

[20]

W. Rytter. Time complexity of loop-free two-way pushdown automata. Information Processing Letters, 16(3): 127--129, 1983.

[21]

W. Rytter. Fast recognition of pushdown automaton and context-free languages. Information and Control, 67(1-3): 12--22, 1985.

Digital Library

[22]

L. Schmitz. An improved transitive closure algorithm. Computing, 30:359--371, 1983.

[23]

M. Sharir and A. Pnueli. Two approaches to interprocedural dataflow analysis. Program Flow Analysis: Theory and Applications, pages 189--234, 1981.

[24]

M. Sridharan, D. Gopan, L. Shan, and R. Bodik. Demand-driven points-to analysis for Java. In 20th ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 59--76, 2005.

Digital Library

[25]

L. G. Valiant. General context-free recognition in less than cubic time. Journal of Computer and System Sciences, 10(2):308--315, 1975.

Digital Library

[26]

M. Yannakakis. Graph-theoretic methods in database theory. In 9th ACM Symposium on Principles of Database Systems, pages 230--242, 1990.

Digital Library

Cited By

Lei YBossut CSui YZhang Q(2024)Context-Free Language Reachability via Skewed TabulationProceedings of the ACM on Programming Languages10.1145/36564518:PLDI(1830-1853)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656451
Shi CLi HLu JLi LChristakis MPradel M(2024)Better Not Together: Staged Solving for Context-Free Language ReachabilityProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680346(1112-1123)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680346
Ren JSui YCheng XFeng YZhao J(2024)Dynamic Transitive Closure-based Static Analysis through the Lens of Quantum SearchACM Transactions on Software Engineering and Methodology10.1145/364438933:5(1-29)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1145/3644389
Show More Cited By

Index Terms

Subcubic algorithms for recursive state machines
1. Theory of computation

Recommendations

Subcubic algorithms for recursive state machines
POPL '08

We show that the reachability problem for recursive state machines (or equivalently, pushdown systems), believed for long to have cubic worst-case complexity, can be solved in slightly subcubic time. All that is necessary for the new bound is a simple ...
Timed recursive state machines

The paper proposes a temporal extension of Recursive State Machines (RSMs), called Timed RSMs (TRSMs), which consists of an indexed collection of Timed Automata, called components. Each component can invoke other components in a potentially recursive ...
Analysis of recursive state machines

Recursive state machines (RSMs) enhance the power of ordinary state machines by allowing vertices to correspond either to ordinary states or to potentially recursive invocations of other state machines. RSMs can model the control flow in sequential ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '08: Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2008

448 pages

ISBN:9781595936899

DOI:10.1145/1328438

General Chair:
George Necula
University of California, Berkeley
,
Program Chair:
Philip Wadler
University of Edinburgh

ACM SIGPLAN Notices Volume 43, Issue 1
POPL '08
January 2008
420 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1328897
Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 January 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL08

Sponsor:

POPL08: The 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 7 - 12, 2008

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
634
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)8

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lei YBossut CSui YZhang Q(2024)Context-Free Language Reachability via Skewed TabulationProceedings of the ACM on Programming Languages10.1145/36564518:PLDI(1830-1853)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656451
Shi CLi HLu JLi LChristakis MPradel M(2024)Better Not Together: Staged Solving for Context-Free Language ReachabilityProceedings of the 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis10.1145/3650212.3680346(1112-1123)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3650212.3680346
Ren JSui YCheng XFeng YZhao J(2024)Dynamic Transitive Closure-based Static Analysis through the Lens of Quantum SearchACM Transactions on Software Engineering and Methodology10.1145/364438933:5(1-29)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1145/3644389
Balasubramanian AMajumdar RThinniyam RZetzsche G(2024)Reachability in Continuous Pushdown VASSProceedings of the ACM on Programming Languages10.1145/36332798:POPL(90-114)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3633279
Shi CLi HSui YLu JLi LXue J(2024)Pearl: A Multi-Derivation Approach to Efficient CFL-Reachability SolvingIEEE Transactions on Software Engineering10.1109/TSE.2024.343768450:9(2379-2397)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1109/TSE.2024.3437684
Koutris PDeep S(2023)The Fine-Grained Complexity of CFL ReachabilityProceedings of the ACM on Programming Languages10.1145/35712527:POPL(1713-1739)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571252
Shi CLi HSui YLu JLi LXue JBissyandé TKlein JBird CSarro F(2023)Two Birds with One Stone: Multi-Derivation for Fast Context-Free Language Reachability AnalysisProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00118(624-636)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00118
Ding SZhang Q(2023)Mutual Refinements of Context-Free Language ReachabilityStatic Analysis10.1007/978-3-031-44245-2_12(231-258)Online publication date: 24-Oct-2023
https://doi.org/10.1007/978-3-031-44245-2_12
Shi QWang YYao PZhang C(2022)Indexing the extended Dyck-CFL reachability for context-sensitive program analysisProceedings of the ACM on Programming Languages10.1145/35633396:OOPSLA2(1438-1468)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563339
Li YSatya KZhang Q(2022)Efficient algorithms for dynamic bidirected Dyck-reachabilityProceedings of the ACM on Programming Languages10.1145/34987246:POPL(1-29)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3498724
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents