---
_id: '480'
abstract:
- lang: eng
text: Graph games provide the foundation for modeling and synthesizing reactive
processes. In the synthesis of stochastic reactive processes, the traditional
model is perfect-information stochastic games, where some transitions of the game
graph are controlled by two adversarial players, and the other transitions are
executed probabilistically. We consider such games where the objective is the
conjunction of several quantitative objectives (specified as mean-payoff conditions),
which we refer to as generalized mean-payoff objectives. The basic decision problem
asks for the existence of a finite-memory strategy for a player that ensures the
generalized mean-payoff objective be satisfied with a desired probability against
all strategies of the opponent. A special case of the decision problem is the
almost-sure problem where the desired probability is 1. Previous results presented
a semi-decision procedure for -approximations of the almost-sure problem. In this
work, we show that both the almost-sure problem as well as the general basic decision
problem are coNP-complete, significantly improving the previous results. Moreover,
we show that in the case of 1-player stochastic games, randomized memoryless strategies
are sufficient and the problem can be solved in polynomial time. In contrast,
in two-player stochastic games, we show that even with randomized strategies exponential
memory is required in general, and present a matching exponential upper bound.
We also study the basic decision problem with infinite-memory strategies and present
computational complexity results for the problem. Our results are relevant in
the synthesis of stochastic reactive systems with multiple quantitative requirements.
alternative_title:
- Proceedings Symposium on Logic in Computer Science
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. Perfect-information stochastic games with generalized
mean-payoff objectives. In: Vol 05-08-July-2016. IEEE; 2016:247-256. doi:10.1145/2933575.2934513'
apa: 'Chatterjee, K., & Doyen, L. (2016). Perfect-information stochastic games
with generalized mean-payoff objectives (Vol. 05-08-July-2016, pp. 247–256). Presented
at the LICS: Logic in Computer Science, New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2934513'
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Perfect-Information Stochastic
Games with Generalized Mean-Payoff Objectives,” 05-08-July-2016:247–56. IEEE,
2016. https://doi.org/10.1145/2933575.2934513.
ieee: 'K. Chatterjee and L. Doyen, “Perfect-information stochastic games with generalized
mean-payoff objectives,” presented at the LICS: Logic in Computer Science, New
York, NY, USA, 2016, vol. 05-08-July-2016, pp. 247–256.'
ista: 'Chatterjee K, Doyen L. 2016. Perfect-information stochastic games with generalized
mean-payoff objectives. LICS: Logic in Computer Science, Proceedings Symposium
on Logic in Computer Science, vol. 05-08-July-2016, 247–256.'
mla: Chatterjee, Krishnendu, and Laurent Doyen. Perfect-Information Stochastic
Games with Generalized Mean-Payoff Objectives. Vol. 05-08-July-2016, IEEE,
2016, pp. 247–56, doi:10.1145/2933575.2934513.
short: K. Chatterjee, L. Doyen, in:, IEEE, 2016, pp. 247–256.
conference:
end_date: 2016-07-08
location: New York, NY, USA
name: 'LICS: Logic in Computer Science'
start_date: 2016-07-05
date_created: 2018-12-11T11:46:42Z
date_published: 2016-07-05T00:00:00Z
date_updated: 2025-09-22T14:22:08Z
day: '05'
department:
- _id: KrCh
doi: 10.1145/2933575.2934513
ec_funded: 1
external_id:
arxiv:
- '1604.06376'
isi:
- '000387609200025'
fulldoi: https://doi.org/10.1145/2933575.2934513
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1604.06376
month: '07'
oa: 1
oa_version: Preprint
page: 247 - 256
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'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided Verification
publication_status: published
publisher: IEEE
publist_id: '7340'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Perfect-information stochastic games with generalized mean-payoff objectives
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 05-08-July-2016
year: '2016'
...
---
_id: '482'
abstract:
- lang: eng
text: Nonlinear electro-optical conversion of microwave radiation into the optical
telecommunication band is achieved within a crystalline whispering gallery mode
resonator, reaching 0.1% photon number conversion efficiency with MHz bandwidth.
alternative_title:
- Optics InfoBase Conference Papers
article_processing_charge: No
author:
- first_name: Alfredo
full_name: Rueda, Alfredo
last_name: Rueda
- first_name: Florian
full_name: Sedlmeir, Florian
last_name: Sedlmeir
- first_name: Michele
full_name: Collodo, Michele
last_name: Collodo
- first_name: Ulrich
full_name: Vogl, Ulrich
last_name: Vogl
- first_name: Birgit
full_name: Stiller, Birgit
last_name: Stiller
- first_name: Gerhard
full_name: Schunk, Gerhard
last_name: Schunk
- first_name: Dmitry
full_name: Strekalov, Dmitry
last_name: Strekalov
- first_name: Christoph
full_name: Marquardt, Christoph
last_name: Marquardt
- first_name: Johannes M
full_name: Fink, Johannes M
id: 4B591CBA-F248-11E8-B48F-1D18A9856A87
last_name: Fink
orcid: 0000-0001-8112-028X
- first_name: Oskar
full_name: Painter, Oskar
last_name: Painter
- first_name: Gerd
full_name: Leuchs, Gerd
last_name: Leuchs
- first_name: Harald
full_name: Schwefel, Harald
last_name: Schwefel
citation:
ama: 'Rueda A, Sedlmeir F, Collodo M, et al. Nonlinear single sideband microwave
to optical conversion using an electro-optic WGM-resonator. In: Optica Publishing
Group; 2016. doi:10.1364/NP.2016.NTh3A.6'
apa: 'Rueda, A., Sedlmeir, F., Collodo, M., Vogl, U., Stiller, B., Schunk, G., …
Schwefel, H. (2016). Nonlinear single sideband microwave to optical conversion
using an electro-optic WGM-resonator. Presented at the NP: Nonlinear Photonics,
Sydney, Australia: Optica Publishing Group. https://doi.org/10.1364/NP.2016.NTh3A.6'
chicago: Rueda, Alfredo, Florian Sedlmeir, Michele Collodo, Ulrich Vogl, Birgit
Stiller, Gerhard Schunk, Dmitry Strekalov, et al. “Nonlinear Single Sideband Microwave
to Optical Conversion Using an Electro-Optic WGM-Resonator.” Optica Publishing
Group, 2016. https://doi.org/10.1364/NP.2016.NTh3A.6.
ieee: 'A. Rueda et al., “Nonlinear single sideband microwave to optical conversion
using an electro-optic WGM-resonator,” presented at the NP: Nonlinear Photonics,
Sydney, Australia, 2016.'
ista: 'Rueda A, Sedlmeir F, Collodo M, Vogl U, Stiller B, Schunk G, Strekalov D,
Marquardt C, Fink JM, Painter O, Leuchs G, Schwefel H. 2016. Nonlinear single
sideband microwave to optical conversion using an electro-optic WGM-resonator.
NP: Nonlinear Photonics, Optics InfoBase Conference Papers, .'
mla: Rueda, Alfredo, et al. Nonlinear Single Sideband Microwave to Optical Conversion
Using an Electro-Optic WGM-Resonator. Optica Publishing Group, 2016, doi:10.1364/NP.2016.NTh3A.6.
short: A. Rueda, F. Sedlmeir, M. Collodo, U. Vogl, B. Stiller, G. Schunk, D. Strekalov,
C. Marquardt, J.M. Fink, O. Painter, G. Leuchs, H. Schwefel, in:, Optica Publishing
Group, 2016.
conference:
end_date: 2016-09-08
location: Sydney, Australia
name: 'NP: Nonlinear Photonics'
start_date: 2016-09-05
date_created: 2018-12-11T11:46:43Z
date_published: 2016-08-29T00:00:00Z
date_updated: 2023-10-17T12:16:43Z
day: '29'
department:
- _id: JoFi
doi: 10.1364/NP.2016.NTh3A.6
fulldoi: https://doi.org/10.1364/NP.2016.NTh3A.6
language:
- iso: eng
month: '08'
oa_version: None
publication_status: published
publisher: Optica Publishing Group
publist_id: '7339'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Nonlinear single sideband microwave to optical conversion using an electro-optic
WGM-resonator
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '510'
abstract:
- lang: eng
text: 'The CLE (CLAVATA3/Embryo Surrounding Region-related) peptides are small secreted
signaling peptides that are primarily involved in the regulation of stem cell
homeostasis in different plant meristems. Particularly, the characterization of
the CLE41-PXY/TDR signaling pathway has greatly advanced our understanding on
the potential roles of CLE peptides in vascular development and wood formation.
Nevertheless, our knowledge on this gene family in a tree species is limited.
In a recent study, we reported on a systematically investigation of the CLE gene
family in Populus trichocarpa . The potential roles of PtCLE genes were studied
by comparative analysis and transcriptional pro fi ling. Among fi fty PtCLE members,
many PtCLE proteins share identical CLE motifs or contain the same CLE motif as
that of AtCLEs, while PtCLE genes exhibited either comparable or distinct expression
patterns comparing to their Arabidopsis counterparts. These fi ndings indicate
the existence of both functional conservation and functional divergence between
PtCLEs and their AtCLE orthologues. Our results provide valuable resources for
future functional investigations of these critical signaling molecules in woody
plants. '
acknowledgement: 'We are grateful to Dr. Long (Laboratoire de Reproduction et Developpement
des Plantes,CNRS,INRA,ENSLyon,UCBL,Universite de Lyon,France)for critical reading
of the article. Work in our group is supported by the National Natural Science Foundation
of China (31271575; 31200902), the Fundamental Research Funds for the Central Univ
ersities (GK201103005), the Specialized Research Fund for the Doctoral Program of
Higher Education from the Ministry of Education of China (20120202120009), the Scientific
Research Foundation for the Returned Overseas Chinese Scholars, State Education
Ministry, and the Natural Science Basic Research Plan in Shaanxi Province of China
(2014JM3064). '
article_number: e1191734
article_processing_charge: No
author:
- first_name: Zhijun
full_name: Liu, Zhijun
last_name: Liu
- first_name: 'Nan'
full_name: Yang, Nan
last_name: Yang
- first_name: Yanting
full_name: Lv, Yanting
last_name: Lv
- first_name: Lixia
full_name: Pan, Lixia
last_name: Pan
- first_name: Shuo
full_name: Lv, Shuo
last_name: Lv
- first_name: Huibin
full_name: Han, Huibin
id: 31435098-F248-11E8-B48F-1D18A9856A87
last_name: Han
- first_name: Guodong
full_name: Wang, Guodong
last_name: Wang
citation:
ama: Liu Z, Yang N, Lv Y, et al. The CLE gene family in Populus trichocarpa. Plant
Signaling & Behavior. 2016;11(6). doi:10.1080/15592324.2016.1191734
apa: Liu, Z., Yang, N., Lv, Y., Pan, L., Lv, S., Han, H., & Wang, G. (2016).
The CLE gene family in Populus trichocarpa. Plant Signaling & Behavior.
Taylor & Francis. https://doi.org/10.1080/15592324.2016.1191734
chicago: Liu, Zhijun, Nan Yang, Yanting Lv, Lixia Pan, Shuo Lv, Huibin Han, and
Guodong Wang. “The CLE Gene Family in Populus Trichocarpa.” Plant Signaling
& Behavior. Taylor & Francis, 2016. https://doi.org/10.1080/15592324.2016.1191734.
ieee: Z. Liu et al., “The CLE gene family in Populus trichocarpa,” Plant
Signaling & Behavior, vol. 11, no. 6. Taylor & Francis, 2016.
ista: Liu Z, Yang N, Lv Y, Pan L, Lv S, Han H, Wang G. 2016. The CLE gene family
in Populus trichocarpa. Plant Signaling & Behavior. 11(6), e1191734.
mla: Liu, Zhijun, et al. “The CLE Gene Family in Populus Trichocarpa.” Plant
Signaling & Behavior, vol. 11, no. 6, e1191734, Taylor & Francis,
2016, doi:10.1080/15592324.2016.1191734.
short: Z. Liu, N. Yang, Y. Lv, L. Pan, S. Lv, H. Han, G. Wang, Plant Signaling &
Behavior 11 (2016).
date_created: 2018-12-11T11:46:53Z
date_published: 2016-06-02T00:00:00Z
date_updated: 2025-09-22T14:21:19Z
day: '02'
department:
- _id: JiFr
doi: 10.1080/15592324.2016.1191734
external_id:
isi:
- '000378740600025'
fulldoi: https://doi.org/10.1080/15592324.2016.1191734
intvolume: ' 11'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4973754/
month: '06'
oa: 1
oa_version: Submitted Version
publication: Plant Signaling & Behavior
publication_status: published
publisher: Taylor & Francis
publist_id: '7308'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The CLE gene family in Populus trichocarpa
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 11
year: '2016'
...
---
_id: '5445'
abstract:
- lang: eng
text: 'We consider the quantitative analysis problem for interprocedural control-flow
graphs (ICFGs). The input consists of an ICFG, a positive weight function that
assigns every transition a positive integer-valued number, and a labelling of
the transitions (events) as good, bad, and neutral events. The weight function
assigns to each transition a numerical value that represents ameasure of how good
or bad an event is. The quantitative analysis problem asks whether there is a
run of the ICFG where the ratio of the sum of the numerical weights of good events
versus the sum of weights of bad events in the long-run is at least a given threshold
(or equivalently, to compute the maximal ratio among all valid paths in the ICFG).
The quantitative analysis problem for ICFGs can be solved in polynomial time,
and we present an efficient and practical algorithm for the problem. We show that
several problems relevant for static program analysis, such as estimating the
worst-case execution time of a program or the average energy consumption of a
mobile application, can be modeled in our framework. We have implemented our algorithm
as a tool in the Java Soot framework. We demonstrate the effectiveness of our
approach with two case studies. First, we show that our framework provides a sound
approach (no false positives) for the analysis of inefficiently-used containers.
Second, we show that our approach can also be used for static profiling of programs
which reasons about methods that are frequently invoked. Our experimental results
show that our tool scales to relatively large benchmarks, and discovers relevant
and useful information that can be used to optimize performance of the programs. '
alternative_title:
- IST Austria Technical Report
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Yaron
full_name: Velner, Yaron
last_name: Velner
citation:
ama: Chatterjee K, Pavlogiannis A, Velner Y. Quantitative Interprocedural Analysis.
IST Austria; 2016. doi:10.15479/AT:IST-2016-523-v1-1
apa: Chatterjee, K., Pavlogiannis, A., & Velner, Y. (2016). Quantitative
interprocedural analysis. IST Austria. https://doi.org/10.15479/AT:IST-2016-523-v1-1
chicago: Chatterjee, Krishnendu, Andreas Pavlogiannis, and Yaron Velner. Quantitative
Interprocedural Analysis. IST Austria, 2016. https://doi.org/10.15479/AT:IST-2016-523-v1-1.
ieee: K. Chatterjee, A. Pavlogiannis, and Y. Velner, Quantitative interprocedural
analysis. IST Austria, 2016.
ista: Chatterjee K, Pavlogiannis A, Velner Y. 2016. Quantitative interprocedural
analysis, IST Austria, 33p.
mla: Chatterjee, Krishnendu, et al. Quantitative Interprocedural Analysis.
IST Austria, 2016, doi:10.15479/AT:IST-2016-523-v1-1.
short: K. Chatterjee, A. Pavlogiannis, Y. Velner, Quantitative Interprocedural Analysis,
IST Austria, 2016.
date_created: 2018-12-12T11:39:22Z
date_published: 2016-03-31T00:00:00Z
date_updated: 2025-04-15T08:11:41Z
day: '31'
ddc:
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2016-523-v1-1
file:
- access_level: open_access
checksum: cef516fa091925b5868813e355268fb4
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:52Z
date_updated: 2020-07-14T12:46:58Z
file_id: '5513'
file_name: IST-2016-523-v1+1_main.pdf
file_size: 1012204
relation: main_file
file_date_updated: 2020-07-14T12:46:58Z
fulldoi: https://doi.org/10.15479/AT:IST-2016-523-v1-1
has_accepted_license: '1'
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '523'
related_material:
record:
- id: '1604'
relation: later_version
status: public
status: public
title: Quantitative interprocedural analysis
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5446'
abstract:
- lang: eng
text: "We study the problem of developing efficient approaches for proving termination
of recursive programs with one-dimensional arrays. Ranking functions serve as
a sound and complete approach for proving termination of non-recursive programs
without array operations. First, we generalize ranking functions to the notion
of measure functions, and prove that measure functions (i) provide a sound method
to prove termination of recursive programs (with one-dimensional arrays), and
(ii) is both sound and complete over recursive programs without array operations.
Our second contribution is the synthesis of measure functions of specific forms
in polynomial time. More precisely, we prove that (i) polynomial measure functions
over recursive programs can be synthesized in polynomial time through Farkas’
Lemma and Handelman’s Theorem, and (ii) measure functions involving logarithm
and exponentiation can be synthesized in polynomial time through abstraction of
logarithmic or exponential terms and Handelman’s Theorem. A key application of
our method is the worst-case analysis of recursive programs. While previous methods
obtain worst-case polynomial bounds of the form O(n^k), where k is an integer,
our polynomial time methods can synthesize bounds of the form O(n log n), as well
as O(n^x), where x is not an integer. We show the applicability of our automated
technique to obtain worst-case complexity of classical recursive algorithms such
as (i) Merge-Sort, the divideand-\r\nconquer algorithm for the Closest-Pair problem,
where we obtain O(n log n) worst-case bound, and (ii) Karatsuba’s algorithm for
polynomial multiplication and Strassen’s algorithm for matrix multiplication,
where we obtain O(n^x) bound, where x is not an integer and close to the best-known
bounds for the respective algorithms. Finally, we present experimental results
to demonstrate the\r\neffectiveness of our approach."
alternative_title:
- IST Austria Technical Report
author:
- first_name: '1'
full_name: Anonymous, 1
last_name: Anonymous
- first_name: '2'
full_name: Anonymous, 2
last_name: Anonymous
- first_name: '3'
full_name: Anonymous, 3
last_name: Anonymous
citation:
ama: Anonymous 1, Anonymous 2, Anonymous 3. Termination and Worst-Case Analysis
of Recursive Programs. IST Austria; 2016.
apa: Anonymous, 1, Anonymous, 2, & Anonymous, 3. (2016). Termination and
worst-case analysis of recursive programs. IST Austria.
chicago: Anonymous, 1, 2 Anonymous, and 3 Anonymous. Termination and Worst-Case
Analysis of Recursive Programs. IST Austria, 2016.
ieee: 1 Anonymous, 2 Anonymous, and 3 Anonymous, Termination and worst-case analysis
of recursive programs. IST Austria, 2016.
ista: Anonymous 1, Anonymous 2, Anonymous 3. 2016. Termination and worst-case analysis
of recursive programs, IST Austria, 26p.
mla: Anonymous, 1, et al. Termination and Worst-Case Analysis of Recursive Programs.
IST Austria, 2016.
short: 1 Anonymous, 2 Anonymous, 3 Anonymous, Termination and Worst-Case Analysis
of Recursive Programs, IST Austria, 2016.
date_created: 2018-12-12T11:39:23Z
date_published: 2016-07-15T00:00:00Z
date_updated: 2020-07-14T23:05:05Z
day: '15'
ddc:
- '000'
file:
- access_level: open_access
checksum: 689069a7abbb34b21516164cbee9e0df
content_type: application/pdf
creator: dernst
date_created: 2019-05-10T13:27:24Z
date_updated: 2020-07-14T12:46:58Z
file_id: '6403'
file_name: popl2017a.pdf
file_size: 686241
relation: main_file
- access_level: closed
checksum: fc08022bfbaac07bac047a9407c0bbb3
content_type: text/plain
creator: dernst
date_created: 2019-05-10T13:27:31Z
date_updated: 2020-07-14T12:46:58Z
file_id: '6404'
file_name: author_names.txt
file_size: 258
relation: main_file
file_date_updated: 2020-07-14T12:46:58Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '26'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '618'
status: public
title: Termination and worst-case analysis of recursive programs
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5447'
abstract:
- lang: eng
text: "We consider the problem of developing automated techniques to aid the average-case
complexity analysis of programs. Several classical textbook algorithms have quite
efficient average-case complexity, whereas the corresponding worst-case bounds
are either inefficient (e.g., QUICK-SORT), or completely ineffective (e.g., COUPONCOLLECTOR).
Since the main focus of average-case analysis is to obtain efficient bounds, we
consider bounds that are either logarithmic,\r\nlinear, or almost-linear (O(log
n), O(n), O(n · log n),\r\nrespectively, where n represents the size of the input).
Our main contribution is a sound approach for deriving such average-case bounds
for randomized recursive programs. Our approach is efficient (a simple linear-time
algorithm), and it is based on (a) the analysis of recurrence relations induced
by randomized algorithms, and (b) a guess-and-check technique. Our approach can
infer the asymptotically optimal average-case bounds for classical randomized
algorithms, including RANDOMIZED-SEARCH, QUICKSORT, QUICK-SELECT, COUPON-COLLECTOR,
where the worstcase\r\nbounds are either inefficient (such as linear as compared
to logarithmic of average-case, or quadratic as compared to linear or almost-linear
of average-case), or ineffective. We have implemented our approach, and the experimental
results show that we obtain the bounds efficiently for various classical algorithms."
alternative_title:
- IST Austria Technical Report
author:
- first_name: '1'
full_name: Anonymous, 1
last_name: Anonymous
- first_name: '2'
full_name: Anonymous, 2
last_name: Anonymous
- first_name: '3'
full_name: Anonymous, 3
last_name: Anonymous
citation:
ama: 'Anonymous 1, Anonymous 2, Anonymous 3. Average-Case Analysis of Programs:
Automated Recurrence Analysis for Almost-Linear Bounds. IST Austria; 2016.'
apa: 'Anonymous, 1, Anonymous, 2, & Anonymous, 3. (2016). Average-case analysis
of programs: Automated recurrence analysis for almost-linear bounds. IST Austria.'
chicago: 'Anonymous, 1, 2 Anonymous, and 3 Anonymous. Average-Case Analysis of
Programs: Automated Recurrence Analysis for Almost-Linear Bounds. IST Austria,
2016.'
ieee: '1 Anonymous, 2 Anonymous, and 3 Anonymous, Average-case analysis of programs:
Automated recurrence analysis for almost-linear bounds. IST Austria, 2016.'
ista: 'Anonymous 1, Anonymous 2, Anonymous 3. 2016. Average-case analysis of programs:
Automated recurrence analysis for almost-linear bounds, IST Austria, 20p.'
mla: 'Anonymous, 1, et al. Average-Case Analysis of Programs: Automated Recurrence
Analysis for Almost-Linear Bounds. IST Austria, 2016.'
short: '1 Anonymous, 2 Anonymous, 3 Anonymous, Average-Case Analysis of Programs:
Automated Recurrence Analysis for Almost-Linear Bounds, IST Austria, 2016.'
date_created: 2018-12-12T11:39:23Z
date_published: 2016-07-15T00:00:00Z
date_updated: 2020-07-14T23:05:06Z
day: '15'
ddc:
- '000'
file:
- access_level: closed
checksum: cf53cdb6d092e68db0b4a0a1506ef8fb
content_type: text/plain
creator: dernst
date_created: 2019-05-10T13:32:16Z
date_updated: 2020-07-14T12:46:58Z
file_id: '6406'
file_name: listofauthors.txt
file_size: 281
relation: main_file
- access_level: open_access
checksum: 7bdd94ba13aa0dec9c46887fcf13870b
content_type: application/pdf
creator: dernst
date_created: 2019-05-10T13:32:16Z
date_updated: 2020-07-14T12:46:58Z
file_id: '6407'
file_name: popl2017b.pdf
file_size: 563642
relation: main_file
file_date_updated: 2020-07-14T12:46:58Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '619'
status: public
title: 'Average-case analysis of programs: Automated recurrence analysis for almost-linear
bounds'
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5448'
abstract:
- lang: eng
text: "We present a new dynamic partial-order reduction method for stateless model
checking of concurrent programs. A common approach for exploring program behaviors
relies on enumerating the traces of the program, without storing the visited states
(aka stateless exploration). As the number of distinct traces grows exponentially,
dynamic partial-order reduction (DPOR) techniques have been successfully used
to partition the space of traces into equivalence classes (Mazurkiewicz partitioning),
with the goal of exploring only few representative traces from each class.\r\nWe
introduce a new equivalence on traces under sequential consistency semantics,
which we call the observation equivalence. Two traces are observationally equivalent
if every read event observes the same write event in both traces. While the traditional
Mazurkiewicz equivalence is control-centric, our new definition is data-centric.
We show that our observation equivalence is coarser than the Mazurkiewicz equivalence,
and in many cases even exponentially coarser. We devise a DPOR exploration of
the trace space, called data-centric DPOR, based on the observation equivalence.\r\n1.
For acyclic architectures, our algorithm is guaranteed to explore exactly one
representative trace from each observation class, while spending polynomial time
per class. Hence, our algorithm is optimal wrt the observation equivalence, and
in several cases explores exponentially fewer traces than any enumerative method
based on the Mazurkiewicz equivalence.\r\n2. For cyclic architectures, we consider
an equivalence between traces which is finer than the observation equivalence;
but coarser than the Mazurkiewicz equivalence, and in some cases is exponentially
coarser. Our data-centric DPOR algorithm remains optimal under this trace equivalence.
\r\nFinally, we perform a basic experimental comparison between the existing Mazurkiewicz-based
DPOR and our data-centric DPOR on a set of academic benchmarks. Our results show
a significant reduction in both running time and the number of explored equivalence
classes."
alternative_title:
- IST Austria Technical Report
arxiv: 1
author:
- first_name: '1'
full_name: Anonymous, 1
last_name: Anonymous
- first_name: '2'
full_name: Anonymous, 2
last_name: Anonymous
- first_name: '3'
full_name: Anonymous, 3
last_name: Anonymous
- first_name: '4'
full_name: Anonymous, 4
last_name: Anonymous
citation:
ama: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. Data-Centric Dynamic
Partial Order Reduction. IST Austria; 2016.
apa: Anonymous, 1, Anonymous, 2, Anonymous, 3, & Anonymous, 4. (2016). Data-centric
dynamic partial order reduction. IST Austria.
chicago: Anonymous, 1, 2 Anonymous, 3 Anonymous, and 4 Anonymous. Data-Centric
Dynamic Partial Order Reduction. IST Austria, 2016.
ieee: 1 Anonymous, 2 Anonymous, 3 Anonymous, and 4 Anonymous, Data-centric dynamic
partial order reduction. IST Austria, 2016.
ista: Anonymous 1, Anonymous 2, Anonymous 3, Anonymous 4. 2016. Data-centric dynamic
partial order reduction, IST Austria, 20p.
mla: Anonymous, 1, et al. Data-Centric Dynamic Partial Order Reduction. IST
Austria, 2016.
short: 1 Anonymous, 2 Anonymous, 3 Anonymous, 4 Anonymous, Data-Centric Dynamic
Partial Order Reduction, IST Austria, 2016.
date_created: 2018-12-12T11:39:23Z
date_published: 2016-07-15T00:00:00Z
date_updated: 2025-05-20T09:45:08Z
day: '15'
ddc:
- '000'
external_id:
arxiv:
- '1610.01188'
file:
- access_level: open_access
checksum: 1d69252d66bcdf782615ddfb911d2957
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:45Z
date_updated: 2020-07-14T12:46:58Z
file_id: '5506'
file_name: IST-2016-620-v1+1_main.pdf
file_size: 538881
relation: main_file
- access_level: closed
checksum: deabb0eb8f237cae4f9542b28b0b6eb2
content_type: text/plain
creator: dernst
date_created: 2019-05-10T13:30:40Z
date_updated: 2020-07-14T12:46:58Z
file_id: '6405'
file_name: authornames.txt
file_size: 121
relation: main_file
file_date_updated: 2020-07-14T12:46:58Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '20'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '620'
related_material:
record:
- id: '5456'
relation: later_version
status: public
- id: '10417'
relation: later_version
status: public
status: public
title: Data-centric dynamic partial order reduction
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5449'
abstract:
- lang: eng
text: "The fixation probability is the probability that a new mutant introduced
in a homogeneous population eventually takes over the entire population.\r\nThe
fixation probability is a fundamental quantity of natural selection, and known
to depend on the population structure.\r\nAmplifiers of natural selection are
population structures which increase the fixation probability of advantageous
mutants, as compared to the baseline case of well-mixed populations. In this work
we focus on symmetric population structures represented as undirected graphs.
In the regime of undirected graphs, the strongest amplifier known has been the
Star graph, and the existence of undirected graphs with stronger amplification
properties has remained open for over a decade.\r\nIn this work we present the
Comet and Comet-swarm families of undirected graphs. We show that for a range
of fitness values of the mutants, the Comet and Comet-swarm graphs have fixation
probability strictly larger than the fixation probability of the Star graph, for
fixed population size and at the limit of large populations, respectively."
alternative_title:
- IST Austria Technical Report
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: 'Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Amplification on Undirected
Population Structures: Comets Beat Stars. IST Austria; 2016. doi:10.15479/AT:IST-2016-648-v1-1'
apa: 'Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2016). Amplification
on undirected population structures: Comets beat stars. IST Austria. https://doi.org/10.15479/AT:IST-2016-648-v1-1'
chicago: 'Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin
Nowak. Amplification on Undirected Population Structures: Comets Beat Stars.
IST Austria, 2016. https://doi.org/10.15479/AT:IST-2016-648-v1-1.'
ieee: 'A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, Amplification
on undirected population structures: Comets beat stars. IST Austria, 2016.'
ista: 'Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Amplification on
undirected population structures: Comets beat stars, IST Austria, 22p.'
mla: 'Pavlogiannis, Andreas, et al. Amplification on Undirected Population Structures:
Comets Beat Stars. IST Austria, 2016, doi:10.15479/AT:IST-2016-648-v1-1.'
short: 'A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Amplification on Undirected
Population Structures: Comets Beat Stars, IST Austria, 2016.'
date_created: 2018-12-12T11:39:24Z
date_published: 2016-11-09T00:00:00Z
date_updated: 2025-09-18T09:50:09Z
day: '09'
ddc:
- '519'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2016-648-v1-1
file:
- access_level: open_access
checksum: 8345a8c1e7d7f0cd92516d182b7fc59e
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:07Z
date_updated: 2020-07-14T12:46:58Z
file_id: '5529'
file_name: IST-2016-648-v1+1_tr.pdf
file_size: 1264221
relation: main_file
file_date_updated: 2020-07-14T12:46:58Z
fulldoi: https://doi.org/10.15479/AT:IST-2016-648-v1-1
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Updated Version
page: '22'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '648'
related_material:
record:
- id: '512'
relation: later_version
status: public
status: public
title: 'Amplification on undirected population structures: Comets beat stars'
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5451'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Strong Amplifiers of Natural
Selection. IST Austria; 2016. doi:10.15479/AT:IST-2016-728-v1-1
apa: Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2016). Strong
amplifiers of natural selection. IST Austria. https://doi.org/10.15479/AT:IST-2016-728-v1-1
chicago: Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin
Nowak. Strong Amplifiers of Natural Selection. IST Austria, 2016. https://doi.org/10.15479/AT:IST-2016-728-v1-1.
ieee: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, Strong amplifiers
of natural selection. IST Austria, 2016.
ista: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Strong amplifiers
of natural selection, IST Austria, 34p.
mla: Pavlogiannis, Andreas, et al. Strong Amplifiers of Natural Selection.
IST Austria, 2016, doi:10.15479/AT:IST-2016-728-v1-1.
short: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Strong Amplifiers of
Natural Selection, IST Austria, 2016.
date_created: 2018-12-12T11:39:24Z
date_published: 2016-12-30T00:00:00Z
date_updated: 2023-02-23T12:27:05Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2016-728-v1-1
file:
- access_level: open_access
checksum: 7b8bb17c322c0556acba6ac169fa71c1
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:04Z
date_updated: 2020-07-14T12:46:59Z
file_id: '5465'
file_name: IST-2016-728-v1+1_main.pdf
file_size: 1014732
relation: main_file
file_date_updated: 2020-07-14T12:46:59Z
fulldoi: https://doi.org/10.15479/AT:IST-2016-728-v1-1
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '34'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '728'
status: public
title: Strong amplifiers of natural selection
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5452'
alternative_title:
- IST Austria Technical Report
article_processing_charge: No
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Arbitrarily Strong Amplifiers
of Natural Selection. IST Austria; 2016. doi:10.15479/AT:IST-2017-728-v2-1
apa: Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2016). Arbitrarily
strong amplifiers of natural selection. IST Austria. https://doi.org/10.15479/AT:IST-2017-728-v2-1
chicago: Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin
Nowak. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria,
2016. https://doi.org/10.15479/AT:IST-2017-728-v2-1.
ieee: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, Arbitrarily strong
amplifiers of natural selection. IST Austria, 2016.
ista: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Arbitrarily strong
amplifiers of natural selection, IST Austria, 32p.
mla: Pavlogiannis, Andreas, et al. Arbitrarily Strong Amplifiers of Natural Selection.
IST Austria, 2016, doi:10.15479/AT:IST-2017-728-v2-1.
short: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong
Amplifiers of Natural Selection, IST Austria, 2016.
date_created: 2018-12-12T11:39:25Z
date_published: 2016-12-30T00:00:00Z
date_updated: 2025-04-15T07:55:39Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2017-728-v2-1
ec_funded: 1
file:
- access_level: open_access
checksum: 58e895f26c82f560c0f0989bf8b08599
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:52:59Z
date_updated: 2020-07-14T12:46:59Z
file_id: '5460'
file_name: IST-2017-728-v2+1_main.pdf
file_size: 811558
relation: main_file
file_date_updated: 2020-07-14T12:46:59Z
fulldoi: https://doi.org/10.15479/AT:IST-2017-728-v2-1
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '32'
project:
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '750'
related_material:
record:
- id: '5453'
relation: later_version
status: public
- id: '5559'
relation: popular_science
status: public
status: public
title: Arbitrarily strong amplifiers of natural selection
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5453'
alternative_title:
- IST Austria Technical Report
author:
- first_name: Andreas
full_name: Pavlogiannis, Andreas
id: 49704004-F248-11E8-B48F-1D18A9856A87
last_name: Pavlogiannis
orcid: 0000-0002-8943-0722
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Martin
full_name: Nowak, Martin
last_name: Nowak
citation:
ama: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. Arbitrarily Strong Amplifiers
of Natural Selection. IST Austria; 2016. doi:10.15479/AT:IST-2017-749-v3-1
apa: Pavlogiannis, A., Tkadlec, J., Chatterjee, K., & Nowak, M. (2016). Arbitrarily
strong amplifiers of natural selection. IST Austria. https://doi.org/10.15479/AT:IST-2017-749-v3-1
chicago: Pavlogiannis, Andreas, Josef Tkadlec, Krishnendu Chatterjee, and Martin
Nowak. Arbitrarily Strong Amplifiers of Natural Selection. IST Austria,
2016. https://doi.org/10.15479/AT:IST-2017-749-v3-1.
ieee: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, and M. Nowak, Arbitrarily strong
amplifiers of natural selection. IST Austria, 2016.
ista: Pavlogiannis A, Tkadlec J, Chatterjee K, Nowak M. 2016. Arbitrarily strong
amplifiers of natural selection, IST Austria, 34p.
mla: Pavlogiannis, Andreas, et al. Arbitrarily Strong Amplifiers of Natural Selection.
IST Austria, 2016, doi:10.15479/AT:IST-2017-749-v3-1.
short: A. Pavlogiannis, J. Tkadlec, K. Chatterjee, M. Nowak, Arbitrarily Strong
Amplifiers of Natural Selection, IST Austria, 2016.
date_created: 2018-12-12T11:39:25Z
date_published: 2016-12-30T00:00:00Z
date_updated: 2025-04-15T07:55:37Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2017-749-v3-1
file:
- access_level: open_access
checksum: 83b0313dab3bff4bdb6ac38695026fda
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:13Z
date_updated: 2020-07-14T12:46:59Z
file_id: '5474'
file_name: IST-2017-749-v3+1_main.pdf
file_size: 1015647
relation: main_file
file_date_updated: 2020-07-14T12:46:59Z
fulldoi: https://doi.org/10.15479/AT:IST-2017-749-v3-1
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '34'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '755'
related_material:
record:
- id: '5452'
relation: earlier_version
status: public
status: public
title: Arbitrarily strong amplifiers of natural selection
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5550'
abstract:
- lang: eng
text: "We collected flower colour information on species in the tribe Antirrhineae
from taxonomic literature. We also retreived molecular data from GenBank for as
many of these species as possible to estimate phylogenetic relationships among
these taxa. We then used the R package 'diversitree' to examine patterns of evolutionary
transitions between anthocyanin and yellow pigmentation across the phylogeny.\r\n\r\nFor
full details of the methods see:\r\nEllis TJ and Field DL \"Repeated gains in
yellow and anthocyanin pigmentation in flower colour transitions in the Antirrhineae”,
Annals of Botany (in press)"
article_processing_charge: No
author:
- first_name: Thomas
full_name: Ellis, Thomas
id: 3153D6D4-F248-11E8-B48F-1D18A9856A87
last_name: Ellis
orcid: 0000-0002-8511-0254
- first_name: David
full_name: Field, David
id: 419049E2-F248-11E8-B48F-1D18A9856A87
last_name: Field
orcid: 0000-0002-4014-8478
citation:
ama: Ellis T, Field D. Flower colour data and phylogeny (NEXUS) files. 2016. doi:10.15479/AT:ISTA:34
apa: Ellis, T., & Field, D. (2016). Flower colour data and phylogeny (NEXUS)
files. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:34
chicago: Ellis, Thomas, and David Field. “Flower Colour Data and Phylogeny (NEXUS)
Files.” Institute of Science and Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:34.
ieee: T. Ellis and D. Field, “Flower colour data and phylogeny (NEXUS) files.” Institute
of Science and Technology Austria, 2016.
ista: Ellis T, Field D. 2016. Flower colour data and phylogeny (NEXUS) files, Institute
of Science and Technology Austria, 10.15479/AT:ISTA:34.
mla: Ellis, Thomas, and David Field. Flower Colour Data and Phylogeny (NEXUS)
Files. Institute of Science and Technology Austria, 2016, doi:10.15479/AT:ISTA:34.
short: T. Ellis, D. Field, (2016).
datarep_id: '34'
date_created: 2018-12-12T12:31:29Z
date_published: 2016-02-19T00:00:00Z
date_updated: 2025-09-22T07:32:43Z
day: '19'
ddc:
- '576'
department:
- _id: NiBa
doi: 10.15479/AT:ISTA:34
file:
- access_level: open_access
checksum: 950f85b80427d357bfeff09608ba02e9
content_type: application/zip
creator: system
date_created: 2018-12-12T13:02:27Z
date_updated: 2020-07-14T12:47:00Z
file_id: '5594'
file_name: IST-2016-34-v1+1_tellis_flower_colour_data.zip
file_size: 4468543
relation: main_file
file_date_updated: 2020-07-14T12:47:00Z
fulldoi: https://doi.org/10.15479/AT:ISTA:34
has_accepted_license: '1'
license: https://creativecommons.org/publicdomain/zero/1.0/
month: '02'
oa: 1
oa_version: Published Version
publisher: Institute of Science and Technology Austria
publist_id: '5828'
related_material:
record:
- id: '1382'
relation: research_paper
status: public
status: public
title: Flower colour data and phylogeny (NEXUS) files
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5555'
abstract:
- lang: eng
text: This FIJI script calculates the population average of the migration speed
as a function of time of all cells from wide field microscopy movies.
article_processing_charge: No
author:
- first_name: Robert
full_name: Hauschild, Robert
id: 4E01D6B4-F248-11E8-B48F-1D18A9856A87
last_name: Hauschild
orcid: 0000-0001-9843-3522
citation:
ama: Hauschild R. Fiji script to determine average speed and direction of migration
of cells. 2016. doi:10.15479/AT:ISTA:44
apa: Hauschild, R. (2016). Fiji script to determine average speed and direction
of migration of cells. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:44
chicago: Hauschild, Robert. “Fiji Script to Determine Average Speed and Direction
of Migration of Cells.” Institute of Science and Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:44.
ieee: R. Hauschild, “Fiji script to determine average speed and direction of migration
of cells.” Institute of Science and Technology Austria, 2016.
ista: Hauschild R. 2016. Fiji script to determine average speed and direction of
migration of cells, Institute of Science and Technology Austria, 10.15479/AT:ISTA:44.
mla: Hauschild, Robert. Fiji Script to Determine Average Speed and Direction
of Migration of Cells. Institute of Science and Technology Austria, 2016,
doi:10.15479/AT:ISTA:44.
short: R. Hauschild, (2016).
datarep_id: '44'
date_created: 2018-12-12T12:31:31Z
date_published: 2016-07-08T00:00:00Z
date_updated: 2024-02-21T13:50:06Z
day: '08'
ddc:
- '570'
department:
- _id: Bio
doi: 10.15479/AT:ISTA:44
file:
- access_level: open_access
checksum: 9f96cddbcd4ed689f48712ffe234d5e5
content_type: application/zip
creator: system
date_created: 2018-12-12T13:03:03Z
date_updated: 2020-07-14T12:47:02Z
file_id: '5621'
file_name: IST-2016-44-v1+1_migrationAnalyzer.zip
file_size: 20692
relation: main_file
file_date_updated: 2020-07-14T12:47:02Z
fulldoi: https://doi.org/10.15479/AT:ISTA:44
has_accepted_license: '1'
keyword:
- cell migration
- wide field microscopy
- FIJI
month: '07'
oa: 1
oa_version: Published Version
publisher: Institute of Science and Technology Austria
status: public
title: Fiji script to determine average speed and direction of migration of cells
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5556'
abstract:
- lang: eng
text: "MATLAB code and processed datasets available for reproducing the results
in: \r\nLukačišin, M.*, Landon, M.*, Jajoo, R*. (2016) Sequence-Specific Thermodynamic
Properties of Nucleic Acids Influence Both Transcriptional Pausing and Backtracking
in Yeast.\r\n*equal contributions"
article_processing_charge: No
author:
- first_name: Martin
full_name: Lukacisin, Martin
id: 298FFE8C-F248-11E8-B48F-1D18A9856A87
last_name: Lukacisin
orcid: 0000-0001-6549-4177
- first_name: Matthieu
full_name: Landon, Matthieu
last_name: Landon
- first_name: Rishi
full_name: Jajoo, Rishi
last_name: Jajoo
citation:
ama: Lukacisin M, Landon M, Jajoo R. MATLAB analysis code for “Sequence-Specific
Thermodynamic Properties of Nucleic Acids Influence Both Transcriptional Pausing
and Backtracking in Yeast.” 2016. doi:10.15479/AT:ISTA:45
apa: Lukacisin, M., Landon, M., & Jajoo, R. (2016). MATLAB analysis code for
“Sequence-Specific Thermodynamic Properties of Nucleic Acids Influence Both Transcriptional
Pausing and Backtracking in Yeast.” Institute of Science and Technology Austria.
https://doi.org/10.15479/AT:ISTA:45
chicago: Lukacisin, Martin, Matthieu Landon, and Rishi Jajoo. “MATLAB Analysis Code
for ‘Sequence-Specific Thermodynamic Properties of Nucleic Acids Influence Both
Transcriptional Pausing and Backtracking in Yeast.’” Institute of Science and
Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:45.
ieee: M. Lukacisin, M. Landon, and R. Jajoo, “MATLAB analysis code for ‘Sequence-Specific
Thermodynamic Properties of Nucleic Acids Influence Both Transcriptional Pausing
and Backtracking in Yeast.’” Institute of Science and Technology Austria, 2016.
ista: Lukacisin M, Landon M, Jajoo R. 2016. MATLAB analysis code for ‘Sequence-Specific
Thermodynamic Properties of Nucleic Acids Influence Both Transcriptional Pausing
and Backtracking in Yeast’, Institute of Science and Technology Austria, 10.15479/AT:ISTA:45.
mla: Lukacisin, Martin, et al. MATLAB Analysis Code for “Sequence-Specific Thermodynamic
Properties of Nucleic Acids Influence Both Transcriptional Pausing and Backtracking
in Yeast.” Institute of Science and Technology Austria, 2016, doi:10.15479/AT:ISTA:45.
short: M. Lukacisin, M. Landon, R. Jajoo, (2016).
datarep_id: '45'
date_created: 2018-12-12T12:31:31Z
date_published: 2016-08-25T00:00:00Z
date_updated: 2025-07-10T11:49:51Z
day: '25'
ddc:
- '571'
department:
- _id: ToBo
doi: 10.15479/AT:ISTA:45
file:
- access_level: open_access
checksum: ee697f2b1ade4dc14d6ac0334dd832ab
content_type: application/zip
creator: system
date_created: 2018-12-12T13:02:58Z
date_updated: 2020-07-14T12:47:02Z
file_id: '5616'
file_name: IST-2016-45-v1+1_PaperCode.zip
file_size: 296722548
relation: main_file
file_date_updated: 2020-07-14T12:47:02Z
fulldoi: https://doi.org/10.15479/AT:ISTA:45
has_accepted_license: '1'
keyword:
- transcription
- pausing
- backtracking
- polymerase
- RNA
- NET-seq
- nucleosome
- basepairing
license: https://creativecommons.org/licenses/by-sa/4.0/
month: '08'
oa: 1
oa_version: Published Version
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '8431'
relation: used_in_publication
status: deleted
- id: '1029'
relation: research_paper
status: public
status: public
title: MATLAB analysis code for 'Sequence-Specific Thermodynamic Properties of Nucleic
Acids Influence Both Transcriptional Pausing and Backtracking in Yeast'
tmp:
image: /images/cc_by_sa.png
legal_code_url: https://creativecommons.org/licenses/by-sa/4.0/legalcode
name: Creative Commons Attribution-ShareAlike 4.0 International Public License (CC
BY-SA 4.0)
short: CC BY-SA (4.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '5557'
abstract:
- lang: eng
text: "Small synthetic discrete tomography problems.\r\nSizes are 32x32, 64z64 and
256x256.\r\nProjection angles are 2, 4, and 6.\r\nNumber of labels are 3 and 5."
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
citation:
ama: Swoboda P. Synthetic discrete tomography problems. 2016. doi:10.15479/AT:ISTA:46
apa: Swoboda, P. (2016). Synthetic discrete tomography problems. Institute of Science
and Technology Austria. https://doi.org/10.15479/AT:ISTA:46
chicago: Swoboda, Paul. “Synthetic Discrete Tomography Problems.” Institute of Science
and Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:46.
ieee: P. Swoboda, “Synthetic discrete tomography problems.” Institute of Science
and Technology Austria, 2016.
ista: Swoboda P. 2016. Synthetic discrete tomography problems, Institute of Science
and Technology Austria, 10.15479/AT:ISTA:46.
mla: Swoboda, Paul. Synthetic Discrete Tomography Problems. Institute of
Science and Technology Austria, 2016, doi:10.15479/AT:ISTA:46.
short: P. Swoboda, (2016).
contributor:
- contributor_type: data_collector
first_name: Jan
last_name: Kuske
datarep_id: '46'
date_created: 2018-12-12T12:31:31Z
date_published: 2016-09-20T00:00:00Z
date_updated: 2024-02-21T13:50:21Z
day: '20'
ddc:
- '006'
department:
- _id: VlKo
doi: 10.15479/AT:ISTA:46
file:
- access_level: open_access
checksum: aa5a16a0dc888da7186fb8fc45e88439
content_type: application/zip
creator: system
date_created: 2018-12-12T13:05:19Z
date_updated: 2020-07-14T12:47:02Z
file_id: '5645'
file_name: IST-2016-46-v1+1_discrete_tomography_synthetic.zip
file_size: 36058401
relation: main_file
file_date_updated: 2020-07-14T12:47:02Z
fulldoi: https://doi.org/10.15479/AT:ISTA:46
has_accepted_license: '1'
keyword:
- discrete tomography
month: '09'
oa: 1
oa_version: Published Version
publisher: Institute of Science and Technology Austria
status: public
title: Synthetic discrete tomography problems
tmp:
image: /images/cc_0.png
legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode
name: Creative Commons Public Domain Dedication (CC0 1.0)
short: CC0 (1.0)
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '5749'
abstract:
- lang: eng
text: Parasitism creates selection for resistance mechanisms in host populations
and is hypothesized to promote increased host evolvability. However, the influence
of these traits on host evolution when parasites are no longer present is unclear.
We used experimental evolution and whole-genome sequencing of Escherichia coli
to determine the effects of past and present exposure to parasitic viruses (phages)
on the spread of mutator alleles, resistance, and bacterial competitive fitness.
We found that mutator alleles spread rapidly during adaptation to any of four
different phage species, and this pattern was even more pronounced with multiple
phages present simultaneously. However, hypermutability did not detectably accelerate
adaptation in the absence of phages and recovery of fitness costs associated with
resistance. Several lineages evolved phage resistance through elevated mucoidy,
and during subsequent evolution in phage-free conditions they rapidly reverted
to nonmucoid, phage-susceptible phenotypes. Genome sequencing revealed that this
phenotypic reversion was achieved by additional genetic changes rather than by
genotypic reversion of the initial resistance mutations. Insertion sequence (IS)
elements played a key role in both the acquisition of resistance and adaptation
in the absence of parasites; unlike single nucleotide polymorphisms, IS insertions
were not more frequent in mutator lineages. Our results provide a genetic explanation
for rapid reversion of mucoidy, a phenotype observed in other bacterial species
including human pathogens. Moreover, this demonstrates that the types of genetic
change underlying adaptation to fitness costs, and consequently the impact of
evolvability mechanisms such as increased point-mutation rates, depend critically
on the mechanism of resistance.
acknowledgement: The authors thank three anonymous reviewers and the editor for helpful
comments on the manuscript, as well as Dominique Schneider for feedback on an earlier
draft, Jenna Gallie for lytic λ and Julien Capelle for T5 and T6. This work was
supported by the Swiss National Science Foundation (PZ00P3_148255 to A.H.) and an
EU Marie Curie PEOPLE Postdoctoral Fellowship for Career Development (FP7-PEOPLE-2012-IEF-331824
to S.W.).
article_processing_charge: No
article_type: original
author:
- first_name: Sébastien
full_name: Wielgoss, Sébastien
last_name: Wielgoss
- first_name: Tobias
full_name: Bergmiller, Tobias
id: 2C471CFA-F248-11E8-B48F-1D18A9856A87
last_name: Bergmiller
orcid: 0000-0001-5396-4346
- first_name: Anna M.
full_name: Bischofberger, Anna M.
last_name: Bischofberger
- first_name: Alex R.
full_name: Hall, Alex R.
last_name: Hall
citation:
ama: Wielgoss S, Bergmiller T, Bischofberger AM, Hall AR. Adaptation to parasites
and costs of parasite resistance in mutator and nonmutator bacteria. Molecular
Biology and Evolution. 2016;33(3):770-782. doi:10.1093/molbev/msv270
apa: Wielgoss, S., Bergmiller, T., Bischofberger, A. M., & Hall, A. R. (2016).
Adaptation to parasites and costs of parasite resistance in mutator and nonmutator
bacteria. Molecular Biology and Evolution. Oxford University Press. https://doi.org/10.1093/molbev/msv270
chicago: Wielgoss, Sébastien, Tobias Bergmiller, Anna M. Bischofberger, and Alex
R. Hall. “Adaptation to Parasites and Costs of Parasite Resistance in Mutator
and Nonmutator Bacteria.” Molecular Biology and Evolution. Oxford University
Press, 2016. https://doi.org/10.1093/molbev/msv270.
ieee: S. Wielgoss, T. Bergmiller, A. M. Bischofberger, and A. R. Hall, “Adaptation
to parasites and costs of parasite resistance in mutator and nonmutator bacteria,”
Molecular Biology and Evolution, vol. 33, no. 3. Oxford University Press,
pp. 770–782, 2016.
ista: Wielgoss S, Bergmiller T, Bischofberger AM, Hall AR. 2016. Adaptation to parasites
and costs of parasite resistance in mutator and nonmutator bacteria. Molecular
Biology and Evolution. 33(3), 770–782.
mla: Wielgoss, Sébastien, et al. “Adaptation to Parasites and Costs of Parasite
Resistance in Mutator and Nonmutator Bacteria.” Molecular Biology and Evolution,
vol. 33, no. 3, Oxford University Press, 2016, pp. 770–82, doi:10.1093/molbev/msv270.
short: S. Wielgoss, T. Bergmiller, A.M. Bischofberger, A.R. Hall, Molecular Biology
and Evolution 33 (2016) 770–782.
date_created: 2018-12-18T13:18:10Z
date_published: 2016-03-01T00:00:00Z
date_updated: 2026-04-29T05:57:02Z
day: '01'
ddc:
- '576'
department:
- _id: CaGu
doi: 10.1093/molbev/msv270
external_id:
isi:
- '000371219500015'
pmid:
- '26609077'
file:
- access_level: open_access
checksum: 47d9010690b6c5c17f2ac830cc63ac5c
content_type: application/pdf
creator: dernst
date_created: 2018-12-18T13:21:45Z
date_updated: 2020-07-14T12:47:10Z
file_id: '5750'
file_name: 2016_MolBiolEvol_Wielgoss.pdf
file_size: 634037
relation: main_file
file_date_updated: 2020-07-14T12:47:10Z
fulldoi: https://doi.org/10.1093/molbev/msv270
has_accepted_license: '1'
intvolume: ' 33'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '03'
oa: 1
oa_version: Published Version
page: 770-782
pmid: 1
publication: Molecular Biology and Evolution
publication_identifier:
eissn:
- 1537-1719
issn:
- 0737-4038
publication_status: published
publisher: Oxford University Press
pubrep_id: '587'
quality_controlled: '1'
related_material:
record:
- id: '9719'
relation: research_data
status: public
scopus_import: '1'
status: public
title: Adaptation to parasites and costs of parasite resistance in mutator and nonmutator
bacteria
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2016'
...
---
OA_type: closed access
_id: '19990'
abstract:
- lang: eng
text: Visualizing molecular localization at high resolution contributes to understanding
of their functions and roles in physiological and pathological conditions. Sodium
dodecyl sulfate-digested freeze-fracture replica labeling (SDS-FRL) is a powerful
electron microscopy method to study high-resolution two-dimensional distribution
of transmembrane proteins and their tightly associated proteins on platinum-carbon
replica. During treatment with SDS, unfixed proteins and intracellular organelle
are dissolved and integral membrane proteins captured and stabilized by carbon
and platinum deposition are denatured, retaining most of their antigenicity, and
exposed on exoplasmic and protoplasmic surfaces of lipid monolayers. The exposure
of these antigens on the surface of replica facilitates the accessibility of antibodies
and therefore provides higher labeling efficiency than those obtained with other
immunoelectron microscopy techniques. In this chapter, we describe the protocols
of SDS-FRL adapted for mammalian brain samples and an additional procedure for
fluorescence-guided electron microscopy for replica immunolabeling.
acknowledgement: We thank Mitsuru Ikeda for preparing replica images used in Fig.
2.
article_processing_charge: No
author:
- first_name: Harumi
full_name: Harada, Harumi
id: 2E55CDF2-F248-11E8-B48F-1D18A9856A87
last_name: Harada
orcid: 0000-0001-7429-7896
- first_name: Ryuichi
full_name: Shigemoto, Ryuichi
id: 499F3ABC-F248-11E8-B48F-1D18A9856A87
last_name: Shigemoto
orcid: 0000-0001-8761-9444
citation:
ama: 'Harada H, Shigemoto R. High-Resolution Localization of Membrane Proteins by
SDS-Digested Freeze-Fracture Replica Labeling (SDS-FRL). In: Receptor and Ion
Channel Detection in the Brain. Neuromethods. Springer Nature; 2016:233-245.
doi:10.1007/978-1-4939-3064-7_17'
apa: Harada, H., & Shigemoto, R. (2016). High-Resolution Localization of Membrane
Proteins by SDS-Digested Freeze-Fracture Replica Labeling (SDS-FRL). In Receptor
and Ion Channel Detection in the Brain (pp. 233–245). Springer Nature. https://doi.org/10.1007/978-1-4939-3064-7_17
chicago: Harada, Harumi, and Ryuichi Shigemoto. “High-Resolution Localization of
Membrane Proteins by SDS-Digested Freeze-Fracture Replica Labeling (SDS-FRL).”
In Receptor and Ion Channel Detection in the Brain, 233–45. Neuromethods.
Springer Nature, 2016. https://doi.org/10.1007/978-1-4939-3064-7_17.
ieee: H. Harada and R. Shigemoto, “High-Resolution Localization of Membrane Proteins
by SDS-Digested Freeze-Fracture Replica Labeling (SDS-FRL),” in Receptor and
Ion Channel Detection in the Brain, Springer Nature, 2016, pp. 233–245.
ista: 'Harada H, Shigemoto R. 2016.High-Resolution Localization of Membrane Proteins
by SDS-Digested Freeze-Fracture Replica Labeling (SDS-FRL). In: Receptor and Ion
Channel Detection in the Brain. , 233–245.'
mla: Harada, Harumi, and Ryuichi Shigemoto. “High-Resolution Localization of Membrane
Proteins by SDS-Digested Freeze-Fracture Replica Labeling (SDS-FRL).” Receptor
and Ion Channel Detection in the Brain, Springer Nature, 2016, pp. 233–45,
doi:10.1007/978-1-4939-3064-7_17.
short: H. Harada, R. Shigemoto, in:, Receptor and Ion Channel Detection in the Brain,
Springer Nature, 2016, pp. 233–245.
corr_author: '1'
date_created: 2025-07-10T13:56:06Z
date_published: 2016-02-02T00:00:00Z
date_updated: 2026-04-07T08:32:03Z
day: '02'
department:
- _id: RySh
doi: 10.1007/978-1-4939-3064-7_17
fulldoi: https://doi.org/10.1007/978-1-4939-3064-7_17
language:
- iso: eng
month: '02'
oa_version: None
page: 233-245
publication: Receptor and Ion Channel Detection in the Brain
publication_identifier:
eisbn:
- '9781493930647'
eissn:
- 1940-6045
isbn:
- '9781493930630'
issn:
- 0893-2336
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
series_title: Neuromethods
status: public
title: High-Resolution Localization of Membrane Proteins by SDS-Digested Freeze-Fracture
Replica Labeling (SDS-FRL)
type: book_chapter
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2016'
...
---
OA_type: closed access
_id: '19991'
abstract:
- lang: eng
text: 'When applying machine learning techniques to real-world problems, prior knowledge
plays a crucial role in enriching the learning system. This prior knowledge is
typically defined by domain experts and can be integrated into machine learning
algorithms in a variety of ways: as a preference of certain prediction functions
over others, as a Bayesian prior over parameters, or as additional information
about the samples in the training set used for learning a prediction function.
The latter setup is called learning using privileged information (LUPI) and was
adopted by Vapnik and Vashist in (Neural Netw, 2009). Formally, LUPI refers to
the setting when, in addition to the main data modality, the learning system has
access to an extra source of information about the training examples. The additional
source of information is only available during training and therefore is called
privileged. The main goal of LUPI is to utilize privileged information and to
learn a better model in the main data modality than one would learn without the
privileged source. As an illustration, for protein classification based on amino-acid
sequences, the protein tertiary structure can be considered additional information.
Another example is recognizing objects in images; the textual information in the
form of image tags contains additional object descriptions and can be used as
privileged.'
article_processing_charge: No
author:
- first_name: Viktoriia
full_name: Sharmanska, Viktoriia
id: 2EA6D09E-F248-11E8-B48F-1D18A9856A87
last_name: Sharmanska
orcid: 0000-0003-0192-9308
- first_name: Novi
full_name: Quadrianto, Novi
last_name: Quadrianto
citation:
ama: 'Sharmanska V, Quadrianto N. Learning Using Privileged Information. In: Encyclopedia
of Machine Learning and Data Mining. Springer Nature; 2016:1-4. doi:10.1007/978-1-4899-7502-7_892-1'
apa: Sharmanska, V., & Quadrianto, N. (2016). Learning Using Privileged Information.
In Encyclopedia of Machine Learning and Data Mining (pp. 1–4). Springer
Nature. https://doi.org/10.1007/978-1-4899-7502-7_892-1
chicago: Sharmanska, Viktoriia, and Novi Quadrianto. “Learning Using Privileged
Information.” In Encyclopedia of Machine Learning and Data Mining, 1–4.
Springer Nature, 2016. https://doi.org/10.1007/978-1-4899-7502-7_892-1.
ieee: V. Sharmanska and N. Quadrianto, “Learning Using Privileged Information,”
in Encyclopedia of Machine Learning and Data Mining, Springer Nature, 2016,
pp. 1–4.
ista: 'Sharmanska V, Quadrianto N. 2016.Learning Using Privileged Information. In:
Encyclopedia of Machine Learning and Data Mining. , 1–4.'
mla: Sharmanska, Viktoriia, and Novi Quadrianto. “Learning Using Privileged Information.”
Encyclopedia of Machine Learning and Data Mining, Springer Nature, 2016,
pp. 1–4, doi:10.1007/978-1-4899-7502-7_892-1.
short: V. Sharmanska, N. Quadrianto, in:, Encyclopedia of Machine Learning and Data
Mining, Springer Nature, 2016, pp. 1–4.
corr_author: '1'
date_created: 2025-07-10T13:57:52Z
date_published: 2016-07-06T00:00:00Z
date_updated: 2025-09-23T10:53:13Z
day: '06'
department:
- _id: ChLa
doi: 10.1007/978-1-4899-7502-7_892-1
fulldoi: https://doi.org/10.1007/978-1-4899-7502-7_892-1
language:
- iso: eng
month: '07'
oa_version: None
page: 1-4
publication: Encyclopedia of Machine Learning and Data Mining
publication_identifier:
eisbn:
- '9781489975027'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Learning Using Privileged Information
type: book_chapter
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '1008'
abstract:
- lang: eng
text: Feedback loops in biological networks, among others, enable differentiation
and cell cycle progression, and increase robustness in signal transduction. In
natural networks, feedback loops are often complex and intertwined, making it
challenging to identify which loops are mainly responsible for an observed behavior.
However, minimal synthetic replicas could allow for such identification. Here,
we engineered a synthetic permease-inducer-repressor system in Saccharomyces cerevisiae
to analyze if a transport-mediated positive feedback loop could be a core mechanism
for the switch-like behavior in the regulation of metabolic gene networks such
as the S. cerevisiae GAL system or the Escherichia coli lac operon. We characterized
the synthetic circuit using deterministic and stochastic mathematical models.
Similar to its natural counterparts, our synthetic system shows bistable and hysteretic
behavior, and the inducer concentration range for bistability as well as the switching
rates between the two stable states depend on the repressor concentration. Our
results indicate that a generic permease–inducer–repressor circuit with a single
feedback loop is sufficient to explain the experimentally observed bistable behavior
of the natural systems. We anticipate that the approach of reimplementing natural
systems with orthogonal parts to identify crucial network components is applicable
to other natural systems such as signaling pathways.
acknowledgement: We thank Julio Polaina (Instituto de Agroqu ı ́ mica y Tecnolog ı
́ a de Alimentos, C.S.I.C., Paterna, Spain) for the gift of plasmid pMR4, Gregor
W. Schmidt for provision of and support with the micro fl uidic device, Markus Du
̈ rr for the cell tracking R script, and Lukas Widmer for the script for MEIGO using
“ parfor ” in MATLAB. We acknowledge the members of the Stelling group for discussions,
comments, and support.
article_processing_charge: No
author:
- first_name: Robert
full_name: Gnügge, Robert
last_name: Gnügge
- first_name: Lekshmi
full_name: Dharmarajan, Lekshmi
last_name: Dharmarajan
- first_name: Moritz
full_name: Lang, Moritz
id: 29E0800A-F248-11E8-B48F-1D18A9856A87
last_name: Lang
- first_name: Jörg
full_name: Stelling, Jörg
last_name: Stelling
citation:
ama: Gnügge R, Dharmarajan L, Lang M, Stelling J. An orthogonal permease–inducer–repressor
feedback loop shows bistability. ACS Synthetic Biology. 2016;5(10):1098-1107.
doi:10.1021/acssynbio.6b00013
apa: Gnügge, R., Dharmarajan, L., Lang, M., & Stelling, J. (2016). An orthogonal
permease–inducer–repressor feedback loop shows bistability. ACS Synthetic Biology.
American Chemical Society. https://doi.org/10.1021/acssynbio.6b00013
chicago: Gnügge, Robert, Lekshmi Dharmarajan, Moritz Lang, and Jörg Stelling. “An
Orthogonal Permease–Inducer–Repressor Feedback Loop Shows Bistability.” ACS
Synthetic Biology. American Chemical Society, 2016. https://doi.org/10.1021/acssynbio.6b00013.
ieee: R. Gnügge, L. Dharmarajan, M. Lang, and J. Stelling, “An orthogonal permease–inducer–repressor
feedback loop shows bistability,” ACS Synthetic Biology, vol. 5, no. 10.
American Chemical Society, pp. 1098–1107, 2016.
ista: Gnügge R, Dharmarajan L, Lang M, Stelling J. 2016. An orthogonal permease–inducer–repressor
feedback loop shows bistability. ACS Synthetic Biology. 5(10), 1098–1107.
mla: Gnügge, Robert, et al. “An Orthogonal Permease–Inducer–Repressor Feedback Loop
Shows Bistability.” ACS Synthetic Biology, vol. 5, no. 10, American Chemical
Society, 2016, pp. 1098–107, doi:10.1021/acssynbio.6b00013.
short: R. Gnügge, L. Dharmarajan, M. Lang, J. Stelling, ACS Synthetic Biology 5
(2016) 1098–1107.
date_created: 2018-12-11T11:49:40Z
date_published: 2016-05-05T00:00:00Z
date_updated: 2025-09-22T14:20:45Z
day: '05'
department:
- _id: CaGu
doi: 10.1021/acssynbio.6b00013
external_id:
isi:
- '000386196100008'
fulldoi: https://doi.org/10.1021/acssynbio.6b00013
intvolume: ' 5'
isi: 1
issue: '10'
language:
- iso: eng
month: '05'
oa_version: None
page: 1098 - 1107
publication: ACS Synthetic Biology
publication_status: published
publisher: American Chemical Society
publist_id: '6390'
quality_controlled: '1'
status: public
title: An orthogonal permease–inducer–repressor feedback loop shows bistability
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 5
year: '2016'
...
---
_id: '1068'
abstract:
- lang: eng
text: 'Games on graphs provide the appropriate framework to study several central
problems in computer science, such as verification and synthesis of reactive systems.
One of the most basic objectives for games on graphs is the liveness (or Büchi)
objective that given a target set of vertices requires that some vertex in the
target set is visited infinitely often. We study generalized Büchi objectives
(i.e., conjunction of liveness objectives), and implications between two generalized
Büchi objectives (known as GR(1) objectives), that arise in numerous applications
in computer-aided verification. We present improved algorithms and conditional
super-linear lower bounds based on widely believed assumptions about the complexity
of (A1) combinatorial Boolean matrix multiplication and (A2) CNF-SAT. We consider
graph games with n vertices, m edges, and generalized Büchi objectives with k
conjunctions. First, we present an algorithm with running time O(k*n^2), improving
the previously known O(k*n*m) and O(k^2*n^2) worst-case bounds. Our algorithm
is optimal for dense graphs under (A1). Second, we show that the basic algorithm
for the problem is optimal for sparse graphs when the target sets have constant
size under (A2). Finally, we consider GR(1) objectives, with k_1 conjunctions
in the antecedent and k_2 conjunctions in the consequent, and present an O(k_1
k_2 n^{2.5})-time algorithm, improving the previously known O(k_1*k_2*n*m)-time
algorithm for m > n^{1.5}. '
acknowledgement: K. C., M. H., and W. D. are partially supported by the Vienna Science
and Technology Fund (WWTF) through project ICT15-003. K. C. is partially supported
by the Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE) and an ERC
Start grant (279307
alternative_title:
- LIPIcs
article_number: '25'
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: Wolfgang
full_name: Dvorák, Wolfgang
last_name: Dvorák
- 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: Veronika
full_name: Loitzenbauer, Veronika
last_name: Loitzenbauer
citation:
ama: 'Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. Conditionally optimal
algorithms for generalized Büchi Games. In: Vol 58. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2016. doi:10.4230/LIPIcs.MFCS.2016.25'
apa: 'Chatterjee, K., Dvorák, W., Henzinger, M., & Loitzenbauer, V. (2016).
Conditionally optimal algorithms for generalized Büchi Games (Vol. 58). Presented
at the MFCS: Mathematical Foundations of Computer Science, Krakow, Poland: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2016.25'
chicago: Chatterjee, Krishnendu, Wolfgang Dvorák, Monika Henzinger, and Veronika
Loitzenbauer. “Conditionally Optimal Algorithms for Generalized Büchi Games,”
Vol. 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPIcs.MFCS.2016.25.
ieee: 'K. Chatterjee, W. Dvorák, M. Henzinger, and V. Loitzenbauer, “Conditionally
optimal algorithms for generalized Büchi Games,” presented at the MFCS: Mathematical
Foundations of Computer Science, Krakow, Poland, 2016, vol. 58.'
ista: 'Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2016. Conditionally
optimal algorithms for generalized Büchi Games. MFCS: Mathematical Foundations
of Computer Science, LIPIcs, vol. 58, 25.'
mla: Chatterjee, Krishnendu, et al. Conditionally Optimal Algorithms for Generalized
Büchi Games. Vol. 58, 25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2016, doi:10.4230/LIPIcs.MFCS.2016.25.
short: K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2016.
conference:
end_date: 2016-08-26
location: Krakow, Poland
name: 'MFCS: Mathematical Foundations of Computer Science'
start_date: 2016-08-22
date_created: 2018-12-11T11:49:58Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2025-07-10T11:49:55Z
day: '01'
ddc:
- '000'
- '004'
- '006'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.MFCS.2016.25
ec_funded: 1
file:
- access_level: open_access
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:02Z
date_updated: 2018-12-12T10:16:02Z
file_id: '5187'
file_name: IST-2017-779-v1+1_LIPIcs-MFCS-2016-25.pdf
file_size: 632786
relation: main_file
file_date_updated: 2018-12-12T10:16:02Z
fulldoi: https://doi.org/10.4230/LIPIcs.MFCS.2016.25
has_accepted_license: '1'
intvolume: ' 58'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/3.0/
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
grant_number: ICT15-003
name: Efficient Algorithms for Computer Aided 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'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6317'
pubrep_id: '779'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Conditionally optimal algorithms for generalized Büchi Games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/3.0/legalcode
name: Creative Commons Attribution 3.0 Unported (CC BY 3.0)
short: CC BY (3.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 58
year: '2016'
...