2018
Whereas Perl-compatible regular expression matchers typically exhibit some variation of leftmost-greedy semantics, those conforming to the posix standard are prescribed leftmost-longest semantics. However, the posix standard leaves some room for interpretation, and Fowler and Kuklewicz have done experimental work to confirm differences between various posix matchers. The Boost library has an interesting take on the posix standard, where it maximises the leftmost match not with respect to subexpressions of the regular expression pattern, but rather, with respect to capturing groups. In our work, we provide the first formalisation of Boost semantics, and we analyse the complexity of regular expression matching when using Boost semantics.
@{196,
author = {Brink van der Merwe and Martin Berglund and Willem Bester},
title = {Formalising Boost POSIX Regular Expression Matching},
abstract = {Whereas Perl-compatible regular expression matchers typically exhibit some variation of leftmost-greedy semantics, those conforming to the posix standard are prescribed leftmost-longest semantics. However, the posix standard leaves some room for interpretation, and Fowler and Kuklewicz have done experimental work to confirm differences between various posix matchers. The Boost library has an interesting take on the posix standard, where it maximises the leftmost match not with respect to subexpressions of the regular expression pattern, but rather, with respect to capturing groups. In our work, we provide the first formalisation of Boost semantics, and we analyse the complexity of regular expression matching when using Boost semantics.},
year = {2018},
journal = {International Colloquium on Theoretical Aspects of Computing},
pages = {99-115},
month = {17/02},
publisher = {Springer},
isbn = {978-3-030-02508-3},
url = {https://link.springer.com/chapter/10.1007/978-3-030-02508-3_6},
}
The W3C standardized Semantic Web languages enable users to capture data without a schema in a manner which is intuitive to them. The challenge is that for the data to be useful, it should be possible to query the data and to query it efficiently, which necessitates a schema. Understanding the structure of data is thus important to both users and storage implementers: the structure of the data gives insight to users in how to query the data while storage implementers can use the structure to optimize queries. In this paper we propose that data mining routines can be used to infer candidate n-ary relations with related uniqueness- and null-free constraints, which can be used to construct an informative Armstrong RDF dataset. The benefit of an informative Armstrong RDF dataset is that it provides example data based on the original data which is a fraction of the size of the original data, while capturing the constraints of the original data faithfully. A case study on a DBPedia person dataset showed that the associated informative Armstrong RDF dataset contained 0.00003% of the statements of the original DBPedia dataset.
@{188,
author = {Henriette Harmse and Katarina Britz and Aurona Gerber},
title = {Informative Armstrong RDF datasets for n-ary relations},
abstract = {The W3C standardized Semantic Web languages enable users to capture data without a schema in a manner which is intuitive to them. The challenge is that for the data to be useful, it should be possible to query the data and to query it efficiently, which necessitates a schema. Understanding the structure of data is thus important to both users and storage implementers: the structure of the data gives insight to users in how to query the data while storage implementers can use the structure to optimize queries. In this paper we propose that data mining routines can be used to infer candidate n-ary relations with related uniqueness- and null-free constraints, which can be used to construct an informative Armstrong RDF dataset. The benefit of an informative Armstrong RDF dataset is that it provides example data based on the original data which is a fraction of the size of the original data, while capturing the constraints of the original data faithfully. A case study on a DBPedia person dataset showed that the associated informative Armstrong RDF dataset contained 0.00003% of the statements of the original DBPedia dataset.},
year = {2018},
journal = {Formal Ontology in Information Systems: 10th International Conference, Cape Town, South Africa},
pages = {187-198},
month = {17/09-21/09},
publisher = {IOS Press},
}
Description logics have been extended in a number of ways to support defeasible reasoning in the KLM tradition. Such features include preferential or rational defeasible concept subsumption, and defeasible roles in complex concept descriptions. Semantically, defeasible subsumption is obtained by means of a preference order on objects, while defeasible roles are obtained by adding a preference order to role interpretations. In this paper, we address an important limitation in defeasible extensions of description logics, namely the restriction in the semantics of defeasible concept subsumption to a single preference order on objects. We do this by inducing a modular preference order on objects from each preference order on roles, and use these to relativise defeasible subsumption. This yields a notion of contextualised rational defeasible subsumption, with contexts described by roles. We also provide a semantic construction for and a method for the computation of contextual rational closure, and present a correspondence result between the two.
@{187,
author = {Katarina Britz and Ivan Varzinczak},
title = {Context and rationality in defeasible subsumption},
abstract = {Description logics have been extended in a number of ways to support defeasible reasoning in the KLM tradition. Such features include preferential or rational defeasible concept subsumption, and defeasible roles in complex concept descriptions. Semantically, defeasible subsumption is obtained by means of a preference order on objects, while defeasible roles are obtained by adding a preference order to role interpretations. In this paper, we address an important limitation in defeasible extensions of description logics, namely the restriction in the semantics of defeasible concept subsumption to a single preference order on objects. We do this by inducing a modular preference order on objects from each preference order on roles, and use these to relativise defeasible subsumption. This yields a notion of contextualised rational defeasible subsumption, with contexts described by roles. We also provide a semantic construction for and a method for the computation of contextual rational closure, and present a correspondence result between the two.},
year = {2018},
journal = {Foundations of Information and Knowledge Systems: 10th International Symposium FoIKS 2018, Budapest, Hungary},
pages = {114-132},
month = {14/05-18/05},
publisher = {Springer},
}
A challenge in ontology engineering is the mismatch in ex- pertise between the ontology engineer and domain expert, which often leads to important constraints not being specified. Domain experts often only focus on specifying constraints that should hold and not on specify- ing constraints that could possibly be violated. In an attempt to bridge this gap we propose the use of “perfect test data”. The generated test data is perfect in that it satisfies all the constraints of an application domain that are required, including ensuring that the test data violates constraints that can be violated. In the context of Description Logic on- tologies we call this test data an “Armstrong ABox”, a notion derived from Armstrong relations in relational database theory. In this paper we detail the theoretical development of Armstrong ABoxes for ALC TBoxes as well as an algorithm for generating such Armstrong ABoxes. The proposed algorithm is based, via the ontology completion algorithm of Baader et al., on attribute exploration in formal concept analysis.
@{186,
author = {Henriette Harmse and Katarina Britz and Aurona Gerber},
title = {Generating Armstrong ABoxes for ALC TBoxes},
abstract = {A challenge in ontology engineering is the mismatch in ex- pertise between the ontology engineer and domain expert, which often leads to important constraints not being specified. Domain experts often only focus on specifying constraints that should hold and not on specify- ing constraints that could possibly be violated. In an attempt to bridge this gap we propose the use of “perfect test data”. The generated test data is perfect in that it satisfies all the constraints of an application domain that are required, including ensuring that the test data violates constraints that can be violated. In the context of Description Logic on- tologies we call this test data an “Armstrong ABox”, a notion derived from Armstrong relations in relational database theory. In this paper we detail the theoretical development of Armstrong ABoxes for ALC TBoxes as well as an algorithm for generating such Armstrong ABoxes. The proposed algorithm is based, via the ontology completion algorithm of Baader et al., on attribute exploration in formal concept analysis.},
year = {2018},
journal = {Theoretical Aspects of Computing: 15th International Colloquium, Stellenbosch, South Africa},
pages = {211-230},
month = {16/10-19/10},
publisher = {Springer},
}
Semi-structured data sets such as product reviews or event log data are simultaneously becoming more widely used and growing ever larger. This paper describes ConceptCloud, a flexible interactive browser for semi-structured datasets, with a focus on the recent trend of implementing server-based architectures to accommodate ever growing datasets. ConceptCloud makes use of an intuitive tag cloud visualization viewer in combination with an underlying concept lattice to provide a formal structure for navigation through datasets without prior knowledge of the structure of the data or compromising scalability. This is achieved by implementing architectural changes to increase the system’s resource efficiency.
@{185,
author = {Joshua Berndt and Bernd Fischer and Katarina Britz},
title = {Scaling the ConceptCloud browser to large semi-structured data sets},
abstract = {Semi-structured data sets such as product reviews or event log data are simultaneously becoming more widely used and growing ever larger. This paper describes ConceptCloud, a flexible interactive browser for semi-structured datasets, with a focus on the recent trend of implementing server-based architectures to accommodate ever growing datasets. ConceptCloud makes use of an intuitive tag cloud visualization viewer in combination with an underlying concept lattice to provide a formal structure for navigation through datasets without prior knowledge of the structure of the data or compromising scalability. This is achieved by implementing architectural changes to increase the system’s resource efficiency.},
year = {2018},
journal = {14th African Conference on Research in Computer Science and Applied Mathematics, Stellenbosch, South Africa, Proceedings},
pages = {276- 283},
month = {14/10-16/10},
publisher = {HAL archives-ouvertes},
url = {https://hal.inria.fr/hal-01881376},
}
Modal accounts of normality in non-monotonic reasoning traditionally have an underlying semantics based on a notion of preference amongst worlds. In this paper, we motivate and investigate an alternative semantics, based on ordered accessibility relations in Kripke frames. The underlying intuition is that some world tuples may be seen as more normal, while others may be seen as more exceptional. We show that this delivers an elegant and intuitive semantic construction, which gives a new perspective on defeasible necessity. Technically, the revisited logic does not change the expressive power of our previously defined preferential modalities. This conclusion follows from an analysis of both semantic constructions via a generalisation of bisimulations to the preferential case. Reasoners based on the previous semantics therefore also suffice for reasoning over the new semantics. We complete the picture by investigating different notions of defeasible conditionals in modal logic that can also be captured within our framework.\footnote{A preliminary version of the work reported in this paper was presented at the Workshop on Nonmonotonic Reasoning.
@article{183,
author = {Katarina Britz and Ivan Varzinczak},
title = {Preferential accessibility and preferred worlds},
abstract = {Modal accounts of normality in non-monotonic reasoning traditionally have an underlying semantics based on a notion of preference amongst worlds. In this paper, we motivate and investigate an alternative semantics, based on ordered accessibility relations in Kripke frames. The underlying intuition is that some world tuples may be seen as more normal, while others may be seen as more exceptional. We show that this delivers an elegant and intuitive semantic construction, which gives a new perspective on defeasible necessity. Technically, the revisited logic does not change the expressive power of our previously defined preferential modalities. This conclusion follows from an analysis of both semantic constructions via a generalisation of bisimulations to the preferential case. Reasoners based on the previous semantics therefore also suffice for reasoning over the new semantics. We complete the picture by investigating different notions of defeasible conditionals in modal logic that can also be captured within our framework.\footnote{A preliminary version of the work reported in this paper was presented at the Workshop on Nonmonotonic Reasoning.},
year = {2018},
journal = {Journal of Logic, Language and Information},
volume = {27},
pages = {133-155},
issue = {2},
publisher = {Springer},
url = {https://doi.org/10.1007/s10849-017-9264-0},
}
We investigate an aspect of defeasibility that has somewhat been overlooked by the non-monotonic reasoning community, namely that of defeasible modes of reasoning. These aim to formalise defeasibility of the traditional notion of necessity in modal logic, in particular of its different readings as action, knowledge and others in specific contexts, rather than defeasibility of conditional forms. Building on an extension of the preferential approach to modal logics, we introduce new modal operators with which to formalise the notion of defeasible necessity and distinct possibility, and that can be used to represent expected effects, refutable knowledge, and so on. We show how KLM-style conditionals can smoothly be integrated with our richer language. We also propose a tableau calculus which is sound and complete with respect to our modal preferential semantics, and of which the computational complexity remains in the same class as that of the underlying classical modal logic.
@article{182,
author = {Katarina Britz and Ivan Varzinczak},
title = {From KLM-Style Conditionals to Defeasible Modalities, and Back},
abstract = {We investigate an aspect of defeasibility that has somewhat been overlooked by the non-monotonic reasoning community, namely that of defeasible modes of reasoning. These aim to formalise defeasibility of the traditional notion of necessity in modal logic, in particular of its different readings as action, knowledge and others in specific contexts, rather than defeasibility of conditional forms. Building on an extension of the preferential approach to modal logics, we introduce new modal operators with which to formalise the notion of defeasible necessity and distinct possibility, and that can be used to represent expected effects, refutable knowledge, and so on. We show how KLM-style conditionals can smoothly be integrated with our richer language. We also propose a tableau calculus which is sound and complete with respect to our modal preferential semantics, and of which the computational complexity remains in the same class as that of the underlying classical modal logic.},
year = {2018},
journal = {Journal of Applied Non-Classical Logics},
volume = {28},
pages = {92-121},
issue = {1},
publisher = {Taylor & Francis},
url = {https://doi.org/10.1080/11663081.2017.1397325},
}
2017
No Abstract
@{215,
author = {Bruce Watson and T. Runge and I. Schaefer and L.G.W.A. Cleophas},
title = {Many-MADFAct: Concurrently Constructing MADFAs},
abstract = {No Abstract},
year = {2017},
journal = {Prague Stringology Conference 2017},
pages = {127-142},
month = {28/08-30/08},
publisher = {Prague Stringology Club},
isbn = {978-80-01-06193-0},
url = {https://dblp.org/db/conf/stringology/stringology2017},
}
No Abstract
@{214,
author = {Bruce Watson},
title = {Efficient pattern matching in degenerate strings with the Burrows-Wheeler transform},
abstract = {No Abstract},
year = {2017},
journal = {WCTA 2017 12th Workshop on Compression, Text and Algorithms},
pages = {1-7},
month = {29/09},
url = {pages.di.unipi.it/spire2017/wcta.html},
}
No Abstract
@article{213,
author = {Bruce Watson and M. Nxumalo and D.G Kourie and L.G.W.A. Cleophas},
title = {An Assessment of Algorithms for Deriving Failure Deterministic Finite Automata},
abstract = {No Abstract},
year = {2017},
journal = {South African Computer Journal},
volume = {29},
pages = {43-68},
issue = {1},
isbn = {2313-7835},
url = {http://dx.doi.org/10.18489/sacj.v29i1.456},
}
No Abstract
@article{212,
author = {Bruce Watson and J.W. Daykin},
title = {Indeterminate String Factorizations and Degenerate Text Transformations},
abstract = {No Abstract},
year = {2017},
journal = {Mathematics in Computer Science},
volume = {11},
pages = {209-218},
issue = {2},
isbn = {1661-8270},
url = {https://core.ac.uk/download/pdf/81595959.pdf},
}
No Abstract
@inbook{179,
author = {Bruce Watson and T. Strauss and D.G Kourie and L.G.W.A. Cleophas},
title = {CSP for Parallelising Brzozowski’s DFA Construction Algorithm},
abstract = {No Abstract},
year = {2017},
journal = {The Role of Theory in Computer Science},
pages = {217-243},
publisher = {World Scientific Publishing Co. Pte. Ltd.},
isbn = {978-981-3148-19-2},
url = {https://doi.org/10.1142/9789813148208_0010},
}
No Abstract
@{178,
author = {Brink van der Merwe and N. Weideman and Martin Berglund},
title = {Turning evil regexes harmless},
abstract = {No Abstract},
year = {2017},
journal = {Conference of South African Institute of Computer Scientists and Information Technologists (SAICSIT'17)},
month = {26/09-28/09},
publisher = {ACM},
url = {https://dl.acm.org/citation.cfm?id=3129416},
}
No Abstract
@{177,
author = {Martin Berglund and H. Björklund and F. Drewes},
title = {Single-rooted DAGs in regular DAG languages: Parikh image and path languages},
abstract = {No Abstract},
year = {2017},
journal = {International Workshop on Tree Adjoining Grammars and Related Formalisms},
pages = {94-101},
month = {04/09-06/09},
publisher = {The Association for Computational Linguistics (ACL)},
isbn = {978-1-945626-98-2},
url = {http://www.aclweb.org/anthology/W/W17/W17-62.pdf},
}
Most modern regular expression matching libraries (one of the rare exceptions being Google’s RE2) allow backreferences, operations which bind a substring to a variable allowing it to be matched again verbatim. However, different implementations not only vary in the syntax permitted when using backreferences, but both implementations and definitions in the literature offer up a number of different variants on how backreferences match. Our aim is to compare the various flavors by considering the formal languages that each can describe, resulting in the establishment of a hierarchy of language classes. Beyond the hierarchy itself, some complexity results are given, and as part of the effort on comparing language classes new pumping lemmas are established, and old ones extended to new classes.
@{176,
author = {Martin Berglund and Brink van der Merwe},
title = {Regular Expressions with Backreferences Re-examined},
abstract = {Most modern regular expression matching libraries (one of the rare exceptions being Google’s RE2) allow backreferences, operations which bind a substring to a variable allowing it to be matched again verbatim. However, different implementations not only vary in the syntax permitted when using backreferences, but both implementations and definitions in the literature offer up a number of different variants on how backreferences match. Our aim is to compare the various flavors by considering the formal languages that each can describe, resulting in the establishment of a hierarchy of language classes. Beyond the hierarchy itself, some complexity results are given, and as part of the effort on comparing language classes new pumping lemmas are established, and old ones extended to new classes.},
year = {2017},
journal = {The Prague Stringology Conference (PSC 2017)},
pages = {30-41},
month = {28/08-30/08},
address = {Czech Technical University in Prague,},
isbn = {ISBN 978-80-01-06193-0},
}
