4 Search Results for "Gutiérrez, Elena"


Document
A Practical Algorithm for Chess Unwinnability

Authors: Miguel Ambrona

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)


Abstract
The FIDE Laws of Chess establish that if a player runs out of time during a game, they lose unless there exists no sequence of legal moves that ends in a checkmate by their opponent, in which case the game is drawn. The problem of determining whether or not a given chess position is unwinnable for a certain player has been considered intractable by the community and, consequently, chess servers do not apply the above rule rigorously, thus unfairly classifying many games. We propose, to the best of our knowledge, the first algorithm for chess unwinnability that is sound, complete and efficient for practical use. We also develop a prototype implementation and evaluate it over the entire Lichess Database (containing more than 3 billion games), successfully identifying all unfairly classified games in the database.

Cite as

Miguel Ambrona. A Practical Algorithm for Chess Unwinnability. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 2:1-2:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{ambrona:LIPIcs.FUN.2022.2,
  author =	{Ambrona, Miguel},
  title =	{{A Practical Algorithm for Chess Unwinnability}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{2:1--2:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.2},
  URN =		{urn:nbn:de:0030-drops-159721},
  doi =		{10.4230/LIPIcs.FUN.2022.2},
  annote =	{Keywords: chess, helpmate, unwinnability, timeout, dead position}
}
Document
A Quasiorder-Based Perspective on Residual Automata

Authors: Pierre Ganty, Elena Gutiérrez, and Pedro Valero

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)


Abstract
In this work, we define a framework of automata constructions based on quasiorders over words to provide new insights on the class of residual automata. We present a new residualization operation and a generalized double-reversal method for building the canonical residual automaton for a given language. Finally, we use our framework to offer a quasiorder-based perspective on NL^*, an online learning algorithm for residual automata. We conclude that quasiorders are fundamental to residual automata as congruences are to deterministic automata.

Cite as

Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A Quasiorder-Based Perspective on Residual Automata. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{ganty_et_al:LIPIcs.MFCS.2020.40,
  author =	{Ganty, Pierre and Guti\'{e}rrez, Elena and Valero, Pedro},
  title =	{{A Quasiorder-Based Perspective on Residual Automata}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.40},
  URN =		{urn:nbn:de:0030-drops-127071},
  doi =		{10.4230/LIPIcs.MFCS.2020.40},
  annote =	{Keywords: Residual Automata, Quasiorders, Double-Reversal Method, Canonical RFA, Regular Languages}
}
Document
A Congruence-based Perspective on Automata Minimization Algorithms

Authors: Pierre Ganty, Elena Gutiérrez, and Pedro Valero

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)


Abstract
In this work we use a framework of finite-state automata constructions based on equivalences over words to provide new insights on the relation between well-known methods for computing the minimal deterministic automaton of a language.

Cite as

Pierre Ganty, Elena Gutiérrez, and Pedro Valero. A Congruence-based Perspective on Automata Minimization Algorithms. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 77:1-77:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{ganty_et_al:LIPIcs.MFCS.2019.77,
  author =	{Ganty, Pierre and Guti\'{e}rrez, Elena and Valero, Pedro},
  title =	{{A Congruence-based Perspective on Automata Minimization Algorithms}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{77:1--77:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.77},
  URN =		{urn:nbn:de:0030-drops-110214},
  doi =		{10.4230/LIPIcs.MFCS.2019.77},
  annote =	{Keywords: Double-Reversal Method, Minimization, Automata, Congruences, Regular Languages}
}
Document
The Parikh Property for Weighted Context-Free Grammars

Authors: Pierre Ganty and Elena Gutiérrez

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)


Abstract
Parikh's Theorem states that every context-free grammar (CFG) is equivalent to some regular CFG when the ordering of symbols in the words is ignored. The same is not true for the so-called weighted CFGs, which additionally assign a weight to each grammar rule. If the result holds for a given weighted CFG G, we say that G satisfies the Parikh property. We prove constructively that the Parikh property holds for every weighted nonexpansive CFG. We also give a decision procedure for the property when the weights are over the rationals.

Cite as

Pierre Ganty and Elena Gutiérrez. The Parikh Property for Weighted Context-Free Grammars. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{ganty_et_al:LIPIcs.FSTTCS.2018.32,
  author =	{Ganty, Pierre and Guti\'{e}rrez, Elena},
  title =	{{The Parikh Property for Weighted Context-Free Grammars}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{32:1--32:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.32},
  URN =		{urn:nbn:de:0030-drops-99315},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.32},
  annote =	{Keywords: Weighted Context-Free Grammars, Algebraic Language Theory, Parikh Image}
}
  • Refine by Author
  • 3 Ganty, Pierre
  • 3 Gutiérrez, Elena
  • 2 Valero, Pedro
  • 1 Ambrona, Miguel

  • Refine by Classification
  • 2 Theory of computation → Formal languages and automata theory
  • 2 Theory of computation → Regular languages
  • 1 Software and its engineering → Software libraries and repositories
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Grammars and context-free languages

  • Refine by Keyword
  • 2 Double-Reversal Method
  • 2 Regular Languages
  • 1 Algebraic Language Theory
  • 1 Automata
  • 1 Canonical RFA
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2018
  • 1 2019
  • 1 2020
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail