Výsledky vyhledávání - "NAKAMURA Yoshiki"

Report

Words-to-Letters Valuations for Language Kleene Algebras with Variable and Constant Complements

We investigate the equational theory for Kleene algebra terms with variable complements and constant complements -- (language) complement where it applies only to variables or constants -- w.r.t. languages. While the equational theory w.r.t. language

Externí odkaz: http://arxiv.org/abs/2411.16397

Zobrazit plný text záznamu

Report

Derivatives on Graphs for the Positive Calculus of Relations with Transitive Closure

Autor: Nakamura, Yoshiki

We prove that the equational theory of the positive calculus of relations with transitive closure (PCoR*) is EXPSPACE-complete. PCoR* terms consist of the following standard operators on binary relations: identity, empty, universality, union, interse

Externí odkaz: http://arxiv.org/abs/2408.08236

Zobrazit plný text záznamu

Report

Note on a Translation from First-Order Logic into the Calculus of Relations Preserving Validity and Finite Validity

Autor: Nakamura, Yoshiki

In this note, we give a linear-size translation from formulas of first-order logic into equations of the calculus of relations preserving validity and finite validity. Our translation also gives a linear-size conservative reduction from formulas of f

Externí odkaz: http://arxiv.org/abs/2310.02845

Zobrazit plný text záznamu

Report

Words-to-Letters Valuations for Language Kleene Algebras with Variable Complements

Autor: Nakamura, Yoshiki, Sin'ya, Ryoma

Publikováno v: EPTCS 386, 2023, pp. 185-199

We investigate the equational theory of Kleene algebra terms with variable complements -- (language) complement where it applies only to variables -- w.r.t. languages. While the equational theory w.r.t. languages coincides with the language equivalen

Externí odkaz: http://arxiv.org/abs/2309.02760

Zobrazit plný text záznamu

Report

On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation

Autor: Nakamura, Yoshiki

We introduce the $k$-variable-occurrence fragment, which is the set of terms having at most $k$ occurrences of variables. We give a sufficient condition for the decidability of the equational theory of the $k$-variable-occurrence fragment using the f

Externí odkaz: http://arxiv.org/abs/2307.05046

Zobrazit plný text záznamu

Report

Existential Calculi of Relations with Transitive Closure: Complexity and Edge Saturations

Autor: Nakamura, Yoshiki

We study the decidability and complexity of equational theories of the existential calculus of relations with transitive closure (ECoR*) and its fragments, where ECoR* is the positive calculus of relations with transitive closure extended with comple

Externí odkaz: http://arxiv.org/abs/2304.12079

Zobrazit plný text záznamu