5 Search Results for "Ryzhikov, Andrew"

Document
DOI: 10.4230/LIPIcs.MFCS.2023.40
Universality and Forall-Exactness of Cost Register Automata with Few Registers

Authors: Laure Daviaud and Andrew Ryzhikov

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
The universality problem asks whether a given finite state automaton accepts all the input words. For quantitative models of automata, where input words are mapped to real values, this is naturally extended to ask whether all the words are mapped to values above (or below) a given threshold. This is known to be undecidable for commonly studied examples such as weighted automata over the positive rational (plus-times) or the integer tropical (min-plus) semirings, or equivalently cost register automata (CRAs) over these semirings. In this paper, we prove that when restricted to CRAs with only three registers, the universality problem is still undecidable, even with additional restrictions for the CRAs to be copyless linear with resets. In contrast, we show that, assuming the unary encoding of updates, the ∀-exact problem (does the CRA output zero on all the words?) for integer min-plus linear CRAs can be decided in polynomial time if the number of registers is constant. Without the restriction on the number of registers this problem is known to be PSPACE-complete.
Cite as

Laure Daviaud and Andrew Ryzhikov. Universality and Forall-Exactness of Cost Register Automata with Few Registers. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{daviaud_et_al:LIPIcs.MFCS.2023.40,
  author =	{Daviaud, Laure and Ryzhikov, Andrew},
  title =	{{Universality and Forall-Exactness of Cost Register Automata with Few Registers}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.40},
  URN =		{urn:nbn:de:0030-drops-185744},
  doi =		{10.4230/LIPIcs.MFCS.2023.40},
  annote =	{Keywords: cost register automata, universality, forall-exact problem, decidability}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.12
Synchronizing Strongly Connected Partial DFAs

Authors: Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szykuła

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is called synchronizing if it has a word (called a reset word) whose action brings a non-empty subset of states to a unique state and is undefined for all other states. While in the general case the problem of checking whether a partial DFA is synchronizing is PSPACE-complete, we show that in the strongly connected case this problem can be efficiently reduced to the same problem for a complete DFA. Using combinatorial, algebraic, and formal languages methods, we develop techniques that relate main synchronization problems for strongly connected partial DFAs with the same problems for complete DFAs. In particular, this includes the Černý and the rank conjectures, the problem of finding a reset word, and upper bounds on the length of the shortest reset words of literal automata of finite prefix codes. We conclude that solving fundamental synchronization problems is equally hard in both models, as an essential improvement of the results for one model implies an improvement for the other.
Cite as

Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov, and Marek Szykuła. Synchronizing Strongly Connected Partial DFAs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{berlinkov_et_al:LIPIcs.STACS.2021.12,
  author =	{Berlinkov, Mikhail V. and Ferens, Robert and Ryzhikov, Andrew and Szyku{\l}a, Marek},
  title =	{{Synchronizing Strongly Connected Partial DFAs}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.12},
  URN =		{urn:nbn:de:0030-drops-136579},
  doi =		{10.4230/LIPIcs.STACS.2021.12},
  annote =	{Keywords: \v{C}ern\'{y} conjecture, literal automaton, partial automaton, prefix code, rank conjecture, reset threshold, reset word, synchronizing automaton, synchronizing word}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.54
The Degree of a Finite Set of Words

Authors: Dominique Perrin and Andrew Ryzhikov

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
We generalize the notions of the degree and composition from uniquely decipherable codes to arbitrary finite sets of words. We prove that if X = Y∘Z is a composition of finite sets of words with Y complete, then d(X) = d(Y) ⋅ d(Z), where d(T) is the degree of T. We also show that a finite set is synchronizing if and only if its degree equals one. This is done by considering, for an arbitrary finite set X of words, the transition monoid of an automaton recognizing X^* with multiplicities. We prove a number of results for such monoids, which generalize corresponding results for unambiguous monoids of relations.
Cite as

Dominique Perrin and Andrew Ryzhikov. The Degree of a Finite Set of Words. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{perrin_et_al:LIPIcs.FSTTCS.2020.54,
  author =	{Perrin, Dominique and Ryzhikov, Andrew},
  title =	{{The Degree of a Finite Set of Words}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{54:1--54:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.54},
  URN =		{urn:nbn:de:0030-drops-132952},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.54},
  annote =	{Keywords: synchronizing set, degree of a set, group of a set, monoid of relations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.57
Long Alternating Paths Exist

Authors: Wolfgang Mulzer and Pavel Valtr

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Let P be a set of 2n points in convex position, such that n points are colored red and n points are colored blue. A non-crossing alternating path on P of length 𝓁 is a sequence p₁, … , p_𝓁 of 𝓁 points from P so that (i) all points are pairwise distinct; (ii) any two consecutive points p_i, p_{i+1} have different colors; and (iii) any two segments p_i p_{i+1} and p_j p_{j+1} have disjoint relative interiors, for i ≠ j. We show that there is an absolute constant ε > 0, independent of n and of the coloring, such that P always admits a non-crossing alternating path of length at least (1 + ε)n. The result is obtained through a slightly stronger statement: there always exists a non-crossing bichromatic separated matching on at least (1 + ε)n points of P. This is a properly colored matching whose segments are pairwise disjoint and intersected by common line. For both versions, this is the first improvement of the easily obtained lower bound of n by an additive term linear in n. The best known published upper bounds are asymptotically of order 4n/3+o(n).
Cite as

Wolfgang Mulzer and Pavel Valtr. Long Alternating Paths Exist. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mulzer_et_al:LIPIcs.SoCG.2020.57,
  author =	{Mulzer, Wolfgang and Valtr, Pavel},
  title =	{{Long Alternating Paths Exist}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{57:1--57:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.57},
  URN =		{urn:nbn:de:0030-drops-122152},
  doi =		{10.4230/LIPIcs.SoCG.2020.57},
  annote =	{Keywords: Non-crossing path, bichromatic point sets}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.21
Finding Short Synchronizing Words for Prefix Codes

Authors: Andrew Ryzhikov and Marek Szykula

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
We study the problems of finding a shortest synchronizing word and its length for a given prefix code. This is done in two different settings: when the code is defined by an arbitrary decoder recognizing its star and when the code is defined by its literal decoder (whose size is polynomially equivalent to the total length of all words in the code). For the first case for every epsilon > 0 we prove n^(1 - epsilon)-inapproximability for recognizable binary maximal prefix codes, Theta(log n)-inapproximability for finite binary maximal prefix codes and n^(1/2 - epsilon)-inapproximability for finite binary prefix codes. By c-inapproximability here we mean the non-existence of a c-approximation polynomial time algorithm under the assumption P != NP, and by n the number of states of the decoder in the input. For the second case, we propose approximation and exact algorithms and conjecture that for finite maximal prefix codes the problem can be solved in polynomial time. We also study the related problems of finding a shortest mortal and a shortest avoiding word.
Cite as

Andrew Ryzhikov and Marek Szykula. Finding Short Synchronizing Words for Prefix Codes. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ryzhikov_et_al:LIPIcs.MFCS.2018.21,
  author =	{Ryzhikov, Andrew and Szykula, Marek},
  title =	{{Finding Short Synchronizing Words for Prefix Codes}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.21},
  URN =		{urn:nbn:de:0030-drops-96037},
  doi =		{10.4230/LIPIcs.MFCS.2018.21},
  annote =	{Keywords: synchronizing word, mortal word, avoiding word, Huffman decoder, inapproximability}
}
  • Refine by Author
  • 4 Ryzhikov, Andrew
  • 1 Berlinkov, Mikhail V.
  • 1 Daviaud, Laure
  • 1 Ferens, Robert
  • 1 Mulzer, Wolfgang
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Formal languages and automata theory
  • 1 Mathematics of computing → Combinatorics
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Quantitative automata

  • Refine by Keyword
  • 2 synchronizing word
  • 1 Huffman decoder
  • 1 Non-crossing path
  • 1 avoiding word
  • 1 bichromatic point sets
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2020
  • 1 2018
  • 1 2021
  • 1 2023

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact