掲載種別：研究論文（学術雑誌）   出版者・発行元：The Japan Society for Industrial and Applied Mathematics  

DOI： 10.14495/jsiaml.12.29

記述言語：英語  

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

その他リンク： http://dblp.uni-trier.de/db/conf/lics/lics2016.html#conf/lics/Uramoto16

記述言語：日本語   出版者・発行元：京都大学  

CiNii Research

その他リンク： http://hdl.handle.net/2433/224201

記述言語：日本語   出版者・発行元：京都大学  

CiNii Research

その他リンク： http://hdl.handle.net/2433/223301

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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