Wyniki wyszukiwania - BazTech

1

Languages Accepted by Weighted Restarting Automata

Wang Qichao

Fundamenta Informaticae

|

2021

|

Vol. 180, nr 1-2

151--177

EN

Weighted restarting automata have been introduced to study quantitative aspects of computations of restarting automata. In earlier works we studied the classes of functions and relations that are computed by weighted restarting automata. Here we use them to define classes of formal languages by restricting the weight associated to a given input word through an additional requirement. In this way, weighted restarting automata can be used as language acceptors. First, we show that by using the notion of acceptance relative to the tropical semiring, we can avoid the use of auxiliary symbols. Furthermore, a certain type of word-weighted restarting automata turns out to be equivalent to non-forgetting restarting automata, and another class of languages accepted by word-weighted restarting automata is shown to be closed under the operation of intersection. This is the first result that shows that a class of languages defined in terms of a quite general class of restarting automata is closed under intersection. Finally, we prove that the restarting automata that are allowed to use auxiliary symbols in a rewrite step, and to keep on reading after performing a rewrite step can be simulated by regular-weighted restarting automata that cannot do this.

2

Some results on graph associated to co-ideals of commutative semirings

Talebi Yahya, Darzi Atefeh

Fasciculi Mathematici

|

2020

|

nr 64

91--100

EN

For a commutative semiring R with non-zero identity, the graph Ω(R) of R, is the graph whose vertices are all elements of R and two distinct vertices x and y are adjacent if and only if the product of the co-ideals generated by x and y is R. In this paper, we study some properties of this graph such as planarity, domination number and connectivity.

3

Polynomially representable semirings

Chajda I., Eigenthaler G.

Demonstratio Mathematica

|

2011

|

Vol. 44, nr 4

693-698

EN

We characterize semirings which can be represented by an algebra of binary polynomials of the form a = x + y where the operations are compositions of functions. Furthermore, we classify, which algebras with two binary and two nullary operations (satisfying some natural identities) can be represented in this way, and how these algebras are related to semirings.

4

Note on Some Order Properties Related to Processes Semantics (I)

Vaida D.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

307-319

EN

This note begins a study of some elementary properties related to the order structures applied in the algebraic approach to processes semantics. The support examples come from the partially additive semantics developed by Steenstrup (1985) and Manes and Arbib (1986) and from process algebra of Baeten and Weijland (1990). The main sources for the algebraic theory are F.A.Smith (1966) and Golan (1999). We show that different properties can be extended to partially additive distributive algebras more general than sum-ordered partial semirings. One establishes that the support examples constitute multilattices, in the sense of Benado (1955). By the examples, the ordering considered, and the references, this preliminary study is related to Rudeanu et al. (2004) and to the algebraic approach to languages due to Mateescu, e.g., (1996), (1989), (1994).

5

Semirings in Operations Research and Computer Science: More Algebra

Rudeanu S., Vaida D.

Fundamenta Informaticae

|

2004

|

Vol. 61, nr 1

61--85

EN

We undertake an axiomatic study of certain semirings and related structures that occur in operations research and computer science. We focus on the properties A,I,U,G,Z,L that have been used in the algebraic study of path problems in graphs and prove that the only implications linking the above properties are essentially those already known. On the other hand we extend those implications to the framework of left and right variants of A,I,U,G,Z,L, and we also prove two embedding theorems. Further generalizations refer mainly to semiring-like algebras with a partially defined addition, which is needed in semantics. As suggested by idempotency (I) and absorption (A), we also examine in some detail the connections between semirings and distributive lattices, which yield new systems of axioms for the latter.

6

All pre-solid varieties of semirings

Denecke K., Hounnon H.

Demonstratio Mathematica

|

2004

|

Vol. 37, nr 1

13--34

EN

A semiring is an algebra with two binary associative operations 4- and o which satisfy two distributive laws. Single semirings as well as classes of semirings are important structures in Automata Theory. Nevertheless, not so much is known about varieties of semirings. An identity t w t' is called a pre-hyperidentity of a variety V of semirings if whenever the operation symbols occurring in t and in t' are replaced by binary terms different from variables, the identity which results, holds in V. A variety V of semirings is called pre-solid if every identity holds as a pre-hyperidentity in V. The set of all pre-solid varieties of semirings forms a complete sublattice of the lattice of all varieties of semirings. To get more insight into the lattice of all varieties of semirings we will give a complete characterization of the lattice of all pre-solid varieties of semirings.