2 Search Results for "Schmidt-Eisenlohr, Felix"

Document
DOI: 10.4230/LIPIcs.CSL.2023.35
Dynamic Complexity of Regular Languages: Big Changes, Small Work

Authors: Felix Tschirbs, Nils Vortmeier, and Thomas Zeume

Published in: LIPIcs, Volume 252, 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)

Abstract
Whether a changing string is member of a certain regular language can be maintained in the DynFO framework of Patnaik and Immerman: after changing the symbol at one position of the string, a first-order update formula can express - using additionally stored information - whether the resulting string is in the regular language. We extend this and further known results by considering changes of many positions at once. We also investigate to which degree the obtained update formulas imply work-efficient parallel dynamic algorithms.
Cite as

Felix Tschirbs, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity of Regular Languages: Big Changes, Small Work. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 252, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{tschirbs_et_al:LIPIcs.CSL.2023.35,
  author =	{Tschirbs, Felix and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Dynamic Complexity of Regular Languages: Big Changes, Small Work}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{35:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2023.35},
  URN =		{urn:nbn:de:0030-drops-174963},
  doi =		{10.4230/LIPIcs.CSL.2023.35},
  annote =	{Keywords: dynamic descriptive complexity, regular languages, batch changes, work}
}
Document
DOI: 10.4230/DagSemProc.10402.2
10402 Report – Working Group on Communication Patterns

Authors: Claudio Casetti, Falko Dressler, Lars Eggert, Felix Schmidt-Eisenlohr, Jerome Haerri, Ozan K. Tonguz, Jörg Ott, and Lars Wischhof

Published in: Dagstuhl Seminar Proceedings, Volume 10402, Inter-Vehicular Communication (2011)

Abstract
The objective of the working group communication patterns during the Dagstuhl Seminar on Vehicular Networks has been to review the current status of the communication patterns and principles and discuss the upcoming challenges the community will face in the near future. This is an executive summary of the discussions during the sessions.
Cite as

Claudio Casetti, Falko Dressler, Lars Eggert, Felix Schmidt-Eisenlohr, Jerome Haerri, Ozan K. Tonguz, Jörg Ott, and Lars Wischhof. 10402 Report – Working Group on Communication Patterns. In Inter-Vehicular Communication. Dagstuhl Seminar Proceedings, Volume 10402, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{casetti_et_al:DagSemProc.10402.2,
  author =	{Casetti, Claudio and Dressler, Falko and Eggert, Lars and Schmidt-Eisenlohr, Felix and Haerri, Jerome and Tonguz, Ozan K. and Ott, J\"{o}rg and Wischhof, Lars},
  title =	{{10402 Report – Working Group on Communication Patterns}},
  booktitle =	{Inter-Vehicular Communication},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10402},
  editor =	{Falko Dressler and Frank Kargl and J\"{o}rg Ott and Ozan K. Tonguz and Lars Wischhof},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10402.2},
  URN =		{urn:nbn:de:0030-drops-29287},
  doi =		{10.4230/DagSemProc.10402.2},
  annote =	{Keywords: V2V, communication principles}
}
  • Refine by Author
  • 1 Casetti, Claudio
  • 1 Dressler, Falko
  • 1 Eggert, Lars
  • 1 Haerri, Jerome
  • 1 Ott, Jörg
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Complexity theory and logic
  • 1 Theory of computation → Logic and databases

  • Refine by Keyword
  • 1 V2V
  • 1 batch changes
  • 1 communication principles
  • 1 dynamic descriptive complexity
  • 1 regular languages
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 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