The Experts below are selected from a list of 291 Experts worldwide ranked by ideXlab platform

Linh Anh Nguyen - One of the best experts on this subject based on the ideXlab platform.

  • Proceedings of the 23th International Workshop on Concurrency, Specification and Programming - A Tractable Rule Language in the Modal and Description Logic that Combines CPDL with Regular Grammar Logic
    Fundamenta Informaticae, 2016
    Co-Authors: Linh Anh Nguyen
    Abstract:

    Combining CPDL (Propositional Dynamic Logic with Converse) and Regular Grammar logic results in an expressive modal logic denoted by CPDLreg. This logic covers TEAMLOG, a logical formalism used to express properties of agents' cooperation in terms of beliefs, goals and intentions. It can also be used as a description logic for expressing terminological knowledge, in which both Regular role inclusion axioms and CPDL-like role constructors are allowed. In this paper, we develop an expressive and tractable rule language called Horn-CPDLreg. As a special property, this rule language allows the concept constructor "universal restriction" to appear on the left hand side of general concept inclusion axioms. We use a special semantics for Horn-CPDLreg that is based on pseudo-interpretations. It is called the constructive semantics and coincides with the traditional semantics when the concept constructor "universal restriction" is disallowed on the left hand side of concept inclusion axioms or when the language is used as an epistemic formalism and the accessibility relations are serial. We provide an algorithm with PTIME data complexity for checking whether a knowledge base in Horn-CPDLreg has a pseudo-model. This shows that the instance checking problem in Horn-CPDLreg with respect to the constructive semantics has PTIME data complexity.

  • a tractable rule language in the modal and description logic that combines cpdl with Regular Grammar logic
    Fundamenta Informaticae, 2016
    Co-Authors: Linh Anh Nguyen
    Abstract:

    Combining CPDL (Propositional Dynamic Logic with Converse) and Regular Grammar logic results in an expressive modal logic denoted by CPDLreg. This logic covers TEAMLOG, a logical formalism used to express properties of agents' cooperation in terms of beliefs, goals and intentions. It can also be used as a description logic for expressing terminological knowledge, in which both Regular role inclusion axioms and CPDL-like role constructors are allowed. In this paper, we develop an expressive and tractable rule language called Horn-CPDLreg. As a special property, this rule language allows the concept constructor "universal restriction" to appear on the left hand side of general concept inclusion axioms. We use a special semantics for Horn-CPDLreg that is based on pseudo-interpretations. It is called the constructive semantics and coincides with the traditional semantics when the concept constructor "universal restriction" is disallowed on the left hand side of concept inclusion axioms or when the language is used as an epistemic formalism and the accessibility relations are serial. We provide an algorithm with PTIME data complexity for checking whether a knowledge base in Horn-CPDLreg has a pseudo-model. This shows that the instance checking problem in Horn-CPDLreg with respect to the constructive semantics has PTIME data complexity.

  • KES-AMSTA - On the Horn Fragments of Serial Regular Grammar Logics with Converse.
    2014
    Co-Authors: Linh Anh Nguyen, Andrzej Szałas
    Abstract:

    We study Horn fragments of serial multimodal logics which are characterized by Regular Grammars with converse. Such logics are useful for reasoning about epistemic states of multiagent systems as well as similarity-based approximate reasoning. We provide the first algorithm with PTIME data complexity for checking satisfiability of a Horn knowledge base in a serial Regular Grammar logic with converse.

  • on the horn fragments of serial Regular Grammar logics with converse
    Agent and Multi-Agent Systems: Technologies and Applications, 2013
    Co-Authors: Linh Anh Nguyen, Andrzej Szalas
    Abstract:

    We study Horn fragments of serial multimodal logics which are characterized by Regular Grammars with converse. Such logics are useful for reasoning about epistemic states of multiagent systems as well as similarity-based approximate reasoning. We provide the first algorithm with PTIME data complexity for checking satisfiability of a Horn knowledge base in a serial Regular Grammar logic with converse.

  • ExpTime Tableau Decision Procedures for Regular Grammar Logics with Converse
    Studia Logica, 2011
    Co-Authors: Linh Anh Nguyen, Andrzej Szałas
    Abstract:

    Grammar logics were introduced by Fariñas del Cerro and Penttonen in 1988 and have been widely studied. In this paper we consider Regular Grammar logics with converse ( REG ^ c logics) and present sound and complete tableau calculi for the general satisfiability problem of REG ^ c logics and the problem of checking consistency of an ABox w.r.t. a TBox in a REG ^ c logic. Using our calculi we develop ExpTime (optimal) tableau decision procedures for the mentioned problems, to which various optimization techniques can be applied. We also prove a new result that the data complexity of the instance checking problem in REG ^ c logics is coNP-complete.

