---
_id: '3289'
abstract:
- lang: eng
text: "Viral manipulation of transduction pathways associated with key cellular
functions such as survival, response to microbial infection, and cytoskeleton
reorganization can provide the supportive milieu for a productive infection. Here,
we demonstrate that vaccinia virus (VACV) infection leads to activation of the
stress-activated protein kinase (SAPK)/extracellular signal-regulated kinase (ERK)
4/7 (MKK4/7)-c-Jun N-terminal protein kinase 1/2 (JNK1/2) pathway; further, the
stimulation of this pathway requires postpenetration, prereplicative events in
the viral replication cycle. Although the formation of intracellular mature virus
(IMV) was not affected in MKK4/7- or JNK1/2-knockout (KO) cells, we did note an
accentuated deregulation of microtubule and actin network organization in infected
JNK1/2-KO cells. This was followed by deregulated viral trafficking to the periphery
and enhanced enveloped particle release. Furthermore, VACV infection induced alterations
in the cell contractility and morphology, and cell migration was reduced in the
JNK-KO cells. In addition, phosphorylation of proteins implicated with early cell
contractility and cell migration, such as microtubule-associated protein 1B and
paxillin, respectively, was not detected in the VACV-infected KO cells. In sum,
our findings uncover a regulatory role played by the MKK4/7-JNK1/2 pathway in
cytoskeleton reorganization during VACV infection.\r\n"
acknowledgement: "This work was supported by grants from Fundação de Amparo a Pesquisa
do Estado de Minas Gerais (FAPEMIG), the Brazilian Federal Agency for Support and
Evaluation of Graduate Education (CAPES), and the National Council for Scientific
and Technological Development (CNPq). A.C.T.C.P., B.S.A.F.B., F.G.G.L., and J.A.P.S.-M.
were recipients of predoctoral fellowships from CNPq. C.A.B., E.G.K., T.S.-P., P.F.P.P.,
and P.C.P.F. are recipients of research fellowships from CNPq. \r\n\r\n\r\nWe are
grateful to Angela S. Lopes, Ilda M. V. Gama, João R. dos Santos, and Andreza A.
Carvalho for their secretarial/technical assistance and to Fernanda Gambogi for
help with immunofluorescence microscopy. We also thank M. C. Sogayar (Department
of Biochemistry, University of São Paulo, São Paulo, Brazil), who kindly provided
us with the A31 cell line, and R. Davis (Howard Hughes Medical Institute, University
of Massachusetts Medical School, Worcester, MA) for the WT and JNK1/2-, MKK4-, MKK7-,
and MKK4/7-KO cells. VACV WR was from C. Jungwirth (Universität Würzburg, Würzburg,
Germany). The recombinant VACV vF13L-GFP and the rabbit polyclonal antibodies against
viral proteins, B5R, D8L, L1R, and A36R, were from B. Moss (NIAID, Bethesda, MD).
The pcDNA3-Myc-JNK2-MKK7 WT plasmid was from Eugen Kerkhoff (Universität Würzburg,
Würzburg, Germany). We also thank Flávio G. da Fonseca (UFMG, Belo Horizonte, MG,
Brazil) and Kathleen A. Boyle (Medical College of Wisconsin, Milwaukee, WI) for
critically reading the manuscript."
article_processing_charge: No
author:
- first_name: Anna
full_name: Pereira, Anna
last_name: Pereira
- first_name: Flávia
full_name: Leite, Flávia
id: 36705F98-F248-11E8-B48F-1D18A9856A87
last_name: Leite
- first_name: Bruno
full_name: Brasil, Bruno
last_name: Brasil
- first_name: Jamaria
full_name: Soares Martins, Jamaria
last_name: Soares Martins
- first_name: Alice
full_name: Torres, Alice
last_name: Torres
- first_name: Paulo
full_name: Pimenta, Paulo
last_name: Pimenta
- first_name: Thais
full_name: Souto Padrón, Thais
last_name: Souto Padrón
- first_name: Paula
full_name: Tranktman, Paula
last_name: Tranktman
- first_name: Paulo
full_name: Ferreira, Paulo
last_name: Ferreira
- first_name: Erna
full_name: Kroon, Erna
last_name: Kroon
- first_name: Cláudio
full_name: Bonjardim, Cláudio
last_name: Bonjardim
citation:
ama: Pereira A, Leite F, Brasil B, et al. A vaccinia virus-driven interplay between
the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization. Journal of Virology.
2012;86(1):172-184. doi:10.1128/JVI.05638-11
apa: Pereira, A., Leite, F., Brasil, B., Soares Martins, J., Torres, A., Pimenta,
P., … Bonjardim, C. (2012). A vaccinia virus-driven interplay between the MKK4/7-JNK1/2
pathway and cytoskeleton reorganization. Journal of Virology. ASM. https://doi.org/10.1128/JVI.05638-11
chicago: Pereira, Anna, Flávia Leite, Bruno Brasil, Jamaria Soares Martins, Alice
Torres, Paulo Pimenta, Thais Souto Padrón, et al. “A Vaccinia Virus-Driven Interplay
between the MKK4/7-JNK1/2 Pathway and Cytoskeleton Reorganization.” Journal
of Virology. ASM, 2012. https://doi.org/10.1128/JVI.05638-11.
ieee: A. Pereira et al., “A vaccinia virus-driven interplay between the MKK4/7-JNK1/2
pathway and cytoskeleton reorganization,” Journal of Virology, vol. 86,
no. 1. ASM, pp. 172–184, 2012.
ista: Pereira A, Leite F, Brasil B, Soares Martins J, Torres A, Pimenta P, Souto
Padrón T, Tranktman P, Ferreira P, Kroon E, Bonjardim C. 2012. A vaccinia virus-driven
interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton reorganization. Journal
of Virology. 86(1), 172–184.
mla: Pereira, Anna, et al. “A Vaccinia Virus-Driven Interplay between the MKK4/7-JNK1/2
Pathway and Cytoskeleton Reorganization.” Journal of Virology, vol. 86,
no. 1, ASM, 2012, pp. 172–84, doi:10.1128/JVI.05638-11.
short: A. Pereira, F. Leite, B. Brasil, J. Soares Martins, A. Torres, P. Pimenta,
T. Souto Padrón, P. Tranktman, P. Ferreira, E. Kroon, C. Bonjardim, Journal of
Virology 86 (2012) 172–184.
date_created: 2018-12-11T12:02:29Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2025-09-30T07:40:18Z
day: '01'
department:
- _id: JoBo
doi: 10.1128/JVI.05638-11
external_id:
isi:
- '000298347700017'
pmid:
- '22031940'
fulldoi: https://doi.org/10.1128/JVI.05638-11
intvolume: ' 86'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3255887/
month: '01'
oa: 1
oa_version: Submitted Version
page: 172 - 184
pmid: 1
publication: Journal of Virology
publication_status: published
publisher: ASM
publist_id: '3356'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A vaccinia virus-driven interplay between the MKK4/7-JNK1/2 pathway and cytoskeleton
reorganization
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 86
year: '2012'
...
---
_id: '3310'
abstract:
- lang: eng
text: The theory of persistent homology opens up the possibility to reason about
topological features of a space or a function quantitatively and in combinatorial
terms. We refer to this new angle at a classical subject within algebraic topology
as a point calculus, which we present for the family of interlevel sets of a real-valued
function. Our account of the subject is expository, devoid of proofs, and written
for non-experts in algebraic topology.
acknowledgement: Research by the third author is partially supported by the National
Science Foundation (NSF) under grant DBI-0820624.
article_processing_charge: No
author:
- first_name: Paul
full_name: Bendich, Paul
id: 43F6EC54-F248-11E8-B48F-1D18A9856A87
last_name: Bendich
- first_name: Sergio
full_name: Cabello, Sergio
last_name: Cabello
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Bendich P, Cabello S, Edelsbrunner H. A point calculus for interlevel set homology.
Pattern Recognition Letters. 2012;33(11):1436-1444. doi:10.1016/j.patrec.2011.10.007
apa: Bendich, P., Cabello, S., & Edelsbrunner, H. (2012). A point calculus for
interlevel set homology. Pattern Recognition Letters. Elsevier. https://doi.org/10.1016/j.patrec.2011.10.007
chicago: Bendich, Paul, Sergio Cabello, and Herbert Edelsbrunner. “A Point Calculus
for Interlevel Set Homology.” Pattern Recognition Letters. Elsevier, 2012.
https://doi.org/10.1016/j.patrec.2011.10.007.
ieee: P. Bendich, S. Cabello, and H. Edelsbrunner, “A point calculus for interlevel
set homology,” Pattern Recognition Letters, vol. 33, no. 11. Elsevier,
pp. 1436–1444, 2012.
ista: Bendich P, Cabello S, Edelsbrunner H. 2012. A point calculus for interlevel
set homology. Pattern Recognition Letters. 33(11), 1436–1444.
mla: Bendich, Paul, et al. “A Point Calculus for Interlevel Set Homology.” Pattern
Recognition Letters, vol. 33, no. 11, Elsevier, 2012, pp. 1436–44, doi:10.1016/j.patrec.2011.10.007.
short: P. Bendich, S. Cabello, H. Edelsbrunner, Pattern Recognition Letters 33 (2012)
1436–1444.
date_created: 2018-12-11T12:02:36Z
date_published: 2012-08-01T00:00:00Z
date_updated: 2025-09-30T07:39:47Z
day: '01'
ddc:
- '000'
department:
- _id: HeEd
doi: 10.1016/j.patrec.2011.10.007
external_id:
isi:
- '000307204300002'
file:
- access_level: open_access
checksum: d65f79775b51258a604ca5ec741297cc
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:00Z
date_updated: 2020-07-14T12:46:06Z
file_id: '5116'
file_name: IST-2016-542-v1+1_2012-J-01-Poinculus.pdf
file_size: 280280
relation: main_file
file_date_updated: 2020-07-14T12:46:06Z
fulldoi: https://doi.org/10.1016/j.patrec.2011.10.007
has_accepted_license: '1'
intvolume: ' 33'
isi: 1
issue: '11'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 1436 - 1444
publication: Pattern Recognition Letters
publication_status: published
publisher: Elsevier
publist_id: '3330'
pubrep_id: '542'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A point calculus for interlevel set homology
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 33
year: '2012'
...
---
_id: '3314'
abstract:
- lang: eng
text: We introduce two-level discounted and mean-payoff games played by two players
on a perfect-information stochastic game graph. The upper level game is a discounted
or mean-payoff game and the lower level game is a (undiscounted) reachability
game. Two-level games model hierarchical and sequential decision making under
uncertainty across different time scales. For both discounted and mean-payoff
two-level games, we show the existence of pure memoryless optimal strategies for
both players and an ordered field property. We show that if there is only one
player (Markov decision processes), then the values can be computed in polynomial
time. It follows that whether the value of a player is equal to a given rational
constant in two-level discounted or mean-payoff games can be decided in NP ∩ coNP.
We also give an alternate strategy improvement algorithm to compute the value.
© 2012 World Scientific Publishing Company.
acknowledgement: This research was funded in part by the US National Science Foundation
grants CCF-0546170, CNS-0702881, DARPA grant HR0011-09-1-0037, Austrian Science
Fund (FWF) NFN Grant S11407-N23 (RiSE) and a Microsoft faculty fellowship.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Ritankar
full_name: Majumdar, Ritankar
last_name: Majumdar
citation:
ama: Chatterjee K, Majumdar R. Discounting and averaging in games across time scales.
International Journal of Foundations of Computer Science. 2012;23(3):609-625.
doi:10.1142/S0129054112400308
apa: Chatterjee, K., & Majumdar, R. (2012). Discounting and averaging in games
across time scales. International Journal of Foundations of Computer Science.
World Scientific Publishing. https://doi.org/10.1142/S0129054112400308
chicago: Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging
in Games across Time Scales.” International Journal of Foundations of Computer
Science. World Scientific Publishing, 2012. https://doi.org/10.1142/S0129054112400308.
ieee: K. Chatterjee and R. Majumdar, “Discounting and averaging in games across
time scales,” International Journal of Foundations of Computer Science,
vol. 23, no. 3. World Scientific Publishing, pp. 609–625, 2012.
ista: Chatterjee K, Majumdar R. 2012. Discounting and averaging in games across
time scales. International Journal of Foundations of Computer Science. 23(3),
609–625.
mla: Chatterjee, Krishnendu, and Ritankar Majumdar. “Discounting and Averaging in
Games across Time Scales.” International Journal of Foundations of Computer
Science, vol. 23, no. 3, World Scientific Publishing, 2012, pp. 609–25, doi:10.1142/S0129054112400308.
short: K. Chatterjee, R. Majumdar, International Journal of Foundations of Computer
Science 23 (2012) 609–625.
date_created: 2018-12-11T12:02:37Z
date_published: 2012-04-01T00:00:00Z
date_updated: 2025-09-30T07:38:00Z
day: '01'
department:
- _id: KrCh
doi: 10.1142/S0129054112400308
external_id:
isi:
- '000304003000004'
fulldoi: https://doi.org/10.1142/S0129054112400308
intvolume: ' 23'
isi: 1
issue: '3'
language:
- iso: eng
month: '04'
oa_version: None
page: 609 - 625
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: International Journal of Foundations of Computer Science
publication_status: published
publisher: World Scientific Publishing
publist_id: '3326'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Discounting and averaging in games across time scales
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 23
year: '2012'
...
---
_id: '3317'
abstract:
- lang: eng
text: The physical distance between presynaptic Ca2+ channels and the Ca2+ sensors
that trigger exocytosis of neurotransmitter-containing vesicles is a key determinant
of the signalling properties of synapses in the nervous system. Recent functional
analysis indicates that in some fast central synapses, transmitter release is
triggered by a small number of Ca2+ channels that are coupled to Ca2+ sensors
at the nanometre scale. Molecular analysis suggests that this tight coupling is
generated by protein–protein interactions involving Ca2+ channels, Ca2+ sensors
and various other synaptic proteins. Nanodomain coupling has several functional
advantages, as it increases the efficacy, speed and energy efficiency of synaptic
transmission.
acknowledgement: "Work of the authors was funded by grants of the Deutsche Forschungsgemeinschaft
to P.J. (grants SFB 780/A5, TR 3/B10 and the Leibniz programme), a European Research
Council Advanced grant to P.J. and a Swiss National Foundation fellowship to E.E.\r\nWe
thank D. Tsien and E. Neher for their comments on this Review, J. Guzmán and A.
Pernía-Andrade for reading earlier versions and E. Kramberger for perfect editorial
support. We apologize that owing to space constraints, not all relevant papers could
be cited.\r\n"
article_processing_charge: No
author:
- first_name: Emmanuel
full_name: Eggermann, Emmanuel
id: 34DACA34-E9AE-11E9-849C-D35BD8ADC20C
last_name: Eggermann
- first_name: Iancu
full_name: Bucurenciu, Iancu
id: 4BD1D872-E9AE-11E9-9EE9-8BF4597A9E2A
last_name: Bucurenciu
- first_name: Sarit
full_name: Goswami, Sarit
id: 3A578F32-F248-11E8-B48F-1D18A9856A87
last_name: Goswami
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: Eggermann E, Bucurenciu I, Goswami S, Jonas PM. Nanodomain coupling between
Ca(2+) channels and sensors of exocytosis at fast mammalian synapses. Nature
Reviews Neuroscience. 2012;13(1):7-21. doi:10.1038/nrn3125
apa: Eggermann, E., Bucurenciu, I., Goswami, S., & Jonas, P. M. (2012). Nanodomain
coupling between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses.
Nature Reviews Neuroscience. Nature Publishing Group. https://doi.org/10.1038/nrn3125
chicago: Eggermann, Emmanuel, Iancu Bucurenciu, Sarit Goswami, and Peter M Jonas.
“Nanodomain Coupling between Ca(2+) Channels and Sensors of Exocytosis at Fast
Mammalian Synapses.” Nature Reviews Neuroscience. Nature Publishing Group,
2012. https://doi.org/10.1038/nrn3125.
ieee: E. Eggermann, I. Bucurenciu, S. Goswami, and P. M. Jonas, “Nanodomain coupling
between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses,”
Nature Reviews Neuroscience, vol. 13, no. 1. Nature Publishing Group, pp.
7–21, 2012.
ista: Eggermann E, Bucurenciu I, Goswami S, Jonas PM. 2012. Nanodomain coupling
between Ca(2+) channels and sensors of exocytosis at fast mammalian synapses.
Nature Reviews Neuroscience. 13(1), 7–21.
mla: Eggermann, Emmanuel, et al. “Nanodomain Coupling between Ca(2+) Channels and
Sensors of Exocytosis at Fast Mammalian Synapses.” Nature Reviews Neuroscience,
vol. 13, no. 1, Nature Publishing Group, 2012, pp. 7–21, doi:10.1038/nrn3125.
short: E. Eggermann, I. Bucurenciu, S. Goswami, P.M. Jonas, Nature Reviews Neuroscience
13 (2012) 7–21.
corr_author: '1'
date_created: 2018-12-11T12:02:38Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2025-09-30T07:34:43Z
day: '01'
ddc:
- '570'
department:
- _id: PeJo
doi: 10.1038/nrn3125
external_id:
isi:
- '000298323200008'
file:
- access_level: open_access
checksum: 4c1c86b2f6e4e1562f5bb800b457ea9f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:13Z
date_updated: 2020-07-14T12:46:07Z
file_id: '4931'
file_name: IST-2017-820-v1+1_17463_3_art_file_109404_ltmxbw.pdf
file_size: 314246
relation: main_file
- access_level: open_access
checksum: bceb2efdd49d115f4dde8486bc1be3f2
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:14Z
date_updated: 2020-07-14T12:46:07Z
file_id: '4932'
file_name: IST-2017-820-v1+2_17463_3_figure_109402_ltmwlp.pdf
file_size: 1840216
relation: main_file
file_date_updated: 2020-07-14T12:46:07Z
fulldoi: https://doi.org/10.1038/nrn3125
has_accepted_license: '1'
intvolume: ' 13'
isi: 1
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 7 - 21
project:
- _id: 25BC64A8-B435-11E9-9278-68D0E5697425
grant_number: JO_780/A5
name: Synaptic Mechanisms of Neuronal Network Function
- _id: 25BDE9A4-B435-11E9-9278-68D0E5697425
grant_number: SFB-TR3-TP10B
name: "Glutamaterge synaptische Ã\x9Cbertragung und Plastizität in hippocampalen
Mikroschaltkreisen"
publication: Nature Reviews Neuroscience
publication_status: published
publisher: Nature Publishing Group
publist_id: '3322'
pubrep_id: '820'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Nanodomain coupling between Ca(2+) channels and sensors of exocytosis at fast
mammalian synapses
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13
year: '2012'
...
---
_id: '3341'
abstract:
- lang: eng
text: 'We consider two-player stochastic games played on a finite state space for
an infinite number of rounds. The games are concurrent: in each round, the two
players (player 1 and player 2) choose their moves independently and simultaneously;
the current state and the two moves determine a probability distribution over
the successor states. We also consider the important special case of turn-based
stochastic games where players make moves in turns, rather than concurrently.
We study concurrent games with \omega-regular winning conditions specified as
parity objectives. The value for player 1 for a parity objective is the maximal
probability with which the player can guarantee the satisfaction of the objective
against all strategies of the opponent. We study the problem of continuity and
robustness of the value function in concurrent and turn-based stochastic parity
gameswith respect to imprecision in the transition probabilities. We present quantitative
bounds on the difference of the value function (in terms of the imprecision of
the transition probabilities) and show the value continuity for structurally equivalent
concurrent games (two games are structurally equivalent if the support of the
transition function is same and the probabilities differ). We also show robustness
of optimal strategies for structurally equivalent turn-based stochastic parity
games. Finally we show that the value continuity property breaks without the structurally
equivalent assumption (even for Markov chains) and show that our quantitative
bound is asymptotically optimal. Hence our results are tight (the assumption is
both necessary and sufficient) and optimal (our quantitative bound is asymptotically
optimal).'
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Chatterjee K. Robustness of structurally equivalent concurrent parity games.
In: Vol 7213. Springer; 2012:270-285. doi:10.1007/978-3-642-28729-9_18'
apa: 'Chatterjee, K. (2012). Robustness of structurally equivalent concurrent parity
games (Vol. 7213, pp. 270–285). Presented at the FoSSaCS: Foundations of Software
Science and Computation Structures, Tallinn, Estonia: Springer. https://doi.org/10.1007/978-3-642-28729-9_18'
chicago: Chatterjee, Krishnendu. “Robustness of Structurally Equivalent Concurrent
Parity Games,” 7213:270–85. Springer, 2012. https://doi.org/10.1007/978-3-642-28729-9_18.
ieee: 'K. Chatterjee, “Robustness of structurally equivalent concurrent parity games,”
presented at the FoSSaCS: Foundations of Software Science and Computation Structures,
Tallinn, Estonia, 2012, vol. 7213, pp. 270–285.'
ista: 'Chatterjee K. 2012. Robustness of structurally equivalent concurrent parity
games. FoSSaCS: Foundations of Software Science and Computation Structures, LNCS,
vol. 7213, 270–285.'
mla: Chatterjee, Krishnendu. Robustness of Structurally Equivalent Concurrent
Parity Games. Vol. 7213, Springer, 2012, pp. 270–85, doi:10.1007/978-3-642-28729-9_18.
short: K. Chatterjee, in:, Springer, 2012, pp. 270–285.
conference:
end_date: 2012-04-01
location: Tallinn, Estonia
name: 'FoSSaCS: Foundations of Software Science and Computation Structures'
start_date: 2012-03-24
corr_author: '1'
date_created: 2018-12-11T12:02:46Z
date_published: 2012-03-22T00:00:00Z
date_updated: 2024-10-09T20:54:38Z
day: '22'
department:
- _id: KrCh
doi: 10.1007/978-3-642-28729-9_18
ec_funded: 1
external_id:
arxiv:
- '1107.2009'
fulldoi: https://doi.org/10.1007/978-3-642-28729-9_18
intvolume: ' 7213'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2009
month: '03'
oa: 1
oa_version: Preprint
page: 270 - 285
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication_status: published
publisher: Springer
publist_id: '3284'
quality_controlled: '1'
related_material:
record:
- id: '5382'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Robustness of structurally equivalent concurrent parity games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7213
year: '2012'
...
---
_id: '3836'
abstract:
- lang: eng
text: Hierarchical Timing Language (HTL) is a coordination language for distributed,
hard real-time applications. HTL is a hierarchical extension of Giotto and, like
its predecessor, based on the logical execution time (LET) paradigm of real-time
programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine
(or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram
structure needs to be flattened; the flattening makes separatecompilation difficult,
and may result in E machinecode of exponential size. In this paper, we propose
a generalization of the E machine, which supports a hierarchicalprogram structure
at runtime through real-time trigger mechanisms that are arranged in a tree. We
present the generalized E machine, and a modular compiler for HTL that generates
code of linear size. The compiler may generate code for any part of a given HTL
program separately in any order.
article_processing_charge: No
author:
- first_name: Arkadeb
full_name: Ghosal, Arkadeb
last_name: Ghosal
- first_name: Daniel
full_name: Iercan, Daniel
last_name: Iercan
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Alberto
full_name: Sangiovanni Vincentelli, Alberto
last_name: Sangiovanni Vincentelli
citation:
ama: Ghosal A, Iercan D, Kirsch C, Henzinger TA, Sangiovanni Vincentelli A. Separate
compilation of hierarchical real-time programs into linear-bounded embedded machine
code. Science of Computer Programming. 2012;77(2):96-112. doi:10.1016/j.scico.2010.06.004
apa: Ghosal, A., Iercan, D., Kirsch, C., Henzinger, T. A., & Sangiovanni Vincentelli,
A. (2012). Separate compilation of hierarchical real-time programs into linear-bounded
embedded machine code. Science of Computer Programming. Elsevier. https://doi.org/10.1016/j.scico.2010.06.004
chicago: Ghosal, Arkadeb, Daniel Iercan, Christoph Kirsch, Thomas A Henzinger, and
Alberto Sangiovanni Vincentelli. “Separate Compilation of Hierarchical Real-Time
Programs into Linear-Bounded Embedded Machine Code.” Science of Computer Programming.
Elsevier, 2012. https://doi.org/10.1016/j.scico.2010.06.004.
ieee: A. Ghosal, D. Iercan, C. Kirsch, T. A. Henzinger, and A. Sangiovanni Vincentelli,
“Separate compilation of hierarchical real-time programs into linear-bounded embedded
machine code,” Science of Computer Programming, vol. 77, no. 2. Elsevier,
pp. 96–112, 2012.
ista: Ghosal A, Iercan D, Kirsch C, Henzinger TA, Sangiovanni Vincentelli A. 2012.
Separate compilation of hierarchical real-time programs into linear-bounded embedded
machine code. Science of Computer Programming. 77(2), 96–112.
mla: Ghosal, Arkadeb, et al. “Separate Compilation of Hierarchical Real-Time Programs
into Linear-Bounded Embedded Machine Code.” Science of Computer Programming,
vol. 77, no. 2, Elsevier, 2012, pp. 96–112, doi:10.1016/j.scico.2010.06.004.
short: A. Ghosal, D. Iercan, C. Kirsch, T.A. Henzinger, A. Sangiovanni Vincentelli,
Science of Computer Programming 77 (2012) 96–112.
date_created: 2018-12-11T12:05:26Z
date_published: 2012-02-01T00:00:00Z
date_updated: 2025-09-30T07:33:11Z
day: '01'
department:
- _id: ToHe
doi: 10.1016/j.scico.2010.06.004
external_id:
isi:
- '000298464800003'
fulldoi: https://doi.org/10.1016/j.scico.2010.06.004
intvolume: ' 77'
isi: 1
issue: '2'
language:
- iso: eng
month: '02'
oa_version: None
page: 96 - 112
publication: Science of Computer Programming
publication_status: published
publisher: Elsevier
publist_id: '2370'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Separate compilation of hierarchical real-time programs into linear-bounded
embedded machine code
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 77
year: '2012'
...
---
_id: '3846'
abstract:
- lang: eng
text: We summarize classical and recent results about two-player games played on
graphs with ω-regular objectives. These games have applications in the verification
and synthesis of reactive systems. Important distinctions are whether a graph
game is turn-based or concurrent; deterministic or stochastic; zero-sum or not.
We cluster known results and open problems according to these classifications.
acknowledgement: This research was supported in part by the ONR grant N00014-02-1-0671,
by the AFOSR MURI grant F49620-00-1-0327, and by the NSF grants CCR-9988172, CCR-0085949,
and CCR-0225610.
article_processing_charge: No
article_type: original
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: Chatterjee K, Henzinger TA. A survey of stochastic ω regular games. Journal
of Computer and System Sciences. 2012;78(2):394-413. doi:10.1016/j.jcss.2011.05.002
apa: Chatterjee, K., & Henzinger, T. A. (2012). A survey of stochastic ω regular
games. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2011.05.002
chicago: Chatterjee, Krishnendu, and Thomas A Henzinger. “A Survey of Stochastic
ω Regular Games.” Journal of Computer and System Sciences. Elsevier, 2012.
https://doi.org/10.1016/j.jcss.2011.05.002.
ieee: K. Chatterjee and T. A. Henzinger, “A survey of stochastic ω regular games,”
Journal of Computer and System Sciences, vol. 78, no. 2. Elsevier, pp.
394–413, 2012.
ista: Chatterjee K, Henzinger TA. 2012. A survey of stochastic ω regular games.
Journal of Computer and System Sciences. 78(2), 394–413.
mla: Chatterjee, Krishnendu, and Thomas A. Henzinger. “A Survey of Stochastic ω
Regular Games.” Journal of Computer and System Sciences, vol. 78, no. 2,
Elsevier, 2012, pp. 394–413, doi:10.1016/j.jcss.2011.05.002.
short: K. Chatterjee, T.A. Henzinger, Journal of Computer and System Sciences 78
(2012) 394–413.
corr_author: '1'
date_created: 2018-12-11T12:05:29Z
date_published: 2012-03-02T00:00:00Z
date_updated: 2025-09-30T07:32:39Z
day: '02'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.jcss.2011.05.002
external_id:
isi:
- '000299719100002'
file:
- access_level: open_access
checksum: 241b939deb4517cdd4426d49c67e3fa2
content_type: application/pdf
creator: kschuh
date_created: 2019-01-29T10:54:28Z
date_updated: 2020-07-14T12:46:17Z
file_id: '5897'
file_name: a_survey_of_stochastic_omega-regular_games.pdf
file_size: 336450
relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
fulldoi: https://doi.org/10.1016/j.jcss.2011.05.002
has_accepted_license: '1'
intvolume: ' 78'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1016/j.jcss.2011.05.002
month: '03'
oa: 1
oa_version: Submitted Version
page: 394 - 413
publication: Journal of Computer and System Sciences
publication_status: published
publisher: Elsevier
publist_id: '2341'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A survey of stochastic ω regular games
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 78
year: '2012'
...
---
_id: '2318'
abstract:
- lang: eng
text: 'We show that bosons interacting via pair potentials with negative scattering
length form bound states for a suitable number of particles. In other words, the
absence of many-particle bound states of any kind implies the non-negativity of
the scattering length of the interaction potential. '
acknowledgement: 'Partial financial support by NSERC '
article_processing_charge: No
arxiv: 1
author:
- first_name: Robert
full_name: Seiringer, Robert
id: 4AFD0470-F248-11E8-B48F-1D18A9856A87
last_name: Seiringer
orcid: 0000-0002-6781-0521
citation:
ama: Seiringer R. Absence of bound states implies non-negativity of the scattering
length. Journal of Spectral Theory. 2012;2(3):321-328. doi:10.4171/JST/31
apa: Seiringer, R. (2012). Absence of bound states implies non-negativity of the
scattering length. Journal of Spectral Theory. EMS Press. https://doi.org/10.4171/JST/31
chicago: Seiringer, Robert. “Absence of Bound States Implies Non-Negativity of the
Scattering Length.” Journal of Spectral Theory. EMS Press, 2012. https://doi.org/10.4171/JST/31.
ieee: R. Seiringer, “Absence of bound states implies non-negativity of the scattering
length,” Journal of Spectral Theory, vol. 2, no. 3. EMS Press, pp. 321–328,
2012.
ista: Seiringer R. 2012. Absence of bound states implies non-negativity of the scattering
length. Journal of Spectral Theory. 2(3), 321–328.
mla: Seiringer, Robert. “Absence of Bound States Implies Non-Negativity of the Scattering
Length.” Journal of Spectral Theory, vol. 2, no. 3, EMS Press, 2012, pp.
321–28, doi:10.4171/JST/31.
short: R. Seiringer, Journal of Spectral Theory 2 (2012) 321–328.
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T11:56:58Z
date_published: 2012-06-24T00:00:00Z
date_updated: 2026-07-06T11:57:04Z
day: '24'
department:
- _id: RoSe
doi: 10.4171/JST/31
external_id:
arxiv:
- '1204.0435'
isi:
- '000209021900004'
fulldoi: https://doi.org/10.4171/JST/31
intvolume: ' 2'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1204.0435
month: '06'
oa: 1
oa_version: Preprint
page: 321-328
publication: Journal of Spectral Theory
publication_status: published
publisher: EMS Press
publist_id: '4609'
quality_controlled: '1'
status: public
title: Absence of bound states implies non-negativity of the scattering length
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2
year: '2012'
...
---
_id: '2954'
abstract:
- lang: eng
text: Spontaneous postsynaptic currents (PSCs) provide key information about the
mechanisms of synaptic transmission and the activity modes of neuronal networks.
However, detecting spontaneous PSCs in vitro and in vivo has been challenging,
because of the small amplitude, the variable kinetics, and the undefined time
of generation of these events. Here, we describe a, to our knowledge, new method
for detecting spontaneous synaptic events by deconvolution, using a template that
approximates the average time course of spontaneous PSCs. A recorded PSC trace
is deconvolved from the template, resulting in a series of delta-like functions.
The maxima of these delta-like events are reliably detected, revealing the precise
onset times of the spontaneous PSCs. Among all detection methods, the deconvolution-based
method has a unique temporal resolution, allowing the detection of individual
events in high-frequency bursts. Furthermore, the deconvolution-based method has
a high amplitude resolution, because deconvolution can substantially increase
the signal/noise ratio. When tested against previously published methods using
experimental data, the deconvolution-based method was superior for spontaneous
PSCs recorded in vivo. Using the high-resolution deconvolution-based detection
algorithm, we show that the frequency of spontaneous excitatory postsynaptic currents
in dentate gyrus granule cells is 4.5 times higher in vivo than in vitro.
acknowledgement: "This work was supported by the Deutsche Forschungsgemeinschaft (TR3/B10)
and a European Research Council Advanced grant to P.J.\r\nWe thank H. Hu, S. J.
Guzman, and C. Schmidt-Hieber for critically reading the manuscript, I. Koeva and
F. Marr for technical support, and E. Kramberger for editorial assistance.\r\n"
article_processing_charge: No
author:
- first_name: Alejandro
full_name: Pernia-Andrade, Alejandro
id: 36963E98-F248-11E8-B48F-1D18A9856A87
last_name: Pernia-Andrade
- first_name: Sarit
full_name: Goswami, Sarit
id: 3A578F32-F248-11E8-B48F-1D18A9856A87
last_name: Goswami
- first_name: Yvonne
full_name: Stickler, Yvonne
id: 63B76600-E9CC-11E9-9B5F-82450873F7A1
last_name: Stickler
- first_name: Ulrich
full_name: Fröbe, Ulrich
last_name: Fröbe
- first_name: Alois
full_name: Schlögl, Alois
id: 45BF87EE-F248-11E8-B48F-1D18A9856A87
last_name: Schlögl
orcid: 0000-0002-5621-8100
- first_name: Peter M
full_name: Jonas, Peter M
id: 353C1B58-F248-11E8-B48F-1D18A9856A87
last_name: Jonas
orcid: 0000-0001-5001-4804
citation:
ama: Pernia-Andrade A, Goswami S, Stickler Y, Fröbe U, Schlögl A, Jonas PM. A deconvolution
based method with high sensitivity and temporal resolution for detection of spontaneous
synaptic currents in vitro and in vivo. Biophysical Journal. 2012;103(7):1429-1439.
doi:10.1016/j.bpj.2012.08.039
apa: Pernia-Andrade, A., Goswami, S., Stickler, Y., Fröbe, U., Schlögl, A., &
Jonas, P. M. (2012). A deconvolution based method with high sensitivity and temporal
resolution for detection of spontaneous synaptic currents in vitro and in vivo.
Biophysical Journal. Biophysical Society. https://doi.org/10.1016/j.bpj.2012.08.039
chicago: Pernia-Andrade, Alejandro, Sarit Goswami, Yvonne Stickler, Ulrich Fröbe,
Alois Schlögl, and Peter M Jonas. “A Deconvolution Based Method with High Sensitivity
and Temporal Resolution for Detection of Spontaneous Synaptic Currents in Vitro
and in Vivo.” Biophysical Journal. Biophysical Society, 2012. https://doi.org/10.1016/j.bpj.2012.08.039.
ieee: A. Pernia-Andrade, S. Goswami, Y. Stickler, U. Fröbe, A. Schlögl, and P. M.
Jonas, “A deconvolution based method with high sensitivity and temporal resolution
for detection of spontaneous synaptic currents in vitro and in vivo,” Biophysical
Journal, vol. 103, no. 7. Biophysical Society, pp. 1429–1439, 2012.
ista: Pernia-Andrade A, Goswami S, Stickler Y, Fröbe U, Schlögl A, Jonas PM. 2012.
A deconvolution based method with high sensitivity and temporal resolution for
detection of spontaneous synaptic currents in vitro and in vivo. Biophysical Journal.
103(7), 1429–1439.
mla: Pernia-Andrade, Alejandro, et al. “A Deconvolution Based Method with High Sensitivity
and Temporal Resolution for Detection of Spontaneous Synaptic Currents in Vitro
and in Vivo.” Biophysical Journal, vol. 103, no. 7, Biophysical Society,
2012, pp. 1429–39, doi:10.1016/j.bpj.2012.08.039.
short: A. Pernia-Andrade, S. Goswami, Y. Stickler, U. Fröbe, A. Schlögl, P.M. Jonas,
Biophysical Journal 103 (2012) 1429–1439.
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T12:00:32Z
date_published: 2012-10-03T00:00:00Z
date_updated: 2026-07-06T12:32:51Z
day: '03'
department:
- _id: PeJo
- _id: ScienComp
doi: 10.1016/j.bpj.2012.08.039
external_id:
isi:
- '000309571400005'
pmid:
- '23062335'
fulldoi: https://doi.org/10.1016/j.bpj.2012.08.039
intvolume: ' 103'
isi: 1
issue: '7'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3471482/
month: '10'
oa: 1
oa_version: Submitted Version
page: 1429 - 1439
pmid: 1
project:
- _id: 25BDE9A4-B435-11E9-9278-68D0E5697425
grant_number: SFB-TR3-TP10B
name: "Glutamaterge synaptische Ã\x9Cbertragung und Plastizität in hippocampalen
Mikroschaltkreisen"
publication: Biophysical Journal
publication_status: published
publisher: Biophysical Society
publist_id: '3774'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A deconvolution based method with high sensitivity and temporal resolution
for detection of spontaneous synaptic currents in vitro and in vivo
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 103
year: '2012'
...
---
_id: '3160'
abstract:
- lang: eng
text: There is a long-running controversy about how early cell fate decisions are
made in the developing mammalian embryo. 1,2 In particular, it is controversial
when the first events that can predict the establishment of the pluripotent and
extra-embryonic lineages in the blastocyst of the pre-implantation embryo occur.
It has long been proposed that the position and polarity of cells at the 16- to
32-cell stage embryo influence their decision to either give rise to the pluripotent
cell lineage that eventually contributes to the inner cell mass (ICM), comprising
the primitive endoderm (PE) and the epiblast (EPI), or the extra-embryonic trophectoderm
(TE) surrounding the blastocoel. The positioning of cells in the embryo at this
developmental stage could largely be the result of random events, making this
a stochastic model of cell lineage allocation. Contrary to such a stochastic model,
some studies have detected putative differences in the lineage potential of individual
blastomeres before compaction, indicating that the first cell fate decisions may
occur as early as at the 4-cell stage. Using a non-invasive, quantitative in vivo
imaging assay to study the kinetic behavior of Oct4 (also known as POU5F1), a
key transcription factor (TF) controlling pre-implantation development in the
mouse embryo, 3-5 a recent study identifies Oct4 kinetics as a predictive measure
of cell lineage patterning in the early mouse embryo. 6 Here, we discuss the implications
of such molecular heterogeneities in early development and offer potential avenues
toward a mechanistic understanding of these observations, contributing to the
resolution of the controversy of developmental cell lineage allocation.
article_processing_charge: No
author:
- first_name: Periklis
full_name: Pantazis, Periklis
last_name: Pantazis
- first_name: Tobias
full_name: Bollenbach, Tobias
id: 3E6DB97A-F248-11E8-B48F-1D18A9856A87
last_name: Bollenbach
orcid: 0000-0003-4398-476X
citation:
ama: Pantazis P, Bollenbach MT. Transcription factor kinetics and the emerging asymmetry
in the early mammalian embryo. Cell Cycle. 2012;11(11):2055-2058. doi:10.4161/cc.20118
apa: Pantazis, P., & Bollenbach, M. T. (2012). Transcription factor kinetics
and the emerging asymmetry in the early mammalian embryo. Cell Cycle. Taylor
& Francis. https://doi.org/10.4161/cc.20118
chicago: Pantazis, Periklis, and Mark Tobias Bollenbach. “Transcription Factor Kinetics
and the Emerging Asymmetry in the Early Mammalian Embryo.” Cell Cycle.
Taylor & Francis, 2012. https://doi.org/10.4161/cc.20118.
ieee: P. Pantazis and M. T. Bollenbach, “Transcription factor kinetics and the emerging
asymmetry in the early mammalian embryo,” Cell Cycle, vol. 11, no. 11.
Taylor & Francis, pp. 2055–2058, 2012.
ista: Pantazis P, Bollenbach MT. 2012. Transcription factor kinetics and the emerging
asymmetry in the early mammalian embryo. Cell Cycle. 11(11), 2055–2058.
mla: Pantazis, Periklis, and Mark Tobias Bollenbach. “Transcription Factor Kinetics
and the Emerging Asymmetry in the Early Mammalian Embryo.” Cell Cycle,
vol. 11, no. 11, Taylor & Francis, 2012, pp. 2055–58, doi:10.4161/cc.20118.
short: P. Pantazis, M.T. Bollenbach, Cell Cycle 11 (2012) 2055–2058.
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T12:01:44Z
date_published: 2012-06-01T00:00:00Z
date_updated: 2026-07-07T05:34:50Z
day: '01'
department:
- _id: ToBo
doi: 10.4161/cc.20118
external_id:
isi:
- '000304770100011'
fulldoi: https://doi.org/10.4161/cc.20118
intvolume: ' 11'
isi: 1
issue: '11'
language:
- iso: eng
month: '06'
oa_version: None
page: 2055 - 2058
publication: Cell Cycle
publication_status: published
publisher: Taylor & Francis
publist_id: '3531'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Transcription factor kinetics and the emerging asymmetry in the early mammalian
embryo
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2012'
...
---
_id: '2048'
abstract:
- lang: eng
text: Leakage resilient cryptography attempts to incorporate side-channel leakage
into the black-box security model and designs cryptographic schemes that are provably
secure within it. Informally, a scheme is leakage-resilient if it remains secure
even if an adversary learns a bounded amount of arbitrary information about the
schemes internal state. Unfortunately, most leakage resilient schemes are unnecessarily
complicated in order to achieve strong provable security guarantees. As advocated
by Yu et al. [CCS’10], this mostly is an artefact of the security proof and in
practice much simpler construction may already suffice to protect against realistic
side-channel attacks. In this paper, we show that indeed for simpler constructions
leakage-resilience can be obtained when we aim for relaxed security notions where
the leakage-functions and/or the inputs to the primitive are chosen non-adaptively.
For example, we show that a three round Feistel network instantiated with a leakage
resilient PRF yields a leakage resilient PRP if the inputs are chosen non-adaptively
(This complements the result of Dodis and Pietrzak [CRYPTO’10] who show that if
a adaptive queries are allowed, a superlogarithmic number of rounds is necessary.)
We also show that a minor variation of the classical GGM construction gives a
leakage resilient PRF if both, the leakage-function and the inputs, are chosen
non-adaptively.
acknowledgement: "Sebastian Faust acknowledges support from the Danish National Research
Foundation and The National Science Foundation of China (under the grant 61061130540)
for the Sino-Danish Center for the Theory of Interactive Computation, within part
of this work was performed; and from the CFEM research center, supported by the
Danish Strategic Research Council. \r\nSupported by the European Research Council/ERC
Starting Grant 259668-PSPC.\r\n"
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Sebastian
full_name: Faust, Sebastian
last_name: Faust
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Joachim
full_name: Schipper, Joachim
id: 7BE863D4-E9CF-11E9-9EDB-90527418172C
last_name: Schipper
citation:
ama: 'Faust S, Pietrzak KZ, Schipper J. Practical leakage-resilient symmetric cryptography.
In: Conference Proceedings CHES 2012. Vol 7428. Springer; 2012:213-232.
doi:10.1007/978-3-642-33027-8_13'
apa: 'Faust, S., Pietrzak, K. Z., & Schipper, J. (2012). Practical leakage-resilient
symmetric cryptography. In Conference proceedings CHES 2012 (Vol. 7428,
pp. 213–232). Leuven, Belgium: Springer. https://doi.org/10.1007/978-3-642-33027-8_13'
chicago: Faust, Sebastian, Krzysztof Z Pietrzak, and Joachim Schipper. “Practical
Leakage-Resilient Symmetric Cryptography.” In Conference Proceedings CHES 2012,
7428:213–32. Springer, 2012. https://doi.org/10.1007/978-3-642-33027-8_13.
ieee: S. Faust, K. Z. Pietrzak, and J. Schipper, “Practical leakage-resilient symmetric
cryptography,” in Conference proceedings CHES 2012, Leuven, Belgium, 2012,
vol. 7428, pp. 213–232.
ista: 'Faust S, Pietrzak KZ, Schipper J. 2012. Practical leakage-resilient symmetric
cryptography. Conference proceedings CHES 2012. CHES: Cryptographic Hardware and
Embedded Systems, LNCS, vol. 7428, 213–232.'
mla: Faust, Sebastian, et al. “Practical Leakage-Resilient Symmetric Cryptography.”
Conference Proceedings CHES 2012, vol. 7428, Springer, 2012, pp. 213–32,
doi:10.1007/978-3-642-33027-8_13.
short: S. Faust, K.Z. Pietrzak, J. Schipper, in:, Conference Proceedings CHES 2012,
Springer, 2012, pp. 213–232.
conference:
end_date: 2012-09-12
location: Leuven, Belgium
name: 'CHES: Cryptographic Hardware and Embedded Systems'
start_date: 2012-09-09
das_tickbox: '1'
date_created: 2018-12-11T11:55:25Z
date_published: 2012-09-01T00:00:00Z
date_updated: 2026-07-07T13:05:30Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-33027-8_13
ec_funded: 1
fulldoi: https://doi.org/10.1007/978-3-642-33027-8_13
intvolume: ' 7428'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.iacr.org/archive/ches2012/74280211/74280211.pdf
month: '09'
oa: 1
oa_version: Preprint
page: 213 - 232
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Conference proceedings CHES 2012
publication_status: published
publisher: Springer
publist_id: '5003'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical leakage-resilient symmetric cryptography
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7428
year: '2012'
...
---
_id: '2049'
abstract:
- lang: eng
text: "We propose a new authentication protocol that is provably secure based on
a ring variant of the learning parity with noise (LPN) problem. The protocol follows
the design principle of the LPN-based protocol from Eurocrypt’11 (Kiltz et al.),
and like it, is a two round protocol secure against active attacks. Moreover,
our protocol has small communication complexity and a very small footprint which
makes it applicable in scenarios that involve low-cost, resource-constrained devices.\r\n\r\nPerformance-wise,
our protocol is more efficient than previous LPN-based schemes, such as the many
variants of the Hopper-Blum (HB) protocol and the aforementioned protocol from
Eurocrypt’11. Our implementation results show that it is even comparable to the
standard challenge-and-response protocols based on the AES block-cipher. Our basic
protocol is roughly 20 times slower than AES, but with the advantage of having
10 times smaller code size. Furthermore, if a few hundred bytes of non-volatile
memory are available to allow the storage of some off-line pre-computations, then
the online phase of our protocols is only twice as slow as AES.\r\n"
acknowledgement: "Supported by the European Research Council / ERC Starting Grant
(259668- PSPC)\r\nWe would like to thank the anonymous referees of this confer-
ence and those of the ECRYPT Workshop on Lightweight Cryptography for very useful
comments, and in particular for the suggestion that the scheme is somewhat vulnerable
to a man-in-the-middle attack whenever an adversary observes two reader challenges
that are the same. We hope that the attack we described in Appendix A corresponds
to what the reviewer had in mind. We also thank Tanja Lange for pointing us to the
pa- per of [Kir11] and for discussions of some of her recent work. "
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Stefan
full_name: Heyse, Stefan
last_name: Heyse
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Vadim
full_name: Lyubashevsky, Vadim
last_name: Lyubashevsky
- first_name: Christof
full_name: Paar, Christof
last_name: Paar
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Heyse S, Kiltz E, Lyubashevsky V, Paar C, Pietrzak KZ. Lapin: An efficient
authentication protocol based on ring-LPN. In: Conference Proceedings FSE 2012.
Vol 7549. Springer; 2012:346-365. doi:10.1007/978-3-642-34047-5_20'
apa: 'Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., & Pietrzak, K. Z. (2012).
Lapin: An efficient authentication protocol based on ring-LPN. In Conference
proceedings FSE 2012 (Vol. 7549, pp. 346–365). Washington, DC, USA: Springer.
https://doi.org/10.1007/978-3-642-34047-5_20'
chicago: 'Heyse, Stefan, Eike Kiltz, Vadim Lyubashevsky, Christof Paar, and Krzysztof
Z Pietrzak. “Lapin: An Efficient Authentication Protocol Based on Ring-LPN.” In
Conference Proceedings FSE 2012, 7549:346–65. Springer, 2012. https://doi.org/10.1007/978-3-642-34047-5_20.'
ieee: 'S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, and K. Z. Pietrzak, “Lapin:
An efficient authentication protocol based on ring-LPN,” in Conference proceedings
FSE 2012, Washington, DC, USA, 2012, vol. 7549, pp. 346–365.'
ista: 'Heyse S, Kiltz E, Lyubashevsky V, Paar C, Pietrzak KZ. 2012. Lapin: An efficient
authentication protocol based on ring-LPN. Conference proceedings FSE 2012. FSE:
Fast Software Encryption, LNCS, vol. 7549, 346–365.'
mla: 'Heyse, Stefan, et al. “Lapin: An Efficient Authentication Protocol Based on
Ring-LPN.” Conference Proceedings FSE 2012, vol. 7549, Springer, 2012,
pp. 346–65, doi:10.1007/978-3-642-34047-5_20.'
short: S. Heyse, E. Kiltz, V. Lyubashevsky, C. Paar, K.Z. Pietrzak, in:, Conference
Proceedings FSE 2012, Springer, 2012, pp. 346–365.
conference:
end_date: 2012-03-21
location: Washington, DC, USA
name: 'FSE: Fast Software Encryption'
start_date: 2012-03-19
das_tickbox: '1'
date_created: 2018-12-11T11:55:25Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2026-07-07T13:06:19Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-34047-5_20
ec_funded: 1
fulldoi: https://doi.org/10.1007/978-3-642-34047-5_20
intvolume: ' 7549'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://www.iacr.org/archive/fse2012/75490350/75490350.pdf
month: '03'
oa: 1
oa_version: Preprint
page: 346 - 365
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Conference proceedings FSE 2012
publication_status: published
publisher: Springer
publist_id: '5002'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Lapin: An efficient authentication protocol based on ring-LPN'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7549
year: '2012'
...
---
_id: '2942'
abstract:
- lang: eng
text: Interface theories provide a formal framework for component-based development
of software and hardware which supports the incremental design of systems and
the independent implementability of components. These capabilities are ensured
through mathematical properties of the parallel composition operator and the refinement
relation for components. More recently, a conjunction operation was added to interface
theories in order to provide support for handling multiple viewpoints, requirements
engineering, and component reuse. Unfortunately, the conjunction operator does
not allow independent implementability in general. In this paper, we study conditions
that need to be imposed on interface models in order to enforce independent implementability
with respect to conjunction. We focus on multiple viewpoint specifications and
propose a new compatibility criterion between two interfaces, which we call orthogonality.
We show that orthogonal interfaces can be refined separately, while preserving
both orthogonality and composability with other interfaces. We illustrate the
independent implementability of different viewpoints with a FIFO buffer example.
acknowledgement: ERC Advanced Grant QUAREM (Quantitative Reactive Modeling), FWF National
Research Network RISE (Rigorous Systems Engineering)
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Dejan
full_name: Nickovic, Dejan
id: 41BCEE5C-F248-11E8-B48F-1D18A9856A87
last_name: Nickovic
citation:
ama: 'Henzinger TA, Nickovic D. Independent implementability of viewpoints. In:
Conference Proceedings Monterey Workshop 2012. Vol 7539. Springer; 2012:380-395.
doi:10.1007/978-3-642-34059-8_20'
apa: 'Henzinger, T. A., & Nickovic, D. (2012). Independent implementability
of viewpoints. In Conference proceedings Monterey Workshop 2012 (Vol. 7539,
pp. 380–395). Oxford, UK: Springer. https://doi.org/10.1007/978-3-642-34059-8_20'
chicago: Henzinger, Thomas A, and Dejan Nickovic. “Independent Implementability
of Viewpoints.” In Conference Proceedings Monterey Workshop 2012, 7539:380–95.
Springer, 2012. https://doi.org/10.1007/978-3-642-34059-8_20.
ieee: T. A. Henzinger and D. Nickovic, “Independent implementability of viewpoints,”
in Conference proceedings Monterey Workshop 2012, Oxford, UK, 2012, vol.
7539, pp. 380–395.
ista: Henzinger TA, Nickovic D. 2012. Independent implementability of viewpoints.
Conference proceedings Monterey Workshop 2012. Monterey Workshop 2012, LNCS, vol.
7539, 380–395.
mla: Henzinger, Thomas A., and Dejan Nickovic. “Independent Implementability of
Viewpoints.” Conference Proceedings Monterey Workshop 2012, vol. 7539,
Springer, 2012, pp. 380–95, doi:10.1007/978-3-642-34059-8_20.
short: T.A. Henzinger, D. Nickovic, in:, Conference Proceedings Monterey Workshop
2012, Springer, 2012, pp. 380–395.
conference:
end_date: 2012-03-21
location: Oxford, UK
name: Monterey Workshop 2012
start_date: 2012-03-19
das_tickbox: '1'
date_created: 2018-12-11T12:00:28Z
date_published: 2012-09-16T00:00:00Z
date_updated: 2026-07-07T13:08:58Z
day: '16'
department:
- _id: ToHe
doi: 10.1007/978-3-642-34059-8_20
ec_funded: 1
fulldoi: https://doi.org/10.1007/978-3-642-34059-8_20
intvolume: ' 7539'
language:
- iso: eng
month: '09'
oa_version: None
page: 380 - 395
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: Conference proceedings Monterey Workshop 2012
publication_status: published
publisher: Springer
publist_id: '3791'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Independent implementability of viewpoints
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7539
year: '2012'
...
---
_id: '3274'
abstract:
- lang: eng
text: A boundary element model of a tunnel running through horizontally layered
soil with anisotropic material properties is presented. Since there is no analytical
fundamental solution for wave propagation inside a layered orthotropic medium
in 3D, the fundamental displacements and stresses have to be calculated numerically.
In our model this is done in the Fourier domain with respect to space and time.
The assumption of a straight tunnel with infinite extension in the x direction
makes it possible to decouple the system for every wave number kx, leading to
a 2.5D-problem, which is suited for parallel computation. The special form of
the fundamental solution, resulting from our Fourier ansatz, and the fact, that
the calculation of the boundary integral equation is performed in the Fourier
domain, enhances the stability and efficiency of the numerical calculations.
acknowledgement: This work was supported by the Austrian Federal Ministry of Transport,
Innovation and Technology under the Grant Bmvit-isb2 and the FFG under the project
Pr. Nr. 809089.
article_processing_charge: No
author:
- first_name: Georg
full_name: Rieckh, Georg
id: 34DA8BD6-F248-11E8-B48F-1D18A9856A87
last_name: Rieckh
- first_name: Wolfgang
full_name: Kreuzer, Wolfgang
last_name: Kreuzer
- first_name: Holger
full_name: Waubke, Holger
last_name: Waubke
- first_name: Peter
full_name: Balazs, Peter
last_name: Balazs
citation:
ama: Rieckh G, Kreuzer W, Waubke H, Balazs P. A 2.5D-Fourier-BEM model for vibrations
in a tunnel running through layered anisotropic soil. Engineering Analysis
with Boundary Elements. 2012;36(6):960-967. doi:10.1016/j.enganabound.2011.12.014
apa: Rieckh, G., Kreuzer, W., Waubke, H., & Balazs, P. (2012). A 2.5D-Fourier-BEM
model for vibrations in a tunnel running through layered anisotropic soil. Engineering
Analysis with Boundary Elements. Elsevier. https://doi.org/10.1016/j.enganabound.2011.12.014
chicago: Rieckh, Georg, Wolfgang Kreuzer, Holger Waubke, and Peter Balazs. “A 2.5D-Fourier-BEM
Model for Vibrations in a Tunnel Running through Layered Anisotropic Soil.” Engineering
Analysis with Boundary Elements. Elsevier, 2012. https://doi.org/10.1016/j.enganabound.2011.12.014.
ieee: G. Rieckh, W. Kreuzer, H. Waubke, and P. Balazs, “A 2.5D-Fourier-BEM model
for vibrations in a tunnel running through layered anisotropic soil,” Engineering
Analysis with Boundary Elements, vol. 36, no. 6. Elsevier, pp. 960–967, 2012.
ista: Rieckh G, Kreuzer W, Waubke H, Balazs P. 2012. A 2.5D-Fourier-BEM model for
vibrations in a tunnel running through layered anisotropic soil. Engineering Analysis
with Boundary Elements. 36(6), 960–967.
mla: Rieckh, Georg, et al. “A 2.5D-Fourier-BEM Model for Vibrations in a Tunnel
Running through Layered Anisotropic Soil.” Engineering Analysis with Boundary
Elements, vol. 36, no. 6, Elsevier, 2012, pp. 960–67, doi:10.1016/j.enganabound.2011.12.014.
short: G. Rieckh, W. Kreuzer, H. Waubke, P. Balazs, Engineering Analysis with Boundary
Elements 36 (2012) 960–967.
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T12:02:24Z
date_published: 2012-06-01T00:00:00Z
date_updated: 2026-07-07T13:10:10Z
day: '01'
department:
- _id: GaTk
doi: 10.1016/j.enganabound.2011.12.014
external_id:
isi:
- '000301691600005'
fulldoi: https://doi.org/10.1016/j.enganabound.2011.12.014
intvolume: ' 36'
isi: 1
issue: '6'
language:
- iso: eng
month: '06'
oa_version: None
page: 960 - 967
publication: Engineering Analysis with Boundary Elements
publication_status: published
publisher: Elsevier
publist_id: '3372'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A 2.5D-Fourier-BEM model for vibrations in a tunnel running through layered
anisotropic soil
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2012'
...
---
_id: '3331'
abstract:
- lang: eng
text: Computing the topology of an algebraic plane curve C means computing a combinatorial
graph that is isotopic to C and thus represents its topology in R2. We prove that,
for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology
of the induced curve can be computed with bit operations ( indicates that we
omit logarithmic factors). Our analysis improves the previous best known complexity
bounds by a factor of n2. The improvement is based on new techniques to compute
and refine isolating intervals for the real roots of polynomials, and on the consequent
amortized analysis of the critical fibers of the algebraic curve.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Kerber, Michael
id: 36E4574A-F248-11E8-B48F-1D18A9856A87
last_name: Kerber
orcid: 0000-0002-8030-9299
- first_name: Michael
full_name: Sagraloff, Michael
last_name: Sagraloff
citation:
ama: Kerber M, Sagraloff M. A worst case bound for topology computation of algebraic
curves. Journal of Symbolic Computation. 2012;47(3):239-258. doi:10.1016/j.jsc.2011.11.001
apa: Kerber, M., & Sagraloff, M. (2012). A worst case bound for topology computation
of algebraic curves. Journal of Symbolic Computation. Elsevier. https://doi.org/10.1016/j.jsc.2011.11.001
chicago: Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology
Computation of Algebraic Curves.” Journal of Symbolic Computation. Elsevier,
2012. https://doi.org/10.1016/j.jsc.2011.11.001.
ieee: M. Kerber and M. Sagraloff, “A worst case bound for topology computation of
algebraic curves,” Journal of Symbolic Computation, vol. 47, no. 3. Elsevier,
pp. 239–258, 2012.
ista: Kerber M, Sagraloff M. 2012. A worst case bound for topology computation of
algebraic curves. Journal of Symbolic Computation. 47(3), 239–258.
mla: Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation
of Algebraic Curves.” Journal of Symbolic Computation, vol. 47, no. 3,
Elsevier, 2012, pp. 239–58, doi:10.1016/j.jsc.2011.11.001.
short: M. Kerber, M. Sagraloff, Journal of Symbolic Computation 47 (2012) 239–258.
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T12:02:43Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2026-07-07T13:11:38Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.jsc.2011.11.001
external_id:
arxiv:
- '1104.1510'
isi:
- '000300115300002'
fulldoi: https://doi.org/10.1016/j.jsc.2011.11.001
intvolume: ' 47'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1104.1510
month: '03'
oa: 1
oa_version: Preprint
page: 239 - 258
publication: Journal of Symbolic Computation
publication_status: published
publisher: Elsevier
publist_id: '3303'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A worst case bound for topology computation of algebraic curves
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 47
year: '2012'
...
---
_id: '2955'
abstract:
- lang: eng
text: 'We consider two-player stochastic games played on finite graphs with reachability
objectives where the first player tries to ensure a target state to be visited
almost-surely (i.e., with probability 1), or positively (i.e., with positive probability),
no matter the strategy of the second player. We classify such games according
to the information and the power of randomization available to the players. On
the basis of information, the game can be one-sided with either (a) player 1,
or (b) player 2 having partial observation (and the other player has perfect observation),
or two-sided with (c) both players having partial observation. On the basis of
randomization, the players (a) may not be allowed to use randomization (pure strategies),
or (b) may choose a probability distribution over actions but the actual random
choice is external and not visible to the player (actions invisible), or (c) may
use full randomization. Our main results for pure strategies are as follows. (1)
For one-sided games with player 1 having partial observation we show that (in
contrast to full randomized strategies) belief-based (subset-construction based)
strategies are not sufficient, and we present an exponential upper bound on memory
both for almostsure and positive winning strategies; we show that the problem
of deciding the existence of almost-sure and positive winning strategies for player
1 is EXPTIME-complete. (2) For one-sided games with player 2 having partial observation
we show that non-elementary memory is both necessary and sufficient for both almost-sure
and positive winning strategies. (3) We show that for the general (two-sided)
case finite-memory strategies are sufficient for both positive and almost-sure
winning, and at least non-elementary memory is required. We establish the equivalence
of the almost-sure winning problems for pure strategies and for randomized strategies
with actions invisible. Our equivalence result exhibits serious flaws in previous
results of the literature: we show a non-elementary memory lower bound for almost-sure
winning whereas an exponential upper bound was previously claimed.'
acknowledgement: 'This work was partially supported by FWF Grant No P 23499-N23, FWF
NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph Games), and Microsoft
faculty fellows award.'
article_number: '6280436'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Laurent
full_name: Doyen, Laurent
last_name: Doyen
citation:
ama: 'Chatterjee K, Doyen L. Partial-observation stochastic games: How to win when
belief fails. In: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on
Logic in Computer Science. IEEE; 2012. doi:10.1109/LICS.2012.28'
apa: 'Chatterjee, K., & Doyen, L. (2012). Partial-observation stochastic games:
How to win when belief fails. In Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science. Dubrovnik, Croatia: IEEE. https://doi.org/10.1109/LICS.2012.28'
chicago: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
Games: How to Win When Belief Fails.” In Proceedings of the 2012 27th Annual
ACM/IEEE Symposium on Logic in Computer Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.28.'
ieee: 'K. Chatterjee and L. Doyen, “Partial-observation stochastic games: How to
win when belief fails,” in Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science, Dubrovnik, Croatia, 2012.'
ista: 'Chatterjee K, Doyen L. 2012. Partial-observation stochastic games: How to
win when belief fails. Proceedings of the 2012 27th Annual ACM/IEEE Symposium
on Logic in Computer Science. LICS: Logic in Computer Science, 6280436.'
mla: 'Chatterjee, Krishnendu, and Laurent Doyen. “Partial-Observation Stochastic
Games: How to Win When Belief Fails.” Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, 6280436, IEEE, 2012, doi:10.1109/LICS.2012.28.'
short: K. Chatterjee, L. Doyen, in:, Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2012.
conference:
end_date: 2012-06-28
location: Dubrovnik, Croatia
name: 'LICS: Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T12:00:32Z
date_published: 2012-08-23T00:00:00Z
date_updated: 2026-07-07T14:01:25Z
day: '23'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.28
ec_funded: 1
external_id:
arxiv:
- '1107.2141'
isi:
- '000309059900023'
fulldoi: https://doi.org/10.1109/LICS.2012.28
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1107.2141
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_status: published
publisher: IEEE
publist_id: '3771'
quality_controlled: '1'
related_material:
record:
- id: '5381'
relation: earlier_version
status: public
- id: '2211'
relation: later_version
status: public
scopus_import: '1'
status: public
title: 'Partial-observation stochastic games: How to win when belief fails'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2012'
...
---
_id: '2967'
abstract:
- lang: eng
text: For programs whose data variables range over Boolean or finite domains, program
verification is decidable, and this forms the basis of recent tools for software
model checking. In this article, we consider algorithmic verification of programs
that use Boolean variables, and in addition, access a single read-only array whose
length is potentially unbounded, and whose elements range over an unbounded data
domain. We show that the reachability problem, while undecidable in general, is
(1) PSPACE-complete for programs in which the array-accessing for-loops are not
nested, (2) decidable for a restricted class of programs with doubly nested loops.
The second result establishes connections to automata and logics defining languages
over data words.
acknowledgement: This research was supported in part by the NSF Cybertrust award CNS
0524059, by the European Research Council (ERC) Advanced Investigator Grant QUAREM,
and by the Austrian Science Fund (FWF) project S11402-N23.
article_number: '27'
article_processing_charge: No
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- first_name: Scott
full_name: Weinstein, Scott
last_name: Weinstein
citation:
ama: Alur R, Cerny P, Weinstein S. Algorithmic analysis of array-accessing programs.
ACM Transactions on Computational Logic. 2012;13(3). doi:10.1145/2287718.2287727
apa: Alur, R., Cerny, P., & Weinstein, S. (2012). Algorithmic analysis of array-accessing
programs. ACM Transactions on Computational Logic. ACM. https://doi.org/10.1145/2287718.2287727
chicago: Alur, Rajeev, Pavol Cerny, and Scott Weinstein. “Algorithmic Analysis of
Array-Accessing Programs.” ACM Transactions on Computational Logic. ACM,
2012. https://doi.org/10.1145/2287718.2287727.
ieee: R. Alur, P. Cerny, and S. Weinstein, “Algorithmic analysis of array-accessing
programs,” ACM Transactions on Computational Logic, vol. 13, no. 3. ACM,
2012.
ista: Alur R, Cerny P, Weinstein S. 2012. Algorithmic analysis of array-accessing
programs. ACM Transactions on Computational Logic. 13(3), 27.
mla: Alur, Rajeev, et al. “Algorithmic Analysis of Array-Accessing Programs.” ACM
Transactions on Computational Logic, vol. 13, no. 3, 27, ACM, 2012, doi:10.1145/2287718.2287727.
short: R. Alur, P. Cerny, S. Weinstein, ACM Transactions on Computational Logic
13 (2012).
das_tickbox: '1'
date_created: 2018-12-11T12:00:36Z
date_published: 2012-08-01T00:00:00Z
date_updated: 2026-07-07T14:01:59Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2287718.2287727
ec_funded: 1
external_id:
isi:
- '000308370100009'
fulldoi: https://doi.org/10.1145/2287718.2287727
intvolume: ' 13'
isi: 1
issue: '3'
language:
- iso: eng
month: '08'
oa_version: None
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: ACM Transactions on Computational Logic
publication_status: published
publisher: ACM
publist_id: '3748'
quality_controlled: '1'
related_material:
record:
- id: '4403'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Algorithmic analysis of array-accessing programs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2012'
...
---
_id: '494'
abstract:
- lang: eng
text: We solve the longstanding open problems of the blow-up involved in the translations,
when possible, of a nondeterministic Büchi word automaton (NBW) to a nondeterministic
co-Büchi word automaton (NCW) and to a deterministic co-Büchi word automaton (DCW).
For the NBW to NCW translation, the currently known upper bound is 2o(nlog n)
and the lower bound is 1.5n. We improve the upper bound to n2n and describe a
matching lower bound of 2ω(n). For the NBW to DCW translation, the currently known
upper bound is 2o(nlog n). We improve it to 2 o(n), which is asymptotically tight.
Both of our upper-bound constructions are based on a simple subset construction,
do not involve intermediate automata with richer acceptance conditions, and can
be implemented symbolically. We continue and solve the open problems of translating
nondeterministic Streett, Rabin, Muller, and parity word automata to NCW and to
DCW. Going via an intermediate NBW is not optimal and we describe direct, simple,
and asymptotically tight constructions, involving a 2o(n) blow-up. The constructions
are variants of the subset construction, providing a unified approach for translating
all common classes of automata to NCW and DCW. Beyond the theoretical importance
of the results, we point to numerous applications of the new constructions. In
particular, they imply a simple subset-construction based translation, when possible,
of LTL to deterministic Büchi word automata.
article_number: '29'
article_processing_charge: No
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Orna
full_name: Kupferman, Orna
last_name: Kupferman
citation:
ama: Boker U, Kupferman O. Translating to Co-Büchi made tight, unified, and useful.
ACM Transactions on Computational Logic. 2012;13(4). doi:10.1145/2362355.2362357
apa: Boker, U., & Kupferman, O. (2012). Translating to Co-Büchi made tight,
unified, and useful. ACM Transactions on Computational Logic. ACM. https://doi.org/10.1145/2362355.2362357
chicago: Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified,
and Useful.” ACM Transactions on Computational Logic. ACM, 2012. https://doi.org/10.1145/2362355.2362357.
ieee: U. Boker and O. Kupferman, “Translating to Co-Büchi made tight, unified, and
useful,” ACM Transactions on Computational Logic, vol. 13, no. 4. ACM,
2012.
ista: Boker U, Kupferman O. 2012. Translating to Co-Büchi made tight, unified, and
useful. ACM Transactions on Computational Logic. 13(4), 29.
mla: Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified,
and Useful.” ACM Transactions on Computational Logic, vol. 13, no. 4, 29,
ACM, 2012, doi:10.1145/2362355.2362357.
short: U. Boker, O. Kupferman, ACM Transactions on Computational Logic 13 (2012).
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T11:46:47Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2026-07-07T14:02:16Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2362355.2362357
external_id:
isi:
- '000310163600002'
fulldoi: https://doi.org/10.1145/2362355.2362357
intvolume: ' 13'
isi: 1
issue: '4'
language:
- iso: eng
month: '10'
oa_version: None
publication: ACM Transactions on Computational Logic
publication_status: published
publisher: ACM
publist_id: '7326'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Translating to Co-Büchi made tight, unified, and useful
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2012'
...
---
_id: '10905'
abstract:
- lang: eng
text: "Energy games belong to a class of turn-based two-player infinite-duration
games played on a weighted directed graph. It is one of the rare and intriguing
combinatorial problems that lie in NP ∩ co−NP, but are not known to be in P. While
the existence of polynomial-time algorithms has been a major open problem for
decades, there is no algorithm that solves any non-trivial subclass in polynomial
time.\r\nIn this paper, we give several results based on the weight structures
of the graph. First, we identify a notion of penalty and present a polynomial-time
algorithm when the penalty is large. Our algorithm is the first polynomial-time
algorithm on a large class of weighted graphs. It includes several counter examples
that show that many previous algorithms, such as value iteration and random facet
algorithms, require at least sub-exponential time. Our main technique is developing
the first non-trivial approximation algorithm and showing how to convert it to
an exact algorithm. Moreover, we show that in a practical case in verification
where weights are clustered around a constant number of values, the energy game
problem can be solved in polynomial time. We also show that the problem is still
as hard as in general when the clique-width is bounded or the graph is strongly
ergodic, suggesting that restricting graph structures need not help."
acknowledgement: 'Supported by the Austrian Science Fund (FWF): P23499-N23, the Austrian
Science Fund (FWF): S11407-N23 (RiSE), an ERC Start Grant (279307: Graph Games),
and a Microsoft Faculty Fellows Award'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Sebastian
full_name: Krinninger, Sebastian
last_name: Krinninger
- first_name: Danupon
full_name: Nanongkai, Danupon
last_name: Nanongkai
citation:
ama: 'Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. Polynomial-time algorithms
for energy games with special weight structures. In: 20th Annual European Symposium
on Algorithms . Vol 7501. Springer; 2012:301-312. doi:10.1007/978-3-642-33090-2_27'
apa: 'Chatterjee, K., Henzinger, M., Krinninger, S., & Nanongkai, D. (2012).
Polynomial-time algorithms for energy games with special weight structures. In
20th Annual European Symposium on Algorithms (Vol. 7501, pp. 301–312).
Ljubljana, Slovenia: Springer. https://doi.org/10.1007/978-3-642-33090-2_27'
chicago: Chatterjee, Krishnendu, Monika Henzinger, Sebastian Krinninger, and Danupon
Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.”
In 20th Annual European Symposium on Algorithms , 7501:301–12. Springer,
2012. https://doi.org/10.1007/978-3-642-33090-2_27.
ieee: K. Chatterjee, M. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time
algorithms for energy games with special weight structures,” in 20th Annual
European Symposium on Algorithms , Ljubljana, Slovenia, 2012, vol. 7501, pp.
301–312.
ista: 'Chatterjee K, Henzinger M, Krinninger S, Nanongkai D. 2012. Polynomial-time
algorithms for energy games with special weight structures. 20th Annual European
Symposium on Algorithms . ESA: European Symposium on Algorithms, LNCS, vol. 7501,
301–312.'
mla: Chatterjee, Krishnendu, et al. “Polynomial-Time Algorithms for Energy Games
with Special Weight Structures.” 20th Annual European Symposium on Algorithms
, vol. 7501, Springer, 2012, pp. 301–12, doi:10.1007/978-3-642-33090-2_27.
short: K. Chatterjee, M. Henzinger, S. Krinninger, D. Nanongkai, in:, 20th Annual
European Symposium on Algorithms , Springer, 2012, pp. 301–312.
conference:
end_date: 2012-09-12
location: Ljubljana, Slovenia
name: 'ESA: European Symposium on Algorithms'
start_date: 2012-09-10
corr_author: '1'
das_tickbox: '1'
date_created: 2022-03-21T08:01:45Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2026-07-08T05:50:39Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-33090-2_27
ec_funded: 1
external_id:
arxiv:
- '1604.08234'
fulldoi: https://doi.org/10.1007/978-3-642-33090-2_27
intvolume: ' 7501'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.08234
month: '10'
oa: 1
oa_version: Preprint
page: 301-312
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: '20th Annual European Symposium on Algorithms '
publication_identifier:
eisbn:
- '9783642330902'
eissn:
- 1611-3349
isbn:
- '9783642330896'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
record:
- id: '535'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Polynomial-time algorithms for energy games with special weight structures
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7501
year: '2012'
...
---
_id: '2891'
abstract:
- lang: eng
text: "Quantitative automata are nondeterministic finite automata with edge weights.
They value a\r\nrun by some function from the sequence of visited weights to the
reals, and value a word by its\r\nminimal/maximal run. They generalize boolean
automata, and have gained much attention in\r\nrecent years. Unfortunately, important
automaton classes, such as sum, discounted-sum, and\r\nlimit-average automata,
cannot be determinized. Yet, the quantitative setting provides the potential\r\nof
approximate determinization. We define approximate determinization with respect
to\r\na distance function, and investigate this potential.\r\nWe show that sum
automata cannot be determinized approximately with respect to any\r\ndistance
function. However, restricting to nonnegative weights allows for approximate determinization\r\nwith
respect to some distance functions.\r\nDiscounted-sum automata allow for approximate
determinization, as the influence of a word’s\r\nsuffix is decaying. However,
the naive approach, of unfolding the automaton computations up\r\nto a sufficient
level, is shown to be doubly exponential in the discount factor. We provide an\r\nalternative
construction that is singly exponential in the discount factor, in the precision,
and\r\nin the number of states. We prove matching lower bounds, showing exponential
dependency on\r\neach of these three parameters.\r\nAverage and limit-average
automata are shown to prohibit approximate determinization with\r\nrespect to
any distance function, and this is the case even for two weights, 0 and 1."
acknowledgement: We thank Laurent Doyen for great ideas and valuable help in analyzing
discounted-sum automata.
alternative_title:
- LIPIcs
article_processing_charge: No
author:
- first_name: Udi
full_name: Boker, Udi
id: 31E297B6-F248-11E8-B48F-1D18A9856A87
last_name: Boker
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
citation:
ama: 'Boker U, Henzinger TA. Approximate determinization of quantitative automata.
In: Leibniz International Proceedings in Informatics. Vol 18. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2012:362-373. doi:10.4230/LIPIcs.FSTTCS.2012.362'
apa: 'Boker, U., & Henzinger, T. A. (2012). Approximate determinization of quantitative
automata. In Leibniz International Proceedings in Informatics (Vol. 18,
pp. 362–373). Hyderabad, India: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.362'
chicago: Boker, Udi, and Thomas A Henzinger. “Approximate Determinization of Quantitative
Automata.” In Leibniz International Proceedings in Informatics, 18:362–73.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012. https://doi.org/10.4230/LIPIcs.FSTTCS.2012.362.
ieee: U. Boker and T. A. Henzinger, “Approximate determinization of quantitative
automata,” in Leibniz International Proceedings in Informatics, Hyderabad,
India, 2012, vol. 18, pp. 362–373.
ista: 'Boker U, Henzinger TA. 2012. Approximate determinization of quantitative
automata. Leibniz International Proceedings in Informatics. FSTTCS: Foundations
of Software Technology and Theoretical Computer Science, LIPIcs, vol. 18, 362–373.'
mla: Boker, Udi, and Thomas A. Henzinger. “Approximate Determinization of Quantitative
Automata.” Leibniz International Proceedings in Informatics, vol. 18, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 362–73, doi:10.4230/LIPIcs.FSTTCS.2012.362.
short: U. Boker, T.A. Henzinger, in:, Leibniz International Proceedings in Informatics,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012, pp. 362–373.
conference:
end_date: 2012-12-17
location: Hyderabad, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2012-12-15
corr_author: '1'
das_tickbox: '1'
date_created: 2018-12-11T12:00:10Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2026-07-28T09:20:59Z
day: '01'
ddc:
- '004'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.FSTTCS.2012.362
ec_funded: 1
file:
- access_level: open_access
checksum: 88da18d3e2cb2e5011d7d10ce38a3864
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:37Z
date_updated: 2020-07-14T12:45:52Z
file_id: '4826'
file_name: IST-2017-805-v1+1_34.pdf
file_size: 559069
relation: main_file
file_date_updated: 2020-07-14T12:45:52Z
fulldoi: https://doi.org/10.4230/LIPIcs.FSTTCS.2012.362
has_accepted_license: '1'
intvolume: ' 18'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/3.0/
month: '12'
oa: 1
oa_version: Published Version
page: 362 - 373
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: Leibniz International Proceedings in Informatics
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '3867'
pubrep_id: '805'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Approximate determinization of quantitative automata
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported (CC BY-NC-ND
3.0)
short: CC BY-NC-ND (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 18
year: '2012'
...