Context-free grammars as a tool for describing polynomial-time subclasses of hard problems

DOI10.1016/0020-0190(82)90086-2zbMath0486.68034OpenAlexW2041034381MaRDI QIDQ1164998

A. O. Slisenko

Publication date: 1982

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(82)90086-2

zbMATH Keywords

polynomial-time algorithmHamiltonian circuit problemcontext-free graph grammar

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Theory of compilers and interpreters (68N20) Paths and cycles (05C38)

Related Items (11)

Tree-like parse and polynomial subclasses of search problems ⋮ String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing ⋮ Metatheorems for decision problems on hyperedge replacement graph languages ⋮ Power properties of NLC graph grammars with a polynomial membership problem ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Fundamental methodological issues of syntactic pattern recognition ⋮ Graph-theoretic properties compatible with graph derivations ⋮ Undecidability of the bandwidth problem on linear graph languages ⋮ The complexity of graph languages generated by hyperedge replacement ⋮ Parallel algorithms for a class of graphs generated recursively ⋮ Generating irregular partitionable data structures

Cites Work

• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Context-free graph grammars

This page was built for publication: Context-free grammars as a tool for describing polynomial-time subclasses of hard problems