Publishing type：Research paper (scientific journal)   Publisher：The Japan Society for Industrial and Applied Mathematics  

DOI： 10.14495/jsiaml.12.29

Language：English  

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE INC  

Kleene algebra with tests (KAT) was introduced by Kozen as an extension of Kleene algebra (KA). So far, the decidability of equational formulas (p = q) and Horn formulas (boolean AND(i)p(i) =q(i) -> p = q) in KAT has been investigated by several authors. Continuing this line of research, the current paper studies the decidability of existentially quantified equational formulas there exists q epsilon P.(p = q) in KAT, where P is a fixed collection of KAT terms and plays a role as a parameter of this decision problem. To design a systematic strategy of deciding problems of this form, given in this paper is an effective procedure of constructing from each KAT term p a finite KAT model K(p) that will be called the canonical finite model of the KAT term p. Applications of this construction are presented, proving the decidability of there exists q epsilon P.(p = q) for several non-trivial P. (C) 2015 Elsevier Inc. All rights reserved.

DOI： 10.1016/j.jlamp.2015.11.001

Web of Science

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

Recently, Eilenberg's variety theorem was reformulated in the light of Stone's duality theorem. On one level, this reformulation led to a unification of several existing Eilenberg-type theorems and further generalizations of these theorems. On another level, this reformulation is also a natural continuation of a research line on profinite monoids that has been developed since the late 1980s. The current paper concerns the latter in particular. In this relation, this paper introduces and studies the class of semi-galois categories, i.e. an extension of galois categories; and develops a particularly fundamental theory concerning semi-galois categories: That is, (I) a duality theorem between profinite monoids and semi-galois categories; (II) a coherent duality-based reformulation of two classical Eilenberg-type variety theorems due to Straubing [30] and Chaubard et al. [10]; and (III) a Galois-type classification of closed subgroups of profinite monoids in terms of finite discrete cofibrations over semi-galois categories.

DOI： 10.1145/2933575.2934528

Web of Science

Other Link： http://dblp.uni-trier.de/db/conf/lics/lics2016.html#conf/lics/Uramoto16

Language：Japanese  

CiNii Books

Other Link： http://hdl.handle.net/2433/224201

Language：Japanese  

CiNii Books

Other Link： http://hdl.handle.net/2433/223301

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

Kleene algebra with tests (KAT) was introduced by Kozen as an extension of Kleene algebra (KA). The decidability of equational formulas p = q and Horn formulas ∧ipi = qi → p = q in KAT has been studied so far by several researchers. Continuing this line of research, this paper studies the decidability of existentially quantified equational formulas ∃q ∈ P. (p = q) in KAT, where P is a fixed collection of KAT terms. A new completeness theorem of KAT is proved, and via the completeness theorem, the decision problem of ∃q ∈ P. (p = q) is reduced to a certain membership problem of regular languages, to which a pseudo-identity- based decision method is applicable. Based on this reduction, an instance of the problem is studied and shown to be decidable. © 2014 Springer International Publishing.

DOI： 10.1007/978-3-319-06251-8_6

Scopus