---
_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.
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.
date_created: 2018-12-11T12:02:43Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2021-01-12T07:42:43Z
day: '01'
department:
- _id: HeEd
doi: 10.1016/j.jsc.2011.11.001
intvolume: ' 47'
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 47
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
date_created: 2018-12-11T12:02:46Z
date_published: 2012-03-22T00:00:00Z
date_updated: 2023-02-23T12:23:46Z
day: '22'
department:
- _id: KrCh
doi: 10.1007/978-3-642-28729-9_18
ec_funded: 1
external_id:
arxiv:
- '1107.2009'
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: '10896'
abstract:
- lang: eng
text: Under physiological conditions the brain, via the purine salvage pathway,
reuses the preformed purine bases hypoxanthine, derived from ATP degradation,
and adenine (Ade), derived from polyamine synthesis, to restore its ATP pool.
However, the massive degradation of ATP during ischemia, although providing valuable
neuroprotective adenosine, results in the accumulation and loss of diffusible
purine metabolites and thereby leads to a protracted reduction in the post-ischemic
ATP pool size. In vivo, this may both limit the ability to deploy ATP-dependent
reparative mechanisms and reduce the subsequent availability of adenosine, whilst
in brain slices results in tissue with substantially lower levels of ATP than
in vivo. In the present review, we describe the mechanisms by which brain tissue
replenishes its ATP, how this can be improved with the clinically tolerated chemicals
D-ribose and adenine, and the functional, and potential therapeutic, implications
of doing so.
acknowledgement: We are grateful to Research into Ageing/Ageing UK and The Dunhill
Trust for funding SzN’s graduate studies, and to Prof Nicholas Dale for his valuable
input.
article_processing_charge: No
author:
- first_name: Stephanie
full_name: zur Nedden, Stephanie
id: 3C77F464-F248-11E8-B48F-1D18A9856A87
last_name: zur Nedden
- first_name: Alexander S.
full_name: Doney, Alexander S.
last_name: Doney
- first_name: Bruno G.
full_name: Frenguelli, Bruno G.
last_name: Frenguelli
citation:
ama: 'zur Nedden S, Doney AS, Frenguelli BG. The double-edged sword: Gaining Adenosine
at the expense of ATP. How to balance the books. In: Masino S, Boison D, eds.
Adenosine. 1st ed. New York: Springer; 2012:109-129. doi:10.1007/978-1-4614-3903-5_6'
apa: 'zur Nedden, S., Doney, A. S., & Frenguelli, B. G. (2012). The double-edged
sword: Gaining Adenosine at the expense of ATP. How to balance the books. In S.
Masino & D. Boison (Eds.), Adenosine (1st ed., pp. 109–129). New York:
Springer. https://doi.org/10.1007/978-1-4614-3903-5_6'
chicago: 'Nedden, Stephanie zur, Alexander S. Doney, and Bruno G. Frenguelli. “The
Double-Edged Sword: Gaining Adenosine at the Expense of ATP. How to Balance the
Books.” In Adenosine, edited by Susan Masino and Detlev Boison, 1st ed.,
109–29. New York: Springer, 2012. https://doi.org/10.1007/978-1-4614-3903-5_6.'
ieee: 'S. zur Nedden, A. S. Doney, and B. G. Frenguelli, “The double-edged sword:
Gaining Adenosine at the expense of ATP. How to balance the books,” in Adenosine,
1st ed., S. Masino and D. Boison, Eds. New York: Springer, 2012, pp. 109–129.'
ista: 'zur Nedden S, Doney AS, Frenguelli BG. 2012.The double-edged sword: Gaining
Adenosine at the expense of ATP. How to balance the books. In: Adenosine. , 109–129.'
mla: 'zur Nedden, Stephanie, et al. “The Double-Edged Sword: Gaining Adenosine at
the Expense of ATP. How to Balance the Books.” Adenosine, edited by Susan
Masino and Detlev Boison, 1st ed., Springer, 2012, pp. 109–29, doi:10.1007/978-1-4614-3903-5_6.'
short: S. zur Nedden, A.S. Doney, B.G. Frenguelli, in:, S. Masino, D. Boison (Eds.),
Adenosine, 1st ed., Springer, New York, 2012, pp. 109–129.
date_created: 2022-03-21T07:16:12Z
date_published: 2012-07-23T00:00:00Z
date_updated: 2022-06-21T11:51:58Z
day: '23'
department:
- _id: HaJa
doi: 10.1007/978-1-4614-3903-5_6
edition: '1'
editor:
- first_name: Susan
full_name: Masino, Susan
last_name: Masino
- first_name: Detlev
full_name: Boison, Detlev
last_name: Boison
language:
- iso: eng
month: '07'
oa_version: None
page: 109-129
place: New York
publication: Adenosine
publication_identifier:
eisbn:
- '9781461439035'
isbn:
- '9781461439028'
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'The double-edged sword: Gaining Adenosine at the expense of ATP. How to balance
the books'
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '10903'
abstract:
- lang: eng
text: We propose a logic-based framework for automated reasoning about sequential
programs manipulating singly-linked lists and arrays with unbounded data. We introduce
the logic SLAD, which allows combining shape constraints, written in a fragment
of Separation Logic, with data and size constraints. We address the problem of
checking the entailment between SLAD formulas, which is crucial in performing
pre-post condition reasoning. Although this problem is undecidable in general
for SLAD, we propose a sound and powerful procedure that is able to solve this
problem for a large class of formulas, beyond the capabilities of existing techniques
and tools. We prove that this procedure is complete, i.e., it is actually a decision
procedure for this problem, for an important fragment of SLAD including known
decidable logics. We implemented this procedure and shown its preciseness and
its efficiency on a significant benchmark of formulas.
acknowledgement: This work has been partially supported by the French ANR project
Veridyc
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Ahmed
full_name: Bouajjani, Ahmed
last_name: Bouajjani
- first_name: Cezara
full_name: Dragoi, Cezara
id: 2B2B5ED0-F248-11E8-B48F-1D18A9856A87
last_name: Dragoi
- first_name: Constantin
full_name: Enea, Constantin
last_name: Enea
- first_name: Mihaela
full_name: Sighireanu, Mihaela
last_name: Sighireanu
citation:
ama: 'Bouajjani A, Dragoi C, Enea C, Sighireanu M. Accurate invariant checking for
programs manipulating lists and arrays with infinite data. In: Automated Technology
for Verification and Analysis. Vol 7561. LNCS. Berlin, Heidelberg: Springer;
2012:167-182. doi:10.1007/978-3-642-33386-6_14'
apa: 'Bouajjani, A., Dragoi, C., Enea, C., & Sighireanu, M. (2012). Accurate
invariant checking for programs manipulating lists and arrays with infinite data.
In Automated Technology for Verification and Analysis (Vol. 7561, pp. 167–182).
Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-33386-6_14'
chicago: 'Bouajjani, Ahmed, Cezara Dragoi, Constantin Enea, and Mihaela Sighireanu.
“Accurate Invariant Checking for Programs Manipulating Lists and Arrays with Infinite
Data.” In Automated Technology for Verification and Analysis, 7561:167–82.
LNCS. Berlin, Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-33386-6_14.'
ieee: A. Bouajjani, C. Dragoi, C. Enea, and M. Sighireanu, “Accurate invariant checking
for programs manipulating lists and arrays with infinite data,” in Automated
Technology for Verification and Analysis, Thiruvananthapuram, India, 2012,
vol. 7561, pp. 167–182.
ista: 'Bouajjani A, Dragoi C, Enea C, Sighireanu M. 2012. Accurate invariant checking
for programs manipulating lists and arrays with infinite data. Automated Technology
for Verification and Analysis. ATVA: Automated Technology for Verification and
AnalysisLNCS, LNCS, vol. 7561, 167–182.'
mla: Bouajjani, Ahmed, et al. “Accurate Invariant Checking for Programs Manipulating
Lists and Arrays with Infinite Data.” Automated Technology for Verification
and Analysis, vol. 7561, Springer, 2012, pp. 167–82, doi:10.1007/978-3-642-33386-6_14.
short: A. Bouajjani, C. Dragoi, C. Enea, M. Sighireanu, in:, Automated Technology
for Verification and Analysis, Springer, Berlin, Heidelberg, 2012, pp. 167–182.
conference:
end_date: 2012-10-06
location: Thiruvananthapuram, India
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2012-10-03
date_created: 2022-03-21T07:58:39Z
date_published: 2012-10-15T00:00:00Z
date_updated: 2023-09-05T14:07:24Z
day: '15'
department:
- _id: ToHe
doi: 10.1007/978-3-642-33386-6_14
intvolume: ' 7561'
language:
- iso: eng
month: '10'
oa_version: None
page: 167-182
place: Berlin, Heidelberg
publication: Automated Technology for Verification and Analysis
publication_identifier:
eisbn:
- '9783642333866'
eissn:
- 1611-3349
isbn:
- '9783642333859'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Accurate invariant checking for programs manipulating lists and arrays with
infinite data
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 7561
year: '2012'
...
---
_id: '10904'
abstract:
- lang: eng
text: Multi-dimensional mean-payoff and energy games provide the mathematical foundation
for the quantitative study of reactive systems, and play a central role in the
emerging quantitative theory of verification and synthesis. In this work, we study
the strategy synthesis problem for games with such multi-dimensional objectives
along with a parity condition, a canonical way to express ω-regular conditions.
While in general, the winning strategies in such games may require infinite memory,
for synthesis the most relevant problem is the construction of a finite-memory
winning strategy (if one exists). Our main contributions are as follows. First,
we show a tight exponential bound (matching upper and lower bounds) on the memory
required for finite-memory winning strategies in both multi-dimensional mean-payoff
and energy games along with parity objectives. This significantly improves the
triple exponential upper bound for multi energy games (without parity) that could
be derived from results in literature for games on VASS (vector addition systems
with states). Second, we present an optimal symbolic and incremental algorithm
to compute a finite-memory winning strategy (if one exists) in such games. Finally,
we give a complete characterization of when finite memory of strategies can be
traded off for randomness. In particular, we show that for one-dimension mean-payoff
parity games, randomized memoryless strategies are as powerful as their pure finite-memory
counterparts.
acknowledgement: 'Author supported by Austrian Science Fund (FWF) Grant No P 23499-N23,
FWF NFN Grant No S11407 (RiSE), ERC Start Grant (279307: Graph Games), Microsoft
faculty fellowship.'
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: Mickael
full_name: Randour, Mickael
last_name: Randour
- first_name: Jean-François
full_name: Raskin, Jean-François
last_name: Raskin
citation:
ama: 'Chatterjee K, Randour M, Raskin J-F. Strategy synthesis for multi-dimensional
quantitative objectives. In: Koutny M, Ulidowski I, eds. CONCUR 2012 - Concurrency
Theory. Vol 7454. Berlin, Heidelberg: Springer; 2012:115-131. doi:10.1007/978-3-642-32940-1_10'
apa: 'Chatterjee, K., Randour, M., & Raskin, J.-F. (2012). Strategy synthesis
for multi-dimensional quantitative objectives. In M. Koutny & I. Ulidowski
(Eds.), CONCUR 2012 - Concurrency Theory (Vol. 7454, pp. 115–131). Berlin,
Heidelberg: Springer. https://doi.org/10.1007/978-3-642-32940-1_10'
chicago: 'Chatterjee, Krishnendu, Mickael Randour, and Jean-François Raskin. “Strategy
Synthesis for Multi-Dimensional Quantitative Objectives.” In CONCUR 2012 -
Concurrency Theory, edited by Maciej Koutny and Irek Ulidowski, 7454:115–31.
Berlin, Heidelberg: Springer, 2012. https://doi.org/10.1007/978-3-642-32940-1_10.'
ieee: K. Chatterjee, M. Randour, and J.-F. Raskin, “Strategy synthesis for multi-dimensional
quantitative objectives,” in CONCUR 2012 - Concurrency Theory, Newcastle
upon Tyne, United Kingdom, 2012, vol. 7454, pp. 115–131.
ista: 'Chatterjee K, Randour M, Raskin J-F. 2012. Strategy synthesis for multi-dimensional
quantitative objectives. CONCUR 2012 - Concurrency Theory. CONCUR: Conference
on Concurrency Theory, LNCS, vol. 7454, 115–131.'
mla: Chatterjee, Krishnendu, et al. “Strategy Synthesis for Multi-Dimensional Quantitative
Objectives.” CONCUR 2012 - Concurrency Theory, edited by Maciej Koutny
and Irek Ulidowski, vol. 7454, Springer, 2012, pp. 115–31, doi:10.1007/978-3-642-32940-1_10.
short: K. Chatterjee, M. Randour, J.-F. Raskin, in:, M. Koutny, I. Ulidowski (Eds.),
CONCUR 2012 - Concurrency Theory, Springer, Berlin, Heidelberg, 2012, pp. 115–131.
conference:
end_date: 2012-09-07
location: Newcastle upon Tyne, United Kingdom
name: 'CONCUR: Conference on Concurrency Theory'
start_date: 2012-09-04
date_created: 2022-03-21T08:00:21Z
date_published: 2012-09-15T00:00:00Z
date_updated: 2023-02-23T10:55:06Z
day: '15'
department:
- _id: KrCh
doi: 10.1007/978-3-642-32940-1_10
ec_funded: 1
editor:
- first_name: Maciej
full_name: Koutny, Maciej
last_name: Koutny
- first_name: Irek
full_name: Ulidowski, Irek
last_name: Ulidowski
external_id:
arxiv:
- '1201.5073'
intvolume: ' 7454'
language:
- iso: eng
month: '09'
oa_version: Preprint
page: 115-131
place: Berlin, Heidelberg
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _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: CONCUR 2012 - Concurrency Theory
publication_identifier:
eisbn:
- '9783642329401'
isbn:
- '9783642329395'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer
quality_controlled: '1'
related_material:
record:
- id: '2716'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Strategy synthesis for multi-dimensional quantitative objectives
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 7454
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 MH, Krinninger S, Nanongkai D. Polynomial-time algorithms
for energy games with special weight structures. In: Algorithms – ESA 2012.
Vol 7501. Springer; 2012:301-312. doi:10.1007/978-3-642-33090-2_27'
apa: 'Chatterjee, K., Henzinger, M. H., Krinninger, S., & Nanongkai, D. (2012).
Polynomial-time algorithms for energy games with special weight structures. In
Algorithms – ESA 2012 (Vol. 7501, pp. 301–312). Ljubljana, Slovenia: Springer.
https://doi.org/10.1007/978-3-642-33090-2_27'
chicago: Chatterjee, Krishnendu, Monika H Henzinger, Sebastian Krinninger, and Danupon
Nanongkai. “Polynomial-Time Algorithms for Energy Games with Special Weight Structures.”
In Algorithms – ESA 2012, 7501:301–12. Springer, 2012. https://doi.org/10.1007/978-3-642-33090-2_27.
ieee: K. Chatterjee, M. H. Henzinger, S. Krinninger, and D. Nanongkai, “Polynomial-time
algorithms for energy games with special weight structures,” in Algorithms
– ESA 2012, Ljubljana, Slovenia, 2012, vol. 7501, pp. 301–312.
ista: 'Chatterjee K, Henzinger MH, Krinninger S, Nanongkai D. 2012. Polynomial-time
algorithms for energy games with special weight structures. Algorithms – ESA 2012.
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.” Algorithms – ESA 2012, vol. 7501, Springer,
2012, pp. 301–12, doi:10.1007/978-3-642-33090-2_27.
short: K. Chatterjee, M.H. Henzinger, S. Krinninger, D. Nanongkai, in:, Algorithms
– ESA 2012, 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
date_created: 2022-03-21T08:01:45Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2023-09-05T14:09:30Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-642-33090-2_27
ec_funded: 1
external_id:
arxiv:
- '1604.08234'
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: Algorithms – ESA 2012
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 7501
year: '2012'
...
---
_id: '10906'
abstract:
- lang: eng
text: HSF(C) is a tool that automates verification of safety and liveness properties
for C programs. This paper describes the verification approach taken by HSF(C)
and provides instructions on how to install and use the tool.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Sergey
full_name: Grebenshchikov, Sergey
last_name: Grebenshchikov
- first_name: Ashutosh
full_name: Gupta, Ashutosh
id: 335E5684-F248-11E8-B48F-1D18A9856A87
last_name: Gupta
- first_name: Nuno P.
full_name: Lopes, Nuno P.
last_name: Lopes
- first_name: Corneliu
full_name: Popeea, Corneliu
last_name: Popeea
- first_name: Andrey
full_name: Rybalchenko, Andrey
last_name: Rybalchenko
citation:
ama: 'Grebenshchikov S, Gupta A, Lopes NP, Popeea C, Rybalchenko A. HSF(C): A software
verifier based on Horn clauses. In: Flanagan C, König B, eds. Tools and Algorithms
for the Construction and Analysis of Systems. Vol 7214. LNCS. Berlin, Heidelberg:
Springer; 2012:549-551. doi:10.1007/978-3-642-28756-5_46'
apa: 'Grebenshchikov, S., Gupta, A., Lopes, N. P., Popeea, C., & Rybalchenko,
A. (2012). HSF(C): A software verifier based on Horn clauses. In C. Flanagan &
B. König (Eds.), Tools and Algorithms for the Construction and Analysis of
Systems (Vol. 7214, pp. 549–551). Berlin, Heidelberg: Springer. https://doi.org/10.1007/978-3-642-28756-5_46'
chicago: 'Grebenshchikov, Sergey, Ashutosh Gupta, Nuno P. Lopes, Corneliu Popeea,
and Andrey Rybalchenko. “HSF(C): A Software Verifier Based on Horn Clauses.” In
Tools and Algorithms for the Construction and Analysis of Systems, edited
by Cormac Flanagan and Barbara König, 7214:549–51. LNCS. Berlin, Heidelberg: Springer,
2012. https://doi.org/10.1007/978-3-642-28756-5_46.'
ieee: 'S. Grebenshchikov, A. Gupta, N. P. Lopes, C. Popeea, and A. Rybalchenko,
“HSF(C): A software verifier based on Horn clauses,” in Tools and Algorithms
for the Construction and Analysis of Systems, Tallinn, Estonia, 2012, vol.
7214, pp. 549–551.'
ista: 'Grebenshchikov S, Gupta A, Lopes NP, Popeea C, Rybalchenko A. 2012. HSF(C):
A software verifier based on Horn clauses. Tools and Algorithms for the Construction
and Analysis of Systems. TACAS: Tools and Algorithms for the Construction and
Analysis of SystemsLNCS, LNCS, vol. 7214, 549–551.'
mla: 'Grebenshchikov, Sergey, et al. “HSF(C): A Software Verifier Based on Horn
Clauses.” Tools and Algorithms for the Construction and Analysis of Systems,
edited by Cormac Flanagan and Barbara König, vol. 7214, Springer, 2012, pp. 549–51,
doi:10.1007/978-3-642-28756-5_46.'
short: S. Grebenshchikov, A. Gupta, N.P. Lopes, C. Popeea, A. Rybalchenko, in:,
C. Flanagan, B. König (Eds.), Tools and Algorithms for the Construction and Analysis
of Systems, Springer, Berlin, Heidelberg, 2012, pp. 549–551.
conference:
end_date: 2012-04-01
location: Tallinn, Estonia
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2012-03-24
date_created: 2022-03-21T08:03:30Z
date_published: 2012-04-01T00:00:00Z
date_updated: 2023-09-05T14:09:54Z
day: '01'
department:
- _id: ToHe
doi: 10.1007/978-3-642-28756-5_46
editor:
- first_name: Cormac
full_name: Flanagan, Cormac
last_name: Flanagan
- first_name: Barbara
full_name: König, Barbara
last_name: König
intvolume: ' 7214'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1007/978-3-642-28756-5_46
month: '04'
oa: 1
oa_version: Published Version
page: 549-551
place: Berlin, Heidelberg
publication: Tools and Algorithms for the Construction and Analysis of Systems
publication_identifier:
eisbn:
- '9783642287565'
eissn:
- 1611-3349
isbn:
- '9783642287558'
issn:
- 0302-9743
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: 'HSF(C): A software verifier based on Horn clauses'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 7214
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
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
date_created: 2018-12-11T11:55:25Z
date_published: 2012-09-01T00:00:00Z
date_updated: 2021-01-12T06:54:58Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-33027-8_13
ec_funded: 1
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
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
date_created: 2018-12-11T11:55:25Z
date_published: 2012-03-01T00:00:00Z
date_updated: 2021-01-12T06:54:58Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-642-34047-5_20
ec_funded: 1
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7549
year: '2012'
...
---
_id: '2263'
abstract:
- lang: eng
text: Nestin-cre transgenic mice have been widely used to direct recombination to
neural stem cells (NSCs) and intermediate neural progenitor cells (NPCs). Here
we report that a readily utilized, and the only commercially available, Nestin-cre
line is insufficient for directing recombination in early embryonic NSCs and NPCs.
Analysis of recombination efficiency in multiple cre-dependent reporters and a
genetic mosaic line revealed consistent temporal and spatial patterns of recombination
in NSCs and NPCs. For comparison we utilized a knock-in Emx1cre line and found
robust recombination in NSCs and NPCs in ventricular and subventricular zones
of the cerebral cortices as early as embryonic day 12.5. In addition we found
that the rate of Nestin-cre driven recombination only reaches sufficiently high
levels in NSCs and NPCs during late embryonic and early postnatal periods. These
findings are important when commercially available cre lines are considered for
directing recombination to embryonic NSCs and NPCs.
author:
- first_name: Huixuan
full_name: Liang, Huixuan
last_name: Liang
- first_name: Simon
full_name: Hippenmeyer, Simon
id: 37B36620-F248-11E8-B48F-1D18A9856A87
last_name: Hippenmeyer
orcid: 0000-0003-2279-1061
- first_name: H.
full_name: Ghashghaei, H.
last_name: Ghashghaei
citation:
ama: Liang H, Hippenmeyer S, Ghashghaei H. A Nestin-cre transgenic mouse is insufficient
for recombination in early embryonic neural progenitors. Biology open.
2012;1(12):1200-1203. doi:10.1242/bio.20122287
apa: Liang, H., Hippenmeyer, S., & Ghashghaei, H. (2012). A Nestin-cre transgenic
mouse is insufficient for recombination in early embryonic neural progenitors.
Biology Open. The Company of Biologists. https://doi.org/10.1242/bio.20122287
chicago: Liang, Huixuan, Simon Hippenmeyer, and H. Ghashghaei. “A Nestin-Cre Transgenic
Mouse Is Insufficient for Recombination in Early Embryonic Neural Progenitors.”
Biology Open. The Company of Biologists, 2012. https://doi.org/10.1242/bio.20122287.
ieee: H. Liang, S. Hippenmeyer, and H. Ghashghaei, “A Nestin-cre transgenic mouse
is insufficient for recombination in early embryonic neural progenitors,” Biology
open, vol. 1, no. 12. The Company of Biologists, pp. 1200–1203, 2012.
ista: Liang H, Hippenmeyer S, Ghashghaei H. 2012. A Nestin-cre transgenic mouse
is insufficient for recombination in early embryonic neural progenitors. Biology
open. 1(12), 1200–1203.
mla: Liang, Huixuan, et al. “A Nestin-Cre Transgenic Mouse Is Insufficient for Recombination
in Early Embryonic Neural Progenitors.” Biology Open, vol. 1, no. 12, The
Company of Biologists, 2012, pp. 1200–03, doi:10.1242/bio.20122287.
short: H. Liang, S. Hippenmeyer, H. Ghashghaei, Biology Open 1 (2012) 1200–1203.
date_created: 2018-12-11T11:56:38Z
date_published: 2012-12-15T00:00:00Z
date_updated: 2021-01-12T06:56:23Z
day: '15'
ddc:
- '576'
department:
- _id: SiHi
doi: 10.1242/bio.20122287
file:
- access_level: open_access
checksum: 605a1800b81227848c361fd6ba7d22ba
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:09Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4990'
file_name: IST-2015-387-v1+1_1200.full.pdf
file_size: 726695
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 1'
issue: '12'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '12'
oa: 1
oa_version: Published Version
page: 1200 - 1203
publication: Biology open
publication_status: published
publisher: The Company of Biologists
publist_id: '4682'
pubrep_id: '387'
quality_controlled: '1'
scopus_import: 1
status: public
title: A Nestin-cre transgenic mouse is insufficient for recombination in early embryonic
neural progenitors
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 1
year: '2012'
...
---
_id: '2302'
abstract:
- lang: eng
text: 'We introduce propagation models (PMs), a formalism able to express several
kinds of equations that describe the behavior of biochemical reaction networks.
Furthermore, we introduce the propagation abstract data type (PADT), which separates
concerns regarding different numerical algorithms for the transient analysis of
biochemical reaction networks from concerns regarding their implementation, thus
allowing for portable and efficient solutions. The state of a propagation abstract
data type is given by a vector that assigns mass values to a set of nodes, and
its (next) operator propagates mass values through this set of nodes. We propose
an approximate implementation of the (next) operator, based on threshold abstraction,
which propagates only "significant" mass values and thus achieves a
compromise between efficiency and accuracy. Finally, we give three use cases for
propagation models: the chemical master equation (CME), the reaction rate equation
(RRE), and a hybrid method that combines these two equations. These three applications
use propagation models in order to propagate probabilities and/or expected values
and variances of the model''s variables.'
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: Maria
full_name: Mateescu, Maria
id: 3B43276C-F248-11E8-B48F-1D18A9856A87
last_name: Mateescu
citation:
ama: Henzinger TA, Mateescu M. The propagation approach for computing biochemical
reaction networks. IEEE ACM Transactions on Computational Biology and Bioinformatics.
2012;10(2):310-322. doi:10.1109/TCBB.2012.91
apa: Henzinger, T. A., & Mateescu, M. (2012). The propagation approach for computing
biochemical reaction networks. IEEE ACM Transactions on Computational Biology
and Bioinformatics. IEEE. https://doi.org/10.1109/TCBB.2012.91
chicago: Henzinger, Thomas A, and Maria Mateescu. “The Propagation Approach for
Computing Biochemical Reaction Networks.” IEEE ACM Transactions on Computational
Biology and Bioinformatics. IEEE, 2012. https://doi.org/10.1109/TCBB.2012.91.
ieee: T. A. Henzinger and M. Mateescu, “The propagation approach for computing biochemical
reaction networks,” IEEE ACM Transactions on Computational Biology and Bioinformatics,
vol. 10, no. 2. IEEE, pp. 310–322, 2012.
ista: Henzinger TA, Mateescu M. 2012. The propagation approach for computing biochemical
reaction networks. IEEE ACM Transactions on Computational Biology and Bioinformatics.
10(2), 310–322.
mla: Henzinger, Thomas A., and Maria Mateescu. “The Propagation Approach for Computing
Biochemical Reaction Networks.” IEEE ACM Transactions on Computational Biology
and Bioinformatics, vol. 10, no. 2, IEEE, 2012, pp. 310–22, doi:10.1109/TCBB.2012.91.
short: T.A. Henzinger, M. Mateescu, IEEE ACM Transactions on Computational Biology
and Bioinformatics 10 (2012) 310–322.
date_created: 2018-12-11T11:56:52Z
date_published: 2012-07-03T00:00:00Z
date_updated: 2021-01-12T06:56:38Z
day: '03'
department:
- _id: ToHe
- _id: CaGu
doi: 10.1109/TCBB.2012.91
ec_funded: 1
external_id:
pmid:
- '22778152'
intvolume: ' 10'
issue: '2'
language:
- iso: eng
month: '07'
oa_version: None
page: 310 - 322
pmid: 1
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
publication: IEEE ACM Transactions on Computational Biology and Bioinformatics
publication_status: published
publisher: IEEE
publist_id: '4625'
quality_controlled: '1'
scopus_import: 1
status: public
title: The propagation approach for computing biochemical reaction networks
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10
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 '
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. European Mathematical Society.
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. European Mathematical Society,
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. European Mathematical
Society, 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, European Mathematical
Society, 2012, pp. 321–28, doi:10.4171/JST/31.
short: R. Seiringer, Journal of Spectral Theory 2 (2012) 321–328.
date_created: 2018-12-11T11:56:58Z
date_published: 2012-06-24T00:00:00Z
date_updated: 2021-01-12T06:56:44Z
day: '24'
department:
- _id: RoSe
doi: 10.4171/JST/31
intvolume: ' 2'
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: European Mathematical Society
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 2
year: '2012'
...
---
_id: '2411'
abstract:
- lang: eng
text: The kingdom of fungi provides model organisms for biotechnology, cell biology,
genetics, and life sciences in general. Only when their phylogenetic relationships
are stably resolved, can individual results from fungal research be integrated
into a holistic picture of biology. However, and despite recent progress, many
deep relationships within the fungi remain unclear. Here, we present the first
phylogenomic study of an entire eukaryotic kingdom that uses a consistency criterion
to strengthen phylogenetic conclusions. We reason that branches (splits) recovered
with independent data and different tree reconstruction methods are likely to
reflect true evolutionary relationships. Two complementary phylogenomic data sets
based on 99 fungal genomes and 109 fungal expressed sequence tag (EST) sets analyzed
with four different tree reconstruction methods shed light from different angles
on the fungal tree of life. Eleven additional data sets address specifically the
phylogenetic position of Blastocladiomycota, Ustilaginomycotina, and Dothideomycetes,
respectively. The combined evidence from the resulting trees supports the deep-level
stability of the fungal groups toward a comprehensive natural system of the fungi.
In addition, our analysis reveals methodologically interesting aspects. Enrichment
for EST encoded data-a common practice in phylogenomic analyses-introduces a strong
bias toward slowly evolving and functionally correlated genes. Consequently, the
generalization of phylogenomic data sets as collections of randomly selected genes
cannot be taken for granted. A thorough characterization of the data to assess
possible influences on the tree reconstruction should therefore become a standard
in phylogenomic analyses.
author:
- first_name: Ingo
full_name: Ebersberger, Ingo
last_name: Ebersberger
- first_name: Ricardo
full_name: De Matos Simoes, Ricardo
last_name: De Matos Simoes
- first_name: Anne
full_name: Kupczok, Anne
id: 2BB22BC2-F248-11E8-B48F-1D18A9856A87
last_name: Kupczok
- first_name: Matthias
full_name: Gube, Matthias
last_name: Gube
- first_name: Erika
full_name: Kothe, Erika
last_name: Kothe
- first_name: Kerstin
full_name: Voigt, Kerstin
last_name: Voigt
- first_name: Arndt
full_name: Von Haeseler, Arndt
last_name: Von Haeseler
citation:
ama: Ebersberger I, De Matos Simoes R, Kupczok A, et al. A consistent phylogenetic
backbone for the fungi. Molecular Biology and Evolution. 2012;29(5):1319-1334.
doi:10.1093/molbev/msr285
apa: Ebersberger, I., De Matos Simoes, R., Kupczok, A., Gube, M., Kothe, E., Voigt,
K., & Von Haeseler, A. (2012). A consistent phylogenetic backbone for the
fungi. Molecular Biology and Evolution. Oxford University Press. https://doi.org/10.1093/molbev/msr285
chicago: Ebersberger, Ingo, Ricardo De Matos Simoes, Anne Kupczok, Matthias Gube,
Erika Kothe, Kerstin Voigt, and Arndt Von Haeseler. “A Consistent Phylogenetic
Backbone for the Fungi.” Molecular Biology and Evolution. Oxford University
Press, 2012. https://doi.org/10.1093/molbev/msr285.
ieee: I. Ebersberger et al., “A consistent phylogenetic backbone for the
fungi,” Molecular Biology and Evolution, vol. 29, no. 5. Oxford University
Press, pp. 1319–1334, 2012.
ista: Ebersberger I, De Matos Simoes R, Kupczok A, Gube M, Kothe E, Voigt K, Von
Haeseler A. 2012. A consistent phylogenetic backbone for the fungi. Molecular
Biology and Evolution. 29(5), 1319–1334.
mla: Ebersberger, Ingo, et al. “A Consistent Phylogenetic Backbone for the Fungi.”
Molecular Biology and Evolution, vol. 29, no. 5, Oxford University Press,
2012, pp. 1319–34, doi:10.1093/molbev/msr285.
short: I. Ebersberger, R. De Matos Simoes, A. Kupczok, M. Gube, E. Kothe, K. Voigt,
A. Von Haeseler, Molecular Biology and Evolution 29 (2012) 1319–1334.
date_created: 2018-12-11T11:57:30Z
date_published: 2012-05-01T00:00:00Z
date_updated: 2021-01-12T06:57:19Z
day: '01'
ddc:
- '570'
- '576'
department:
- _id: JoBo
doi: 10.1093/molbev/msr285
file:
- access_level: open_access
checksum: d565dcac27d1736c0c378ea6fcf22d69
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:30Z
date_updated: 2020-07-14T12:45:40Z
file_id: '5013'
file_name: IST-2015-384-v1+1_Mol_Biol_Evol-2012-Ebersberger-1319-34.pdf
file_size: 754922
relation: main_file
file_date_updated: 2020-07-14T12:45:40Z
has_accepted_license: '1'
intvolume: ' 29'
issue: '5'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '05'
oa: 1
oa_version: Published Version
page: 1319 - 1334
publication: Molecular Biology and Evolution
publication_status: published
publisher: Oxford University Press
publist_id: '4515'
pubrep_id: '384'
quality_controlled: '1'
scopus_import: 1
status: public
title: A consistent phylogenetic backbone for the fungi
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2012'
...
---
_id: '493'
abstract:
- lang: eng
text: 'The BCI competition IV stands in the tradition of prior BCI competitions
that aim to provide high quality neuroscientific data for open access to the scientific
community. As experienced already in prior competitions not only scientists from
the narrow field of BCI compete, but scholars with a broad variety of backgrounds
and nationalities. They include high specialists as well as students.The goals
of all BCI competitions have always been to challenge with respect to novel paradigms
and complex data. We report on the following challenges: (1) asynchronous data,
(2) synthetic, (3) multi-class continuous data, (4) sessionto-session transfer,
(5) directionally modulated MEG, (6) finger movements recorded by ECoG. As after
past competitions, our hope is that winning entries may enhance the analysis methods
of future BCIs.'
acknowledgement: "The studies were in part or completely supported by the Bundesministerium
für Bildung und Forschung (BMBF), Fkz 01IB001A, 01GQ0850, by the German Science
Foundation (DFG, contract MU 987/3-2), by the European ICT Programme Projects FP7-224631
and 216886, the World Class University Program through the National Research Foundation
of Korea funded by the Ministry of Education, Science, and Technology (Grant R31-10008),
the US Army Research Office [W911NF-08-1-0216 (Gerwin Schalk) and W911NF-07-1-0415
(Gerwin Schalk)] and the NIH [EB006356 (Gerwin Schalk) and EB000856 (Gerwin Schalk),
the WIN-Kolleg of the Heidelberg Academy of Sciences and Humanities, German Federal
Ministry of Education and Research grants 01GQ0420, 01GQ0761, 01GQ0762, and 01GQ0830,
German Research Foundation grants 550/B5 and C6, and by a scholarship from the German
National Academic Foundation. This paper only reflects the authors’ views and funding
agencies are not liable for any use that may be made of the information contained
herein.\r\n"
article_number: '55'
author:
- first_name: Michael
full_name: Tangermann, Michael
last_name: Tangermann
- first_name: Klaus
full_name: Müller, Klaus
last_name: Müller
- first_name: Ad
full_name: Aertsen, Ad
last_name: Aertsen
- first_name: Niels
full_name: Birbaumer, Niels
last_name: Birbaumer
- first_name: Christoph
full_name: Braun, Christoph
last_name: Braun
- first_name: Clemens
full_name: Brunner, Clemens
last_name: Brunner
- first_name: Robert
full_name: Leeb, Robert
last_name: Leeb
- first_name: Carsten
full_name: Mehring, Carsten
last_name: Mehring
- first_name: Kai
full_name: Miller, Kai
last_name: Miller
- first_name: Gernot
full_name: Müller Putz, Gernot
last_name: Müller Putz
- first_name: Guido
full_name: Nolte, Guido
last_name: Nolte
- first_name: Gert
full_name: Pfurtscheller, Gert
last_name: Pfurtscheller
- first_name: Hubert
full_name: Preissl, Hubert
last_name: Preissl
- first_name: Gerwin
full_name: Schalk, Gerwin
last_name: Schalk
- 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: Carmen
full_name: Vidaurre, Carmen
last_name: Vidaurre
- first_name: Stephan
full_name: Waldert, Stephan
last_name: Waldert
- first_name: Benjamin
full_name: Blankertz, Benjamin
last_name: Blankertz
citation:
ama: Tangermann M, Müller K, Aertsen A, et al. Review of the BCI competition IV.
Frontiers in Neuroscience. 2012;6. doi:10.3389/fnins.2012.00055
apa: Tangermann, M., Müller, K., Aertsen, A., Birbaumer, N., Braun, C., Brunner,
C., … Blankertz, B. (2012). Review of the BCI competition IV. Frontiers in
Neuroscience. Frontiers Research Foundation. https://doi.org/10.3389/fnins.2012.00055
chicago: Tangermann, Michael, Klaus Müller, Ad Aertsen, Niels Birbaumer, Christoph
Braun, Clemens Brunner, Robert Leeb, et al. “Review of the BCI Competition IV.”
Frontiers in Neuroscience. Frontiers Research Foundation, 2012. https://doi.org/10.3389/fnins.2012.00055.
ieee: M. Tangermann et al., “Review of the BCI competition IV,” Frontiers
in Neuroscience, vol. 6. Frontiers Research Foundation, 2012.
ista: Tangermann M, Müller K, Aertsen A, Birbaumer N, Braun C, Brunner C, Leeb R,
Mehring C, Miller K, Müller Putz G, Nolte G, Pfurtscheller G, Preissl H, Schalk
G, Schlögl A, Vidaurre C, Waldert S, Blankertz B. 2012. Review of the BCI competition
IV. Frontiers in Neuroscience. 6, 55.
mla: Tangermann, Michael, et al. “Review of the BCI Competition IV.” Frontiers
in Neuroscience, vol. 6, 55, Frontiers Research Foundation, 2012, doi:10.3389/fnins.2012.00055.
short: M. Tangermann, K. Müller, A. Aertsen, N. Birbaumer, C. Braun, C. Brunner,
R. Leeb, C. Mehring, K. Miller, G. Müller Putz, G. Nolte, G. Pfurtscheller, H.
Preissl, G. Schalk, A. Schlögl, C. Vidaurre, S. Waldert, B. Blankertz, Frontiers
in Neuroscience 6 (2012).
date_created: 2018-12-11T11:46:46Z
date_published: 2012-07-13T00:00:00Z
date_updated: 2021-01-12T08:01:03Z
day: '13'
ddc:
- '004'
department:
- _id: ScienComp
- _id: PeJo
doi: 10.3389/fnins.2012.00055
file:
- access_level: open_access
checksum: 195238221c4b0b0f4035f6f6c16ea17c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:18:34Z
date_updated: 2020-07-14T12:46:35Z
file_id: '5356'
file_name: IST-2018-945-v1+1_2012_Schloegl_Review_of.pdf
file_size: 2693701
relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: ' 6'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
publication: Frontiers in Neuroscience
publication_status: published
publisher: Frontiers Research Foundation
publist_id: '7327'
pubrep_id: '945'
quality_controlled: '1'
scopus_import: 1
status: public
title: Review of the BCI competition IV
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 6
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'
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 (TOCL). 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 (TOCL). 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 (TOCL). 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 (TOCL), 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 (TOCL). 13(4), 29.
mla: Boker, Udi, and Orna Kupferman. “Translating to Co-Büchi Made Tight, Unified,
and Useful.” ACM Transactions on Computational Logic (TOCL), vol. 13, no.
4, 29, ACM, 2012, doi:10.1145/2362355.2362357.
short: U. Boker, O. Kupferman, ACM Transactions on Computational Logic (TOCL) 13
(2012).
date_created: 2018-12-11T11:46:47Z
date_published: 2012-10-01T00:00:00Z
date_updated: 2021-01-12T08:01:03Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2362355.2362357
intvolume: ' 13'
issue: '4'
language:
- iso: eng
month: '10'
oa_version: None
publication: ACM Transactions on Computational Logic (TOCL)
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2012'
...
---
_id: '495'
abstract:
- lang: eng
text: An automaton with advice is a finite state automaton which has access to an
additional fixed infinite string called an advice tape. We refine the Myhill-Nerode
theorem to characterize the languages of finite strings that are accepted by automata
with advice. We do the same for tree automata with advice.
alternative_title:
- EPTCS
author:
- first_name: Alex
full_name: Kruckman, Alex
last_name: Kruckman
- first_name: Sasha
full_name: Rubin, Sasha
id: 2EC51194-F248-11E8-B48F-1D18A9856A87
last_name: Rubin
- first_name: John
full_name: Sheridan, John
last_name: Sheridan
- first_name: Ben
full_name: Zax, Ben
last_name: Zax
citation:
ama: 'Kruckman A, Rubin S, Sheridan J, Zax B. A Myhill Nerode theorem for automata
with advice. In: Proceedings GandALF 2012. Vol 96. Open Publishing Association;
2012:238-246. doi:10.4204/EPTCS.96.18'
apa: 'Kruckman, A., Rubin, S., Sheridan, J., & Zax, B. (2012). A Myhill Nerode
theorem for automata with advice. In Proceedings GandALF 2012 (Vol. 96,
pp. 238–246). Napoli, Italy: Open Publishing Association. https://doi.org/10.4204/EPTCS.96.18'
chicago: Kruckman, Alex, Sasha Rubin, John Sheridan, and Ben Zax. “A Myhill Nerode
Theorem for Automata with Advice.” In Proceedings GandALF 2012, 96:238–46.
Open Publishing Association, 2012. https://doi.org/10.4204/EPTCS.96.18.
ieee: A. Kruckman, S. Rubin, J. Sheridan, and B. Zax, “A Myhill Nerode theorem for
automata with advice,” in Proceedings GandALF 2012, Napoli, Italy, 2012,
vol. 96, pp. 238–246.
ista: 'Kruckman A, Rubin S, Sheridan J, Zax B. 2012. A Myhill Nerode theorem for
automata with advice. Proceedings GandALF 2012. GandALF: Games, Automata, Logics
and Formal Verification, EPTCS, vol. 96, 238–246.'
mla: Kruckman, Alex, et al. “A Myhill Nerode Theorem for Automata with Advice.”
Proceedings GandALF 2012, vol. 96, Open Publishing Association, 2012, pp.
238–46, doi:10.4204/EPTCS.96.18.
short: A. Kruckman, S. Rubin, J. Sheridan, B. Zax, in:, Proceedings GandALF 2012,
Open Publishing Association, 2012, pp. 238–246.
conference:
end_date: 2012-09-08
location: Napoli, Italy
name: 'GandALF: Games, Automata, Logics and Formal Verification'
start_date: 2012-09-06
date_created: 2018-12-11T11:46:47Z
date_published: 2012-10-07T00:00:00Z
date_updated: 2021-01-12T08:01:04Z
day: '07'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4204/EPTCS.96.18
ec_funded: 1
file:
- access_level: open_access
checksum: 56277f95edc9d531fa3bdc5f9579fda8
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:15:31Z
date_updated: 2020-07-14T12:46:35Z
file_id: '5152'
file_name: IST-2018-944-v1+1_2012_Rubin_A_Myhill.pdf
file_size: 97736
relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: ' 96'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 238 - 246
project:
- _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'
publication: Proceedings GandALF 2012
publication_status: published
publisher: Open Publishing Association
publist_id: '7325'
pubrep_id: '944'
quality_controlled: '1'
scopus_import: 1
status: public
title: A Myhill Nerode theorem for automata with advice
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 96
year: '2012'
...
---
_id: '496'
abstract:
- lang: eng
text: 'We study the expressive power of logical interpretations on the class of
scattered trees, namely those with countably many infinite branches. Scattered
trees can be thought of as the tree analogue of scattered linear orders. Every
scattered tree has an ordinal rank that reflects the structure of its infinite
branches. We prove, roughly, that trees and orders of large rank cannot be interpreted
in scattered trees of small rank. We consider a quite general notion of interpretation:
each element of the interpreted structure is represented by a set of tuples of
subsets of the interpreting tree. Our trees are countable, not necessarily finitely
branching, and may have finitely many unary predicates as labellings. We also
show how to replace injective set-interpretations in (not necessarily scattered)
trees by ''finitary'' set-interpretations.'
alternative_title:
- LICS
article_number: '6280474'
author:
- first_name: Alexander
full_name: Rabinovich, Alexander
last_name: Rabinovich
- first_name: Sasha
full_name: Rubin, Sasha
id: 2EC51194-F248-11E8-B48F-1D18A9856A87
last_name: Rubin
citation:
ama: 'Rabinovich A, Rubin S. Interpretations in trees with countably many branches.
In: IEEE; 2012. doi:10.1109/LICS.2012.65'
apa: 'Rabinovich, A., & Rubin, S. (2012). Interpretations in trees with countably
many branches. Presented at the LICS: Symposium on Logic in Computer Science,
Dubrovnik, Croatia: IEEE. https://doi.org/10.1109/LICS.2012.65'
chicago: Rabinovich, Alexander, and Sasha Rubin. “Interpretations in Trees with
Countably Many Branches.” IEEE, 2012. https://doi.org/10.1109/LICS.2012.65.
ieee: 'A. Rabinovich and S. Rubin, “Interpretations in trees with countably many
branches,” presented at the LICS: Symposium on Logic in Computer Science, Dubrovnik,
Croatia, 2012.'
ista: 'Rabinovich A, Rubin S. 2012. Interpretations in trees with countably many
branches. LICS: Symposium on Logic in Computer Science, LICS, , 6280474.'
mla: Rabinovich, Alexander, and Sasha Rubin. Interpretations in Trees with Countably
Many Branches. 6280474, IEEE, 2012, doi:10.1109/LICS.2012.65.
short: A. Rabinovich, S. Rubin, in:, IEEE, 2012.
conference:
end_date: 2012-06-28
location: Dubrovnik, Croatia
name: 'LICS: Symposium on Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T11:46:47Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2021-01-12T08:01:05Z
day: '01'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.65
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arise.or.at/pubpdf/Interpretations_in_Trees_with_Countably_Many_Branches.pdf
month: '01'
oa: 1
oa_version: Preprint
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication_status: published
publisher: IEEE
publist_id: '7324'
quality_controlled: '1'
scopus_import: 1
status: public
title: Interpretations in trees with countably many branches
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '497'
abstract:
- lang: eng
text: 'One central issue in the formal design and analysis of reactive systems is
the notion of refinement that asks whether all behaviors of the implementation
is allowed by the specification. The local interpretation of behavior leads to
the notion of simulation. Alternating transition systems (ATSs) provide a general
model for composite reactive systems, and the simulation relation for ATSs is
known as alternating simulation. The simulation relation for fair transition systems
is called fair simulation. In this work our main contributions are as follows:
(1) We present an improved algorithm for fair simulation with Büchi fairness constraints;
our algorithm requires O(n 3·m) time as compared to the previous known O(n 6)-time
algorithm, where n is the number of states and m is the number of transitions.
(2) We present a game based algorithm for alternating simulation that requires
O(m2)-time as compared to the previous known O((n·m)2)-time algorithm, where n
is the number of states and m is the size of transition relation. (3) We present
an iterative algorithm for alternating simulation that matches the time complexity
of the game based algorithm, but is more space efficient than the game based algorithm.
© Krishnendu Chatterjee, Siddhesh Chaubal, and Pritish Kamath.'
alternative_title:
- LIPIcs
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Siddhesh
full_name: Chaubal, Siddhesh
last_name: Chaubal
- first_name: Pritish
full_name: Kamath, Pritish
last_name: Kamath
citation:
ama: 'Chatterjee K, Chaubal S, Kamath P. Faster algorithms for alternating refinement
relations. In: Vol 16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2012:167-182.
doi:10.4230/LIPIcs.CSL.2012.167'
apa: 'Chatterjee, K., Chaubal, S., & Kamath, P. (2012). Faster algorithms for
alternating refinement relations (Vol. 16, pp. 167–182). Presented at the EACSL:
European Association for Computer Science Logic, Fontainebleau, France: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2012.167'
chicago: Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. “Faster Algorithms
for Alternating Refinement Relations,” 16:167–82. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2012. https://doi.org/10.4230/LIPIcs.CSL.2012.167.
ieee: 'K. Chatterjee, S. Chaubal, and P. Kamath, “Faster algorithms for alternating
refinement relations,” presented at the EACSL: European Association for Computer
Science Logic, Fontainebleau, France, 2012, vol. 16, pp. 167–182.'
ista: 'Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating
refinement relations. EACSL: European Association for Computer Science Logic,
LIPIcs, vol. 16, 167–182.'
mla: Chatterjee, Krishnendu, et al. Faster Algorithms for Alternating Refinement
Relations. Vol. 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2012,
pp. 167–82, doi:10.4230/LIPIcs.CSL.2012.167.
short: K. Chatterjee, S. Chaubal, P. Kamath, in:, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2012, pp. 167–182.
conference:
end_date: 2012-09-06
location: Fontainebleau, France
name: 'EACSL: European Association for Computer Science Logic'
start_date: 2012-09-03
date_created: 2018-12-11T11:46:48Z
date_published: 2012-09-01T00:00:00Z
date_updated: 2023-02-23T12:23:32Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.CSL.2012.167
ec_funded: 1
file:
- access_level: open_access
checksum: f1b0dd99240800db2d7dbf9b5131fe5e
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:50Z
date_updated: 2020-07-14T12:46:35Z
file_id: '4712'
file_name: IST-2018-943-v1+1_2012_Chatterjee_Faster_Algorithms.pdf
file_size: 471236
relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: ' 16'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: 167 - 182
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: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7323'
pubrep_id: '943'
quality_controlled: '1'
related_material:
record:
- id: '5378'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Faster algorithms for alternating refinement relations
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 16
year: '2012'
...
---
_id: '498'
abstract:
- lang: eng
text: Understanding patterns and correlates of local adaptation in heterogeneous
landscapes can provide important information in the selection of appropriate seed
sources for restoration. We assessed the extent of local adaptation of fitness
components in 12 population pairs of the perennial herb Rutidosis leptorrhynchoides
(Asteraceae) and examined whether spatial scale (0.7-600 km), environmental distance,
quantitative (QST) and neutral (FST) genetic differentiation, and size of the
local and foreign populations could predict patterns of adaptive differentiation.
Local adaptation varied among populations and fitness components. Including all
population pairs, local adaptation was observed for seedling survival, but not
for biomass, while foreign genotype advantage was observed for reproduction (number
of inflorescences). Among population pairs, local adaptation increased with QST
and local population size for biomass. QST was associated with environmental distance,
suggesting ecological selection for phenotypic divergence. However, low FST and
variation in population structure in small populations demonstrates the interaction
of gene flow and drift in constraining local adaptation in R. leptorrhynchoides.
Our study indicates that for species in heterogeneous landscapes, collecting seed
from large populations from similar environments to candidate sites is likely
to provide the most appropriate seed sources for restoration.
acknowledgement: "We thank Graham Pickup, David Steer, Linda Broadhurst, Lan Li and
Carole Elliott for technical assistance. The New\r\nSouth Wales Department of Environment
and Climate Change, ACT Parks, Conservation and Lands and the\r\nDepartment of Sustainability
and Environment in Victoria provided permits for seed and soil collection. We thank\r\nSpencer
C. H. Barrett for comments that improved the quality of the manuscript.\r\n"
author:
- first_name: Melinda
full_name: Pickup, Melinda
id: 2C78037E-F248-11E8-B48F-1D18A9856A87
last_name: Pickup
orcid: 0000-0001-6118-0541
- first_name: David
full_name: Field, David
id: 419049E2-F248-11E8-B48F-1D18A9856A87
last_name: Field
orcid: 0000-0002-4014-8478
- first_name: David
full_name: Rowell, David
last_name: Rowell
- first_name: Andrew
full_name: Young, Andrew
last_name: Young
citation:
ama: 'Pickup M, Field D, Rowell D, Young A. Predicting local adaptation in fragmented
plant populations: Implications for restoration genetics. Evolutionary Applications.
2012;5(8):913-924. doi:10.1111/j.1752-4571.2012.00284.x'
apa: 'Pickup, M., Field, D., Rowell, D., & Young, A. (2012). Predicting local
adaptation in fragmented plant populations: Implications for restoration genetics.
Evolutionary Applications. Wiley-Blackwell. https://doi.org/10.1111/j.1752-4571.2012.00284.x'
chicago: 'Pickup, Melinda, David Field, David Rowell, and Andrew Young. “Predicting
Local Adaptation in Fragmented Plant Populations: Implications for Restoration
Genetics.” Evolutionary Applications. Wiley-Blackwell, 2012. https://doi.org/10.1111/j.1752-4571.2012.00284.x.'
ieee: 'M. Pickup, D. Field, D. Rowell, and A. Young, “Predicting local adaptation
in fragmented plant populations: Implications for restoration genetics,” Evolutionary
Applications, vol. 5, no. 8. Wiley-Blackwell, pp. 913–924, 2012.'
ista: 'Pickup M, Field D, Rowell D, Young A. 2012. Predicting local adaptation in
fragmented plant populations: Implications for restoration genetics. Evolutionary
Applications. 5(8), 913–924.'
mla: 'Pickup, Melinda, et al. “Predicting Local Adaptation in Fragmented Plant Populations:
Implications for Restoration Genetics.” Evolutionary Applications, vol.
5, no. 8, Wiley-Blackwell, 2012, pp. 913–24, doi:10.1111/j.1752-4571.2012.00284.x.'
short: M. Pickup, D. Field, D. Rowell, A. Young, Evolutionary Applications 5 (2012)
913–924.
date_created: 2018-12-11T11:46:48Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2021-01-12T08:01:06Z
day: '01'
ddc:
- '576'
department:
- _id: NiBa
doi: 10.1111/j.1752-4571.2012.00284.x
file:
- access_level: open_access
checksum: 233007138606aca5a2f75f7ae1742f43
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:33Z
date_updated: 2020-07-14T12:46:35Z
file_id: '4821'
file_name: IST-2018-942-v1+1_Pickup_et_al-2012-Evolutionary_Applications.pdf
file_size: 396136
relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: ' 5'
issue: '8'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: 913 - 924
publication: Evolutionary Applications
publication_status: published
publisher: Wiley-Blackwell
publist_id: '7322'
pubrep_id: '942'
quality_controlled: '1'
status: public
title: 'Predicting local adaptation in fragmented plant populations: Implications
for restoration genetics'
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2012'
...
---
_id: '506'
article_processing_charge: No
article_type: original
author:
- first_name: Michael K
full_name: Sixt, Michael K
id: 41E9FBEA-F248-11E8-B48F-1D18A9856A87
last_name: Sixt
orcid: 0000-0002-6620-9179
citation:
ama: 'Sixt MK. Cell migration: Fibroblasts find a new way to get ahead. Journal
of Cell Biology. 2012;197(3):347-349. doi:10.1083/jcb.201204039'
apa: 'Sixt, M. K. (2012). Cell migration: Fibroblasts find a new way to get ahead.
Journal of Cell Biology. Rockefeller University Press. https://doi.org/10.1083/jcb.201204039'
chicago: 'Sixt, Michael K. “Cell Migration: Fibroblasts Find a New Way to Get Ahead.”
Journal of Cell Biology. Rockefeller University Press, 2012. https://doi.org/10.1083/jcb.201204039.'
ieee: 'M. K. Sixt, “Cell migration: Fibroblasts find a new way to get ahead,” Journal
of Cell Biology, vol. 197, no. 3. Rockefeller University Press, pp. 347–349,
2012.'
ista: 'Sixt MK. 2012. Cell migration: Fibroblasts find a new way to get ahead. Journal
of Cell Biology. 197(3), 347–349.'
mla: 'Sixt, Michael K. “Cell Migration: Fibroblasts Find a New Way to Get Ahead.”
Journal of Cell Biology, vol. 197, no. 3, Rockefeller University Press,
2012, pp. 347–49, doi:10.1083/jcb.201204039.'
short: M.K. Sixt, Journal of Cell Biology 197 (2012) 347–349.
date_created: 2018-12-11T11:46:51Z
date_published: 2012-04-30T00:00:00Z
date_updated: 2021-01-12T08:01:11Z
day: '30'
ddc:
- '570'
department:
- _id: MiSi
doi: 10.1083/jcb.201204039
file:
- access_level: open_access
checksum: 45c02be33ebd99fc3077d60b9c90bdfa
content_type: application/pdf
creator: kschuh
date_created: 2019-02-12T09:03:09Z
date_updated: 2020-07-14T12:46:36Z
file_id: '5957'
file_name: 2012_CellBiology_Sixt.pdf
file_size: 986566
relation: main_file
file_date_updated: 2020-07-14T12:46:36Z
has_accepted_license: '1'
intvolume: ' 197'
issue: '3'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 347 - 349
publication: Journal of Cell Biology
publication_status: published
publisher: Rockefeller University Press
publist_id: '7314'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Cell migration: Fibroblasts find a new way to get ahead'
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 197
year: '2012'
...