Pushdown reachability with constant treewidth
type: Item
instance of: scholarly article
title: Pushdown reachability with constant treewidth
zbMATH Open document ID: 1422.68184
author: Krishnendu Chatterjee
author: Georg Osang
published in: Information Processing Letters
publication date: 2017-11-03T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 6802742
zbMATH Keywords: pushdown systems
zbMATH Keywords: reachability
zbMATH Keywords: constant tree-width graphs
zbMATH Keywords: graph algorithms
MaRDI profile type: Publication
full work available at URL: j.ipl.2017.02.003
OpenAlex ID: W2591236525
cites work: If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
cites work: Regularity Lemmas and Combinatorial Algorithms
cites work: Q4291429
cites work: SOFSEM 2005: Theory and Practice of Computer Science
cites work: Algorithms for algebraic path properties in concurrent systems of constant treewidth components
cites work: Faster algorithms for algebraic path properties in recursive state machines with constant treewidth
cites work: Subcubic algorithms for recursive state machines
cites work: Matrix multiplication via arithmetic progressions
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Q4223067
cites work: Q4707790
cites work: S-functions for graphs
cites work: Complete problems for deterministic polynomial time
cites work: Fast context-free grammar parsing requires fast boolean matrix multiplication
cites work: Q3688439
cites work: Computer Aided Verification
cites work: Graph minors. III. Planar tree-width
cites work: All structured programs have small tree width and good register allocation
cites work: General context-free recognition in less than cubic time
cites work: Efficient algorithms for clique problems
DOI: 10.1016/J.IPL.2017.02.003
description: scientific article; zbMATH DE number 6802742