---
_id: '338'
abstract:
- lang: eng
text: The ample chemical and structural freedom of quaternary compounds permits
engineering materials that fulfill the requirements of a wide variety of applications.
In this work, the mechanisms to achieve unprecedented size, shape, and composition
control in quaternary nanocrystals are detailed. The described procedure allows
obtaining tetrahedral and penta-tetrahedral quaternary nanocrystals with tuned
size distributions and controlled compositions from a plethora of I 2-II-IV-VI
4 semiconductors.
acknowledgement: "This work was supported by the Spanish MICINN Projects MAT2008-05779,
MAT2008-03400-E/MAT, MAT2010-15138, ENE2008-03277-E/CON, CSD2009-00050, and CSD2009-00013.
M.I. thanks the Spanish MICINN for her Ph.D. grant. J.A. and R.Z. also acknowledge
Generalitat de Catalunya 2009-SGR-770 and XaRMAE. A.C. is grateful for financial
support through the Ramon y Cajal program of the Spanish MICINN.\r\n\r\n"
article_processing_charge: No
article_type: original
author:
- first_name: Maria
full_name: Ibáñez, Maria
id: 43C61214-F248-11E8-B48F-1D18A9856A87
last_name: Ibáñez
orcid: 0000-0001-5013-2843
- first_name: Reza
full_name: Zamani, Reza
last_name: Zamani
- first_name: Wenhua
full_name: Li, Wenhua
last_name: Li
- first_name: Alexey
full_name: Shavel, Alexey
last_name: Shavel
- first_name: Jordi
full_name: Arbiol, Jordi
last_name: Arbiol
- first_name: Joan
full_name: Morante, Joan
last_name: Morante
- first_name: Andreu
full_name: Cabot, Andreu
last_name: Cabot
citation:
ama: Ibáñez M, Zamani R, Li W, et al. Extending the nanocrystal synthesis control
to quaternary compositions. Crystal Growth and Design . 2012;12(3):1085-1090.
doi:10.1021/cg201709c
apa: Ibáñez, M., Zamani, R., Li, W., Shavel, A., Arbiol, J., Morante, J., &
Cabot, A. (2012). Extending the nanocrystal synthesis control to quaternary compositions.
Crystal Growth and Design . American Chemical Society (ACS). https://doi.org/10.1021/cg201709c
chicago: Ibáñez, Maria, Reza Zamani, Wenhua Li, Alexey Shavel, Jordi Arbiol, Joan
Morante, and Andreu Cabot. “Extending the Nanocrystal Synthesis Control to Quaternary
Compositions.” Crystal Growth and Design . American Chemical Society (ACS),
2012. https://doi.org/10.1021/cg201709c.
ieee: M. Ibáñez et al., “Extending the nanocrystal synthesis control to quaternary
compositions,” Crystal Growth and Design , vol. 12, no. 3. American Chemical
Society (ACS), pp. 1085–1090, 2012.
ista: Ibáñez M, Zamani R, Li W, Shavel A, Arbiol J, Morante J, Cabot A. 2012. Extending
the nanocrystal synthesis control to quaternary compositions. Crystal Growth and
Design . 12(3), 1085–1090.
mla: Ibáñez, Maria, et al. “Extending the Nanocrystal Synthesis Control to Quaternary
Compositions.” Crystal Growth and Design , vol. 12, no. 3, American Chemical
Society (ACS), 2012, pp. 1085–90, doi:10.1021/cg201709c.
short: M. Ibáñez, R. Zamani, W. Li, A. Shavel, J. Arbiol, J. Morante, A. Cabot,
Crystal Growth and Design 12 (2012) 1085–1090.
date_created: 2018-12-11T11:45:54Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2021-01-12T07:43:05Z
day: '01'
doi: 10.1021/cg201709c
extern: '1'
intvolume: ' 12'
issue: '3'
language:
- iso: eng
month: '01'
oa_version: None
page: 1085 - 1090
publication: 'Crystal Growth and Design '
publication_status: published
publisher: American Chemical Society (ACS)
publist_id: '7488'
quality_controlled: '1'
status: public
title: Extending the nanocrystal synthesis control to quaternary compositions
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12
year: '2012'
...
---
_id: '339'
abstract:
- lang: eng
text: A high-yield and upscalable colloidal synthesis route for the production of
quaternary I 2-II-IV-VI 4 nanocrystals, particularly stannite Cu 2+xCd 1-xSnSe
4, with narrow size distribution and precisely controlled composition is presented.
It is also shown here how the diversity of valences in the constituent elements
allows an effective control of their electrical conductivity through the adjustment
of the cation ratios. At the same time, while the crystallographic complexity
of quaternary chalcogenides is associated with intrinsically low thermal conductivities,
the reduction of the lattice dimensions to the nanoscale further reduces the materials
thermal conductivity. In the specific case of the stannite crystal structure,
a convenient slab distribution of the valence band maximum states permits a partial
decoupling of the p-type electrical conductivity from both the Seebeck coefficient
and the thermal conductivity. Combining these features, we demonstrate how an
initial optimization of the nanocrystals Cd/Cu ratio allowed us to obtain low-temperature
solution-processed materials with ZT values up to 0.71 at 685 K.
acknowledgement: This work was supported by the Spanish MICINN Projects MAT2008-05779,
MAT2008-03400-E/MAT, MAT2010-15138, ENE2008-03277-E/CON, CSD2009-00050. and CSD2009-00013.
M.I. and N.G.-C. thank the Spanish MICINN for the PhD grant. J.A. and R.Z. also
acknowledge Generalitat de Catalunya 2009-SGR-770 and XaRMAE. A.C. is thankful for
financial support through the Ramon y Cajal program of the Spanish MICINN. N.G.-C.
and J.D.P. are thankful for the computer resources, technical expertise and assistance
provided by the Barcelona Supercomputing Center - Centro Nacional de Supercomputación.
article_processing_charge: No
article_type: original
author:
- first_name: Maria
full_name: Ibáñez, Maria
id: 43C61214-F248-11E8-B48F-1D18A9856A87
last_name: Ibáñez
orcid: 0000-0001-5013-2843
- first_name: Doris
full_name: Cadavid, Doris
last_name: Cadavid
- first_name: Reza
full_name: Zamani, Reza
last_name: Zamani
- first_name: Nuria
full_name: García Castelló, Nuria
last_name: García Castelló
- first_name: Victora
full_name: Izquierdo Roca, Victora
last_name: Izquierdo Roca
- first_name: Wenhua
full_name: Li, Wenhua
last_name: Li
- first_name: Andrew
full_name: Fairbrother, Andrew
last_name: Fairbrother
- first_name: Joan
full_name: Prades, Joan
last_name: Prades
- first_name: Alexey
full_name: Shavel, Alexey
last_name: Shavel
- first_name: Jordi
full_name: Arbiol, Jordi
last_name: Arbiol
- first_name: Alejandro
full_name: Pérez Rodríguez, Alejandro
last_name: Pérez Rodríguez
- first_name: Joan
full_name: Morante, Joan
last_name: Morante
- first_name: Andreu
full_name: Cabot, Andreu
last_name: Cabot
citation:
ama: 'Ibáñez M, Cadavid D, Zamani R, et al. Composition control and thermoelectric
properties of quaternary chalcogenide nanocrystals: The case of stannite Cu2CdSnSe4.
Chemistry of Materials. 2012;24(3):562-570. doi:10.1021/cm2031812'
apa: 'Ibáñez, M., Cadavid, D., Zamani, R., García Castelló, N., Izquierdo Roca,
V., Li, W., … Cabot, A. (2012). Composition control and thermoelectric properties
of quaternary chalcogenide nanocrystals: The case of stannite Cu2CdSnSe4. Chemistry
of Materials. American Chemical Society. https://doi.org/10.1021/cm2031812'
chicago: 'Ibáñez, Maria, Doris Cadavid, Reza Zamani, Nuria García Castelló, Victora
Izquierdo Roca, Wenhua Li, Andrew Fairbrother, et al. “Composition Control and
Thermoelectric Properties of Quaternary Chalcogenide Nanocrystals: The Case of
Stannite Cu2CdSnSe4.” Chemistry of Materials. American Chemical Society,
2012. https://doi.org/10.1021/cm2031812.'
ieee: 'M. Ibáñez et al., “Composition control and thermoelectric properties
of quaternary chalcogenide nanocrystals: The case of stannite Cu2CdSnSe4,” Chemistry
of Materials, vol. 24, no. 3. American Chemical Society, pp. 562–570, 2012.'
ista: 'Ibáñez M, Cadavid D, Zamani R, García Castelló N, Izquierdo Roca V, Li W,
Fairbrother A, Prades J, Shavel A, Arbiol J, Pérez Rodríguez A, Morante J, Cabot
A. 2012. Composition control and thermoelectric properties of quaternary chalcogenide
nanocrystals: The case of stannite Cu2CdSnSe4. Chemistry of Materials. 24(3),
562–570.'
mla: 'Ibáñez, Maria, et al. “Composition Control and Thermoelectric Properties of
Quaternary Chalcogenide Nanocrystals: The Case of Stannite Cu2CdSnSe4.” Chemistry
of Materials, vol. 24, no. 3, American Chemical Society, 2012, pp. 562–70,
doi:10.1021/cm2031812.'
short: M. Ibáñez, D. Cadavid, R. Zamani, N. García Castelló, V. Izquierdo Roca,
W. Li, A. Fairbrother, J. Prades, A. Shavel, J. Arbiol, A. Pérez Rodríguez, J.
Morante, A. Cabot, Chemistry of Materials 24 (2012) 562–570.
date_created: 2018-12-11T11:45:54Z
date_published: 2012-01-31T00:00:00Z
date_updated: 2021-01-12T07:43:09Z
day: '31'
doi: 10.1021/cm2031812
extern: '1'
intvolume: ' 24'
issue: '3'
language:
- iso: eng
month: '01'
oa_version: None
page: 562 - 570
publication: Chemistry of Materials
publication_status: published
publisher: American Chemical Society
publist_id: '7489'
quality_controlled: '1'
status: public
title: 'Composition control and thermoelectric properties of quaternary chalcogenide
nanocrystals: The case of stannite Cu2CdSnSe4'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '2012'
...
---
_id: '340'
abstract:
- lang: eng
text: 'A procedure for the continuous production of Cu 2ZnSnS 4 (CZTS) nanoparticles
with controlled composition is presented. CZTS nanoparticles were prepared through
the reaction of the metals'' amino complexes with elemental sulfur in a continuous-flow
reactor at moderate temperatures (300-330 °C). High-resolution transmission electron
microscopy and X-ray diffraction analysis showed the nanocrystals to have a crystallographic
structure compatible with that of the kesterite. Chemical characterization of
the materials showed the presence of the four elements in each individual nanocrystal.
Composition control was achieved by adjusting the solution flow rate through the
reactor and the proper choice of the nominal precursor concentration within the
flowing solution. Single-particle analysis revealed a composition distribution
within each sample, which was optimized at the highest synthesis temperatures
used. '
acknowledgement: This work was supported by the Spanish MICINN Projects MAT2008-05779,
MAT2008-03400-E/MAT, CDS2009-00050, CSD2009-00013, and ENE2008-03277-E/CON. M.I.
thanks the Spanish MICINN for her Ph.D. grant. A.C. is thankful for financial support
through the Ramón y Cajal Program.
article_processing_charge: No
article_type: original
author:
- first_name: Alexey
full_name: Shavel, Alexey
last_name: Shavel
- first_name: Doris
full_name: Cadavid, Doris
last_name: Cadavid
- first_name: Maria
full_name: Ibáñez, Maria
id: 43C61214-F248-11E8-B48F-1D18A9856A87
last_name: Ibáñez
orcid: 0000-0001-5013-2843
- first_name: Alex
full_name: Carrete, Alex
last_name: Carrete
- first_name: Andreu
full_name: Cabot, Andreu
last_name: Cabot
citation:
ama: Shavel A, Cadavid D, Ibáñez M, Carrete A, Cabot A. Continuous production of
Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the
American Chemical Society. 2012;134(3):1438-1441. doi:10.1021/ja209688a
apa: Shavel, A., Cadavid, D., Ibáñez, M., Carrete, A., & Cabot, A. (2012). Continuous
production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal
of the American Chemical Society. ACS. https://doi.org/10.1021/ja209688a
chicago: Shavel, Alexey, Doris Cadavid, Maria Ibáñez, Alex Carrete, and Andreu Cabot.
“Continuous Production of Cu Inf 2 Inf ZnSnS Inf 4 Inf Nanocrystals in a Flow
Reactor.” Journal of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja209688a.
ieee: A. Shavel, D. Cadavid, M. Ibáñez, A. Carrete, and A. Cabot, “Continuous production
of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor,” Journal of
the American Chemical Society, vol. 134, no. 3. ACS, pp. 1438–1441, 2012.
ista: Shavel A, Cadavid D, Ibáñez M, Carrete A, Cabot A. 2012. Continuous production
of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow reactor. Journal of the
American Chemical Society. 134(3), 1438–1441.
mla: Shavel, Alexey, et al. “Continuous Production of Cu Inf 2 Inf ZnSnS Inf 4 Inf
Nanocrystals in a Flow Reactor.” Journal of the American Chemical Society,
vol. 134, no. 3, ACS, 2012, pp. 1438–41, doi:10.1021/ja209688a.
short: A. Shavel, D. Cadavid, M. Ibáñez, A. Carrete, A. Cabot, Journal of the American
Chemical Society 134 (2012) 1438–1441.
date_created: 2018-12-11T11:45:54Z
date_published: 2012-01-02T00:00:00Z
date_updated: 2021-01-12T07:43:13Z
day: '02'
doi: 10.1021/ja209688a
extern: '1'
intvolume: ' 134'
issue: '3'
language:
- iso: eng
month: '01'
oa_version: None
page: 1438 - 1441
publication: Journal of the American Chemical Society
publication_status: published
publisher: ACS
publist_id: '7490'
quality_controlled: '1'
status: public
title: Continuous production of Cu inf 2 inf ZnSnS inf 4 inf nanocrystals in a flow
reactor
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 134
year: '2012'
...
---
_id: '345'
abstract:
- lang: eng
text: 'Nanocomposites are highly promising materials to enhance the efficiency of
current thermoelectric devices. A straightforward and at the same time highly
versatile and controllable approach to produce nanocomposites is the assembly
of solution-processed nanocrystal building blocks. The convenience of this bottom-up
approach to produce nanocomposites with homogeneous phase distributions and adjustable
composition is demonstrated here by blending Ag2Te and PbTe colloidal nanocrystals
to form Ag2Te–PbTe bulk nanocomposites. The thermoelectric properties of these
nanocomposites are analyzed in the temperature range from 300 to 700 K. The evolution
of their electrical conductivity and Seebeck coefficient is discussed in terms
of the blend composition and the characteristics of the constituent materials. '
acknowledgement: Acknowledgments The research was supported by the European Regional
Development Funds and the Spanish MICINN Projects MAT2008-05779, MAT2008-03400-E/MAT,
MAT2010-15138, MAT2010-21510, CSD2009-00050, and ENE2008-03277-E/CON. M.I. is grateful
to the Spanish MIC-INN for her PhD grant. A. Cirera acknowledges support from ICREA
Academia program. A. Cabot is grateful to the Spanish MICINN for financial support
through the Ramón y Cajal program.
article_processing_charge: No
article_type: original
author:
- first_name: Doris
full_name: Cadavid, Doris
last_name: Cadavid
- first_name: Maria
full_name: Ibáñez, Maria
id: 43C61214-F248-11E8-B48F-1D18A9856A87
last_name: Ibáñez
orcid: 0000-0001-5013-2843
- first_name: Stéphane
full_name: Gorsse, Stéphane
last_name: Gorsse
- first_name: Antonio
full_name: López, Antonio
last_name: López
- first_name: Albert
full_name: Cirera, Albert
last_name: Cirera
- first_name: Joan
full_name: Morante, Joan
last_name: Morante
- first_name: Andreu
full_name: Cabot, Andreu
last_name: Cabot
citation:
ama: 'Cadavid D, Ibáñez M, Gorsse S, et al. Bottom-up processing of thermoelectric
nanocomposites from colloidal nanocrystal building blocks: The case of Ag2Te–PbTe.
Journal of Nanoparticle Research. 2012;14(12). doi:10.1007/s11051-012-1328-0'
apa: 'Cadavid, D., Ibáñez, M., Gorsse, S., López, A., Cirera, A., Morante, J., &
Cabot, A. (2012). Bottom-up processing of thermoelectric nanocomposites from colloidal
nanocrystal building blocks: The case of Ag2Te–PbTe. Journal of Nanoparticle
Research. Kluwer. https://doi.org/10.1007/s11051-012-1328-0'
chicago: 'Cadavid, Doris, Maria Ibáñez, Stéphane Gorsse, Antonio López, Albert Cirera,
Joan Morante, and Andreu Cabot. “Bottom-up Processing of Thermoelectric Nanocomposites
from Colloidal Nanocrystal Building Blocks: The Case of Ag2Te–PbTe.” Journal
of Nanoparticle Research. Kluwer, 2012. https://doi.org/10.1007/s11051-012-1328-0.'
ieee: 'D. Cadavid et al., “Bottom-up processing of thermoelectric nanocomposites
from colloidal nanocrystal building blocks: The case of Ag2Te–PbTe,” Journal
of Nanoparticle Research, vol. 14, no. 12. Kluwer, 2012.'
ista: 'Cadavid D, Ibáñez M, Gorsse S, López A, Cirera A, Morante J, Cabot A. 2012.
Bottom-up processing of thermoelectric nanocomposites from colloidal nanocrystal
building blocks: The case of Ag2Te–PbTe. Journal of Nanoparticle Research. 14(12).'
mla: 'Cadavid, Doris, et al. “Bottom-up Processing of Thermoelectric Nanocomposites
from Colloidal Nanocrystal Building Blocks: The Case of Ag2Te–PbTe.” Journal
of Nanoparticle Research, vol. 14, no. 12, Kluwer, 2012, doi:10.1007/s11051-012-1328-0.'
short: D. Cadavid, M. Ibáñez, S. Gorsse, A. López, A. Cirera, J. Morante, A. Cabot,
Journal of Nanoparticle Research 14 (2012).
date_created: 2018-12-11T11:45:56Z
date_published: 2012-12-01T00:00:00Z
date_updated: 2021-01-12T07:43:32Z
day: '01'
doi: 10.1007/s11051-012-1328-0
extern: '1'
intvolume: ' 14'
issue: '12'
language:
- iso: eng
month: '12'
oa_version: None
publication: Journal of Nanoparticle Research
publication_status: published
publisher: Kluwer
publist_id: '7485'
quality_controlled: '1'
status: public
title: 'Bottom-up processing of thermoelectric nanocomposites from colloidal nanocrystal
building blocks: The case of Ag2Te–PbTe'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14
year: '2012'
...
---
_id: '347'
abstract:
- lang: eng
text: 'A synthetic route for producing Cu 2ZnGeSe 4 nanocrystals with narrow size
distributions and controlled composition is presented. These nanocrystals were
used to produce densely packed nanomaterials by hot-pressing. From the characterization
of the thermoelectric properties of these nanomaterials, Cu 2ZnGeSe 4 is demonstrated
to show excellent thermoelectric properties. A very preliminary adjustment of
the nanocrystal composition has already resulted in a figure of merit of up to
0.55 at 450°C. '
acknowledgement: This work was supported by the Spanish MICINN Projects MAT2008-05779,
MAT2008-03400-E/MAT, MAT2010-15138, ENE2008-03277-E/CON, CSD2009-00050, and CSD2009-00013.
M.I. thanks the Spanish MICINN for her Ph.D. Grant. J.A. and R.Z. also acknowledge
Generalitat de Catalunya 2009-SGR-770 and XaRMAE. A.C. is thankful for financial
support through the Ramon y Cajal Program of the Spanish MICINN.
article_processing_charge: No
article_type: original
author:
- first_name: Maria
full_name: Ibáñez, Maria
id: 43C61214-F248-11E8-B48F-1D18A9856A87
last_name: Ibáñez
orcid: 0000-0001-5013-2843
- first_name: Reza
full_name: Zamani, Reza
last_name: Zamani
- first_name: Aaron
full_name: Lalonde, Aaron
last_name: Lalonde
- first_name: Doris
full_name: Cadavid, Doris
last_name: Cadavid
- first_name: Wenhua
full_name: Li, Wenhua
last_name: Li
- first_name: Alexey
full_name: Shavel, Alexey
last_name: Shavel
- first_name: Jordi
full_name: Arbiol, Jordi
last_name: Arbiol
- first_name: Joan
full_name: Morante, Joan
last_name: Morante
- first_name: Stéphane
full_name: Gorsse, Stéphane
last_name: Gorsse
- first_name: G Jeffrey
full_name: Snyder, G Jeffrey
last_name: Snyder
- first_name: Andreu
full_name: Cabot, Andreu
last_name: Cabot
citation:
ama: 'Ibáñez M, Zamani R, Lalonde A, et al. Cu 2ZnGeSe 4 nanocrystals: Synthesis
and thermoelectric properties. Journal of the American Chemical Society.
2012;134(9):4060-4063. doi:10.1021/ja211952z'
apa: 'Ibáñez, M., Zamani, R., Lalonde, A., Cadavid, D., Li, W., Shavel, A., … Cabot,
A. (2012). Cu 2ZnGeSe 4 nanocrystals: Synthesis and thermoelectric properties.
Journal of the American Chemical Society. ACS. https://doi.org/10.1021/ja211952z'
chicago: 'Ibáñez, Maria, Reza Zamani, Aaron Lalonde, Doris Cadavid, Wenhua Li, Alexey
Shavel, Jordi Arbiol, et al. “Cu 2ZnGeSe 4 Nanocrystals: Synthesis and Thermoelectric
Properties.” Journal of the American Chemical Society. ACS, 2012. https://doi.org/10.1021/ja211952z.'
ieee: 'M. Ibáñez et al., “Cu 2ZnGeSe 4 nanocrystals: Synthesis and thermoelectric
properties,” Journal of the American Chemical Society, vol. 134, no. 9.
ACS, pp. 4060–4063, 2012.'
ista: 'Ibáñez M, Zamani R, Lalonde A, Cadavid D, Li W, Shavel A, Arbiol J, Morante
J, Gorsse S, Snyder GJ, Cabot A. 2012. Cu 2ZnGeSe 4 nanocrystals: Synthesis and
thermoelectric properties. Journal of the American Chemical Society. 134(9), 4060–4063.'
mla: 'Ibáñez, Maria, et al. “Cu 2ZnGeSe 4 Nanocrystals: Synthesis and Thermoelectric
Properties.” Journal of the American Chemical Society, vol. 134, no. 9,
ACS, 2012, pp. 4060–63, doi:10.1021/ja211952z.'
short: M. Ibáñez, R. Zamani, A. Lalonde, D. Cadavid, W. Li, A. Shavel, J. Arbiol,
J. Morante, S. Gorsse, G.J. Snyder, A. Cabot, Journal of the American Chemical
Society 134 (2012) 4060–4063.
date_created: 2018-12-11T11:45:57Z
date_published: 2012-03-07T00:00:00Z
date_updated: 2021-01-12T07:43:40Z
day: '07'
doi: 10.1021/ja211952z
extern: '1'
intvolume: ' 134'
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://authors.library.caltech.edu/30261/
month: '03'
oa: 1
oa_version: None
page: 4060 - 4063
publication: Journal of the American Chemical Society
publication_status: published
publisher: ACS
publist_id: '7487'
quality_controlled: '1'
status: public
title: 'Cu 2ZnGeSe 4 nanocrystals: Synthesis and thermoelectric properties'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 134
year: '2012'
...
---
_id: '3836'
abstract:
- lang: eng
text: Hierarchical Timing Language (HTL) is a coordination language for distributed,
hard real-time applications. HTL is a hierarchical extension of Giotto and, like
its predecessor, based on the logical execution time (LET) paradigm of real-time
programming. Giotto is compiled into code for a virtual machine, called the EmbeddedMachine
(or E machine). If HTL is targeted to the E machine, then the hierarchicalprogram
structure needs to be flattened; the flattening makes separatecompilation difficult,
and may result in E machinecode of exponential size. In this paper, we propose
a generalization of the E machine, which supports a hierarchicalprogram structure
at runtime through real-time trigger mechanisms that are arranged in a tree. We
present the generalized E machine, and a modular compiler for HTL that generates
code of linear size. The compiler may generate code for any part of a given HTL
program separately in any order.
author:
- first_name: Arkadeb
full_name: Ghosal, Arkadeb
last_name: Ghosal
- first_name: Daniel
full_name: Iercan, Daniel
last_name: Iercan
- first_name: Christoph
full_name: Kirsch, Christoph
last_name: Kirsch
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000−0002−2985−7724
- first_name: Alberto
full_name: Sangiovanni Vincentelli, Alberto
last_name: Sangiovanni Vincentelli
citation:
ama: Ghosal A, Iercan D, Kirsch C, Henzinger TA, Sangiovanni Vincentelli A. Separate
compilation of hierarchical real-time programs into linear-bounded embedded machine
code. Science of Computer Programming. 2012;77(2):96-112. doi:10.1016/j.scico.2010.06.004
apa: Ghosal, A., Iercan, D., Kirsch, C., Henzinger, T. A., & Sangiovanni Vincentelli,
A. (2012). Separate compilation of hierarchical real-time programs into linear-bounded
embedded machine code. Science of Computer Programming. Elsevier. https://doi.org/10.1016/j.scico.2010.06.004
chicago: Ghosal, Arkadeb, Daniel Iercan, Christoph Kirsch, Thomas A Henzinger, and
Alberto Sangiovanni Vincentelli. “Separate Compilation of Hierarchical Real-Time
Programs into Linear-Bounded Embedded Machine Code.” Science of Computer Programming.
Elsevier, 2012. https://doi.org/10.1016/j.scico.2010.06.004.
ieee: A. Ghosal, D. Iercan, C. Kirsch, T. A. Henzinger, and A. Sangiovanni Vincentelli,
“Separate compilation of hierarchical real-time programs into linear-bounded embedded
machine code,” Science of Computer Programming, vol. 77, no. 2. Elsevier,
pp. 96–112, 2012.
ista: Ghosal A, Iercan D, Kirsch C, Henzinger TA, Sangiovanni Vincentelli A. 2012.
Separate compilation of hierarchical real-time programs into linear-bounded embedded
machine code. Science of Computer Programming. 77(2), 96–112.
mla: Ghosal, Arkadeb, et al. “Separate Compilation of Hierarchical Real-Time Programs
into Linear-Bounded Embedded Machine Code.” Science of Computer Programming,
vol. 77, no. 2, Elsevier, 2012, pp. 96–112, doi:10.1016/j.scico.2010.06.004.
short: A. Ghosal, D. Iercan, C. Kirsch, T.A. Henzinger, A. Sangiovanni Vincentelli,
Science of Computer Programming 77 (2012) 96–112.
date_created: 2018-12-11T12:05:26Z
date_published: 2012-02-01T00:00:00Z
date_updated: 2021-01-12T07:52:32Z
day: '01'
department:
- _id: ToHe
doi: 10.1016/j.scico.2010.06.004
intvolume: ' 77'
issue: '2'
language:
- iso: eng
month: '02'
oa_version: None
page: 96 - 112
publication: Science of Computer Programming
publication_status: published
publisher: Elsevier
publist_id: '2370'
quality_controlled: '1'
scopus_import: 1
status: public
title: Separate compilation of hierarchical real-time programs into linear-bounded
embedded machine code
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2012'
...
---
_id: '2972'
abstract:
- lang: eng
text: 'Energy parity games are infinite two-player turn-based games played on weighted
graphs. The objective of the game combines a (qualitative) parity condition with
the (quantitative) requirement that the sum of the weights (i.e., the level of
energy in the game) must remain positive. Beside their own interest in the design
and synthesis of resource-constrained omega-regular specifications, energy parity
games provide one of the simplest model of games with combined qualitative and
quantitative objectives. Our main results are as follows: (a) exponential memory
is sufficient and may be necessary for winning strategies in energy parity games;
(b) the problem of deciding the winner in energy parity games can be solved in
NP ∩ coNP; and (c) we give an algorithm to solve energy parity by reduction to
energy games. We also show that the problem of deciding the winner in energy parity
games is logspace-equivalent to the problem of deciding the winner in mean-payoff
parity games, which can thus be solved in NP ∩ coNP. As a consequence we also
obtain a conceptually simple algorithm to solve mean-payoff parity games.'
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. Energy parity games. Theoretical Computer Science.
2012;458:49-60. doi:10.1016/j.tcs.2012.07.038
apa: Chatterjee, K., & Doyen, L. (2012). Energy parity games. Theoretical
Computer Science. Elsevier. https://doi.org/10.1016/j.tcs.2012.07.038
chicago: Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” Theoretical
Computer Science. Elsevier, 2012. https://doi.org/10.1016/j.tcs.2012.07.038.
ieee: K. Chatterjee and L. Doyen, “Energy parity games,” Theoretical Computer
Science, vol. 458. Elsevier, pp. 49–60, 2012.
ista: Chatterjee K, Doyen L. 2012. Energy parity games. Theoretical Computer Science.
458, 49–60.
mla: Chatterjee, Krishnendu, and Laurent Doyen. “Energy Parity Games.” Theoretical
Computer Science, vol. 458, Elsevier, 2012, pp. 49–60, doi:10.1016/j.tcs.2012.07.038.
short: K. Chatterjee, L. Doyen, Theoretical Computer Science 458 (2012) 49–60.
date_created: 2018-12-11T12:00:37Z
date_published: 2012-11-02T00:00:00Z
date_updated: 2023-02-23T11:45:29Z
day: '02'
ddc:
- '004'
department:
- _id: KrCh
doi: 10.1016/j.tcs.2012.07.038
ec_funded: 1
external_id:
arxiv:
- '1001.5183'
file:
- access_level: open_access
checksum: 719e4a5af5a01ad3f2f7f7f05b3c2b09
content_type: application/pdf
creator: kschuh
date_created: 2019-02-06T11:56:22Z
date_updated: 2020-07-14T12:45:57Z
file_id: '5935'
file_name: 2012_Elsevier_Chatterjee.pdf
file_size: 351271
relation: main_file
file_date_updated: 2020-07-14T12:45:57Z
has_accepted_license: '1'
intvolume: ' 458'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 49 - 60
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: Theoretical Computer Science
publication_status: published
publisher: Elsevier
publist_id: '3736'
pubrep_id: '935'
quality_controlled: '1'
related_material:
record:
- id: '3851'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Energy parity games
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 458
year: '2012'
...
---
_id: '2967'
abstract:
- lang: eng
text: For programs whose data variables range over Boolean or finite domains, program
verification is decidable, and this forms the basis of recent tools for software
model checking. In this article, we consider algorithmic verification of programs
that use Boolean variables, and in addition, access a single read-only array whose
length is potentially unbounded, and whose elements range over an unbounded data
domain. We show that the reachability problem, while undecidable in general, is
(1) PSPACE-complete for programs in which the array-accessing for-loops are not
nested, (2) decidable for a restricted class of programs with doubly nested loops.
The second result establishes connections to automata and logics defining languages
over data words.
acknowledgement: This research was supported in part by the NSF Cybertrust award CNS
0524059, by the European Research Council (ERC) Advanced Investigator Grant QUAREM,
and by the Austrian Science Fund (FWF) project S11402-N23.
article_number: '27'
author:
- first_name: Rajeev
full_name: Alur, Rajeev
last_name: Alur
- first_name: Pavol
full_name: Cerny, Pavol
id: 4DCBEFFE-F248-11E8-B48F-1D18A9856A87
last_name: Cerny
- first_name: Scott
full_name: Weinstein, Scott
last_name: Weinstein
citation:
ama: Alur R, Cerny P, Weinstein S. Algorithmic analysis of array-accessing programs.
ACM Transactions on Computational Logic (TOCL). 2012;13(3). doi:10.1145/2287718.2287727
apa: Alur, R., Cerny, P., & Weinstein, S. (2012). Algorithmic analysis of array-accessing
programs. ACM Transactions on Computational Logic (TOCL). ACM. https://doi.org/10.1145/2287718.2287727
chicago: Alur, Rajeev, Pavol Cerny, and Scott Weinstein. “Algorithmic Analysis of
Array-Accessing Programs.” ACM Transactions on Computational Logic (TOCL).
ACM, 2012. https://doi.org/10.1145/2287718.2287727.
ieee: R. Alur, P. Cerny, and S. Weinstein, “Algorithmic analysis of array-accessing
programs,” ACM Transactions on Computational Logic (TOCL), vol. 13, no.
3. ACM, 2012.
ista: Alur R, Cerny P, Weinstein S. 2012. Algorithmic analysis of array-accessing
programs. ACM Transactions on Computational Logic (TOCL). 13(3), 27.
mla: Alur, Rajeev, et al. “Algorithmic Analysis of Array-Accessing Programs.” ACM
Transactions on Computational Logic (TOCL), vol. 13, no. 3, 27, ACM, 2012,
doi:10.1145/2287718.2287727.
short: R. Alur, P. Cerny, S. Weinstein, ACM Transactions on Computational Logic
(TOCL) 13 (2012).
date_created: 2018-12-11T12:00:36Z
date_published: 2012-08-01T00:00:00Z
date_updated: 2023-02-23T12:09:43Z
day: '01'
department:
- _id: ToHe
doi: 10.1145/2287718.2287727
ec_funded: 1
intvolume: ' 13'
issue: '3'
language:
- iso: eng
month: '08'
oa_version: None
project:
- _id: 25EE3708-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '267989'
name: Quantitative Reactive Modeling
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
publication: ACM Transactions on Computational Logic (TOCL)
publication_status: published
publisher: ACM
publist_id: '3748'
quality_controlled: '1'
related_material:
record:
- id: '4403'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Algorithmic analysis of array-accessing programs
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 13
year: '2012'
...
---
_id: '492'
abstract:
- lang: eng
text: 'Background: Characterizing root system architecture (RSA) is essential to
understanding the development and function of vascular plants. Identifying RSA-associated
genes also represents an underexplored opportunity for crop improvement. Software
tools are needed to accelerate the pace at which quantitative traits of RSA are
estimated from images of root networks.Results: We have developed GiA Roots (General
Image Analysis of Roots), a semi-automated software tool designed specifically
for the high-throughput analysis of root system images. GiA Roots includes user-assisted
algorithms to distinguish root from background and a fully automated pipeline
that extracts dozens of root system phenotypes. Quantitative information on each
phenotype, along with intermediate steps for full reproducibility, is returned
to the end-user for downstream analysis. GiA Roots has a GUI front end and a command-line
interface for interweaving the software into large-scale workflows. GiA Roots
can also be extended to estimate novel phenotypes specified by the end-user.Conclusions:
We demonstrate the use of GiA Roots on a set of 2393 images of rice roots representing
12 genotypes from the species Oryza sativa. We validate trait measurements against
prior analyses of this image set that demonstrated that RSA traits are likely
heritable and associated with genotypic differences. Moreover, we demonstrate
that GiA Roots is extensible and an end-user can add functionality so that GiA
Roots can estimate novel RSA traits. In summary, we show that the software can
function as an efficient tool as part of a workflow to move from large numbers
of root images to downstream analysis.'
article_number: '116'
article_processing_charge: No
author:
- first_name: Taras
full_name: Galkovskyi, Taras
last_name: Galkovskyi
- first_name: Yuriy
full_name: Mileyko, Yuriy
last_name: Mileyko
- first_name: Alexander
full_name: Bucksch, Alexander
last_name: Bucksch
- first_name: Brad
full_name: Moore, Brad
last_name: Moore
- first_name: Olga
full_name: Symonova, Olga
id: 3C0C7BC6-F248-11E8-B48F-1D18A9856A87
last_name: Symonova
- first_name: Charles
full_name: Price, Charles
last_name: Price
- first_name: Chrostopher
full_name: Topp, Chrostopher
last_name: Topp
- first_name: Anjali
full_name: Iyer Pascuzzi, Anjali
last_name: Iyer Pascuzzi
- first_name: Paul
full_name: Zurek, Paul
last_name: Zurek
- first_name: Suqin
full_name: Fang, Suqin
last_name: Fang
- first_name: John
full_name: Harer, John
last_name: Harer
- first_name: Philip
full_name: Benfey, Philip
last_name: Benfey
- first_name: Joshua
full_name: Weitz, Joshua
last_name: Weitz
citation:
ama: 'Galkovskyi T, Mileyko Y, Bucksch A, et al. GiA Roots: Software for the high
throughput analysis of plant root system architecture. BMC Plant Biology.
2012;12. doi:10.1186/1471-2229-12-116'
apa: 'Galkovskyi, T., Mileyko, Y., Bucksch, A., Moore, B., Symonova, O., Price,
C., … Weitz, J. (2012). GiA Roots: Software for the high throughput analysis of
plant root system architecture. BMC Plant Biology. BioMed Central. https://doi.org/10.1186/1471-2229-12-116'
chicago: 'Galkovskyi, Taras, Yuriy Mileyko, Alexander Bucksch, Brad Moore, Olga
Symonova, Charles Price, Chrostopher Topp, et al. “GiA Roots: Software for the
High Throughput Analysis of Plant Root System Architecture.” BMC Plant Biology.
BioMed Central, 2012. https://doi.org/10.1186/1471-2229-12-116.'
ieee: 'T. Galkovskyi et al., “GiA Roots: Software for the high throughput
analysis of plant root system architecture,” BMC Plant Biology, vol. 12.
BioMed Central, 2012.'
ista: 'Galkovskyi T, Mileyko Y, Bucksch A, Moore B, Symonova O, Price C, Topp C,
Iyer Pascuzzi A, Zurek P, Fang S, Harer J, Benfey P, Weitz J. 2012. GiA Roots:
Software for the high throughput analysis of plant root system architecture. BMC
Plant Biology. 12, 116.'
mla: 'Galkovskyi, Taras, et al. “GiA Roots: Software for the High Throughput Analysis
of Plant Root System Architecture.” BMC Plant Biology, vol. 12, 116, BioMed
Central, 2012, doi:10.1186/1471-2229-12-116.'
short: T. Galkovskyi, Y. Mileyko, A. Bucksch, B. Moore, O. Symonova, C. Price, C.
Topp, A. Iyer Pascuzzi, P. Zurek, S. Fang, J. Harer, P. Benfey, J. Weitz, BMC
Plant Biology 12 (2012).
date_created: 2018-12-11T11:46:46Z
date_published: 2012-07-26T00:00:00Z
date_updated: 2022-08-25T14:59:17Z
day: '26'
ddc:
- '005'
- '514'
- '516'
doi: 10.1186/1471-2229-12-116
extern: '1'
file:
- access_level: open_access
checksum: 0c629e36acd5f2878ff7dd088d67d494
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:12:35Z
date_updated: 2020-07-14T12:46:35Z
file_id: '4953'
file_name: IST-2018-946-v1+1_2012_Symonova_GiA_Roots.pdf
file_size: 1691436
relation: main_file
file_date_updated: 2020-07-14T12:46:35Z
has_accepted_license: '1'
intvolume: ' 12'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: BMC Plant Biology
publication_status: published
publisher: BioMed Central
publist_id: '7328'
pubrep_id: '946'
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'GiA Roots: Software for the high throughput analysis of plant root system
architecture'
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: 12
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
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: '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: '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: '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: '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: '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'
...
---
_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
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: '3165'
abstract:
- lang: eng
text: Computing the winning set for Büchi objectives in alternating games on graphs
is a central problem in computer aided verification with a large number of applications.
The long standing best known upper bound for solving the problem is Õ(n·m), where
n is the number of vertices and m is the number of edges in the graph. We are
the first to break the Õ(n·m) boundary by presenting a new technique that reduces
the running time to O(n 2). This bound also leads to O(n 2) time algorithms for
computing the set of almost-sure winning vertices for Büchi objectives (1) in
alternating games with probabilistic transitions (improving an earlier bound of
Õ(n·m)), (2) in concurrent graph games with constant actions (improving an earlier
bound of O(n 3)), and (3) in Markov decision processes (improving for m > n
4/3 an earlier bound of O(min(m 1.5, m·n 2/3)). We also show that the same technique
can be used to compute the maximal end-component decomposition of a graph in time
O(n 2), which is an improvement over earlier bounds for m > n 4/3. Finally,
we show how to maintain the winning set for Büchi objectives in alternating games
under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized
time per operation. This is the first dynamic algorithm for this problem.
acknowledgement: 'The research was supported by Austrian Science Fund (FWF) Grant
No P 23499-N23 on Modern Graph Algorithmic Techniques in Formal Verification, Vienna
Science and Technology Fund (WWTF) Grant ICT10-002, FWF NFN Grant No S11407-N23
(RiSE), ERC Start grant (279307: Graph Games), and Microsoft faculty fellows award.'
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'Chatterjee K, Henzinger MH. An O(n2) time algorithm for alternating Büchi
games. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
SIAM; 2012:1386-1399. doi:10.1137/1.9781611973099.109'
apa: 'Chatterjee, K., & Henzinger, M. H. (2012). An O(n2) time algorithm for
alternating Büchi games. In Proceedings of the Annual ACM-SIAM Symposium on
Discrete Algorithms (pp. 1386–1399). Kyoto, Japan: SIAM. https://doi.org/10.1137/1.9781611973099.109'
chicago: Chatterjee, Krishnendu, and Monika H Henzinger. “An O(N2) Time Algorithm
for Alternating Büchi Games.” In Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, 1386–99. SIAM, 2012. https://doi.org/10.1137/1.9781611973099.109.
ieee: K. Chatterjee and M. H. Henzinger, “An O(n2) time algorithm for alternating
Büchi games,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms,
Kyoto, Japan, 2012, pp. 1386–1399.
ista: 'Chatterjee K, Henzinger MH. 2012. An O(n2) time algorithm for alternating
Büchi games. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
SODA: Symposium on Discrete Algorithms, 1386–1399.'
mla: Chatterjee, Krishnendu, and Monika H. Henzinger. “An O(N2) Time Algorithm for
Alternating Büchi Games.” Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms, SIAM, 2012, pp. 1386–99, doi:10.1137/1.9781611973099.109.
short: K. Chatterjee, M.H. Henzinger, in:, Proceedings of the Annual ACM-SIAM Symposium
on Discrete Algorithms, SIAM, 2012, pp. 1386–1399.
conference:
end_date: 2012-01-19
location: Kyoto, Japan
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2012-01-17
date_created: 2018-12-11T12:01:46Z
date_published: 2012-01-01T00:00:00Z
date_updated: 2023-02-23T12:23:35Z
day: '01'
department:
- _id: KrCh
doi: 10.1137/1.9781611973099.109
ec_funded: 1
external_id:
arxiv:
- '1109.5018'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1109.5018
month: '01'
oa: 1
oa_version: None
page: 1386 - 1399
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _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
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_status: published
publisher: SIAM
publist_id: '3519'
pubrep_id: '15'
quality_controlled: '1'
related_material:
record:
- id: '2141'
relation: later_version
status: public
- id: '5379'
relation: earlier_version
status: public
status: public
title: An O(n2) time algorithm for alternating Büchi games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '2956'
abstract:
- lang: eng
text: 'Two-player games on graphs are central in many problems in formal verification
and program analysis such as synthesis and verification of open systems. In this
work we consider solving recursive game graphs (or pushdown game graphs) that
can model the control flow of sequential programs with recursion. While pushdown
games have been studied before with qualitative objectives, such as reachability
and parity objectives, in this work we study for the first time such games with
the most well-studied quantitative objective, namely, mean payoff objectives.
In pushdown games two types of strategies are relevant: (1) global strategies,
that depend on the entire global history; and (2) modular strategies, that have
only local memory and thus do not depend on the context of invocation, but only
on the history of the current invocation of the module. Our main results are as
follows: (1) One-player pushdown games with mean-payoff objectives under global
strategies are decidable in polynomial time. (2) Two-player pushdown games with
mean-payoff objectives under global strategies are undecidable. (3) One-player
pushdown games with mean-payoff objectives under modular strategies are NP-hard.
(4) Two-player pushdown games with mean-payoff objectives under modular strategies
can be solved in NP (i.e., both one-player and two-player pushdown games with
mean-payoff objectives under modular strategies are NP-complete). We also establish
the optimal strategy complexity showing that global strategies for mean-payoff
objectives require infinite memory even in one-player pushdown games; and memoryless
modular strategies are sufficient in two-player pushdown games. Finally we also
show that all the problems have the same computational complexity if the stack
boundedness condition is added, where along with the mean-payoff objective the
player must also ensure that the stack height is bounded.'
acknowledgement: "The research was supported by Austrian Science Fund (FWF) Grant
No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE), ERC Start grant (279307: Graph
Games), Microsoft faculty fellows award, the Israeli Centers of Research Excellence
(ICORE) program, (Center No. 4/11), the RICH Model Toolkit (ICT COST Action IC0901),
and was carried out in partial fulfillment of the requirements for the Ph.D. degree
of the second author.\r\nA Technical Report of this paper is available via internal
link."
article_number: '6280438'
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Yaron
full_name: Velner, Yaron
last_name: Velner
citation:
ama: 'Chatterjee K, Velner Y. Mean payoff pushdown games. In: Proceedings of
the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE;
2012. doi:10.1109/LICS.2012.30'
apa: 'Chatterjee, K., & Velner, Y. (2012). Mean payoff pushdown games. In Proceedings
of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. Dubrovnik,
Croatia : IEEE. https://doi.org/10.1109/LICS.2012.30'
chicago: Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.”
In Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science. IEEE, 2012. https://doi.org/10.1109/LICS.2012.30.
ieee: K. Chatterjee and Y. Velner, “Mean payoff pushdown games,” in Proceedings
of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, Dubrovnik,
Croatia , 2012.
ista: 'Chatterjee K, Velner Y. 2012. Mean payoff pushdown games. Proceedings of
the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic
in Computer Science, 6280438.'
mla: Chatterjee, Krishnendu, and Yaron Velner. “Mean Payoff Pushdown Games.” Proceedings
of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, 6280438,
IEEE, 2012, doi:10.1109/LICS.2012.30.
short: K. Chatterjee, Y. Velner, in:, Proceedings of the 2012 27th Annual ACM/IEEE
Symposium on Logic in Computer Science, IEEE, 2012.
conference:
end_date: 2012-06-28
location: 'Dubrovnik, Croatia '
name: 'LICS: Logic in Computer Science'
start_date: 2012-06-25
date_created: 2018-12-11T12:00:32Z
date_published: 2012-08-23T00:00:00Z
date_updated: 2023-02-23T12:23:30Z
day: '23'
department:
- _id: KrCh
doi: 10.1109/LICS.2012.30
ec_funded: 1
language:
- iso: eng
month: '08'
oa_version: None
project:
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S 11407_N23
name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2587B514-B435-11E9-9278-68D0E5697425
name: Microsoft Research Faculty Fellowship
publication: Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer
Science
publication_status: published
publisher: IEEE
publist_id: '3770'
quality_controlled: '1'
related_material:
record:
- id: '5377'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Mean payoff pushdown games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '5377'
abstract:
- lang: eng
text: 'Two-player games on graphs are central in many problems in formal verification
and program analysis such as synthesis and verification of open systems. In this
work we consider solving recursive game graphs (or pushdown game graphs) that
can model the control flow of sequential programs with recursion. While pushdown
games have been studied before with qualitative objectives, such as reachability
and ω-regular objectives, in this work we study for the first time such games
with the most well-studied quantitative objective, namely, mean-payoff objectives.
In pushdown games two types of strategies are relevant: (1) global strategies,
that depend on the entire global history; and (2) modular strategies, that have
only local memory and thus do not depend on the context of invocation, but only
on the history of the current invocation of the module. Our main results are as
follows: (1) One-player pushdown games with mean-payoff objectives under global
strategies are decidable in polynomial time. (2) Two- player pushdown games with
mean-payoff objectives under global strategies are undecidable. (3) One-player
pushdown games with mean-payoff objectives under modular strategies are NP- hard.
(4) Two-player pushdown games with mean-payoff objectives under modular strategies
can be solved in NP (i.e., both one-player and two-player pushdown games with
mean-payoff objectives under modular strategies are NP-complete). We also establish
the optimal strategy complexity showing that global strategies for mean-payoff
objectives require infinite memory even in one-player pushdown games; and memoryless
modular strategies are sufficient in two- player pushdown games. Finally we also
show that all the problems have the same complexity if the stack boundedness condition
is added, where along with the mean-payoff objective the player must also ensure
that the stack height is bounded.'
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: Yaron
full_name: Velner, Yaron
last_name: Velner
citation:
ama: Chatterjee K, Velner Y. Mean-Payoff Pushdown Games. IST Austria; 2012.
doi:10.15479/AT:IST-2012-0002
apa: Chatterjee, K., & Velner, Y. (2012). Mean-payoff pushdown games.
IST Austria. https://doi.org/10.15479/AT:IST-2012-0002
chicago: Chatterjee, Krishnendu, and Yaron Velner. Mean-Payoff Pushdown Games.
IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0002.
ieee: K. Chatterjee and Y. Velner, Mean-payoff pushdown games. IST Austria,
2012.
ista: Chatterjee K, Velner Y. 2012. Mean-payoff pushdown games, IST Austria, 33p.
mla: Chatterjee, Krishnendu, and Yaron Velner. Mean-Payoff Pushdown Games.
IST Austria, 2012, doi:10.15479/AT:IST-2012-0002.
short: K. Chatterjee, Y. Velner, Mean-Payoff Pushdown Games, IST Austria, 2012.
date_created: 2018-12-12T11:38:59Z
date_published: 2012-07-02T00:00:00Z
date_updated: 2023-02-23T11:05:50Z
day: '02'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2012-0002
file:
- access_level: open_access
checksum: a03c08c1589dbb0c96183a8bcf3ab240
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:54:00Z
date_updated: 2020-07-14T12:46:38Z
file_id: '5522'
file_name: IST-2012-002_IST-2012-0002.pdf
file_size: 592098
relation: main_file
file_date_updated: 2020-07-14T12:46:38Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '33'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '10'
related_material:
record:
- id: '2956'
relation: later_version
status: public
status: public
title: Mean-payoff pushdown games
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...
---
_id: '5378'
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(n3 · m) time as compared to the previous known O(n6)-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.'
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: 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. IST Austria; 2012. doi:10.15479/AT:IST-2012-0001
apa: Chatterjee, K., Chaubal, S., & Kamath, P. (2012). Faster algorithms
for alternating refinement relations. IST Austria. https://doi.org/10.15479/AT:IST-2012-0001
chicago: Chatterjee, Krishnendu, Siddhesh Chaubal, and Pritish Kamath. Faster
Algorithms for Alternating Refinement Relations. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0001.
ieee: K. Chatterjee, S. Chaubal, and P. Kamath, Faster algorithms for alternating
refinement relations. IST Austria, 2012.
ista: Chatterjee K, Chaubal S, Kamath P. 2012. Faster algorithms for alternating
refinement relations, IST Austria, 21p.
mla: Chatterjee, Krishnendu, et al. Faster Algorithms for Alternating Refinement
Relations. IST Austria, 2012, doi:10.15479/AT:IST-2012-0001.
short: K. Chatterjee, S. Chaubal, P. Kamath, Faster Algorithms for Alternating Refinement
Relations, IST Austria, 2012.
date_created: 2018-12-12T11:38:59Z
date_published: 2012-07-04T00:00:00Z
date_updated: 2023-02-23T12:21:38Z
day: '04'
ddc:
- '000'
- '005'
department:
- _id: KrCh
doi: 10.15479/AT:IST-2012-0001
file:
- access_level: open_access
checksum: ec8d1857cc7095d3de5107a0162ced37
content_type: application/pdf
creator: system
date_created: 2018-12-12T11:53:28Z
date_updated: 2020-07-14T12:46:39Z
file_id: '5489'
file_name: IST-2012-0001_IST-2012-0001.pdf
file_size: 394256
relation: main_file
file_date_updated: 2020-07-14T12:46:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '21'
publication_identifier:
issn:
- 2664-1690
publication_status: published
publisher: IST Austria
pubrep_id: '14'
related_material:
record:
- id: '497'
relation: later_version
status: public
status: public
title: Faster algorithms for alternating refinement relations
type: technical_report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...