Complexity of regex crosswords

DOI10.1007/978-3-030-13435-8_16MaRDI QIDQ2278278zbMATH OpenOpenAlexFDO

Authors Daniel Padé, S. Fenner

Publication date 4 December 2019

Full work available at URL https://doi.org/10.1007/978-3-030-13435-8_16

zbMATH Keywords

complexityNP-completepicture languageregex crosswordregular expressions

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Combinatorics in computer science (68R05)

Recommendations

• The complexity of regex crosswords
• Mathematical Foundations of Computer Science 2004
• On regular expression proof complexity
• scientific article; zbMATH DE number 7651219
• Regular expression length via arithmetic formula complexity
• Regular expression length via arithmetic formula complexity
• Descriptional complexity of deterministic regular expressions
• Succinctness of the Complement and Intersection of Regular Expressions
• Succinctness of the complement and intersection of regular expressions
• In Search of Most Complex Regular Languages

Cited in

(2)

• The complexity of regex crosswords
• On Vaughan Pratt's crossword problem

This page was built for publication: Complexity of regex crosswords

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