Complexity Results for POMSET Languages

DOI10.1137/0406035MaRDI QIDQ3136615zbMATHOpenAlexFDO

Authors Joan Feigenbaum, Jeremy Kahn, C. 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

zbMATH Keywords

NP-completeequalitycontainmentmembershipconcurrent systempomset\(\Pi^ P_ 2\)-completegraph-isomorphismpomset language

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• scientific article; zbMATH DE number 1927576
• Towards a language theory for infinite N-free pomsets.
• Parsing Partially Ordered Multisets
• Algebra and theory of order-deterministic pomsets
• The equational theory of pomsets

Cited in

(10)

• scientific article; zbMATH DE number 1916672 (Why is no real title available?)
• An algebra for pomsets.
• Graph Ramsey theory and the polynomial hierarchy
• Pomset Languages of Finite Step Transition Systems
• Free shuffle algebras in language varieties
• scientific article; zbMATH DE number 1104370 (Why is no real title available?)
• Nonfinite axiomatizability of the equational theory of shuffle
• Free shuffle algebras in language varieties extended abstract
• Realisability of pomsets
• scientific article; zbMATH DE number 1927576 (Why is no real title available?)

This page was built for publication: Complexity Results for POMSET Languages

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