for Journals by Title or ISSN
for Articles by Keywords
help

Publisher: Springer-Verlag   (Total: 2335 journals)

 A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z  

        1 2 3 4 5 6 7 8 | Last   [Sort by number of followers]   [Restore default list]

Showing 1 - 200 of 2335 Journals sorted alphabetically
3D Research     Hybrid Journal   (Followers: 19, SJR: 0.214, h-index: 10)
4OR: A Quarterly J. of Operations Research     Hybrid Journal   (Followers: 9, SJR: 1.073, h-index: 25)
AAPS J.     Hybrid Journal   (Followers: 16, SJR: 1.192, h-index: 74)
AAPS PharmSciTech     Hybrid Journal   (Followers: 6, SJR: 0.718, h-index: 54)
Abdominal Imaging     Hybrid Journal   (Followers: 16, SJR: 0.723, h-index: 60)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 2, SJR: 0.447, h-index: 12)
Academic Psychiatry     Full-text available via subscription   (Followers: 22, SJR: 0.492, h-index: 32)
Academic Questions     Hybrid Journal   (Followers: 7, SJR: 0.135, h-index: 6)
Accreditation and Quality Assurance: J. for Quality, Comparability and Reliability in Chemical Measurement     Hybrid Journal   (Followers: 26, SJR: 0.378, h-index: 30)
Acoustical Physics     Hybrid Journal   (Followers: 10, SJR: 0.355, h-index: 20)
Acta Analytica     Hybrid Journal   (Followers: 7, SJR: 0.387, h-index: 6)
Acta Applicandae Mathematicae     Hybrid Journal   (Followers: 1, SJR: 0.624, h-index: 34)
Acta Biotheoretica     Hybrid Journal   (Followers: 5, SJR: 0.419, h-index: 25)
Acta Diabetologica     Hybrid Journal   (Followers: 14, SJR: 1.318, h-index: 46)
Acta Endoscopica     Hybrid Journal   (Followers: 1, SJR: 0.113, h-index: 8)
acta ethologica     Hybrid Journal   (Followers: 4, SJR: 0.465, h-index: 23)
Acta Geochimica     Hybrid Journal   (Followers: 3)
Acta Geodaetica et Geophysica     Hybrid Journal   (Followers: 1, SJR: 0.294, h-index: 13)
Acta Geotechnica     Hybrid Journal   (Followers: 6, SJR: 1.818, h-index: 22)
Acta Informatica     Hybrid Journal   (Followers: 5, SJR: 0.524, h-index: 32)
Acta Mathematica     Hybrid Journal   (Followers: 10, SJR: 8.021, h-index: 47)
Acta Mathematica Hungarica     Hybrid Journal   (Followers: 2, SJR: 0.53, h-index: 29)
Acta Mathematica Sinica, English Series     Hybrid Journal   (Followers: 5, SJR: 0.406, h-index: 30)
Acta Mathematica Vietnamica     Hybrid Journal   (SJR: 0.451, h-index: 5)
Acta Mathematicae Applicatae Sinica, English Series     Hybrid Journal   (SJR: 0.22, h-index: 20)
Acta Mechanica     Hybrid Journal   (Followers: 18, SJR: 0.898, h-index: 52)
Acta Mechanica Sinica     Hybrid Journal   (Followers: 4, SJR: 0.426, h-index: 29)
Acta Metallurgica Sinica (English Letters)     Hybrid Journal   (Followers: 5, SJR: 0.525, h-index: 18)
Acta Meteorologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.524, h-index: 14)
Acta Neurochirurgica     Hybrid Journal   (Followers: 7, SJR: 0.833, h-index: 73)
Acta Neurologica Belgica     Hybrid Journal   (SJR: 0.348, h-index: 27)
Acta Neuropathologica     Hybrid Journal   (Followers: 3, SJR: 6.61, h-index: 117)
Acta Oceanologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.295, h-index: 17)
Acta Parasitologica     Hybrid Journal   (Followers: 9, SJR: 0.581, h-index: 28)
Acta Physiologiae Plantarum     Hybrid Journal   (Followers: 2, SJR: 0.551, h-index: 39)
Acta Politica     Hybrid Journal   (Followers: 13, SJR: 0.658, h-index: 20)
adhäsion KLEBEN & DICHTEN     Hybrid Journal   (Followers: 5, SJR: 0.103, h-index: 4)
ADHD Attention Deficit and Hyperactivity Disorders     Hybrid Journal   (Followers: 20, SJR: 0.871, h-index: 15)
Adhesion Adhesives & Sealants     Hybrid Journal   (Followers: 7)
Administration and Policy in Mental Health and Mental Health Services Research     Partially Free   (Followers: 15, SJR: 0.795, h-index: 40)
Adsorption     Hybrid Journal   (Followers: 4, SJR: 0.774, h-index: 52)
Advances in Applied Clifford Algebras     Hybrid Journal   (Followers: 3, SJR: 0.319, h-index: 15)
Advances in Atmospheric Sciences     Hybrid Journal   (Followers: 34, SJR: 0.959, h-index: 44)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 15, SJR: 1.255, h-index: 44)
Advances in Contraception     Hybrid Journal   (Followers: 2)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 48, SJR: 1.113, h-index: 14)
Advances in Gerontology     Partially Free   (Followers: 7, SJR: 0.141, h-index: 3)
Advances in Health Sciences Education     Hybrid Journal   (Followers: 23, SJR: 1.397, h-index: 42)
Advances in Manufacturing     Hybrid Journal   (Followers: 3, SJR: 0.2, h-index: 4)
Advances in Polymer Science     Hybrid Journal   (Followers: 40, SJR: 0.637, h-index: 89)
Advances in Therapy     Hybrid Journal   (Followers: 6, SJR: 0.79, h-index: 44)
Aegean Review of the Law of the Sea and Maritime Law     Hybrid Journal   (Followers: 7)
Aequationes Mathematicae     Hybrid Journal   (Followers: 2, SJR: 0.882, h-index: 23)
Aerobiologia     Hybrid Journal   (Followers: 1, SJR: 0.511, h-index: 36)
Aesthetic Plastic Surgery     Hybrid Journal   (Followers: 8, SJR: 0.821, h-index: 49)
African Archaeological Review     Hybrid Journal   (Followers: 14, SJR: 0.612, h-index: 24)
Afrika Matematika     Hybrid Journal   (Followers: 1, SJR: 0.248, h-index: 6)
AGE     Hybrid Journal   (Followers: 7, SJR: 1.358, h-index: 33)
Ageing Intl.     Hybrid Journal   (Followers: 6, SJR: 0.337, h-index: 10)
Aggiornamenti CIO     Hybrid Journal   (Followers: 1)
Aging Clinical and Experimental Research     Hybrid Journal   (Followers: 3, SJR: 0.529, h-index: 55)
Agricultural Research     Hybrid Journal   (Followers: 3)
Agriculture and Human Values     Hybrid Journal   (Followers: 12, SJR: 1.197, h-index: 49)
Agroforestry Systems     Hybrid Journal   (Followers: 20, SJR: 0.64, h-index: 56)
Agronomy for Sustainable Development     Hybrid Journal   (Followers: 10, SJR: 1.732, h-index: 59)
AI & Society     Hybrid Journal   (Followers: 7, SJR: 0.171, h-index: 19)
AIDS and Behavior     Hybrid Journal   (Followers: 13, SJR: 2.006, h-index: 71)
Air Quality, Atmosphere & Health     Hybrid Journal   (Followers: 2, SJR: 0.706, h-index: 19)
Akupunktur & Aurikulomedizin     Full-text available via subscription   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 2, SJR: 0.566, h-index: 18)
Algebra Universalis     Hybrid Journal   (Followers: 2, SJR: 0.388, h-index: 22)
Algebras and Representation Theory     Hybrid Journal   (Followers: 1, SJR: 0.868, h-index: 20)
Algorithmica     Hybrid Journal   (Followers: 7, SJR: 0.898, h-index: 56)
Allergo J.     Full-text available via subscription   (Followers: 1, SJR: 0.183, h-index: 20)
Allergo J. Intl.     Hybrid Journal   (Followers: 2)
Alpine Botany     Hybrid Journal   (Followers: 3, SJR: 0.729, h-index: 20)
ALTEX : Alternatives to Animal Experimentation     Open Access   (Followers: 3, SJR: 1.392, h-index: 32)
AMBIO     Hybrid Journal   (Followers: 14, SJR: 1.094, h-index: 87)
American J. of Cardiovascular Drugs     Hybrid Journal   (Followers: 10, SJR: 0.864, h-index: 39)
American J. of Community Psychology     Hybrid Journal   (Followers: 24, SJR: 1.237, h-index: 83)
American J. of Criminal Justice     Hybrid Journal   (Followers: 5, SJR: 0.634, h-index: 13)
American J. of Cultural Sociology     Hybrid Journal   (Followers: 11, SJR: 0.283, h-index: 3)
American J. of Dance Therapy     Hybrid Journal   (Followers: 4, SJR: 0.175, h-index: 13)
American J. of Potato Research     Hybrid Journal   (Followers: 2, SJR: 0.558, h-index: 35)
American J. of Psychoanalysis     Hybrid Journal   (Followers: 20, SJR: 0.293, h-index: 13)
American Sociologist     Hybrid Journal   (Followers: 10, SJR: 0.18, h-index: 13)
Amino Acids     Hybrid Journal   (Followers: 8, SJR: 1.362, h-index: 83)
AMS Review     Partially Free   (Followers: 4)
Analog Integrated Circuits and Signal Processing     Hybrid Journal   (Followers: 5, SJR: 0.21, h-index: 37)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 4, SJR: 0.665, h-index: 7)
Analysis in Theory and Applications     Hybrid Journal  
Analysis of Verbal Behavior     Hybrid Journal   (Followers: 4)
Analytical and Bioanalytical Chemistry     Hybrid Journal   (Followers: 32, SJR: 1.096, h-index: 123)
Anatomical Science Intl.     Hybrid Journal   (Followers: 2, SJR: 0.301, h-index: 26)
Angewandte Schmerztherapie und Palliativmedizin     Hybrid Journal  
Angiogenesis     Hybrid Journal   (Followers: 3, SJR: 2.212, h-index: 69)
Animal Cognition     Hybrid Journal   (Followers: 13, SJR: 1.122, h-index: 55)
Annales françaises de médecine d'urgence     Hybrid Journal   (Followers: 1, SJR: 0.156, h-index: 4)
Annales Henri Poincaré     Hybrid Journal   (Followers: 3, SJR: 1.377, h-index: 32)
Annales mathématiques du Québec     Hybrid Journal   (Followers: 4)
Annali dell'Universita di Ferrara     Hybrid Journal   (SJR: 0.504, h-index: 14)
Annali di Matematica Pura ed Applicata     Hybrid Journal   (Followers: 1, SJR: 1.167, h-index: 26)
Annals of Behavioral Medicine     Hybrid Journal   (Followers: 10, SJR: 2.112, h-index: 98)
Annals of Biomedical Engineering     Hybrid Journal   (Followers: 18, SJR: 1.182, h-index: 94)
Annals of Combinatorics     Hybrid Journal   (Followers: 3, SJR: 0.849, h-index: 15)
Annals of Data Science     Hybrid Journal   (Followers: 8)
Annals of Dyslexia     Hybrid Journal   (Followers: 9, SJR: 0.857, h-index: 40)
Annals of Finance     Hybrid Journal   (Followers: 27, SJR: 0.686, h-index: 14)
Annals of Forest Science     Hybrid Journal   (Followers: 4, SJR: 0.929, h-index: 57)
Annals of Global Analysis and Geometry     Hybrid Journal   (Followers: 1, SJR: 1.136, h-index: 23)
Annals of Hematology     Hybrid Journal   (Followers: 13, SJR: 1.117, h-index: 62)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 6, SJR: 0.593, h-index: 42)
Annals of Microbiology     Hybrid Journal   (Followers: 9, SJR: 0.402, h-index: 26)
Annals of Nuclear Medicine     Hybrid Journal   (Followers: 5, SJR: 0.68, h-index: 45)
Annals of Operations Research     Hybrid Journal   (Followers: 8, SJR: 1.186, h-index: 78)
Annals of Regional Science     Hybrid Journal   (Followers: 7, SJR: 0.405, h-index: 42)
Annals of Software Engineering     Hybrid Journal   (Followers: 12)
Annals of Solid and Structural Mechanics     Hybrid Journal   (Followers: 9, SJR: 0.553, h-index: 8)
Annals of Surgical Oncology     Hybrid Journal   (Followers: 11, SJR: 1.902, h-index: 127)
Annals of Telecommunications     Hybrid Journal   (Followers: 7, SJR: 0.315, h-index: 25)
Annals of the Institute of Statistical Mathematics     Hybrid Journal   (Followers: 1, SJR: 0.931, h-index: 31)
Antonie van Leeuwenhoek     Hybrid Journal   (Followers: 5, SJR: 0.992, h-index: 87)
Apidologie     Hybrid Journal   (Followers: 4, SJR: 1.14, h-index: 57)
APOPTOSIS     Hybrid Journal   (Followers: 7, SJR: 1.554, h-index: 87)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2, SJR: 0.354, h-index: 27)
Applications of Mathematics     Hybrid Journal   (Followers: 1, SJR: 0.274, h-index: 20)
Applied Biochemistry and Biotechnology     Hybrid Journal   (Followers: 44, SJR: 0.575, h-index: 80)
Applied Biochemistry and Microbiology     Hybrid Journal   (Followers: 17, SJR: 0.267, h-index: 26)
Applied Categorical Structures     Hybrid Journal   (Followers: 2, SJR: 0.361, h-index: 21)
Applied Composite Materials     Hybrid Journal   (Followers: 45, SJR: 0.705, h-index: 35)
Applied Entomology and Zoology     Partially Free   (Followers: 2, SJR: 0.554, h-index: 34)
Applied Geomatics     Hybrid Journal   (Followers: 3, SJR: 0.323, h-index: 9)
Applied Geophysics     Hybrid Journal   (Followers: 7, SJR: 0.541, h-index: 13)
Applied Intelligence     Hybrid Journal   (Followers: 13, SJR: 0.777, h-index: 43)
Applied Magnetic Resonance     Hybrid Journal   (Followers: 3, SJR: 0.358, h-index: 34)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 4, SJR: 0.955, h-index: 33)
Applied Mathematics - A J. of Chinese Universities     Hybrid Journal   (SJR: 0.275, h-index: 8)
Applied Mathematics and Mechanics     Hybrid Journal   (Followers: 4, SJR: 0.37, h-index: 26)
Applied Microbiology and Biotechnology     Hybrid Journal   (Followers: 61, SJR: 1.262, h-index: 161)
Applied Physics A     Hybrid Journal   (Followers: 8, SJR: 0.535, h-index: 121)
Applied Physics B: Lasers and Optics     Hybrid Journal   (Followers: 22, SJR: 0.983, h-index: 104)
Applied Psychophysiology and Biofeedback     Hybrid Journal   (Followers: 6, SJR: 0.677, h-index: 47)
Applied Research in Quality of Life     Hybrid Journal   (Followers: 10, SJR: 0.288, h-index: 15)
Applied Solar Energy     Hybrid Journal   (Followers: 16, SJR: 0.251, h-index: 6)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 4, SJR: 0.351, h-index: 9)
Aquaculture Intl.     Hybrid Journal   (Followers: 21, SJR: 0.613, h-index: 40)
Aquarium Sciences and Conservation     Hybrid Journal   (Followers: 1)
Aquatic Ecology     Hybrid Journal   (Followers: 31, SJR: 0.646, h-index: 44)
Aquatic Geochemistry     Hybrid Journal   (Followers: 3, SJR: 0.764, h-index: 39)
Aquatic Sciences     Hybrid Journal   (Followers: 12, SJR: 1.172, h-index: 53)
Arabian J. for Science and Engineering     Hybrid Journal   (Followers: 5, SJR: 0.345, h-index: 20)
Arabian J. of Geosciences     Hybrid Journal   (Followers: 1, SJR: 0.417, h-index: 16)
Archaeological and Anthropological Sciences     Hybrid Journal   (Followers: 21, SJR: 1.056, h-index: 15)
Archaeologies     Hybrid Journal   (Followers: 12, SJR: 0.397, h-index: 13)
Archiv der Mathematik     Hybrid Journal   (Followers: 1, SJR: 0.597, h-index: 29)
Archival Science     Hybrid Journal   (Followers: 51, SJR: 0.804, h-index: 22)
Archive for History of Exact Sciences     Hybrid Journal   (Followers: 7, SJR: 0.28, h-index: 15)
Archive for Mathematical Logic     Hybrid Journal   (Followers: 1, SJR: 0.946, h-index: 23)
Archive for Rational Mechanics and Analysis     Hybrid Journal   (SJR: 4.091, h-index: 66)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 4, SJR: 0.865, h-index: 40)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4, SJR: 2.841, h-index: 40)
Archives of Dermatological Research     Hybrid Journal   (Followers: 6, SJR: 0.9, h-index: 65)
Archives of Environmental Contamination and Toxicology     Hybrid Journal   (Followers: 10, SJR: 0.846, h-index: 84)
Archives of Gynecology and Obstetrics     Hybrid Journal   (Followers: 16, SJR: 0.695, h-index: 47)
Archives of Microbiology     Hybrid Journal   (Followers: 8, SJR: 0.702, h-index: 85)
Archives of Orthopaedic and Trauma Surgery     Hybrid Journal   (Followers: 8, SJR: 1.039, h-index: 56)
Archives of Osteoporosis     Hybrid Journal   (Followers: 2, SJR: 1.092, h-index: 13)
Archives of Sexual Behavior     Hybrid Journal   (Followers: 9, SJR: 1.198, h-index: 74)
Archives of Toxicology     Hybrid Journal   (Followers: 16, SJR: 1.595, h-index: 76)
Archives of Virology     Hybrid Journal   (Followers: 4, SJR: 1.086, h-index: 90)
Archives of Women's Mental Health     Hybrid Journal   (Followers: 13, SJR: 1.264, h-index: 50)
Archivio di Ortopedia e Reumatologia     Hybrid Journal  
Archivum Immunologiae et Therapiae Experimentalis     Hybrid Journal   (Followers: 2, SJR: 1.2, h-index: 42)
ArgoSpine News & J.     Hybrid Journal   (SJR: 0.102, h-index: 3)
Argumentation     Hybrid Journal   (Followers: 4, SJR: 0.295, h-index: 18)
Arid Ecosystems     Hybrid Journal   (Followers: 3)
Arkiv för Matematik     Hybrid Journal   (Followers: 1, SJR: 0.948, h-index: 22)
Arnold Mathematical J.     Hybrid Journal   (Followers: 1)
Arthropod-Plant Interactions     Hybrid Journal   (Followers: 2, SJR: 0.797, h-index: 17)
Arthroskopie     Hybrid Journal   (Followers: 1, SJR: 0.145, h-index: 8)
Artificial Intelligence and Law     Hybrid Journal   (Followers: 8, SJR: 0.288, h-index: 25)
Artificial Intelligence Review     Hybrid Journal   (Followers: 15, SJR: 0.948, h-index: 48)
Artificial Life and Robotics     Hybrid Journal   (Followers: 8, SJR: 0.231, h-index: 14)
Asia Europe J.     Hybrid Journal   (Followers: 4, SJR: 0.247, h-index: 9)
Asia Pacific Education Review     Hybrid Journal   (Followers: 9, SJR: 0.371, h-index: 17)
Asia Pacific J. of Management     Hybrid Journal   (Followers: 11, SJR: 1.676, h-index: 50)
Asia-Pacific Education Researcher     Hybrid Journal   (Followers: 11, SJR: 0.353, h-index: 13)
Asia-Pacific Financial Markets     Hybrid Journal   (Followers: 2, SJR: 0.19, h-index: 15)
Asia-Pacific J. of Atmospheric Sciences     Hybrid Journal   (Followers: 20, SJR: 1.006, h-index: 14)
Asian Business & Management     Hybrid Journal   (Followers: 7, SJR: 0.41, h-index: 10)
Asian J. of Business Ethics     Hybrid Journal   (Followers: 7)
Asian J. of Criminology     Hybrid Journal   (Followers: 5, SJR: 0.263, h-index: 8)
AStA Advances in Statistical Analysis     Hybrid Journal   (Followers: 2, SJR: 0.681, h-index: 15)
AStA Wirtschafts- und Sozialstatistisches Archiv     Hybrid Journal   (Followers: 5, SJR: 0.195, h-index: 5)
ästhetische dermatologie & kosmetologie     Full-text available via subscription  
Astronomy and Astrophysics Review     Hybrid Journal   (Followers: 21, SJR: 4.511, h-index: 44)
Astronomy Letters     Hybrid Journal   (Followers: 19, SJR: 0.58, h-index: 30)
Astronomy Reports     Hybrid Journal   (Followers: 12, SJR: 0.473, h-index: 23)
Astrophysical Bulletin     Hybrid Journal   (Followers: 2, SJR: 0.469, h-index: 11)
Astrophysics     Hybrid Journal   (Followers: 22, SJR: 0.243, h-index: 11)

        1 2 3 4 5 6 7 8 | Last   [Sort by number of followers]   [Restore default list]

