Search Results

Documents authored by Masopust, Tomás

Document
DOI: 10.4230/LIPIcs.MFCS.2023.16
Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification

Authors: Jiří Balun, Tomáš Masopust, and Petr Osička

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

Abstract
Opacity is a property of privacy and security applications asking whether, given a system model, a passive intruder that makes online observations of system’s behaviour can ascertain some "secret" information of the system. Deciding opacity is a PSpace-complete problem, and hence there are no polynomial-time algorithms to verify opacity under the assumption that PSpace differs from PTime. This assumption, however, gives rise to a question whether the existing exponential-time algorithms are the best possible or whether there are faster, sub-exponential-time algorithms. We show that under the (Strong) Exponential Time Hypothesis, there are no algorithms that would be significantly faster than the existing algorithms. As a by-product, we obtained a new conditional lower bound on the time complexity of deciding universality (and therefore also inclusion and equivalence) for nondeterministic finite automata.
Cite as

Jiří Balun, Tomáš Masopust, and Petr Osička. Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{balun_et_al:LIPIcs.MFCS.2023.16,
  author =	{Balun, Ji\v{r}{\'\i} and Masopust, Tom\'{a}\v{s} and Osi\v{c}ka, Petr},
  title =	{{Speed Me up If You Can: Conditional Lower Bounds on Opacity Verification}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{16:1--16: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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.16},
  URN =		{urn:nbn:de:0030-drops-185504},
  doi =		{10.4230/LIPIcs.MFCS.2023.16},
  annote =	{Keywords: Finite automata, opacity, fine-grained complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.61
On the Complexity of Universality for Partially Ordered NFAs

Authors: Markus Krötzsch, Tomás Masopust, and Michaël Thomazo

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, i.e., for which cycles occur only in the form of self-loops on a single state. A poNFA is universal if it accepts all words over its input alphabet. Deciding universality is \PSpace-complete for poNFAs, and we show that this remains true even when restricting to a fixed alphabet. This is nontrivial since standard encodings of alphabet symbols in, e.g., binary can turn self-loops into longer cycles. A lower coNP-complete complexity bound can be obtained if we require that all self-loops in the poNFA are deterministic, in the sense that the symbol read in the loop cannot occur in any other transition from that state. We find that such restricted poNFAs (rpoNFAs) characterise the class of R-trivial languages, and we establish the complexity of deciding if the language of an NFA is R-trivial. Nevertheless, the limitation to fixed alphabets turns out to be essential even in the restricted case: deciding universality of rpoNFAs with unbounded alphabets is PSPACE-complete. Our results also prove the complexity of the inclusion and equivalence problems, since universality provides the lower bound, while the upper bound is mostly known or proved in the paper.
Cite as

Markus Krötzsch, Tomás Masopust, and Michaël Thomazo. On the Complexity of Universality for Partially Ordered NFAs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{krotzsch_et_al:LIPIcs.MFCS.2016.61,
  author =	{Kr\"{o}tzsch, Markus and Masopust, Tom\'{a}s and Thomazo, Micha\"{e}l},
  title =	{{On the Complexity of Universality for Partially Ordered NFAs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{61:1--61:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.61},
  URN =		{urn:nbn:de:0030-drops-64738},
  doi =		{10.4230/LIPIcs.MFCS.2016.61},
  annote =	{Keywords: automata, nondeterminism, partial order, universality}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.67
Piecewise Testable Languages and Nondeterministic Automata

Authors: Tomás Masopust

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
A regular language is k-piecewise testable if it is a finite boolean combination of languages of the form Sigma^* a_1 Sigma^* ... Sigma^* a_n Sigma^*, where a_i in Sigma and 0 <= n <= k. Given a DFA A and k >= 0, it is an NL-complete problem to decide whether the language L(A) is piecewise testable and, for k >= 4, it is coNP-complete to decide whether the language L(A) is k-piecewise testable. It is known that the depth of the minimal DFA serves as an upper bound on k. Namely, if L(A) is piecewise testable, then it is k-piecewise testable for k equal to the depth of A. In this paper, we show that some form of nondeterminism does not violate this upper bound result. Specifically, we define a class of NFAs, called ptNFAs, that recognize piecewise testable languages and show that the depth of a ptNFA provides an (up to exponentially better) upper bound on k than the minimal DFA. We provide an application of our result, discuss the relationship between k-piecewise testability and the depth of NFAs, and study the complexity of k-piecewise testability for ptNFAs.
Cite as

Tomás Masopust. Piecewise Testable Languages and Nondeterministic Automata. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{masopust:LIPIcs.MFCS.2016.67,
  author =	{Masopust, Tom\'{a}s},
  title =	{{Piecewise Testable Languages and Nondeterministic Automata}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.67},
  URN =		{urn:nbn:de:0030-drops-64799},
  doi =		{10.4230/LIPIcs.MFCS.2016.67},
  annote =	{Keywords: automata, logics, languages, k-piecewise testability, nondeterminism}
}
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 About DROPS Imprint Privacy Contact