Andrzej Szalas - One of the best experts on this subject based on the ideXlab platform.

  • on the horn fragments of serial Regular Grammar logics with converse
    Agent and Multi-Agent Systems: Technologies and Applications, 2013
    Co-Authors: Linh Anh Nguyen, Andrzej Szalas
    Abstract:

    We study Horn fragments of serial multimodal logics which are characterized by Regular Grammars with converse. Such logics are useful for reasoning about epistemic states of multiagent systems as well as similarity-based approximate reasoning. We provide the first algorithm with PTIME data complexity for checking satisfiability of a Horn knowledge base in a serial Regular Grammar logic with converse.

  • a tableau calculus for Regular Grammar logics with converse
    Conference on Automated Deduction, 2009
    Co-Authors: Linh Anh Nguyen, Andrzej Szalas
    Abstract:

    We give a sound and complete tableau calculus for deciding the general satisfiability problem of Regular Grammar logics with converse (REG c logics). Tableaux of our calculus are defined as "and-or" graphs with global caching. Our calculus extends the tableau calculus for Regular Grammar logics given by Gore and Nguyen [11] by using a cut rule and existential automaton-modal operators to deal with converse. We use it to develop an ExpTime (optimal) tableau decision procedure for the general satisfiability problem of REG c logics. We also briefly discuss optimizations for the procedure.

Bruce W. Watson - One of the best experts on this subject based on the ideXlab platform.

  • A new Regular Grammar pattern matching algorithm
    Theoretical Computer Science, 2003
    Co-Authors: Bruce W. Watson
    Abstract:

    AbstractThis paper presents a Boyer–Moore type algorithm for Regular Grammar pattern matching, answering a variant of an open problem posed by Aho (Pattern Matching in Strings, Academic Press, New York, 1980, p. 342). The new algorithm handles patterns specified by Regular (left linear) Grammars—a generalization of the Boyer–Moore (single keyword) and Commentz-Walter (multiple keyword) algorithms.Like the Boyer–Moore and Commentz-Walter algorithms, the new algorithm makes use of shift functions which can be precomputed and tabulated. The precomputation functions are derived, and it is shown that they can be obtained from Commentz-Walter's d1 and d2 shift functions.In most cases, the Boyer–Moore (respectively, Commentz-Walter) algorithm has greatly outperformed the Knuth–Morris–Pratt (respectively, Aho–Corasick) algorithm. In practice, an earlier version of the algorithm presented in this paper also frequently outperforms the Regular Grammar generalization of the Aho–Corasick algorithm

  • a new Regular Grammar pattern matching algorithm
    European Symposium on Algorithms, 1996
    Co-Authors: Bruce W. Watson
    Abstract:

    This paper presents a Boyer-Moore type algorithm for Regular Grammar pattern matching, answering a variant of an open problem posed by A.V. Aho in 1980 [2, p. 342]. The new algorithm handles patterns specified by Regular (left linear) Grammars — a generalization of the Boyer-Moore (single keyword) and Commentz-Walter (multiple keyword) algorithms, both considered extensively in [17] and [14, Chapter 4]. Like the Boyer-Moore and Commentz-Walter algorithms, the new algorithm makes use of shift functions which can be precomputed and tabulated. The precomputation functions are derived, and it is shown that they can be precomputed from Commentz-Walter's d1 and d2 shift functions.

  • ESA - A New Regular Grammar Pattern Matching Algorithm
    Algorithms — ESA '96, 1996
    Co-Authors: Bruce W. Watson
    Abstract:

    This paper presents a Boyer-Moore type algorithm for Regular Grammar pattern matching, answering a variant of an open problem posed by A.V. Aho in 1980 [2, p. 342]. The new algorithm handles patterns specified by Regular (left linear) Grammars — a generalization of the Boyer-Moore (single keyword) and Commentz-Walter (multiple keyword) algorithms, both considered extensively in [17] and [14, Chapter 4]. Like the Boyer-Moore and Commentz-Walter algorithms, the new algorithm makes use of shift functions which can be precomputed and tabulated. The precomputation functions are derived, and it is shown that they can be precomputed from Commentz-Walter's d1 and d2 shift functions.

