Formal Methods

At RISC we understand by formal methods the application of methods from symbolic computation (especially from formal logic) to rigorously reason about properties of computer programs, in particular to verify their correctness with respect to a specification.

The term "formal methods" applies to all techniques that make computer software and computing systems subject to formal reasoning. By treating a computer program as a mathematical object with a formal semantics, we can rigorously argue about its behavior, e.g., why it always computes the correct result; this reasoning can be supported or even automated by corresponding software. Formal methods are industrially applied wherever computer/program failures are not acceptable, e.g. to mission-critical software, computer chips, or communication protocols.

Formal methods comprise at least two aspects:

  1. "Specification" means to describe the expected behavior of a program in a mathematically precise way (e.g. as a logic formula, see the "ensures" clause in the attached picture which gives the specification of a program).
  2. "Verification": means to demonstrate with mathematical rigor that every possible execution of the program does not crash and indeed satisfies its specification, preferably with computer support (by reasoners that apply proof-based techniques or by model checkers that investigate the space of all possible executions).

Furthermore, the "Validation" of a specification aims to ensure that this specification actually describes the intended behavior; thus the verification of a program with respect to this specification indeed demonstrates that the program satisfies the properties that we are interested in.

Even if the complete verification of a program may sometimes not be feasible, a "light-weight" application of formal methods may help to increase our confidence in the correctness of a program:

  • "Extended Static Checking" and "Bounded Model Checking" apply logic-based techniques to detect errors in a program; while these techniques do not necessarily ensure that a program is correct (they falsify a program rather than verifying it), they at least raise its quality;
  • "Runtime Verification" supervises the execution of a program by an automatically generated monitor that triggers a warning if the program violates its specification; while this does not rule out possible future errors, it at least ensures that the execution so far has been correct.

The support respectively automation of all these aspects by software (automated program verifiers, interactive verification assistants, model checkers, static program analyzers, specification analyzers) is a hot topic of research.

Software

RISC ProgramExplorer

An Interactive Program Reasoning Environment

