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

DOI10.1007/978-3-540-74593-8_23zbMATH Open1211.68237OpenAlexW1524308938MaRDI QIDQ3608489FDOQ3608489

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

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

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)

Cited In (3)

• A simple P-complete problem and its language-theoretic representations
• The Boolean formula value problem as formal language
• Title not available (Why is that?)

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)