scientific article; zbMATH DE number 7298596

MaRDI QIDQ5145160zbMATH OpenFDO

Authors Alexander Okhotin

Publication date 20 January 2021

Full work available at URL https://arxiv.org/abs/0906.3208, http://eptcs.web.cse.unsw.edu.au/paper.cgi?CSP08.18

Mathematics Subject Classification ID

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

Recommendations

• A simple P-complete problem and its language-theoretic representations
• DNA Computing
• On the computational complexity of P automata
• Generating small automata and the Černý conjecture
• Some computational limits of trellis automata
• A Simple P-Complete Problem and Its Representations by Language Equations
• On a representation of tree automata
• Exact complexity of problems of incompletely specified automata
• Descriptional and computational complexity of the circuit representation of finite automata
• Tight bounds for complementing parity automata

Cited in

(3)

• The hardest linear conjunctive language
• A Simple P-Complete Problem and Its Representations by Language Equations
• A simple P-complete problem and its language-theoretic representations

This page was built for publication:

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