for Journals by Title or ISSN
for Articles by Keywords
help

Publisher: Springer-Verlag (Total: 2355 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 2355 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: 10, SJR: 1.073, h-index: 25)
AAPS J.     Hybrid Journal   (Followers: 22, SJR: 1.192, h-index: 74)
AAPS PharmSciTech     Hybrid Journal   (Followers: 7, SJR: 0.718, h-index: 54)
Abdominal Imaging     Hybrid Journal   (Followers: 14, SJR: 0.723, h-index: 60)
Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg     Hybrid Journal   (Followers: 3, SJR: 0.447, h-index: 12)
Academic Psychiatry     Full-text available via subscription   (Followers: 23, SJR: 0.492, h-index: 32)
Academic Questions     Hybrid Journal   (Followers: 8, 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: 11, SJR: 0.355, h-index: 20)
Acoustics Australia     Hybrid Journal  
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: 4, SJR: 0.419, h-index: 25)
Acta Diabetologica     Hybrid Journal   (Followers: 15, 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: 6)
Acta Geodaetica et Geophysica     Hybrid Journal   (Followers: 2, SJR: 0.294, h-index: 13)
Acta Geotechnica     Hybrid Journal   (Followers: 7, SJR: 1.818, h-index: 22)
Acta Informatica     Hybrid Journal   (Followers: 5, SJR: 0.524, h-index: 32)
Acta Mathematica     Hybrid Journal   (Followers: 11, 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: 6, 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: 20, SJR: 0.898, h-index: 52)
Acta Mechanica Sinica     Hybrid Journal   (Followers: 5, 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: 6, SJR: 0.833, h-index: 73)
Acta Neurologica Belgica     Hybrid Journal   (Followers: 1, SJR: 0.348, h-index: 27)
Acta Neuropathologica     Hybrid Journal   (Followers: 5, SJR: 6.61, h-index: 117)
Acta Oceanologica Sinica     Hybrid Journal   (Followers: 3, SJR: 0.295, h-index: 17)
Acta Parasitologica     Hybrid Journal   (Followers: 10, 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)
Activitas Nervosa Superior     Hybrid Journal  
adhäsion KLEBEN & DICHTEN     Hybrid Journal   (Followers: 5, SJR: 0.103, h-index: 4)
ADHD Attention Deficit and Hyperactivity Disorders     Hybrid Journal   (Followers: 22, SJR: 0.871, h-index: 15)
Adhesion Adhesives & Sealants     Hybrid Journal   (Followers: 8)
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: 35, SJR: 0.959, h-index: 44)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 18, SJR: 1.255, h-index: 44)
Advances in Contraception     Hybrid Journal   (Followers: 3)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 52, SJR: 1.113, h-index: 14)
Advances in Gerontology     Partially Free   (Followers: 8, SJR: 0.141, h-index: 3)
Advances in Health Sciences Education     Hybrid Journal   (Followers: 25, 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: 41, SJR: 0.637, h-index: 89)
Advances in Therapy     Hybrid Journal   (Followers: 5, 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: 2, SJR: 0.511, h-index: 36)
Aesthetic Plastic Surgery     Hybrid Journal   (Followers: 9, SJR: 0.821, h-index: 49)
African Archaeological Review     Hybrid Journal   (Followers: 16, 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: 7, 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: 13, SJR: 1.197, h-index: 49)
Agroforestry Systems     Hybrid Journal   (Followers: 19, SJR: 0.64, h-index: 56)
Agronomy for Sustainable Development     Hybrid Journal   (Followers: 11, SJR: 1.732, h-index: 59)
AI & Society     Hybrid Journal   (Followers: 6, 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: 3, SJR: 0.706, h-index: 19)
Akupunktur & Aurikulomedizin     Full-text available via subscription   (Followers: 1)
Algebra and Logic     Hybrid Journal   (Followers: 4, 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: 8, 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: 5, 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: 15, SJR: 1.094, h-index: 87)
American J. of Cardiovascular Drugs     Hybrid Journal   (Followers: 16, SJR: 0.864, h-index: 39)
American J. of Community Psychology     Hybrid Journal   (Followers: 26, SJR: 1.237, h-index: 83)
American J. of Criminal Justice     Hybrid Journal   (Followers: 8, SJR: 0.634, h-index: 13)
American J. of Cultural Sociology     Hybrid Journal   (Followers: 15, 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: 22, SJR: 0.293, h-index: 13)
American Sociologist     Hybrid Journal   (Followers: 14, 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: 7, SJR: 0.21, h-index: 37)
Analysis and Mathematical Physics     Hybrid Journal   (Followers: 3, SJR: 0.665, h-index: 7)
Analysis in Theory and Applications     Hybrid Journal   (Followers: 1)
Analysis of Verbal Behavior     Hybrid Journal   (Followers: 5)
Analytical and Bioanalytical Chemistry     Hybrid Journal   (Followers: 30, 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: 16, 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: 13, 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: 11)
Annals of Dyslexia     Hybrid Journal   (Followers: 10, SJR: 0.857, h-index: 40)
Annals of Finance     Hybrid Journal   (Followers: 28, SJR: 0.686, h-index: 14)
Annals of Forest Science     Hybrid Journal   (Followers: 6, 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: 16, SJR: 1.117, h-index: 62)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 12, SJR: 0.593, h-index: 42)
Annals of Microbiology     Hybrid Journal   (Followers: 10, SJR: 0.402, h-index: 26)
Annals of Nuclear Medicine     Hybrid Journal   (Followers: 4, SJR: 0.68, h-index: 45)
Annals of Operations Research     Hybrid Journal   (Followers: 10, SJR: 1.186, h-index: 78)
Annals of Ophthalmology     Hybrid Journal   (Followers: 12)
Annals of Regional Science     Hybrid Journal   (Followers: 8, SJR: 0.405, h-index: 42)
Annals of Software Engineering     Hybrid Journal   (Followers: 13)
Annals of Solid and Structural Mechanics     Hybrid Journal   (Followers: 10, SJR: 0.553, h-index: 8)
Annals of Surgical Oncology     Hybrid Journal   (Followers: 14, SJR: 1.902, h-index: 127)
Annals of Telecommunications     Hybrid Journal   (Followers: 8, 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: 8, 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: 42, SJR: 0.575, h-index: 80)
Applied Biochemistry and Microbiology     Hybrid Journal   (Followers: 16, SJR: 0.267, h-index: 26)
Applied Cancer Research     Open Access  
Applied Categorical Structures     Hybrid Journal   (Followers: 2, SJR: 0.361, h-index: 21)
Applied Composite Materials     Hybrid Journal   (Followers: 48, SJR: 0.705, h-index: 35)
Applied Entomology and Zoology     Partially Free   (Followers: 3, SJR: 0.554, h-index: 34)
Applied Geomatics     Hybrid Journal   (Followers: 4, SJR: 0.323, h-index: 9)
Applied Geophysics     Hybrid Journal   (Followers: 8, SJR: 0.541, h-index: 13)
Applied Intelligence     Hybrid Journal   (Followers: 11, SJR: 0.777, h-index: 43)
Applied Magnetic Resonance     Hybrid Journal   (Followers: 4, SJR: 0.358, h-index: 34)
Applied Mathematics & Optimization     Hybrid Journal   (Followers: 6, 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: 5, SJR: 0.37, h-index: 26)
Applied Microbiology and Biotechnology     Hybrid Journal   (Followers: 62, 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: 24, SJR: 0.983, h-index: 104)
Applied Psychophysiology and Biofeedback     Hybrid Journal   (Followers: 8, SJR: 0.677, h-index: 47)
Applied Research in Quality of Life     Hybrid Journal   (Followers: 11, SJR: 0.288, h-index: 15)
Applied Solar Energy     Hybrid Journal   (Followers: 18, SJR: 0.251, h-index: 6)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 5, SJR: 0.351, h-index: 9)
Aquaculture Intl.     Hybrid Journal   (Followers: 22, SJR: 0.613, h-index: 40)
Aquarium Sciences and Conservation     Hybrid Journal   (Followers: 1)
Aquatic Ecology     Hybrid Journal   (Followers: 32, SJR: 0.646, h-index: 44)
Aquatic Geochemistry     Hybrid Journal   (Followers: 4, SJR: 0.764, h-index: 39)
Aquatic Sciences     Hybrid Journal   (Followers: 13, 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: 23, 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: 56, SJR: 0.804, h-index: 22)
Archive for History of Exact Sciences     Hybrid Journal   (Followers: 8, 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: 5, SJR: 0.865, h-index: 40)
Archives and Museum Informatics     Hybrid Journal   (Followers: 138)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4, SJR: 2.841, h-index: 40)
Archives of Dermatological Research     Hybrid Journal   (Followers: 7, SJR: 0.9, h-index: 65)
Archives of Environmental Contamination and Toxicology     Hybrid Journal   (Followers: 13, 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: 10, SJR: 1.198, h-index: 74)
Archives of Toxicology     Hybrid Journal   (Followers: 17, SJR: 1.595, h-index: 76)
Archives of Virology     Hybrid Journal   (Followers: 5, SJR: 1.086, h-index: 90)
Archives of Women's Mental Health     Hybrid Journal   (Followers: 14, 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: 5, 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: 11, SJR: 0.288, h-index: 25)
Artificial Intelligence Review     Hybrid Journal   (Followers: 14, 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: 5, SJR: 0.247, h-index: 9)
Asia Pacific Education Review     Hybrid Journal   (Followers: 12, SJR: 0.371, h-index: 17)
Asia Pacific J. of Management     Hybrid Journal   (Followers: 16, SJR: 1.676, h-index: 50)
Asia-Pacific Education Researcher     Hybrid Journal   (Followers: 12, 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: 8, SJR: 0.41, h-index: 10)
Asian J. of Business Ethics     Hybrid Journal   (Followers: 8)
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  

        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  [2355 journals]
  • Sparsification and subexponential approximation
    • Authors: Édouard Bonnet; Vangelis Th. Paschos
      Pages: 1 - 15
      Abstract: Instance sparsification is well-known in the world of exact computation since it is very closely linked to the Exponential Time Hypothesis. In this paper, we extend the concept of sparsification in order to capture subexponential time approximation. We develop a new tool for inapproximability, called approximation preserving sparsification, and use it in order to get strong inapproximability results in subexponential time for several fundamental optimization problems such as min dominating set , min feedback vertex set , min set cover, min feedback arc set, and others.
      PubDate: 2018-02-01
      DOI: 10.1007/s00236-016-0281-2
      Issue No: Vol. 55, No. 1 (2018)
       
  • Conjunctive query containment over trees using schema information
    • Authors: Henrik Björklund; Wim Martens; Thomas Schwentick
      Pages: 17 - 56
      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: 2018-02-01
      DOI: 10.1007/s00236-016-0282-1
      Issue No: Vol. 55, No. 1 (2018)
       
  • Online edge coloring of paths and trees with a fixed number of colors
    • Authors: Lene M. Favrholdt; Jesper W. Mikkelsen
      Pages: 57 - 80
      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: 2018-02-01
      DOI: 10.1007/s00236-016-0283-0
      Issue No: Vol. 55, No. 1 (2018)
       
  • A new bound for the D0L language equivalence problem
    • Authors: Juha Honkala
      Pages: 81 - 88
      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: 2018-02-01
      DOI: 10.1007/s00236-016-0286-x
      Issue No: Vol. 55, No. 1 (2018)
       
  • An analysis of the M $$^X$$ X /M/1 queue with multiple working vacations
           by GI/M/1 type Markov process
    • Authors: Hongbo Zhang
      Abstract: In this paper, we analyze an M/M/1 queue with batch arrival and multiple working vacations. We describe the queueing model by a special GI/M/1 type Markov process with infinite phases, and by the matrix analytic method, we not only give the stationary queue length distribution of the model, but also obtain the exact number of vacations completed by the server.
      PubDate: 2018-02-05
      DOI: 10.1007/s00236-018-0316-y
       
  • On path-controlled insertion–deletion systems
    • Authors: Henning Fernau; Lakshmanan Kuppusamy; Indhumathi Raman
      Abstract: A graph-controlled insertion–deletion system is a regulated extension of an insertion–deletion system. It has several components and each component contains some insertion–deletion rules. These components are the vertices of a directed control graph. A transition is performed by any applicable rule in the current component on a string and the resultant string is then moved to the target component specified in the rule. This also describes the arcs of the control graph. Starting from an axiom in the initial component, strings thus move through the control graph. The language of the system is the set of all terminal strings collected in the final component. In this paper, we investigate a variant of the main question in this area: which combinations of size parameters (the maximum number of components, the maximal length of the insertion string, the maximal length of the left context for insertion, the maximal length of the right context for insertion; plus three similar restrictions with respect to deletion) are sufficient to maintain computational completeness of such restricted systems under the additional restriction that the (undirected) control graph is a path' Notice that these results also bear consequences for the domain of insertion–deletion P systems, improving on a number of previous results from the literature, concerning in particular the number of components (membranes) that are necessary for computational completeness results.
      PubDate: 2018-02-05
      DOI: 10.1007/s00236-018-0312-2
       
  • Symbolic checking of Fuzzy CTL on Fuzzy Program Graph
    • Authors: Masoud Ebrahimi; Gholamreza Sotudeh; Ali Movaghar
      Abstract: Few fuzzy temporal logics and modeling formalisms are developed such that their model checking is both effective and efficient. State-space explosion makes model checking of fuzzy temporal logics inefficient. That is because either the modeling formalism itself is not compact, or the verification approach requires an exponentially larger yet intermediate representation of the modeling formalism. To exemplify, Fuzzy Program Graph (FzPG) is a very compact, and powerful formalism to model fuzzy systems; yet, it is required to be translated into an equal Fuzzy Kripke model with an exponential blow-up should it be formally verified. In this paper, we introduce Fuzzy Computation Tree Logic (FzCTL) and its direct symbolic model checking over FzPG that avoids the aforementioned state-space explosion. Considering compactness and readability of FzPG along with expressiveness of FzCTL, we believe the proposed method is applicable in real-world scenarios. Finally, we study formal verification of fuzzy flip-flops to demonstrate capabilities of the proposed method.
      PubDate: 2018-02-03
      DOI: 10.1007/s00236-018-0311-3
       
  • Preface for the special issue GandALF 2015
    • Authors: Javier Esparza; Enrico Tronci
      PubDate: 2018-02-01
      DOI: 10.1007/s00236-018-0315-z
       
  • Petri nets are dioids: a new algebraic foundation for non-deterministic
           net theory
    • Authors: Paolo Baldan; Fabio Gadducci
      Abstract: In a seminal paper Montanari and Meseguer have shown that an algebraic interpretation of Petri nets in terms of commutative monoids can be used to provide an elegant characterisation of the deterministic computations of a net, accounting for their sequential and parallel composition. A smoother and more complete theory for deterministic computations has been later developed by relying on the concept of pre-net, a variation of Petri nets with a non-commutative flavor. This paper shows that, along the same lines, by adding an (idempotent) operation and thus considering dioids (idempotent semirings) rather than just monoids, one can faithfully characterise the non-deterministic computations of a net.
      PubDate: 2018-01-24
      DOI: 10.1007/s00236-018-0314-0
       
  • Special issue of the 21st International Conference on Tools and Algorithms
           for the Construction and Analysis of Systems (TACAS 2015)
    • Authors: Christel Baier; Cesare Tinelli
      Pages: 727 - 728
      PubDate: 2017-12-01
      DOI: 10.1007/s00236-017-0298-1
      Issue No: Vol. 54, No. 8 (2017)
       
  • Approximate counting in SMT and value estimation for probabilistic
           programs
    • Authors: Dmitry Chistikov; Rayna Dimitrova; Rupak Majumdar
      Pages: 729 - 764
      Abstract: #SMT, or model counting for logical theories, is a well-known hard problem that generalizes such tasks as counting the number of satisfying assignments to a Boolean formula and computing the volume of a polytope. In the realm of satisfiability modulo theories (SMT) there is a growing need for model counting solvers, coming from several application domains (quantitative information flow, static analysis of probabilistic programs). In this paper, we show a reduction from an approximate version of #SMT  to SMT. We focus on the theories of integer arithmetic and linear real arithmetic. We propose model counting algorithms that provide approximate solutions with formal bounds on the approximation error. They run in polynomial time and make a polynomial number of queries to the SMT solver for the underlying theory, exploiting “for free” the sophisticated heuristics implemented within modern SMT solvers. We have implemented the algorithms and used them to solve the value problem for a model of loop-free probabilistic programs with nondeterminism.
      PubDate: 2017-12-01
      DOI: 10.1007/s00236-017-0297-2
      Issue No: Vol. 54, No. 8 (2017)
       
  • Model checking the evolution of gene regulatory networks
    • Authors: Mirco Giacobbe; Călin C. Guet; Ashutosh Gupta; Thomas A. Henzinger; Tiago Paixão; Tatjana Petrov
      Pages: 765 - 787
      Abstract: The behaviour of gene regulatory networks (GRNs) is typically analysed using simulation-based statistical testing-like methods. In this paper, we demonstrate that we can replace this approach by a formal verification-like method that gives higher assurance and scalability. We focus on Wagner’s weighted GRN model with varying weights, which is used in evolutionary biology. In the model, weight parameters represent the gene interaction strength that may change due to genetic mutations. For a property of interest, we synthesise the constraints over the parameter space that represent the set of GRNs satisfying the property. We experimentally show that our parameter synthesis procedure computes the mutational robustness of GRNs—an important problem of interest in evolutionary biology—more efficiently than the classical simulation method. We specify the property in linear temporal logic. We employ symbolic bounded model checking and SMT solving to compute the space of GRNs that satisfy the property, which amounts to synthesizing a set of linear constraints on the weights.
      PubDate: 2017-12-01
      DOI: 10.1007/s00236-016-0278-x
      Issue No: Vol. 54, No. 8 (2017)
       
  • Stateless model checking for TSO and PSO
    • Authors: Parosh Aziz Abdulla; Stavros Aronis; Mohamed Faouzi Atig; Bengt Jonsson; Carl Leonardsson; Konstantinos Sagonas
      Pages: 789 - 818
      Abstract: We present a technique for efficient stateless model checking of programs that execute under the relaxed memory models TSO and PSO. The basis for our technique is a novel representation of executions under TSO and PSO, called chronological traces. Chronological traces induce a partial order relation on relaxed memory executions, capturing dependencies that are needed to represent the interaction via shared variables. They are optimal in the sense that they only distinguish computations that are inequivalent under the widely-used representation by Shasha and Snir. This allows an optimal dynamic partial order reduction algorithm to explore a minimal number of executions while still guaranteeing full coverage. We apply our techniques to check, under the TSO and PSO memory models, LLVM assembly produced for C/pthreads programs. Our experiments show that our technique reduces the verification effort for relaxed memory models to be almost that for the standard model of sequential consistency. This article is an extended version of Abdulla et al. (Tools and algorithms for the construction and analysis of systems, Springer, New York, pp 353–367, 2015), appearing in TACAS 2015.
      PubDate: 2017-12-01
      DOI: 10.1007/s00236-016-0275-0
      Issue No: Vol. 54, No. 8 (2017)
       
  • Model-checking iterated games
    • Authors: Chung-Hao Huang; Sven Schewe; Farn Wang
      Pages: 625 - 654
      Abstract: We propose a logic for the definition of the collaborative power of groups of agents to enforce different temporal objectives. The resulting temporal cooperation logic (TCL) extends ATL by allowing for successive definition of strategies for agents and agencies. Different to previous logics with similar aims, our extension cuts a fine line between extending the power and maintaining a low complexity: model checking TCL sentences is EXPTIME complete in the logic, and NL complete in the model. This advancement over nonelementary logics is bought by disallowing a too close entanglement between the cooperation and competition. We show how allowing such an entanglement immediately leads to a nonelementary complexity. We have implemented a model checker for the logic and shown the feasibility of model checking on a few benchmarks.
      PubDate: 2017-11-01
      DOI: 10.1007/s00236-016-0277-y
      Issue No: Vol. 54, No. 7 (2017)
       
  • Safraless LTL synthesis considering maximal realizability
    • Authors: Takashi Tomita; Atsushi Ueno; Masaya Shimakawa; Shigeki Hagihara; Naoki Yonezaki
      Pages: 655 - 692
      Abstract: Linear temporal logic (LTL) synthesis is a formal method for automatically composing a reactive system that realizes a given behavioral specification described in LTL if the specification is realizable. Even if the whole specification is unrealizable, it is preferable to synthesize a best-effort reactive system. That is, a system that maximally realizes its partial specifications. Therefore, we categorized specifications into must specifications (which should never be violated) and desirable specifications (the violation of which may be unavoidable). In this paper, we propose a method for synthesizing a reactive system that realizes all must specifications and strongly endeavors to satisfy each desirable specification. The general form of the desirable specifications without assumptions is \(\mathbf{G }\varphi \) , which means “ \(\varphi \) always holds”. In our approach, the best effort to satisfy \(\mathbf{G }\varphi \) is to maximize the number of steps satisfying \(\varphi \) in the interaction. To quantitatively evaluate the number of steps, we used a mean-payoff objective based on LTL formulae. Our method applies the Safraless approach to construct safety games from given must and desirable specifications, where the must specification can be written in full LTL and may include assumptions. It then transforms the safety games constructed from the desirable specifications into mean-payoff games and finally composes a reactive system as an optimal strategy on a synchronized product of the games.
      PubDate: 2017-11-01
      DOI: 10.1007/s00236-016-0280-3
      Issue No: Vol. 54, No. 7 (2017)
       
  • A theory of formal synthesis via inductive learning
    • Authors: Susmit Jha; Sanjit A. Seshia
      Pages: 693 - 726
      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-11-01
      DOI: 10.1007/s00236-017-0294-5
      Issue No: Vol. 54, No. 7 (2017)
       
  • A first step in characterizing three-element codes
    • Authors: Cao Chunhua; Lu Qing; Yang Di
      Abstract: It is always an interesting subject to investigate whether a three-element language is a code or not. In this paper, we consider a special class of three-element languages, where two words have the same length which is less than the length of the third word. We give a necessary and sufficient condition to state whether a three-element language in this class is a code. This result partially resolves the problem proposed by Professor H. J. Shyr in 1990s.
      PubDate: 2017-11-29
      DOI: 10.1007/s00236-017-0309-2
       
  • Bounded choice-free Petri net synthesis: algorithmic issues
    • Authors: Eike Best; Raymond Devillers; Uli Schlachter
      Abstract: This paper describes a synthesis procedure dedicated to the construction of choice-free Petri nets from finite persistent transition systems, whenever possible. Taking advantage of the properties of choice-free Petri nets, a two-step approach is proposed. A pre-synthesis step checks necessary structural properties of the transition system and constructs some data structures needed for the second step. Then, a minimised set of simplified systems of linear inequalities is distilled from a general region-theoretic approach. This leads to a substantial narrowing of the sets of states for which linear inequalities must be solved, and allows an early detection of failures, supported by constructive error messages. The performance of the resulting algorithm is measured and compared numerically with existing synthesis tools.
      PubDate: 2017-11-20
      DOI: 10.1007/s00236-017-0310-9
       
  • Fast deterministic parsers for transition networks
    • Authors: Angelo Borsotti; Luca Breveglieri; Stefano Crespi Reghizzi; Angelo Morzenti
      Abstract: Extended BNF grammars (EBNF) allow regular expressions in the right parts of their rules. They are widely used to define languages, and can be represented by recursive Transition Networks (TN) consisting of a set of finite-state machines. We present a novel direct construction of efficient shift-reduce ELR(1) parsers for TNs. We show that such a parser works deterministically if the TN is free from the classical shift-reduce and reduce–reduce conflicts of the LR(1) parsers, and from a new conflict type called convergence conflict. Such a novel condition for determinism is proved correct and is more general than those proposed in the past for EBNF grammars or TNs. Such ELR(1) parsers perform fewer shift moves than the equivalent LR(1) parsers. A simple optimization of the reduction moves is described.
      PubDate: 2017-11-04
      DOI: 10.1007/s00236-017-0308-3
       
  • Spanning the spectrum from safety to liveness
    • Authors: Rachel Faran; Orna Kupferman
      Abstract: Of special interest in formal verification are safety specifications, which assert that the system stays within some allowed region, in which nothing “bad” happens. Equivalently, a computation violates a safety specification if it has a “bad prefix”—a prefix all whose extensions violate the specification. The theoretical properties of safety specifications as well as their practical advantages with respect to general specifications have been widely studied. Safety is binary: a specification is either safety or not safety. We introduce a quantitative measure for safety. Intuitively, the safety level of a language L measures the fraction of words not in L that have a bad prefix. In particular, a safety language has safety level 1 and a liveness language has safety level 0. Thus, our study spans the spectrum between traditional safety and liveness. The formal definition of safety level is based on probability and measures the probability of a random word not in L to have a bad prefix. We study the problem of finding the safety level of languages given by means of deterministic and nondeterministic automata as well as LTL formulas, and the problem of deciding their membership in specific classes along the spectrum (safety, almost-safety, fraction-safety, etc.). We also study properties of the different classes and the structure of deterministic automata for them.
      PubDate: 2017-10-23
      DOI: 10.1007/s00236-017-0307-4
       
 
 
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.159.30.26
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-