Journal Cover Acta Informatica
  [SJR: 0.524]   [H-I: 32]   [5 followers]  Follow
    
   Hybrid Journal Hybrid journal (It can contain Open Access articles)
   ISSN (Print) 1432-0525 - ISSN (Online) 0001-5903
   Published by Springer-Verlag Homepage  [2335 journals]
  • A general account of coinduction up-to
    • Authors: Filippo Bonchi; Daniela Petrişan; Damien Pous; Jurriaan Rot
      Pages: 127 - 190
      Abstract: Abstract Bisimulation up-to enhances the coinductive proof method for bisimilarity, providing efficient proof techniques for checking properties of different kinds of systems. We prove the soundness of such techniques in a fibrational setting, building on the seminal work of Hermida and Jacobs. This allows us to systematically obtain up-to techniques not only for bisimilarity but for a large class of coinductive predicates modeled as coalgebras. The fact that bisimulations up to context can be safely used in any language specified by GSOS rules can also be seen as an instance of our framework, using the well-known observation by Turi and Plotkin that such languages form bialgebras. In the second part of the paper, we provide a new categorical treatment of weak bisimilarity on labeled transition systems and we prove the soundness of up-to context for weak bisimulations of systems specified by cool rule formats, as defined by Bloom to ensure congruence of weak bisimilarity. The weak transition systems obtained from such cool rules give rise to lax bialgebras, rather than to bialgebras. Hence, to reach our goal, we extend the categorical framework developed in the first part to an ordered setting.
      PubDate: 2017-03-01
      DOI: 10.1007/s00236-016-0271-4
      Issue No: Vol. 54, No. 2 (2017)
       
  • Verification of population protocols
    • Authors: Javier Esparza; Pierre Ganty; Jérôme Leroux; Rupak Majumdar
      Pages: 191 - 215
      Abstract: Abstract Population protocols (Angluin et al. in PODC, 2004) are a formal model of sensor networks consisting of identical mobile devices. Two devices can interact and thereby change their states. Computations are infinite sequences of interactions satisfying a strong fairness constraint. A population protocol is well specified if for every initial configuration C of devices, and every computation starting at C, all devices eventually agree on a consensus value depending only on C. If a protocol is well specified, then it is said to compute the predicate that assigns to each initial configuration its consensus value. While the computational power of well-specified protocols has been extensively studied, the two basic verification problems remain open: Is a given protocol well specified? Does a given protocol compute a given predicate? We prove that both problems are decidable by reduction to the reachability problem of Petri nets. We also give a new proof of the fact that the predicates computed by well-defined protocols are those definable in Presburger arithmetic (Angluin et al. in PODC, 2006).
      PubDate: 2017-03-01
      DOI: 10.1007/s00236-016-0272-3
      Issue No: Vol. 54, No. 2 (2017)
       
  • Reactive synthesis without regret
    • Authors: Paul Hunter; Guillermo A. Pérez; Jean-François Raskin
      Pages: 3 - 39
      Abstract: Abstract Two-player zero-sum games of infinite duration and their quantitative versions are used in verification to model the interaction between a controller (Eve) and its environment (Adam). The question usually addressed is that of the existence (and computability) of a strategy for Eve that can maximize her payoff against any strategy of Adam. In this work, we are interested in strategies of Eve that minimize her regret, i.e. strategies that minimize the difference between her actual payoff and the payoff she could have achieved if she had known the strategy of Adam in advance. We give algorithms to compute the strategies of Eve that ensure minimal regret against an adversary whose choice of strategy is (1) unrestricted, (2) limited to positional strategies, or (3) limited to word strategies, and show that the two last cases have natural modelling applications. These results apply for quantitative games defined with the classical payoff functions \(\mathsf {Inf}\) , \(\mathsf {Sup}\) , \({\mathsf {LimInf}}\) , \(\mathsf {LimSup}\) , and mean-payoff. We also show that our notion of regret minimization in which Adam is limited to word strategies generalizes the notion of good for games introduced by Henzinger and Piterman, and is related to the notion of determinization by pruning due to Aminof, Kupferman and Lampert.
      PubDate: 2017-02-01
      DOI: 10.1007/s00236-016-0268-z
      Issue No: Vol. 54, No. 1 (2017)
       
  • Assume-admissible synthesis
    • Authors: Romain Brenguier; Jean-François Raskin; Ocan Sankur
      Pages: 41 - 83
      Abstract: In this paper, we introduce a novel rule for synthesis of reactive systems, applicable to systems made of n components which have each their own objectives. This rule is based on the notion of admissible strategies. We compare this rule with previous rules defined in the literature, and show that contrary to the previous proposals, it defines sets of solutions which are rectangular. This property leads to solutions which are robust and resilient, and allows one to synthesize strategies separately for each agent. We provide algorithms with optimal complexity and also an abstraction framework compatible with the new rule.
      PubDate: 2017-02-01
      DOI: 10.1007/s00236-016-0273-2
      Issue No: Vol. 54, No. 1 (2017)
       
  • Pseudopolynomial iterative algorithm to solve total-payoff games and
           min-cost reachability games
    • Authors: Thomas Brihaye; Gilles Geeraerts; Axel Haddad; Benjamin Monmege
      Pages: 85 - 125
      Abstract: Abstract Quantitative games are two-player zero-sum games played on directed weighted graphs. Total-payoff games—that can be seen as a refinement of the well-studied mean-payoff games—are the variant where the payoff of a play is computed as the sum of the weights. Our aim is to describe the first pseudo-polynomial time algorithm for total-payoff games in the presence of arbitrary weights. It consists of a non-trivial application of the value iteration paradigm. Indeed, it requires to study, as a milestone, a refinement of these games, called min-cost reachability games, where we add a reachability objective to one of the players. For these games, we give an efficient value iteration algorithm to compute the values and optimal strategies (when they exist), that runs in pseudo-polynomial time. We also propose heuristics to speed up the computations.
      PubDate: 2017-02-01
      DOI: 10.1007/s00236-016-0276-z
      Issue No: Vol. 54, No. 1 (2017)
       
  • Algorithms for monitoring real-time properties
    • Authors: David Basin; Felix Klaedtke; Eugen Zălinescu
      Abstract: Abstract Real-time logics are popular specification languages for reasoning about systems intended to meet timing constraints. Numerous formalisms have been proposed with different underlying time models that can be characterized along two dimensions: dense versus discrete time and point-based versus interval-based. We present monitoring algorithms for the past-only fragment of metric temporal logics that differ along these two dimensions, analyze their complexity, and compare them on a class of formulas for which the point-based and the interval-based settings coincide. Our comparison reveals similarities and differences between the monitoring algorithms and highlights key concepts underlying our and prior monitoring algorithms. For example, point-based algorithms are conceptually simpler and more efficient than interval-based ones as they are invoked only at time points occurring in the monitored trace and their reasoning is limited to just those time points.
      PubDate: 2017-03-03
      DOI: 10.1007/s00236-017-0295-4
       
  • A theory of formal synthesis via inductive learning
    • Authors: Susmit Jha; Sanjit A. Seshia
      Abstract: Abstract Formal synthesis is the process of generating a program satisfying a high-level formal specification. In recent times, effective formal synthesis methods have been proposed based on the use of inductive learning. We refer to this class of methods that learn programs from examples as formal inductive synthesis. In this paper, we present a theoretical framework for formal inductive synthesis. We discuss how formal inductive synthesis differs from traditional machine learning. We then describe oracle-guided inductive synthesis (OGIS), a framework that captures a family of synthesizers that operate by iteratively querying an oracle. An instance of OGIS that has had much practical impact is counterexample-guided inductive synthesis (CEGIS). We present a theoretical characterization of CEGIS for learning any program that computes a recursive language. In particular, we analyze the relative power of CEGIS variants where the types of counterexamples generated by the oracle varies. We also consider the impact of bounded versus unbounded memory available to the learning algorithm. In the special case where the universe of candidate programs is finite, we relate the speed of convergence to the notion of teaching dimension studied in machine learning theory. Altogether, the results of the paper take a first step towards a theoretical foundation for the emerging field of formal inductive synthesis.
      PubDate: 2017-02-15
      DOI: 10.1007/s00236-017-0294-5
       
  • A core calculus for dynamic delta-oriented programming
    • Authors: Ferruccio Damiani; Luca Padovani; Ina Schaefer; Christoph Seidl
      Abstract: Abstract Delta-oriented programming (DOP) is a flexible approach to the implementation of software product lines (SPLs). Delta-oriented SPLs consist of a code base (a set of delta modules encapsulating changes to object-oriented programs) and a product line declaration (providing the connection of the delta modules with the product features). In this paper, we present a core calculus that extends DOP with the capability to switch the implemented product configuration at runtime. A dynamic delta-oriented SPL is a delta-oriented SPL with a dynamic reconfiguration graph that specifies how to switch between different feature configurations. Dynamic DOP supports also (unanticipated) software evolution such that at runtime, the product line declaration, the code base and the dynamic reconfiguration graph can be changed in any (unanticipated) way that preserves the currently running product, which is essential when evolution affects existing features. The type system of our dynamic DOP core calculus ensures that the dynamic reconfigurations lead to type safe products and do not cause runtime type errors.
      PubDate: 2017-01-31
      DOI: 10.1007/s00236-017-0293-6
       
  • Special issue: Selected papers from the 26th International Conference on
           Concurrency Theory (CONCUR 2015)
    • Authors: Luca Aceto; David de Frutos Escrig
      PubDate: 2017-01-19
      DOI: 10.1007/s00236-017-0292-7
       
  • Descending chains and narrowing on template abstract domains
    • Authors: Gianluca Amato; Simone Di Nardo Di Maio; Maria Chiara Meo; Francesca Scozzari
      Abstract: A static analysis by abstract interpretation is typically composed of an ascending phase followed by a descending one. The descending phase is used to improve the precision of the analysis after that a post-fixpoint has been reached. Termination is often guaranteed by using narrowing operators, especially on numerical domains which are generally endowed with infinite descending chains. Under the hypothesis of dealing with reducible flow graphs, we provide an abstract semantics which improves the analysis precision and we show that, for a large class of numerical abstract domains over integer variables (such as intervals, octagons, template parallelotopes and template polyhedra), infinite descending chains cannot arise and we can safely omit narrowing. The abstract semantics is a slight variation of the standard one and can be easily implemented. We also provide an acceleration procedure which ensures termination of the descending phase without narrowing even with non-reducible graphs. Finally, we propose a new family of weak narrowing operators for real variables which improve the analysis precision.
      PubDate: 2017-01-04
      DOI: 10.1007/s00236-016-0291-0
       
  • Characteristic bisimulation for higher-order session processes
    • Authors: Dimitrios Kouzapas; Jorge A. Pérez; Nobuko Yoshida
      Abstract: Abstract For higher-order (process) languages, characterising contextual equivalence is a long-standing issue. In the setting of a higher-order \(\pi \) -calculus with session types, we develop characteristic bisimilarity, a typed bisimilarity which fully characterises contextual equivalence. To our knowledge, ours is the first characterisation of its kind. Using simple values inhabiting (session) types, our approach distinguishes from untyped methods for characterising contextual equivalence in higher-order processes: we show that observing as inputs only a precise finite set of higher-order values suffices to reason about higher-order session processes. We demonstrate how characteristic bisimilarity can be used to justify optimisations in session protocols with mobile code communication.
      PubDate: 2016-12-24
      DOI: 10.1007/s00236-016-0289-7
       
  • Reachability analysis of reversal-bounded automata on
           series–parallel graphs
    • Authors: Rayna Dimitrova; Rupak Majumdar
      Abstract: Abstract Extensions to finite-state automata on strings, such as multi-head automata or multi-counter automata, have been successfully used to encode many infinite-state non-regular verification problems. In this paper, we consider a generalization of automata-theoretic infinite-state verification from strings to labelled series–parallel graphs. We define a model of non-deterministic, 2-way, concurrent automata working on series–parallel graphs and communicating through shared registers on the nodes of the graph. We consider the following verification problem: given a family of series–parallel graphs described by a context-free graph transformation system (GTS), and a concurrent automaton over series–parallel graphs, is some graph generated by the GTS accepted by the automaton? The general problem is undecidable already for (one-way) multi-head automata over strings. We show that a bounded version, where the automata make a fixed number of reversals along the graph and use a fixed number of shared registers is decidable, even though there is no bound on the sizes of series–parallel graphs generated by the GTS. Our decidability result is based on establishing that the number of context switches can be bounded and on an encoding of the computation of bounded concurrent automata that allows us to reduce the reachability problem to the emptiness problem for pushdown automata.
      PubDate: 2016-12-18
      DOI: 10.1007/s00236-016-0290-1
       
  • Dynamic Bayesian networks for formal verification of structured stochastic
           processes
    • Authors: Sadegh Esmaeil Zadeh Soudjani; Alessandro Abate; Rupak Majumdar
      Abstract: We study the problem of finite-horizon probabilistic invariance for discrete-time Markov processes over general (uncountable) state spaces. We compute discrete-time, finite-state Markov chains as formal abstractions of the given Markov processes. Our abstraction differs from existing approaches in two ways: first, we exploit the structure of the underlying Markov process to compute the abstraction separately for each dimension; second, we employ dynamic Bayesian networks (DBN) as compact representations of the abstraction. In contrast, approaches which represent and store the (exponentially large) Markov chain explicitly incur significantly higher memory requirements. In our experiments, explicit representations scaled to models of dimension less than half the size as those analyzable by DBN representations. We show how to construct a DBN abstraction of a Markov process satisfying an independence assumption on the driving process noise. We compute a guaranteed bound on the error in the abstraction w.r.t. the probabilistic invariance property—the dimension-dependent abstraction makes the error bounds more precise than existing approaches. Additionally, we show how factor graphs and the sum-product algorithm for DBNs can be used to solve the finite-horizon probabilistic invariance problem. Together, DBN-based representations and algorithms can be significantly more efficient than explicit representations of Markov chains for abstracting and model checking structured Markov processes.
      PubDate: 2016-12-03
      DOI: 10.1007/s00236-016-0287-9
       
  • Big data interpolation using functional representation
    • Authors: Hadassa Daltrophe; Shlomi Dolev; Zvi Lotker
      Abstract: Given a large set of measurement data, in order to identify a simple function that captures the essence of the data, we suggest representing the data by an abstract function, in particular by polynomials. We interpolate the datapoints to define a polynomial that would represent the data succinctly. The interpolation is challenging, since in practice the data can be noisy and even Byzantine where the Byzantine data represents an adversarial value that is not limited to being close to the correct measured data. We present two solutions, one that extends the Welch-Berlekamp technique (Error correction for algebraic block codes, 1986) to eliminate the outliers appearance in the case of multidimensional data, and copes with discrete noise and Byzantine data; and the other solution is based on Arora and Khot (J Comput Syst Sci 67(2):325–340, 2003) method which handles noisy data, and we have generalized it in the case of multidimensional noisy and Byzantine data.
      PubDate: 2016-11-28
      DOI: 10.1007/s00236-016-0288-8
       
  • A new bound for the D0L language equivalence problem
    • Authors: Juha Honkala
      Abstract: Abstract We study the language equivalence problem for smooth and loop-free D0L systems. We show that the number of initial terms in the associated D0L sequences we have to consider to decide language equivalence depends only on the cardinality of the underlying alphabet.
      PubDate: 2016-11-24
      DOI: 10.1007/s00236-016-0286-x
       
  • The complexity of counting models of linear-time temporal logic
    • Authors: Hazem Torfah; Martin Zimmermann
      Abstract: Abstract We determine the complexity of counting models of bounded size of specifications expressed in linear-time temporal logic. Counting word-models is #P-complete, if the bound is given in unary, and as hard as counting accepting runs of nondeterministic polynomial space Turing machines, if the bound is given in binary. Counting tree-models is as hard as counting accepting runs of nondeterministic exponential time Turing machines, if the bound is given in unary. For a binary encoding of the bound, the problem is at least as hard as counting accepting runs of nondeterministic exponential space Turing machines, and not harder than counting accepting runs of nondeterministic doubly-exponential time Turing machines. Finally, counting arbitrary transition systems satisfying a formula is #P-hard and not harder than counting accepting runs of nondeterministic polynomial time Turing machines with a PSPACE oracle, if the bound is given in unary. If the bound is given in binary, then counting arbitrary models is as hard as counting accepting runs of nondeterministic exponential time Turing machines.
      PubDate: 2016-11-17
      DOI: 10.1007/s00236-016-0284-z
       
  • Multiparty session types as coherence proofs
    • Authors: Marco Carbone; Fabrizio Montesi; Carsten Schürmann; Nobuko Yoshida
      Abstract: Abstract We propose a Curry–Howard correspondence between a language for programming multiparty sessions and a generalisation of Classical Linear Logic (CLL). In this framework, propositions correspond to the local behaviour of a participant in a multiparty session type, proofs to processes, and proof normalisation to executing communications. Our key contribution is generalising duality, from CLL, to a new notion of n-ary compatibility, called coherence. Building on coherence as a principle of compositionality, we generalise the cut rule of CLL to a new rule for composing many processes communicating in a multiparty session. We prove the soundness of our model by showing the admissibility of our new rule, which entails deadlock-freedom via our correspondence.
      PubDate: 2016-11-16
      DOI: 10.1007/s00236-016-0285-y
       
  • Online edge coloring of paths and trees with a fixed number of colors
    • Abstract: Abstract We study a version of online edge coloring, where the goal is to color as many edges as possible using only a given number, k, of available colors. All of our results are with regard to competitive analysis. Previous attempts to identify optimal algorithms for this problem have failed, even for bipartite graphs. Thus, in this paper, we analyze even more restricted graph classes, paths and trees. For paths, we consider \(k=2\) , and for trees, we consider any \(k \ge 2\) . We prove that a natural greedy algorithm called \({\textsc {First-Fit}}\) is optimal among deterministic algorithms, on paths as well as trees. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. For trees, we prove that to obtain a better competitive ratio than \({\textsc {First-Fit}}\) , the algorithm would have to be both randomized and unfair (i.e., reject edges that could have been colored), and even such algorithms cannot be much better than \({\textsc {First-Fit}}\) .
      PubDate: 2016-11-02
      DOI: 10.1007/s00236-016-0283-0
       
  • Conjunctive query containment over trees using schema information
    • Authors: Henrik Björklund; Wim Martens; Thomas Schwentick
      Abstract: Abstract We study the containment, satisfiability, and validity problems for conjunctive queries over trees with respect to a schema. We show that conjunctive query containment and validity are 2EXPTIME -complete with respect to a schema, in both cases where the schema is given as a DTD or as a tree automaton. Furthermore, we show that satisfiability for conjunctive queries with respect to a schema can be decided in NP . The problem is NP -hard already for queries using only one kind of axis. Finally, we consider conjunctive queries that can test for equalities and inequalities of data values. Here, satisfiability and validity are decidable, but containment is undecidable, even without schema information. On the other hand, containment with respect to a schema becomes decidable again if the “larger” query is not allowed to use both equalities and inequalities.
      PubDate: 2016-10-18
      DOI: 10.1007/s00236-016-0282-1
       
  • Parameterized linear temporal logics meet costs: still not costlier than
           LTL
    • Authors: Martin Zimmermann
      Abstract: Abstract We continue the investigation of parameterized extensions of linear temporal logic (LTL) that retain the attractive algorithmic properties of LTL: a polynomial space model checking algorithm and a doubly-exponential time algorithm for solving games. Alur et al. and Kupferman et al. showed that this is the case for parametric LTL (PLTL) and PROMPT-LTL respectively, which have temporal operators equipped with variables that bound their scope in time. Later, this was also shown to be true for parametric LDL (PLDL), which extends PLTL to be able to express all \(\omega \) -regular properties. Here, we generalize PLTL to systems with costs, i.e., we do not bound the scope of operators in time, but bound the scope in terms of the cost accumulated during time. Again, we show that model checking and solving games for specifications in PLTL with costs is not harder than the corresponding problems for LTL. Finally, we discuss PLDL with costs and extensions to multiple cost functions.
      PubDate: 2016-10-13
      DOI: 10.1007/s00236-016-0279-9
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
Home (Search)
Subjects A-Z
Publishers A-Z
Customise
APIs
Your IP address: 54.204.83.136
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016