Subcubic algorithms for recursive state machines

DOI10.1145/1328438.1328460MaRDI QIDQ3189835zbMATH OpenOpenAlexFDO

Authors Swarat Chaudhuri

Publication date 12 September 2014

Published in Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1328438.1328460

zbMATH Keywords

CFL-reachabilitycontext-free languagescubic bottleneckinterprocedural analysispushdown systemsrecursive state machinestransitive closure

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 1796135
• STACS 2005
• Faster algorithms for weighted recursive state machines
• Tools and Algorithms for the Construction and Analysis of Systems
• Timed recursive state machines: expressiveness and complexity

Cited in

(11)

• Pushdown reachability with constant treewidth
• HARD: A hypercube embedding algorithm for state assignment of finite state machines
• Tight bounds for reachability problems on one-counter and pushdown systems
• Faster algorithms for algebraic path properties in recursive state machines with constant treewidth
• Cubic finite state machine
• Faster algorithms for weighted recursive state machines
• The Complexity of Andersen’s Analysis in Practice
• Tools and Algorithms for the Construction and Analysis of Systems
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• The complexity of bidirected reachability in valence systems
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds

This page was built for publication: Subcubic algorithms for recursive state machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3189835)