The RISC ProgramExplorer is a computer-supported program reasoning environment for a simple imperative programming language "MiniJava"; it incorporates the RISC ProofNavigator as a semi-automatic proving assistant. The environment has been developed mainly for educational purposes (see this paper for a ...

MoreSoftware Website

RISC ProofNavigator

An Interactive Proof Assistant for Program/System Verification

The RISC ProofNavigator is an interactive proof assistant for supporting formal reasoning about computer programs and computing systems, see the README file and this short paper for the main ideas; it is the core reasoning component of the RISC ProgramExplorer. ...

MoreSoftware Website

RISCAL

The RISC Algorithm Language: A Language and Associated Software System for Specifying and Verifying Mathematical Algorithms

The RISC Algorithm Language (RISCAL) is a specification language and associated software system for describing mathematical algorithms, formally specifying their behavior based on mathematical theories, and validating the correctness of algorithms, specifications, and theories by execution/evaluation. The software has been ...

MoreSoftware Website

Publications

2018

Teaching the Formalization of Mathematical Theories and Algorithms via the Automatic Checking of Finite Models

Wolfgang Schreiner, Alexander Brunhuemer, Christoph Fürst

In: Post-Proceedings ThEdu'17, Pedro Quaresma and Walther Neuper (ed.), Proceedings of 6th International Workshop on Theorem proving components for Educational software (ThEdu'17), Gothenburg, Sweden, 6 Aug 2017, Electronic Proceedings in Theoretical Computer Science (EPTCS) 267, pp. 120-139. 2018. Open Publishing Association, ISSN 2075-2180. [url] [pdf]
[bib]
@inproceedings{RISC5531,
author = {Wolfgang Schreiner and Alexander Brunhuemer and Christoph Fürst},
title = {{Teaching the Formalization of Mathematical Theories and Algorithms via the Automatic Checking of Finite Models}},
booktitle = {{Post-Proceedings ThEdu'17}},
language = {english},
abstract = {Education in the practical applications of logic and proving such as the formalspecification and verification of computer programs is substantially hampered bythe fact that most time and effort that is invested in proving is actuallywasted in vain: because of errors in the specifications respectively algorithmsthat students have developed, their proof attempts are often pointless (becausethe proposition proved is actually not of interest) or a priori doomed to fail(because the proposition to be proved does actually not hold); this is afrequent source of frustration and gives formal methods a bad reputation. RISCAL(RISC Algorithm Language) is a formal specification language and associatedsoftware system that attempts to overcome this problem by making logicformalization fun rather than a burden. To this end, RISCAL allows students toeasily validate the correctness of instances of propositions respectivelyalgorithms by automatically evaluating/executing and checking them on (small)finite models. Thus many/most errors can be quickly detected and subsequentproof attempts can be focused on propositions that are more/most likely to beboth meaningful and true.},
series = {Electronic Proceedings in Theoretical Computer Science (EPTCS)},
volume = {267},
pages = {120--139},
publisher = {Open Publishing Association},
isbn_issn = {ISSN 2075-2180},
year = {2018},
editor = {Pedro Quaresma and Walther Neuper},
refereed = {yes},
keywords = {formal methods, program specification and verification, model checking, computer science education, logic},
sponsor = {Supported by the Johannes Kepler University Linz, Linz Institute of Technology (LIT), Project LOGTECHEDU "Logic Technology for Computer Science Education"},
length = {20},
conferencename = {6th International Workshop on Theorem proving components for Educational software (ThEdu'17), Gothenburg, Sweden, 6 Aug 2017},
url = {http://dx.doi.org/10.4204/EPTCS.267.8}
}

Validating Mathematical Theories and Algorithms with RISCAL

Wolfgang Schreiner

In: Intelligent Computer Mathematics, F. Rabe, W. Farmer, G. Passmore, A. Youssef (ed.), Proceedings of CICM 2018, 11th Conference on Intelligent Computer Mathematics, Hagenberg, Austria, August 13-17, 2018, Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence 11006, pp. 248-254. 2018. Springer, Berlin, ISBN 978-3-319-96811-7. The final authenticated version is available online at Springer. [url] [pdf]
[bib]
@inproceedings{RISC5704,
author = {Wolfgang Schreiner},
title = {{Validating Mathematical Theories and Algorithms with RISCAL}},
booktitle = {{Intelligent Computer Mathematics}},
language = {english},
abstract = {RISCAL is a language for describing mathematical algo-rithms and formally specifying their behavior with respect to user-definedtheories in first-order logic. This language is based on a type system thatconstrains the size of all types by formal parameters; thus a RISCALspecification denotes an infinite class of models of which every instancehas finite size. This allows the RISCAL software to fully automaticallycheck in small instances the validity of theorems and the correctness ofalgorithms. Our goal is to quickly detect errors respectively inadequa-cies in the formalization by falsification in small model instances beforeattempting actual correctness proofs for the whole model class.},
series = {Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence},
volume = {11006},
pages = {248--254},
publisher = {Springer},
address = {Berlin},
isbn_issn = {ISBN 978-3-319-96811-7},
year = {2018},
note = {The final authenticated version is available online at Springer},
editor = {F. Rabe and W. Farmer and G. Passmore and A. Youssef},
refereed = {yes},
keywords = {Formal specification, Falsification, Model checking},
sponsor = {Supported by the Johannes Kepler University, Linz Institute of Technology (LIT), project LOGTECHEDU, and by the OEAD WTZ project SK 14/2018 SemTech.},
length = {7},
conferencename = {CICM 2018, 11th Conference on Intelligent Computer Mathematics, Hagenberg, Austria, August 13-17, 2018},
url = {https://doi.org/10.1007/978-3-319-96812-4_21}
}

Logic as a Path to Enlightenment (Work in Progress Report)

Wolfgang Schreiner

In: Computer Mathematics in Education - Enlightenment or Incantation?, Walther Neuper (ed.), Proceedings of CME-EI18, Workshop at CICM 2018, 11th Conference on Intelligent Computer Mathematics, Hagenberg, Austria, August 17, 2018., pp. 1-5. August 2018. To be published at CEUR Workshop Proceedings, http://CEUR-ws.org, ISSN 1613-0073. [pdf]
[bib]
@inproceedings{RISC5711,
author = {Wolfgang Schreiner},
title = {{Logic as a Path to Enlightenment (Work in Progress Report)}},
booktitle = {{Computer Mathematics in Education - Enlightenment or Incantation?}},
language = {english},
pages = {1--5},
publisher = {To be published at CEUR Workshop Proceedings, http://CEUR-ws.org},
isbn_issn = {ISSN 1613-0073},
year = {2018},
month = {August},
editor = {Walther Neuper},
refereed = {yes},
keywords = {RISC Algorithm Language, RISCAL, Model Checking, Verification},
sponsor = {Supported by the Johannes Kepler University, Linz Institute of Technology (LIT), project LOGTECHEDU, and by the OEAD WTZ project SK 14/2018 SemTech.},
length = {3},
conferencename = {CME-EI18, Workshop at CICM 2018, 11th Conference on Intelligent Computer Mathematics, Hagenberg, Austria, August 17, 2018.}
}

2017

Measuring the Gap: Algorithmic Approximation Bounds for the Space Complexity of Stream Specifications

David M. Cerna , Wolfgang Schreiner

In: Epic series in computer science, Mohamed Mosbah, Michaël Rusinowitch (eds). (ed.), Proceedings of SCSS 2017, 8th International Symposium on Symbolic Computation in Software Science, Epic 45, pp. 1-15. April 2017. Easy chair, ISSN 2398-7340. [url] [pdf]
[bib]
@inproceedings{RISC5404,
author = {David M. Cerna and Wolfgang Schreiner},
title = {{Measuring the Gap: Algorithmic Approximation Bounds for the Space Complexity of Stream Specifications}},
booktitle = {{Epic series in computer science}},
language = {english},
abstract = {Measuring the Gap: Algorithmic Approximation Bounds for the Space Complexity of Stream Specifications},
series = {Epic},
volume = {45},
pages = {1--15},
publisher = {Easy chair},
isbn_issn = {ISSN 2398-7340},
year = {2017},
month = {April},
editor = {Mohamed Mosbah and Michaël Rusinowitch (eds).},
refereed = {yes},
length = {12},
conferencename = {SCSS 2017, 8th International Symposium on Symbolic Computation in Software Science},
url = {http://easychair.org/publications/download/Measuring_the_Gap_Algorithmic_Approximation_Bounds_for_the_Space_Complexity_of_Stream_Specifications}
}

Ceres in Intuitionistic Logic

David Cerna, Alexander Leitsch, Giselle Reis, Simon Wolfsteiner

Annals of Pure and Applied Logic, pp. 1783-1836. October 2017. Elsevier, ISSN 0168-0072. [url]
[bib]
@article{RISC5429,
author = {David Cerna and Alexander Leitsch and Giselle Reis and Simon Wolfsteiner},
title = {{Ceres in Intuitionistic Logic}},
language = {english},
abstract = {Abstract In this paper we present a procedure allowing the extension of a CERES-based cut-elimination method to intuitionistic logic. Previous results concerning this problem manage to capture fragments of intuitionistic logic, but in many essential cases structural constraints were violated during normal form construction resulting in a classical proof. The heart of the \{CERES\} method is the resolution calculus, which ignores the structural constraints of the well known intuitionistic sequent calculi. We propose, as a method of avoiding the structural violations, the generalization of resolution from the resolving of clauses to the resolving of cut-free proofs, in other words, what we call proof resolution. The result of proof resolution is a cut-free proof rather than a clause. Note that resolution on ground clauses is essentially atomic cut, thus using proof resolution to construct cut-free proofs one would need to join the two proofs together and remove the atoms which where resolved. To efficiently perform this joining (and guarantee that the resulting cut-free proof is intuitionistic) we develop the concept of proof subsumption (similar to clause subsumption) and indexed resolution, a refinement indexing atoms by their corresponding positions in the cut formula. Proof subsumption serves as a tool to prove the completeness of the new method CERES-i, and indexed resolution provides an efficient strategy for the joining of two proofs which is in general a nondeterministic search. Such a refinement is essential for any attempt to implement this method. Finally we compare the complexity of CERES-i with that of Gentzen-based methods.},
journal = {Annals of Pure and Applied Logic},
pages = {1783--1836},
publisher = {Elsevier},
isbn_issn = { ISSN 0168-0072},
year = {2017},
month = {October},
refereed = {yes},
length = {66},
url = {http://www.sciencedirect.com/science/article/pii/S0168007217300490}
}

An overview of PρLog

Besik Dundua, Temur Kutsia, Klaus Reisenberger-Hagmayr

In: Proceedings of the 19th International Symposium on Practical Aspects of Declarative Languages, PADL 2017, Y. Lierler and W. Taha (ed.), Lecture Notes in Computer Science 10137, pp. 34-49. 2017. Springer, ISBN 978-3-319-51675-2. [pdf]
[bib]
@inproceedings{RISC5416,
author = {Besik Dundua and Temur Kutsia and Klaus Reisenberger-Hagmayr},
title = {{An overview of PρLog}},
booktitle = {{ Proceedings of the 19th International Symposium on Practical Aspects of Declarative Languages, PADL 2017}},
language = {english},
series = {Lecture Notes in Computer Science},
volume = {10137},
pages = {34--49},
publisher = {Springer},
isbn_issn = {ISBN 978-3-319-51675-2},
year = {2017},
editor = {Y. Lierler and W. Taha},
refereed = {yes},
length = {16}
}

Nominal Unification of Higher Order Expressions with Recursive Let

Manfred Schmidt-Schauss, Temur Kutsia, Jordy Levy, Mateu Villaret

In: Proceedings of the 26th International Symposium on Logic-Based Program Synthesis and Transformation, LOPSTR 2016, M. Hermenegildo and P. Lopez-Garcia (ed.), LNCS 10184, pp. 328-344. 2017. Springer, ISBN 978-3-319-63138-7. [pdf]
[bib]
@inproceedings{RISC5438,
author = {Manfred Schmidt-Schauss and Temur Kutsia and Jordy Levy and Mateu Villaret},
title = {{Nominal Unification of Higher Order Expressions with Recursive Let}},
booktitle = {{ Proceedings of the 26th International Symposium on Logic-Based Program Synthesis and Transformation, LOPSTR 2016}},
language = {english},
series = {LNCS},
volume = {10184},
pages = {328--344},
publisher = {Springer},
isbn_issn = {ISBN 978-3-319-63138-7},
year = {2017},
editor = {M. Hermenegildo and P. Lopez-Garcia},
refereed = {yes},
length = {17}
}

Mathematical Aspects of Computer and Information Sciences

Johannes Blömer, Ilias Kotsireas, Temur Kutsia, Dimitris E. Simos, editors

Lecture Notes in Computer Science 10693, 2017. Springer, ISBN 978-3-319-72452-2. [url]
[bib]
@booklet{RISC5518,
author = {Johannes Blömer and Ilias Kotsireas and Temur Kutsia and Dimitris E. Simos and editors},
title = {{Mathematical Aspects of Computer and Information Sciences}},
language = {english},
series = {Lecture Notes in Computer Science},
volume = {10693},
publisher = {Springer},
isbn_issn = {ISBN 978-3-319-72452-2},
year = {2017},
edition = { },
translation = {0},
length = {462},
url = {https://doi.org/10.1007/978-3-319-72453-9}
}

MK-fuzzy Automata and MSO Logics

Manfred Droste, Temur Kutsia, George Rahonis, Wolfgang Schreiner

In: 8th Symposium on Games, Automata, Logics and Formal Verification (GandALF’17), P. Bouyer, A. Orlandini, P. San Pietro (ed.), Electronic Proceedings in Theoretical Computer Science (EPTCS) 256, pp. 106-120. September 2017. Rome, Italy, September 22-27, ISSN 2075-2180. [pdf]
[bib]
@inproceedings{RISC5470,
author = {Manfred Droste and Temur Kutsia and George Rahonis and Wolfgang Schreiner},
title = {{MK-fuzzy Automata and MSO Logics}},
booktitle = {{8th Symposium on Games, Automata, Logics and Formal Verification (GandALF’17)}},
language = {english},
abstract = {We introduce MK-fuzzy automata over a bimonoid K which is related to the fuzzification of theMcCarthy-Kleene logic. Our automata are inspired by, and intend to contribute to, practical applicationsbeing in development in a project on runtime network monitoring based on predicate logic. We investigate closure propertiesof the class of recognizable MK-fuzzy languages accepted by MK-fuzzy automata as well asof deterministically recognizable MK-fuzzy languages accepted by their deterministic counterparts.Moreover, we establish a Nivat-like result for recognizable MK-fuzzy languages. We introduce anMK-fuzzy MSO logic and show the expressive equivalence of a fragment of this logic with MK-fuzzyautomata, i.e., a B¨uchi type theorem},
series = { Electronic Proceedings in Theoretical Computer Science (EPTCS)},
volume = {256},
pages = {106--120},
address = {Rome, Italy, September 22-27},
isbn_issn = {ISSN 2075-2180},
year = {2017},
month = {September},
editor = {P. Bouyer and A. Orlandini and P. San Pietro},
refereed = {yes},
keywords = {Many-valued logic, fuzzy logic, MSO logic, runtime monitoring.},
sponsor = {The project “LogicGuard II: The Optimized Checking of Time-Quantified Logic Formulas with Applications in Computer Security” is sponsored by the FFG BRIDGE program, project No. 846003.},
length = {15}
}

Modeling RF-Based Sensor Networks by Using Dual-Source Retrial Queueing Systems

Ovidiu Constantin Novac, Tamás Bérczes, Attila Kuki, Ádám Tóth, Wolfgang Schreiner

In: ICEMES 2017, 14th International Conference on Engineering of Modern Electric Systems, Oradea, Romania, June 1–2, 2017, Mircea Gordan, Teodor Leuca, Florin Constantinescu (ed.), pp. 149-153. 2017. IEEE Xplore, ISBN 978-1-5090-6073-3. [url]
[bib]
@inproceedings{RISC5480,
author = {Ovidiu Constantin Novac and Tamás Bérczes and Attila Kuki and Ádám Tóth and Wolfgang Schreiner},
title = {{Modeling RF-Based Sensor Networks by Using Dual-Source Retrial Queueing Systems}},
booktitle = {{ICEMES 2017, 14th International Conference on Engineering of Modern Electric Systems, Oradea, Romania, June 1–2, 2017}},
language = {english},
abstract = {Here, we would like to study the efficiency and utilization of radio frequency (RF) transmission in wireless sensor networks. A new dual source queueing model (with finite and infinite numbers of sensors) is introduced in order to obtain the most frequently studied system performance characteristics (e.g. mean response time, average number of jobs waiting for transmission, and the utilization of the RF unit). The different types of sensors form the “sources” and the RF unit forms the “central servicing node” of this model. The elements of the sensor fields are classified according to their working purposes: The first class is the “Emergency” or “Special” class which is responsible to notify special rare events (e.g. fire alarms). The other class is the “Standard” class where sensors measure data from standard conventional events or occurrences (eg. motion detection, wind speed, level of darkness etc). For energy efficiency reasons the Central Unit (or Radio Frequency Unit - RFU) might switch into a reduced functioning mode. This reduced communication mode is for saving energy. The transmissions are closed in this mode. Returning from the reduced mode two cases are considered and two models are created to compare their steady-state system performance characteristics: In the first model, the RF transmission is available randomly to the sensor nodes (“Non-Controlled” case). In the other case, the Central Unit jobs which come from the Special class, can use the wireless service immediately (“Controlled” case).},
pages = {149--153},
publisher = {IEEE Xplore},
isbn_issn = {ISBN 978-1-5090-6073-3},
year = {2017},
editor = {Mircea Gordan and Teodor Leuca and Florin Constantinescu},
refereed = {yes},
keywords = {wireless sensors, performance evaluation, retrial queueing, stochastic simulation },
length = {5},
url = {https://doi.org/10.1109/EMES.2017.7980402}
}

2016

Practical Event Monitoring in the LogicGuard Framework

Wolfgang Schreiner, David Cerna, Temur Kutsia, Michael Krieger, Bashar Ahmad, Helmut Otto, Martin Rummerstorfer, Thomas Gössl

In: embedded world Conference 2016, February 23-25 2016, Nürnberg, Germany, Matthias Sturm et al. (ed.), pp. -. February 2016. Design & Elektronik, Haar, Germany, ISBN 978-3-645-50159-0. [pdf]
[bib]
@inproceedings{RISC5261,
author = {Wolfgang Schreiner and David Cerna and Temur Kutsia and Michael Krieger and Bashar Ahmad and Helmut Otto and Martin Rummerstorfer and Thomas Gössl},
title = {{Practical Event Monitoring in the LogicGuard Framework}},
booktitle = {{embedded world Conference 2016, February 23-25 2016, Nürnberg, Germany}},
language = {english},
abstract = {We describe further progress on the previously introduced LogicGuard specification language and execution framework. This framework generates from a high-level logic specification of a desired property of a stream of events an executable program that observes the stream in real time for violations of the property. While previous presentations were based on an early and incomplete prototype, we are now able to report on some practical applications of the operational framework in the context of network security. As a startup example, we present the “Rogue DHCP” scenario where a device illicitly poses as a DHCP server in order to feed newly connected devices with wrong connectivity information; the monitor detects this attack by looking for duplicate offers to the same DHCP client, of which one is from the attacker. Our main scenario is “Dynamic DNS (DDNS) Cache Poisoining” where an attacker poses as a DDNS client and feeds the DDNS server with wrong DNS update information; the monitor detects this attack by learning about the frequency of legitimate DDNS updates and reporting updates that occur significantly earlier than expected.},
pages = {--},
publisher = {Design & Elektronik},
address = {Haar, Germany},
isbn_issn = {ISBN 978-3-645-50159-0},
year = {2016},
month = {February},
editor = {Matthias Sturm et al.},
refereed = {no},
keywords = {formal methods, runtime verification, event processing},
length = {7}
}

Space Analysis of a Predicate Logic Fragment for the Specification of Stream Monitors

David M. Cerna, Wolfgang Schreiner, and Temur Kutsia

In: SCSS 2016. 7th International Symposium on Symbolic Computation in Software Science, James H. Davenport and Fadoua Ghourabi (ed.), Proceedings of The 7th International Symposium on Symbolic Computation in Software Science, EPiC Series in Computing 39, pp. 29-41. 2016. EasyChair, ISSN 2040-557X. [url] [pdf]
[bib]
@inproceedings{RISC5264,
author = {David M. Cerna and Wolfgang Schreiner and and Temur Kutsia},
title = {{Space Analysis of a Predicate Logic Fragment for the Specification of Stream Monitors}},
booktitle = {{SCSS 2016. 7th International Symposium on Symbolic Computation in Software Science}},
language = {english},
abstract = {We analyze the space complexity of monitoring streams of messages whose expected behavior isspecified in a fragment of predicate logic; this fragment is the core of the LogicGuard specificationlanguage that has been developed in an industrial context for the runtime monitoring of network traffic.The execution of the monitors is defined by an operational semantics for the step-wise evaluation offormulas, which requires the preservation of formula instances in memory until their truth value can bedetermined. In the presented work, we analyze the number of instances that have to be preserved overtime for a significant fragment of the core language that involves only “future looking quantifiers”; thislays the foundations for the space analysis of the entire core language.},
series = {EPiC Series in Computing},
volume = {39},
pages = {29--41},
publisher = {EasyChair},
isbn_issn = {ISSN 2040-557X},
year = {2016},
editor = {James H. Davenport and Fadoua Ghourabi},
refereed = {yes},
length = {13},
conferencename = {The 7th International Symposium on Symbolic Computation in Software Science},
url = {http://easychair.org/publications/paper/Space_Analysis_of_a_Predicate_Logic_Fragment_for_the_Specification_of_Stream_Monitors}
}

Predicting Space Requirements for a Stream Monitor Specification Language

David M. Cerna and Wolfgang Schreiner, Temur Kutsia

In: Runtime Verification - 16th International Conference, RV 2016, Madrid, Spain, September 23-30, 2016, Proceedings, Yliès Falcone and César Sánchez (ed.), Proceedings of Runtime Verification, pp. 135-151. September 2016. Springer International Publishing, 978-3-319-46981-2. [url] [pdf]
[bib]
@inproceedings{RISC5369,
author = {David M. Cerna and Wolfgang Schreiner and Temur Kutsia},
title = {{Predicting Space Requirements for a Stream Monitor Specification Language}},
booktitle = {{Runtime Verification - 16th International Conference, RV 2016, Madrid, Spain, September 23-30, 2016, Proceedings}},
language = {english},
pages = {135--151},
publisher = {Springer International Publishing},
isbn_issn = {978-3-319-46981-2},
year = {2016},
month = {September},
editor = {Yliès Falcone and César Sánchez},
refereed = {yes},
length = {17},
conferencename = {Runtime Verification},
url = {http://dx.doi.org/10.1007/978-3-319-46982-9_9}
}

Anti-Unification of Concepts in Description Logic EL

Boris Konev, Temur Kutsia

In: Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016, Chitta Baral, James P. Delgrande, Frank Wolter (ed.), pp. 227-236. April 25-29 2016. AAAI Press, Cape Town, South Africa, 978-1-57735-755-1. [url]
[bib]
@inproceedings{RISC5281,
author = {Boris Konev and Temur Kutsia},
title = {{Anti-Unification of Concepts in Description Logic EL}},
booktitle = {{Proceedings of the 15th International Conference on Principles of Knowledge Representation and Reasoning, KR 2016}},
language = {english},
pages = {227--236},
publisher = {AAAI Press},
address = {Cape Town, South Africa},
isbn_issn = {978-1-57735-755-1},
year = {2016},
month = {April 25--29},
editor = {Chitta Baral and James P. Delgrande and Frank Wolter},
refereed = {yes},
length = {10},
url = {http://www.aaai.org/ocs/index.php/KR/KR16/paper/download/12880/12479}
}

Analysis of Finite-Source Cluster Networks

Adam Toth, Tamas Berczes, Attila Kuki, Bela Almasi, Wolfgang Schreiner, Jinting Wang, Fang Wang

Creative Mathematics and Informatics 25(2), pp. 223-235. 2016. SINUS Association, ISSN 1584 - 286X.
[bib]
@article{RISC5217,
author = {Adam Toth and Tamas Berczes and Attila Kuki and Bela Almasi and Wolfgang Schreiner and Jinting Wang and Fang Wang},
title = {{Analysis of Finite-Source Cluster Networks}},
language = {english},
abstract = {Nowadays the distributed heterogeneous resources of networks, like the computational grid,start to have a greater part of interest so, the investigations of such systems are vital. Because of the more efficient utilisation of the resources, the job scheduling becomes more challenging for the system administrators. The allocation of the arriving jobs has a great impact on the efficiency and the energy consumption of the system. In this paper, we present a finite source generalized model for the performance evaluation of scheduling compute-intensive jobs based on the infinite model of Tien Van Do. The available computers are classified into three groups. This classification is based on two aspects: high performance priority (HP) and energy efficiency priority (EE). We investigate three schemes (separate queue, class queue and common queue) for buffering the jobs in a computational cluster that is built from Commercial Off-The-Shelf (COTS) servers. Our main interest is to calculate performance measures and energy consumption of the system using the different buffering schemes and classifications.},
journal = {Creative Mathematics and Informatics},
volume = {25},
number = {2},
pages = {223--235},
publisher = {SINUS Association},
isbn_issn = {ISSN 1584 - 286X},
year = {2016},
refereed = {yes},
sponsor = {Stiftung Aktion Österreich-Ungarn contract 90öu6. },
length = {14}
}

Predicting Space Requirements for a Stream Monitor Specification Language

David M. Cerna and Wolfgang Schreiner, Temur Kutsia

In: Runtime Verification - 16th International Conference, RV 2016, Madrid, Spain, September 23-30, 2016, Proceedings, Yli{\`{e}}s Falcone and C{\'{e}}sar S{\'{a}}nchez (ed.), pp. 135-151. 2016. 978-3-319-46981-2. [url]
[bib]
@inproceedings{RISC5739,
author = {David M. Cerna and Wolfgang Schreiner and Temur Kutsia},
title = {{Predicting Space Requirements for a Stream Monitor Specification Language}},
booktitle = {{Runtime Verification - 16th International Conference, RV 2016, Madrid, Spain, September 23-30, 2016, Proceedings}},
language = {english},
pages = {135--151},
isbn_issn = {978-3-319-46981-2},
year = {2016},
editor = {Yli{\`{e}}s Falcone and C{\'{e}}sar S{\'{a}}nchez},
refereed = {yes},
length = {17},
url = {https://doi.org/10.1007/978-3-319-46982-9_9}
}

Predicting Space Requirements for a Stream Monitor Specification Language

David M. Cerna and Wolfgang Schreiner and Temur Kutsia

In: Runtime Verification - 16th International Conference, {RV} 2016, Madrid, Spain, September 23-30, 2016, Proceedings, Yli{\`{e}}s Falcone and C{\'{e}}sar S{\'{a}}nchez (ed.), pp. 135-151. 2016. 978-3-319-46981-2.
[bib]
@inproceedings{RISC5740,
author = {David M. Cerna and Wolfgang Schreiner and Temur Kutsia},
title = {{Predicting Space Requirements for a Stream Monitor Specification Language}},
booktitle = {{Runtime Verification - 16th International Conference, {RV} 2016, Madrid, Spain, September 23-30, 2016, Proceedings}},
language = {english},
pages = {135--151},
isbn_issn = {978-3-319-46981-2},
year = {2016},
editor = {Yli{\`{e}}s Falcone and C{\'{e}}sar S{\'{a}}nchez},
refereed = {yes},
length = {17}
}

Formally Modeling and Analyzing Mathematical Algorithms with Software Specification Languages & Tools

Daniela Ritirc

Research Institute for Symbolic Computation (RISC), Johannes Kepler University, Linz, Austria. Diploma Thesis. January 2016. [pdf]
[bib]
@mastersthesis{RISC5224,
author = {Daniela Ritirc},
title = {{Formally Modeling and Analyzing Mathematical Algorithms with Software Specification Languages & Tools}},
language = {english},
abstract = {In this thesis the behaviour of software specification languages and tools on mathematicalalgorithms shall be investigated. The main goal is to investigate how tools which havebeen designed for modeling and analyzing software in other application contexts can beapplied to mathematical algorithms. For this purpose, two different mathematical algorithms,namely the DPLL method and Dijkstra’s Shortest Path Algorithm are selected.Furthermore five well-known software specification languages are selected: JML, Alloy,TLA/PlusCal, VDM and Event-B. It shall be examined how far the algorithms can bemodeled and how far model checking respectively verification succeeds. The goal of thethesis is not a proper verification/check of every model with every tool but a survey ofthe potential as well as the difficulties of the usage of software specification languagesfor the analysis of mathematical algorithms.As a starting point for each algorithm a formal specification is derived and the algorithmsare supplied in pseudo-code. A Java prototype is implemented for each algorithmwhich is then specified by JML annotations. Furthermore the algorithms are modelled inTLA/PlusCal, Alloy, VDM and Event-B and for each language the appropriate analysissupported by the tool is selected (visualizing, model checking, verification).The main result of the thesis is that each tool shows some success when it is usedfor specifying and analyzing mathematical algorithms, because modeling the algorithmssucceeded in every language. In TLA, VDM and Alloy it was possible to completelymodel check the specifications. Furthermore it was possible to visualize the algorithmsin Alloy. In JML and Event-B it was possible to verify major parts of the model;},
year = {2016},
month = {January},
translation = {0},
school = {Research Institute for Symbolic Computation (RISC), Johannes Kepler University, Linz, Austria},
keywords = {formal methods, model checking, program verification},
length = {167}
}

2015

Securing Device Communication by Predicate Logic Specifications

Wolfgang Schreiner, Temur Kutsia, Michael Krieger, Bashar Ahmad, Helmut Otto, Martin Rummerstorfer

In: embedded world Conference 2015, February 24-26 2015, Nürnberg, Germany, Matthias Sturm et al. (ed.), pp. -. February 2015. Design&Elektronik, Haar, Germany, ISBN 978-3-645-50144-6. [pdf]
[bib]
@inproceedings{RISC5098,
author = {Wolfgang Schreiner and Temur Kutsia and Michael Krieger and Bashar Ahmad and Helmut Otto and Martin Rummerstorfer},
title = {{Securing Device Communication by Predicate Logic Specifications}},
booktitle = {{embedded world Conference 2015, February 24-26 2015, Nürnberg, Germany}},
language = {english},
abstract = {We present a novel approach to the runtime monitoring of network traffic where from a high-level specification of security properties an executable monitor is generated; this monitor observes the network traffic in real time for violation of the specified properties in order to report respectively prevent these violations. The specification formalism is purely based on the classical notions of predicate logic and set theory with the corresponding level of expressiveness; compared to other more restricted formalisms it has thus much stronger capabilities to describe properties of interest. Its high level of flexibility makes our approach also applicable to other problem areas and engineering domains such as process control where it is important to guarantee that sequences of events conform to a particular protocol.},
pages = {--},
publisher = {Design&Elektronik},
address = {Haar, Germany},
isbn_issn = {ISBN 978-3-645-50144-6},
year = {2015},
month = {February},
editor = {Matthias Sturm et al.},
refereed = {no},
keywords = {runtime monitoring; network security; event streams; predicate logic},
sponsor = {Supported by the Austrian Research Promotion Agency (FFG) in the frame of the BRIDGE program by the project 846003 “LogicGuard II”},
length = {9}
}

Nominal Anti-Unification

Alexander Baumgartner, Temur Kutsia, Jordi Levy, Mateu Villaret

In: Proceedings of the 26th International Conference on Rewriting Techniques and Applications, RTA'15, Maribel Fernandez (ed.), Leibniz International Proceedings in Informatics (LIPIcs) , pp. 57-73. 2015. ISSN 1868-8969. [pdf]
[bib]
@inproceedings{RISC5149,
author = {Alexander Baumgartner and Temur Kutsia and Jordi Levy and Mateu Villaret},
title = {{Nominal Anti-Unification}},
booktitle = {{Proceedings of the 26th International Conference on Rewriting Techniques and Applications, RTA'15}},
language = {english},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
pages = {57--73},
isbn_issn = {ISSN 1868-8969},
year = {2015},
editor = {Maribel Fernandez},
refereed = {yes},
sponsor = {FWF under the project P 24087-N18},
length = {17}
}

Loading…