Complexity Results for POMSET Languages

DOI10.1137/0406035MaRDI QIDQ3136615zbMATH OpenOpenAlexFDO

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

\(\Pi^ P_ 2\)-completeconcurrent systemcontainmentequalitygraph-isomorphismmembershipNP-completepomsetpomset 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

(11)

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

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)