Name
Abstract | ||
|---|---|---|
In order to generalize the Kleene theorem from the free monoid to richer algebraic structures, we consider the non deterministic acceptance by a finite automaton of subsets of vertices of a graph. The subsets accepted in such a way are the equational subsets of vertices of the graph in the sense of Mezei and Wright. We introduce the notion of deterministic acceptance by finite automaton. A graph satisfies the Kleene equality if the two acceptance modes are equivalent, and in this case, the equational subsets form a Boolean algebra. We establish that the infinite grid and the transition graphs of deterministic pushdown automata satisfy the Kleene equality and we present families of graphs in which the free product of graphs preserves the Kleene equality. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11821069_19 | MFCS |
Keywords | Field | DocType |
finite automaton,free monoid,deterministic pushdown,kleene equality,acceptance mode,equational subsets,non deterministic acceptance,deterministic acceptance,transition graph,kleene theorem,free product,satisfiability,boolean algebra | Kleene algebra,Discrete mathematics,Combinatorics,Deterministic automaton,Kleene star,Deterministic pushdown automaton,Cayley graph,Kleene's recursion theorem,Graph product,Free monoid,Mathematics | Conference |
Volume | ISSN | ISBN |
4162 | 0302-9743 | 3-540-37791-3 |
Citations | PageRank | References |
1 | 0.36 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| arnaud carayol | 1 | 216 | 20.22 |
| Didier Caucal | 2 | 470 | 39.15 |