Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Modern Aspects of Complexity Within Formal Languages Read chapter Read first chapter

2019 | OriginalPaper | Chapter

Complexity of Regex Crosswords

Authors : Stephen Fenner, Daniel Padé

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In a regular expression crossword puzzle, one is given two non-empty lists \(\langle {} \langle {} R_1,\ldots , R_m \rangle {}\) and \(\langle {} C_1, \ldots , C_n \rangle {} \rangle {}\) over some alphabet, and the challenge is to fill in an \(m\times n\) grid of characters such that the string formed by the \(i^\text {th}\) row is in \(L(R_i)\) and the string in the \(j^\text {th}\) column is in \(L(C_j)\). We consider a restriction of this puzzle where all the \(R_i\) are equal to one another and similarly the \(C_j\). We consider a 2-player version of this puzzle, showing it to be https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-13435-8_16/480713_1_En_16_IEq10_HTML.gif -complete. Using a reduction from https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-13435-8_16/480713_1_En_16_IEq11_HTML.gif , we also give a new, simple proof of the known result that the existence problem of a solution for the restricted (1-player) puzzle is https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-13435-8_16/480713_1_En_16_IEq12_HTML.gif -complete.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter State Complexity of Pseudocatenation
next chapter Generalized Predictive Shift-Reduce Parsing for Hyperedge Replacement Graph Grammars
Footnotes
1
Glen Takahashi posted this question to Stack Exchange in 2012 [13], but it has been asked by others independently.
 
2
In the same paper, a restriction of https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-13435-8_16/480713_1_En_16_IEq32_HTML.gif where the unique row and column regexes are equal to each other was also shown https://static-content.springer.com/image/chp%3A10.1007%2F978-3-030-13435-8_16/480713_1_En_16_IEq33_HTML.gif -complete.
 
3
More precisely, the question is whether the sentence \(\exists x_0 \forall y_0 \cdots \exists x_{k-1} \forall y_{k-1}\exists x_k [\tilde{\varphi }(x_0, y_0, \ldots , x_{k-1}, y_{k-1}, x_k) = \textsc {True}]\) holds in the two-element Boolean algebra \((\{\textsc {False},\textsc {True}\},\mathrel {\wedge },\mathrel {\vee },\lnot )\).
 
4
For the last move of the game, Rose or Colin may encounter a row or column, respectively, that is already completely filled in. In this case, she or he wins if and only if the row or column matches the corresponding regular expression.
 
Literature
1.
2.
3.
4.
5.
6.
Berger, R.: The undecidability of the domino problem. No. 66 in memoirs of the American Mathematical Society. American Mathematical Society, Providence, Rhode Island (1966). mR0216954MathSciNetCrossRef
7.
8.
Fenner, S.: The complexity of some regex crossword problems (2014)
9.
Giammarresi, D., Restivo, A.: Recognizable picture languages. Int. J. Pattern Recogn. Artif. Intell. 31–46 (1992)
10.
11.
Latteux, M., Simplot, D.: Recognizable picture languages and domino tiling. Theor. Comput. Sci. 178(1–2), 275–283 (1997). NoteMathSciNetCrossRef
12.
Rosenfeld, A., Rheinboldt, W.: Picture Languages: Formal Models for Picture Recognition. Computer Science and Applied Mathematics. Elsevier Inc., Academic Press Inc., New York (1979)MATH
13.
14.
Metadata
Title
Complexity of Regex Crosswords
Authors
Stephen Fenner
Daniel Padé
Copyright Year
2019
Book
Language and Automata Theory and Applications

Print ISBN: 978-3-030-13434-1

Electronic ISBN: 978-3-030-13435-8

Copyright Year: 2019

DOI
https://doi.org/10.1007/978-3-030-13435-8_16

Premium Partner

    Image Credits