21 Search Results for "Hlinen�, Petr"

Document
DOI: 10.4230/LIPIcs.SoCG.2018.33
Structure and Generation of Crossing-Critical Graphs

Authors: Zdenek Dvorák, Petr Hlinený, and Bojan Mohar

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_{3,3}, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.
Cite as

Zdenek Dvorák, Petr Hlinený, and Bojan Mohar. Structure and Generation of Crossing-Critical Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2018.33,
  author =	{Dvor\'{a}k, Zdenek and Hlinen\'{y}, Petr and Mohar, Bojan},
  title =	{{Structure and Generation of Crossing-Critical Graphs}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.33},
  URN =		{urn:nbn:de:0030-drops-87460},
  doi =		{10.4230/LIPIcs.SoCG.2018.33},
  annote =	{Keywords: crossing number, crossing-critical, path-width, exhaustive generation}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.21
On Colourability of Polygon Visibility Graphs

Authors: Onur Cagirici, Petr Hlinený, and Bodhayan Roy

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
We study the problem of colouring the visibility graphs of polygons. In particular, we provide a polynomial algorithm for 4-colouring of the polygon visibility graphs, and prove that the 6- colourability question is already NP-complete for them.
Cite as

Onur Cagirici, Petr Hlinený, and Bodhayan Roy. On Colourability of Polygon Visibility Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cagirici_et_al:LIPIcs.FSTTCS.2017.21,
  author =	{Cagirici, Onur and Hlinen\'{y}, Petr and Roy, Bodhayan},
  title =	{{On Colourability of Polygon Visibility Graphs}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.21},
  URN =		{urn:nbn:de:0030-drops-83814},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.21},
  annote =	{Keywords: polygon visibility graph, graph coloring, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.30
Inserting Multiple Edges into a Planar Graph

Authors: Markus Chimani and Petr Hlinený

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
Let G be a connected planar (but not yet embedded) graph and F a set of additional edges not in G. The multiple edge insertion problem (MEI) asks for a drawing of G+F with the minimum number of pairwise edge crossings, such that the subdrawing of G is plane. An optimal solution to this problem is known to approximate the crossing number of the graph G+F. Finding an exact solution to MEI is NP-hard for general F, but linear time solvable for the special case of |F|=1 [Gutwenger et al, SODA 2001/Algorithmica] and polynomial time solvable when all of F are incident to a new vertex [Chimani et al, SODA 2009]. The complexity for general F but with constant k=|F| was open, but algorithms both with relative and absolute approximation guarantees have been presented [Chuzhoy et al, SODA 2011], [Chimani-Hlineny, ICALP 2011]. We show that the problem is fixed parameter tractable (FPT) in k for biconnected G, or if the cut vertices of G have bounded degrees. We give the first exact algorithm for this problem; it requires only O(|V(G)|) time for any constant k.
Cite as

Markus Chimani and Petr Hlinený. Inserting Multiple Edges into a Planar Graph. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.SoCG.2016.30,
  author =	{Chimani, Markus and Hlinen\'{y}, Petr},
  title =	{{Inserting Multiple Edges into a Planar Graph}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.30},
  URN =		{urn:nbn:de:0030-drops-59223},
  doi =		{10.4230/LIPIcs.SoCG.2016.30},
  annote =	{Keywords: crossing number, edge insertion, parameterized complexity, path homotopy, funnel algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.42
Crossing Number is Hard for Kernelization

Authors: Petr Hlinený and Marek Dernár

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
The graph crossing number problem, cr(G)<=k, asks for a drawing of a graph G in the plane with at most k edge crossings. Although this problem is in general notoriously difficult, it is fixed-parameter tractable for the parameter k [Grohe, STOC 2001]. This suggests a closely related question of whether this problem has a polynomial kernel, meaning whether every instance of cr(G)<=k can be in polynomial time reduced to an equivalent instance of size polynomial in k (and independent of |G|). We answer this question in the negative. Along the proof we show that the tile crossing number problem of twisted planar tiles is NP-hard, which has been an open problem for some time, too, and then employ the complexity technique of cross-composition. Our result holds already for the special case of graphs obtained from planar graphs by adding one edge.
Cite as

Petr Hlinený and Marek Dernár. Crossing Number is Hard for Kernelization. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hlineny_et_al:LIPIcs.SoCG.2016.42,
  author =	{Hlinen\'{y}, Petr and Dern\'{a}r, Marek},
  title =	{{Crossing Number is Hard for Kernelization}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{42:1--42:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.42},
  URN =		{urn:nbn:de:0030-drops-59347},
  doi =		{10.4230/LIPIcs.SoCG.2016.42},
  annote =	{Keywords: crossing number; tile crossing number; parameterized complexity; polynomial kernel; cross-composition}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.MEMICS.2009
OASIcs, Volume 13, MEMICS'09, Complete Volume

Authors: Petr Hlinený, Václav Matyáš, and Tomáš Vojnar

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
OASIcs, Volume 13, MEMICS'09, Complete Volume
Cite as

Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@Proceedings{hlineny_et_al:OASIcs.MEMICS.2009,
  title =	{{OASIcs, Volume 13, MEMICS'09, Complete Volume}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2009},
  URN =		{urn:nbn:de:0030-drops-35756},
  doi =		{10.4230/OASIcs.MEMICS.2009},
  annote =	{Keywords: Mathematics of Computing, Physical Sciences and Engineering}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2010.73
Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width

Authors: Robert Ganian, Petr Hlinený, and Jan Obdrzálek

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract
We provide a parameterized polynomial algorithm for the propositional model counting problem #SAT, the runtime of which is single-exponential in the rank-width of a formula. Previously, analogous algorithms have been known --e.g. [Fischer, Makowsky, and Ravve]-- with a single-exponential dependency on the clique-width of a formula. Our algorithm thus presents an exponential runtime improvement (since clique-width reaches up to exponentially higher values than rank-width), and can be of practical interest for small values of rank-width. We also provide an algorithm for the MAX-SAT problem along the same lines.
Cite as

Robert Ganian, Petr Hlinený, and Jan Obdrzálek. Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 73-83, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.FSTTCS.2010.73,
  author =	{Ganian, Robert and Hlinen\'{y}, Petr and Obdrz\'{a}lek, Jan},
  title =	{{Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{73--83},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.73},
  URN =		{urn:nbn:de:0030-drops-28541},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.73},
  annote =	{Keywords: propositional model counting; satisfiability; rank-width; clique-width ; parameterized complexity}
}
Document
Front Matter
DOI: 10.4230/DROPS.MEMICS.2009.2342
Preface -- Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)

Authors: Petr Hlinený, Václav Matyáš, and Tomáš Vojnar

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
The 2009 edition of the International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) is the fifth in a~row of three-day workshops organized in South Moravia by Faculty of Information Technology of Brno University of Technology and Faculty of Informatics of Masaryk University. MEMICS'09 was held in Znojmo, Czech Republic, on November 13--15, 2009.
Cite as

Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. i-vi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{hlineny_et_al:OASIcs:2009:DROPS.MEMICS.2009.2342,
  author =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  title =	{{Preface -- Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{i--vi},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2342},
  URN =		{urn:nbn:de:0030-drops-23425},
  doi =		{10.4230/DROPS.MEMICS.2009.2342},
  annote =	{Keywords: MEMICS 2009}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2355
A Privacy-Aware Protocol for Sociometric Questionnaires

Authors: Marián Novotný

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
In the paper we design a protocol for sociometric questionnaires, which serves the privacy of responders. We propose a representation of a sociogram by a weighted digraph and interpret individual and collective phenomena of sociometry in terms of graph theory. We discuss security requirements for a privacy-aware protocol for sociometric questionnaires. In the scheme we use additively homomorphic public key cryptosystem, which allows single multiplication. We present the threshold version of the public key system and define individual phases of the scheme. The proposed protocol ensures desired security requirements and can compute sociometric indices without revealing private information about choices of responders.
Cite as

Marián Novotný. A Privacy-Aware Protocol for Sociometric Questionnaires. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{novotny:OASIcs:2009:DROPS.MEMICS.2009.2355,
  author =	{Novotn\'{y}, Mari\'{a}n},
  title =	{{A Privacy-Aware Protocol for Sociometric Questionnaires}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{1--9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2355},
  URN =		{urn:nbn:de:0030-drops-23551},
  doi =		{10.4230/DROPS.MEMICS.2009.2355},
  annote =	{Keywords: Sociometry, sociogram, privacy, homomorphic encryption, security protocols}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2345
A Quantitative Characterization of Weighted Kripke Structures in Temporal Logic

Authors: Kim G. Larsen, Uli Fahrenberg, and Claus Thrane

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
We extend the usual notion of Kripke Structures with a weighted transition relation, and generalize the usual Boolean satisfaction relation of CTL to a map which assigns to states and temporal formulae a real-valued distance describing the degree of satisfaction. We describe a general approach to obtaining quantitative interpretations for a generic extension of the CTL syntax, and show that, for one such interpretation, the logic is both adequate and expressive with respect to quantitative bisimulation.
Cite as

Kim G. Larsen, Uli Fahrenberg, and Claus Thrane. A Quantitative Characterization of Weighted Kripke Structures in Temporal Logic. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 10-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{larsen_et_al:OASIcs:2009:DROPS.MEMICS.2009.2345,
  author =	{Larsen, Kim G. and Fahrenberg, Uli and Thrane, Claus},
  title =	{{A Quantitative Characterization of Weighted Kripke Structures in Temporal Logic}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{10--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2345},
  URN =		{urn:nbn:de:0030-drops-23454},
  doi =		{10.4230/DROPS.MEMICS.2009.2345},
  annote =	{Keywords: Quantitative analysis, Kripke structures, characteristic formulae, bisimulation distance, weighted CTL}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2349
Comparison of Algorithms for Checking Emptiness on Büchi Automata

Authors: Andreas Gaiser and Stefan Schwoon

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
We re-investigate the problem of LTL model-checking for finite-state systems. Typical solutions, like in Spin, work on the fly, reducing the problem to Büchi emptiness. This can be done in linear time, and a variety of algorithms with this property exist. Nonetheless, subtle design decisions can make a great difference to their actual performance in practice, especially when used on-the-fly. We compare a number of algorithms experimentally on a large benchmark suite, measure their actual run-time performance, and propose improvements. Compared with the algorithm implemented in Spin, our best algorithm is faster by about 33 % on average. We therefore recommend that, for on-the-fly explicit-state model checking, nested DFS should be replaced by better solutions.
Cite as

Andreas Gaiser and Stefan Schwoon. Comparison of Algorithms for Checking Emptiness on Büchi Automata. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 18-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{gaiser_et_al:OASIcs:2009:DROPS.MEMICS.2009.2349,
  author =	{Gaiser, Andreas and Schwoon, Stefan},
  title =	{{Comparison of Algorithms for Checking Emptiness on B\"{u}chi Automata}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{18--26},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2349},
  URN =		{urn:nbn:de:0030-drops-23494},
  doi =		{10.4230/DROPS.MEMICS.2009.2349},
  annote =	{Keywords: LTL Model checking, Depth first search}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2351
Derivation in Scattered Context Grammar via Lazy Function Evaluation

Authors: Ota Jirák and Dušan Kolář

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
This paper discusses scattered context grammars (SCG) and considers the application of scattered context grammar production rules. We use function that represents single derivation step over the given sentential form. Moreover, we define this function in such a way, so that it represents the delayed execution of scattered context grammar production rules using the same principles as a lazy evaluation in functional programming. Finally, we prove equivalence of the usual and the delayed execution of SCG production rules.
Cite as

Ota Jirák and Dušan Kolář. Derivation in Scattered Context Grammar via Lazy Function Evaluation. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 27-36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{jirak_et_al:OASIcs:2009:DROPS.MEMICS.2009.2351,
  author =	{Jir\'{a}k, Ota and Kol\'{a}\v{r}, Du\v{s}an},
  title =	{{Derivation in Scattered Context Grammar via Lazy Function Evaluation}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{27--36},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2351},
  URN =		{urn:nbn:de:0030-drops-23517},
  doi =		{10.4230/DROPS.MEMICS.2009.2351},
  annote =	{Keywords: SCG, delayed execution, derivation, lazy evaluation}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2353
Embedded Process Functional Language

Authors: Marek Bĕhálek and Petr Šaloun

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
Embedded systems represent an important area of computer engineering. Demands on embedded applications are increasing. To address these issues, different agile methodologies are used in traditional desktop applications today. These agile methodologies often try to eliminate development risks in early design phases. Possible solution is to create a working model or a prototype of critical system parts. Then we can use this prototype in negotiation with customer and also to prove technological aspects of our solution. From this perspective functional languages are very attractive. They have excellent abstraction mechanism and they can be used as a tool producing a kind of executable design. In this paper we present our work on a domain specific functional language targeted to embedded systems Embedded process functional language. Created language works on a high level of abstraction and it uses other technologies (even other functional languages) created for embedded systems development on lower levels. It can be used like a modeling or a prototyping language in early development phases.
Cite as

Marek Bĕhálek and Petr Šaloun. Embedded Process Functional Language. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 37-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{behalek_et_al:OASIcs:2009:DROPS.MEMICS.2009.2353,
  author =	{B\u{e}h\'{a}lek, Marek and \v{S}aloun, Petr},
  title =	{{Embedded Process Functional Language}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{37--44},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2353},
  URN =		{urn:nbn:de:0030-drops-23535},
  doi =		{10.4230/DROPS.MEMICS.2009.2353},
  annote =	{Keywords: Embedded systems, model, high abstraction level, functional programming}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2343
Exact Quantum Query Algorithm for Error Detection Code Verification

Authors: Alina Vasilieva

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
Quantum algorithms can be analyzed in a query model to compute Boolean functions. Function input is provided in a black box, and the aim is to compute the function value using as few queries to the black box as possible. A repetition code is an error detection scheme that repeats each bit of the original message r times. After a message with redundant bits is transmitted via a communication channel, it must be verified. If the received message consists of r-size blocks of equal bits, the conclusion is that there were no errors. The verification procedure can be interpreted as an application of a query algorithm, where input is a message to be checked. Classically, for N-bit message, values of all N variables must be queried. We demonstrate an exact quantum algorithm that uses only N/2 queries.
Cite as

Alina Vasilieva. Exact Quantum Query Algorithm for Error Detection Code Verification. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 45-52, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{vasilieva:OASIcs:2009:DROPS.MEMICS.2009.2343,
  author =	{Vasilieva, Alina},
  title =	{{Exact Quantum Query Algorithm for Error Detection Code Verification}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{45--52},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2343},
  URN =		{urn:nbn:de:0030-drops-23434},
  doi =		{10.4230/DROPS.MEMICS.2009.2343},
  annote =	{Keywords: Quantum computing, quantum query algorithms, algorithm complexity, Boolean functions, algorithm design}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2348
Faster Algorithm for Mean-Payoff Games

Authors: Jakub Chaloupka and Luboš Brim

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
We study some existing techniques for solving mean-payoff games (MPGs), improve them, and design a randomized algorithm for solving MPGs with currently the best expected complexity.
Cite as

Jakub Chaloupka and Luboš Brim. Faster Algorithm for Mean-Payoff Games. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 53-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{chaloupka_et_al:OASIcs:2009:DROPS.MEMICS.2009.2348,
  author =	{Chaloupka, Jakub and Brim, Lubo\v{s}},
  title =	{{Faster Algorithm for Mean-Payoff Games}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{53--61},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2348},
  URN =		{urn:nbn:de:0030-drops-23481},
  doi =		{10.4230/DROPS.MEMICS.2009.2348},
  annote =	{Keywords: Mean-payoff games, randomized algorithms, computational complexity}
}
Document
DOI: 10.4230/DROPS.MEMICS.2009.2347
One size does not fit all - how to approach intrusion detection in wireless sensor networks

Authors: Andriy Stetsko and Václav Matyáš

Published in: OASIcs, Volume 13, Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09) (2009)

Abstract
A wireless sensor network (WSN) is a highly distributed network of resource constrained and wireless devices called sensor nodes. In the work we consider intrusion detection systems as they are proper mechanisms to defend internal attacks on WSNs. A wide diversity of WSN applications on one side and limited resources on other side implies that "one-fit-all" intrusion detection system is not optimal. We present a conceptual proposal for a suite of tools that enable an automatic design of intrusion detection system that will be (near) optimal for a given network topology, capabilities of sensor nodes and anticipated attacks.
Cite as

Andriy Stetsko and Václav Matyáš. One size does not fit all - how to approach intrusion detection in wireless sensor networks. In Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09). Open Access Series in Informatics (OASIcs), Volume 13, pp. 62-69, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{stetsko_et_al:OASIcs:2009:DROPS.MEMICS.2009.2347,
  author =	{Stetsko, Andriy and Maty\'{a}\v{s}, V\'{a}clav},
  title =	{{One size does not fit all - how to approach intrusion detection in wireless sensor networks}},
  booktitle =	{Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'09)},
  pages =	{62--69},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-15-6},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{13},
  editor =	{Hlinen\'{y}, Petr and Maty\'{a}\v{s}, V\'{a}clav and Vojnar, Tom\'{a}\v{s}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DROPS.MEMICS.2009.2347},
  URN =		{urn:nbn:de:0030-drops-23479},
  doi =		{10.4230/DROPS.MEMICS.2009.2347},
  annote =	{Keywords: Intrusion detection, wireless sensor networks}
}
  • Refine by Author
  • 7 Hlinený, Petr
  • 3 Matyáš, Václav
  • 2 Ganian, Robert
  • 2 Vojnar, Tomáš
  • 1 Beneš, Nikola
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 crossing number
  • 1 Asynchronous Design
  • 1 Boolean functions
  • 1 Boundedness
  • 1 Coverability
  • Show More...

  • Refine by Type
  • 21 document

  • Refine by Publication Year
  • 15 2009
  • 2 2016
  • 2 2018
  • 1 2010
  • 1 2012

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