3 Search Results for "Majumdar, Rupak M."

Document
DOI: 10.4230/LIPIcs.ITCS.2024.22
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds

Authors: Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphabets. We show that this barrier appears in many variations throughout the algorithmic literature by introducing a framework of Colored Walk problems. These yield fine-grained equivalent formulations of the NFA Acceptance problem as problems concerning detection of an s-t-walk with a prescribed color sequence in a given edge- or node-colored graph. For NFA Acceptance on sparse NFAs (or equivalently, Colored Walk in sparse graphs), a tight lower bound under the Strong Exponential Time Hypothesis has been rediscovered several times in recent years. We show that our hardness hypothesis, which concerns dense NFAs, has several interesting implications: - It gives a tight lower bound for Context-Free Language Reachability. This proves conditional optimality for the class of 2NPDA-complete problems, explaining the cubic bottleneck of interprocedural program analysis. - It gives a tight (n+nm^{1/3})^{1-o(1)} lower bound for the Word Break problem on strings of length n and dictionaries of total size m. - It implies the popular OMv hypothesis. Since the NFA acceptance problem is a static (i.e., non-dynamic) problem, this provides a static reason for the hardness of many dynamic problems. Thus, a proof of the NFA Acceptance hypothesis would resolve several interesting barriers. Conversely, a refutation of the NFA Acceptance hypothesis may lead the way to attacking the current barriers observed for Context-Free Language Reachability, the Word Break problem and the growing list of dynamic problems proven hard under the OMv hypothesis.
Cite as

Karl Bringmann, Allan Grønlund, Marvin Künnemann, and Kasper Green Larsen. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ITCS.2024.22,
  author =	{Bringmann, Karl and Gr{\o}nlund, Allan and K\"{u}nnemann, Marvin and Larsen, Kasper Green},
  title =	{{The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{22:1--22:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.22},
  URN =		{urn:nbn:de:0030-drops-195500},
  doi =		{10.4230/LIPIcs.ITCS.2024.22},
  annote =	{Keywords: Fine-grained complexity theory, non-deterministic finite automata}
}
Document
DOI: 10.4230/DagRep.4.3.85
Verification of Cyber-Physical Systems (Dagstuhl Seminar 14122)

Authors: Rupak Majumdar, Richard M. Murray, and Pavithra Prabhakar

Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)

Abstract
Cyber-physical systems refer to a new genre of engineered systems consisting of a tight coupling between computation, communication and physical entities. The main focus of the seminar was to discuss issues related to the reliable development of cyber-physical systems by using formal verification. This is a multi-disciplinary area requiring collaboration between areas focusing discrete systems analysis and continuous systems analysis. To this end, the seminar brought together researchers working in the fields of formal methods, control theory and hybrid systems to identify and discuss potential issues and research questions which require collaboration between the communities. This report documents the program and the outcomes of Dagstuhl Seminar 14122 "Verification of Cyber-Physical Systems".
Cite as

Rupak Majumdar, Richard M. Murray, and Pavithra Prabhakar. Verification of Cyber-Physical Systems (Dagstuhl Seminar 14122). In Dagstuhl Reports, Volume 4, Issue 3, pp. 85-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{majumdar_et_al:DagRep.4.3.85,
  author =	{Majumdar, Rupak and Murray, Richard M. and Prabhakar, Pavithra},
  title =	{{Verification of Cyber-Physical Systems (Dagstuhl Seminar 14122)}},
  pages =	{85--102},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{3},
  editor =	{Majumdar, Rupak and Murray, Richard M. and Prabhakar, Pavithra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.4.3.85},
  URN =		{urn:nbn:de:0030-drops-45937},
  doi =		{10.4230/DagRep.4.3.85},
  annote =	{Keywords: Formal Verification, Cyber-Physical Systems, Hybrid Systems}
}
Document
DOI: 10.4230/DagRep.2.11.45
Games and Decisions for Rigorous Systems Engineering (Dagstuhl Seminar 12461)

Authors: Nikolaj Bjorner, Krishnendu Chatterjee, Laura Kovacs, and Rupak M. Majumdar

Published in: Dagstuhl Reports, Volume 2, Issue 11 (2013)

Abstract
This report documents the program and the outcomes of the Dagstuhl Seminar 12461 "Games and Decisions for Rigorous Systems Engineering". The seminar brought together researchers working in rigorous software engineering, with a special focus on the interaction between synthesis and automated deduction. This event was the first seminar of this kind and a kickoff of a series of seminars organised on rigorous systems engineering. The theme of the seminar was close in spirit to many events that have been held over the last decades. The talks scheduled during the seminar naturally reflected fundamental research themes of the involved communities.
Cite as

Nikolaj Bjorner, Krishnendu Chatterjee, Laura Kovacs, and Rupak M. Majumdar. Games and Decisions for Rigorous Systems Engineering (Dagstuhl Seminar 12461). In Dagstuhl Reports, Volume 2, Issue 11, pp. 45-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{bjorner_et_al:DagRep.2.11.45,
  author =	{Bjorner, Nikolaj and Chatterjee, Krishnendu and Kovacs, Laura and Majumdar, Rupak M.},
  title =	{{Games and Decisions for Rigorous Systems Engineering (Dagstuhl Seminar 12461)}},
  pages =	{45--65},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Bjorner, Nikolaj and Chatterjee, Krishnendu and Kovacs, Laura and Majumdar, Rupak M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.2.11.45},
  URN =		{urn:nbn:de:0030-drops-39092},
  doi =		{10.4230/DagRep.2.11.45},
  annote =	{Keywords: Systems Engineering, Software Verification, Reactive Synthesis, Automated Deduction}
}
  • Refine by Author
  • 1 Bjorner, Nikolaj
  • 1 Bringmann, Karl
  • 1 Chatterjee, Krishnendu
  • 1 Grønlund, Allan
  • 1 Kovacs, Laura
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Automated Deduction
  • 1 Cyber-Physical Systems
  • 1 Fine-grained complexity theory
  • 1 Formal Verification
  • 1 Hybrid Systems
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2013
  • 1 2014
  • 1 2024

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