Complexity Results for POMSET Languages

DOI10.1137/0406035zbMATH Open0781.68058OpenAlexW2010303126MaRDI QIDQ3136615FDOQ3136615

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

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

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)

Cited In (9)

• Pomset Languages of Finite Step Transition Systems
• Title not available (Why is that?)
• Free shuffle algebras in language varieties
• Title not available (Why is that?)
• Graph Ramsey theory and the polynomial hierarchy
• An algebra for pomsets.
• Free shuffle algebras in language varieties extended abstract
• Title not available (Why is that?)
• Nonfinite axiomatizability of the equational theory of shuffle

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)