Rajeev Gore - One of the best experts on this subject based on the ideXlab platform.

  • Grammar logics in nested sequent calculus proof theory and decision procedures
    arXiv: Logic in Computer Science, 2012
    Co-Authors: Alwen Tiu, Egor Ianovski, Rajeev Gore
    Abstract:

    A Grammar logic refers to an extension to the multi-modal logic K in which the modal axioms are generated from a formal Grammar. We consider a proof theory, in nested sequent calculus, of Grammar logics with converse, i.e., every modal operator [a] comes with a converse. Extending previous works on nested sequent systems for tense logics, we show all Grammar logics (with or without converse) can be formalised in nested sequent calculi, where the axioms are internalised in the calculi as structural rules. Syntactic cut-elimination for these calculi is proved using a procedure similar to that for display logics. If the Grammar is context-free, then one can get rid of all structural rules, in favor of deep inference and additional propagation rules. We give a novel semi-decision procedure for context-free Grammar logics, using nested sequent calculus with deep inference, and show that, in the case where the given context-free Grammar is Regular, this procedure terminates. Unlike all other existing decision procedures for Regular Grammar logics in the literature, our procedure does not assume that a finite state automaton encoding the axioms is given.

  • a tableau calculus with automaton labelled formulae for Regular Grammar logics
    Theorem Proving with Analytic Tableaux and Related Methods, 2005
    Co-Authors: Rajeev Gore, Linh Anh Nguyen
    Abstract:

    We present a sound and complete tableau calculus for the class of Regular Grammar logics. Our tableau rules use a special feature called automaton-labelled formulae, which are similar to formulae of automaton propositional dynamic logic. Our calculus is cut-free and has the analytic superformula property so it gives a decision procedure. We show that the known EXPTIME upper bound for Regular Grammar logics can be obtained using our tableau calculus. We also give an effective Craig interpolation lemma for Regular Grammar logics using our calculus.

  • TABLEAUX - A tableau calculus with automaton-labelled formulae for Regular Grammar logics
    Lecture Notes in Computer Science, 2005
    Co-Authors: Rajeev Gore, Linh Anh Nguyen
    Abstract:

    We present a sound and complete tableau calculus for the class of Regular Grammar logics. Our tableau rules use a special feature called automaton-labelled formulae, which are similar to formulae of automaton propositional dynamic logic. Our calculus is cut-free and has the analytic superformula property so it gives a decision procedure. We show that the known EXPTIME upper bound for Regular Grammar logics can be obtained using our tableau calculus. We also give an effective Craig interpolation lemma for Regular Grammar logics using our calculus.

Andrzej Szałas - One of the best experts on this subject based on the ideXlab platform.

  • KES-AMSTA - On the Horn Fragments of Serial Regular Grammar Logics with Converse.
    2014
    Co-Authors: Linh Anh Nguyen, Andrzej Szałas
    Abstract:

    We study Horn fragments of serial multimodal logics which are characterized by Regular Grammars with converse. Such logics are useful for reasoning about epistemic states of multiagent systems as well as similarity-based approximate reasoning. We provide the first algorithm with PTIME data complexity for checking satisfiability of a Horn knowledge base in a serial Regular Grammar logic with converse.

  • ExpTime Tableau Decision Procedures for Regular Grammar Logics with Converse
    Studia Logica, 2011
    Co-Authors: Linh Anh Nguyen, Andrzej Szałas
    Abstract:

    Grammar logics were introduced by Fariñas del Cerro and Penttonen in 1988 and have been widely studied. In this paper we consider Regular Grammar logics with converse ( REG ^ c logics) and present sound and complete tableau calculi for the general satisfiability problem of REG ^ c logics and the problem of checking consistency of an ABox w.r.t. a TBox in a REG ^ c logic. Using our calculi we develop ExpTime (optimal) tableau decision procedures for the mentioned problems, to which various optimization techniques can be applied. We also prove a new result that the data complexity of the instance checking problem in REG ^ c logics is coNP-complete.

  • CADE - A Tableau Calculus for Regular Grammar Logics with Converse
    Automated Deduction – CADE-22, 2009
    Co-Authors: Linh Anh Nguyen, Andrzej Szałas
    Abstract:

    We give a sound and complete tableau calculus for deciding the general satisfiability problem of Regular Grammar logics with converse (REG c logics). Tableaux of our calculus are defined as "and-or" graphs with global caching. Our calculus extends the tableau calculus for Regular Grammar logics given by Gore and Nguyen [11] by using a cut rule and existential automaton-modal operators to deal with converse. We use it to develop an ExpTime (optimal) tableau decision procedure for the general satisfiability problem of REG c logics. We also briefly discuss optimizations for the procedure.