4 Search Results for "Vermeir, Dirk"

Document
DOI: 10.4230/LIPIcs.STACS.2026.41
On the Complexity of Computing Strahler Numbers

Authors: Moses Ganardi and Markus Lohrey

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
It is shown that the problem of computing the Strahler number of a binary tree given as a term is complete for the circuit complexity class uniform NC¹. For several variants, where the binary tree is given by a pointer structure or in a succinct form by a directed acyclic graph or a tree straight-line program, the complexity of computing the Strahler number is determined as well. The problem, whether a given context-free grammar in Chomsky normal form produces a derivation tree (resp., an acyclic derivation tree), whose Strahler number is at least a given number k is shown to be P-complete (resp., PSPACE-complete).
Cite as

Moses Ganardi and Markus Lohrey. On the Complexity of Computing Strahler Numbers. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 41:1-41:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ganardi_et_al:LIPIcs.STACS.2026.41,
  author =	{Ganardi, Moses and Lohrey, Markus},
  title =	{{On the Complexity of Computing Strahler Numbers}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{41:1--41:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.41},
  URN =		{urn:nbn:de:0030-drops-255301},
  doi =		{10.4230/LIPIcs.STACS.2026.41},
  annote =	{Keywords: Strahler number, circuit complexity classes, context-free grammars}
}
Document
DOI: 10.4230/OASIcs.Gabbrielli.9
A Concurrent Language for Argumentation: Preliminary Notes

Authors: Stefano Bistarelli and Carlo Taticchi

Published in: OASIcs, Volume 86, Recent Developments in the Design and Implementation of Programming Languages (2020)

Abstract
While agent-based modelling languages naturally implement concurrency, the currently available languages for argumentation do not allow to explicitly model this type of interaction. In this paper we introduce a concurrent language for handling process arguing and communicating using a shared argumentation framework (reminding shared constraint store as in concurrent constraint). We introduce also basic expansions, contraction and revision procedures as main bricks for enforcement, debate, negotiation and persuasion.
Cite as

Stefano Bistarelli and Carlo Taticchi. A Concurrent Language for Argumentation: Preliminary Notes. In Recent Developments in the Design and Implementation of Programming Languages. Open Access Series in Informatics (OASIcs), Volume 86, pp. 9:1-9:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bistarelli_et_al:OASIcs.Gabbrielli.9,
  author =	{Bistarelli, Stefano and Taticchi, Carlo},
  title =	{{A Concurrent Language for Argumentation: Preliminary Notes}},
  booktitle =	{Recent Developments in the Design and Implementation of Programming Languages},
  pages =	{9:1--9:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-171-9},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{86},
  editor =	{de Boer, Frank S. and Mauro, Jacopo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Gabbrielli.9},
  URN =		{urn:nbn:de:0030-drops-132311},
  doi =		{10.4230/OASIcs.Gabbrielli.9},
  annote =	{Keywords: Argumentation, Concurrent Language, Debating, Negotiation, Belief Revision}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2010.34
Communicating Answer Set Programs

Authors: Kim Bauters, Jeroen Janssen, Steven Schockaert, Dirk Vermeir, and Martine De Cock

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract
Answer set programming is a form of declarative programming that has proven very successful in succinctly formulating and solving complex problems. Although mechanisms for representing and reasoning with the combined answer set programs of multiple agents have already been proposed, the actual gain in expressivity when adding communication has not been thoroughly studied. We show that allowing simple programs to talk to each other results in the same expressivity as adding negation-as-failure. Furthermore, we show that the ability to focus on one program in a network of simple programs results in the same expressivity as adding disjunction in the head of the rules.
Cite as

Kim Bauters, Jeroen Janssen, Steven Schockaert, Dirk Vermeir, and Martine De Cock. Communicating Answer Set Programs. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 34-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{bauters_et_al:LIPIcs.ICLP.2010.34,
  author =	{Bauters, Kim and Janssen, Jeroen and Schockaert, Steven and Vermeir, Dirk and De Cock, Martine},
  title =	{{Communicating Answer Set Programs}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{34--43},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.34},
  URN =		{urn:nbn:de:0030-drops-25813},
  doi =		{10.4230/LIPIcs.ICLP.2010.34},
  annote =	{Keywords: }
}
Document
DOI: 10.4230/LIPIcs.ICLP.2010.64
Efficient Solving of Time-dependent Answer Set Programs

Authors: Timur Fayruzov, Jeroen Janssen, Dirk Vermeir, Chris Cornelis, and Martine De Cock

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract
Answer set programs with time predicates are useful to model systems whose properties depend on time, like for example gene regulatory networks. A state of such a system at time point t then corresponds to the literals of an answer set that are grounded with time constant t. An important task when modelling time-dependent systems is to find steady states from which the system's behaviour does not change anymore. This task is complicated by the fact that it is typically not known in advance at what time steps these steady states occur. A brute force approach of estimating a time upper bound tmax and grounding and solving the program w.r.t. that upper bound leads to a suboptimal solving time when the estimate is too low or too high. In this paper we propose a more efficient algorithm for solving Markovian programs, which are time-dependent programs for which the next state depends only on the previous state. Instead of solving these Markovian programs for a long time interval {0,...,tmax}, we successively find answer sets of parts of the grounded program. Our approach guarantees the discovery of all steady states and cycles while avoiding unnecessary extra work.
Cite as

Timur Fayruzov, Jeroen Janssen, Dirk Vermeir, Chris Cornelis, and Martine De Cock. Efficient Solving of Time-dependent Answer Set Programs. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 64-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fayruzov_et_al:LIPIcs.ICLP.2010.64,
  author =	{Fayruzov, Timur and Janssen, Jeroen and Vermeir, Dirk and Cornelis, Chris and De Cock, Martine},
  title =	{{Efficient Solving of Time-dependent Answer Set Programs}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{64--73},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.64},
  URN =		{urn:nbn:de:0030-drops-25841},
  doi =		{10.4230/LIPIcs.ICLP.2010.64},
  annote =	{Keywords: Answer set programming, time-dependent programs, gene regulation networks}
}
  • Refine by Type
  • 4 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2020
  • 2 2010

  • Refine by Author
  • 2 De Cock, Martine
  • 2 Janssen, Jeroen
  • 2 Vermeir, Dirk
  • 1 Bauters, Kim
  • 1 Bistarelli, Stefano
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 1 Computing methodologies → Concurrent programming languages
  • 1 Computing methodologies → Knowledge representation and reasoning
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Grammars and context-free languages

  • Refine by Keyword
  • 1 Answer set programming
  • 1 Argumentation
  • 1 Belief Revision
  • 1 Concurrent Language
  • 1 Debating
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact