On the Complexity of the Equational Theory of Relational Action Algebras | Zendy

Wojciech Buszkowski | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On the Complexity of the Equational Theory of Relational Action Algebras

Author(s) -

Wojciech Buszkowski

Publication year - 2006

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-37873-1

DOI - 10.1007/11828563_7

Subject(s) - computer science , action (physics) , algebra over a field , equational logic , theoretical computer science , programming language , rewriting , pure mathematics , mathematics , physics , quantum mechanics

Pratt [22] defines action algebras as Kleene algebras with residuals. In [9] it is shown that the equational theory of *-continuous action algebras (lattices) is Π$^{0}_{1}$–complete. Here we show that the equational theory of relational action algebras (lattices) is Π$^{0}_{1}$ –hard, and some its fragments are Π$^{0}_{1}$–complete. We also show that the equational theory of action algebras (lattices) of regular languages is Π$^{0}_{1}$–complete.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research