A Simple P-Complete Problem and Its Representations by Language Equations

DOI10.1007/978-3-540-74593-8_23MaRDI QIDQ3608489zbMATHOpenAlexFDO

Authors Alexander Okhotin

Publication date 5 March 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74593-8_23

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)

Recommendations

• A simple P-complete problem and its language-theoretic representations
• scientific article; zbMATH DE number 7298596
• Decision problems for language equations
• The hardest linear conjunctive language
• A syntactical definition of the problem

Cited in

(3)

• scientific article; zbMATH DE number 7298596 (Why is no real title available?)
• The Boolean formula value problem as formal language
• A simple P-complete problem and its language-theoretic representations

This page was built for publication: A Simple P-Complete Problem and Its Representations by Language Equations

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