Complexity Results for POMSET Languages
From MaRDI portal
Publication:3136615
DOI10.1137/0406035zbMath0781.68058OpenAlexW2010303126MaRDI QIDQ3136615
Jeremy Kahn, Joan Feigenbaum, Carstent Lund
Publication date: 14 October 1993
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0406035
NP-completeequalitycontainmentmembershipconcurrent systempomset\(\Pi^ P_ 2\)-completegraph-isomorphismpomset language
Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (4)
Nonfinite axiomatizability of the equational theory of shuffle ⋮ Free shuffle algebras in language varieties extended abstract ⋮ Free shuffle algebras in language varieties ⋮ Graph Ramsey theory and the polynomial hierarchy
This page was built for publication: Complexity Results for POMSET Languages
