The tree width of auxiliary storage

DOI10.1145/1926385.1926419MaRDI QIDQ5408550zbMATH OpenOpenAlexFDO

Authors Parthasarathy Madhusudan, Gennaro Parlato

Publication date 10 April 2014

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

Full work available at URL https://eprints.soton.ac.uk/272444/1/graphautomata.pdf

zbMATH Keywords

automatabounded tree-widthdecision proceduresmodel checking

Mathematics Subject Classification ID

Trees (05C05) Formal languages and automata (68Q45) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Deciding emptiness for stack automata on infinite trees
• Emptiness problems for distributed automata
• Distributed graph automata
• Decidability Results for Well-Structured Transition Systems with Auxiliary Storage
• Emptiness problems for distributed automata

Cited in

(35)

• Realizability of concurrent recursive programs
• Reachability analysis of reversal-bounded automata on series-parallel graphs
• On exteriority notions in book embeddings and treewidth
• Deterministic input-driven queue automata: finite turns, decidability, and closure properties
• The complexity of model checking multi-stack systems
• Tinput-Driven Pushdown Automata
• Automata and Logics for Concurrent Systems: Five Models in Five Pages
• When input-driven pushdown automata meet reversiblity
• Reachability of multistack pushdown systems with scope-bounded matching relations
• Descriptional complexity of input-driven pushdown automata
• Emptiness problems for distributed automata
• A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
• Parameterized Verification of Communicating Automata under Context Bounds
• On the complexity of intersecting regular, context-free, and tree languages
• Emptiness of ordered multi-pushdown automata is 2ETIME-complete
• Analyzing timed systems using tree automata
• Temporal logics for concurrent recursive programs: satisfiability and model checking
• The \(\mu\)-calculus alternation hierarchy collapses over structures with restricted connectivity
• Bounded context switching for valence systems
• Reachability analysis of reversal-bounded automata on series-parallel graphs
• Digging input-driven pushdown automata
• scientific article; zbMATH DE number 7471708 (Why is no real title available?)
• Revisiting underapproximate reachability for multipushdown systems
• Non axiomatisability of positive relation algebras with constants, via graph homomorphisms
• Data multi-pushdown automata
• Towards an Efficient Tree Automata based technique for Timed Systems
• On the path-width of integer linear programming
• What's decidable about program verification modulo axioms?
• Context-bounded analysis of TSO systems
• Ramsey-based inclusion checking for visibly pushdown automata
• Decidable models of integer-manipulating programs with recursive parallelism
• Reasoning About Data Trees Using CHCs
• On the complexity of multi-pushdown games
• Weighted tiling systems for graphs: evaluation complexity
• Sweeping input-driven pushdown automata

This page was built for publication: The tree width of auxiliary storage

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