Name
Abstract | ||
|---|---|---|
We introduce new classes of weighted automata on words. Equipped with pebbles and a two-way mechanism, they go beyond the class of recognizable formal power series, but capture a weighted version of first-order logic with bounded transitive closure. In contrast to previous work, this logic allows for unrestricted use of universal quantification. Our main result states that pebble weighted automata, nested weighted automata, and this weighted logic are expressively equivalent. We also give new logical characterizations of the recognizable series. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-14162-1_49 | ICALP (2) |
Keywords | Field | DocType |
new logical characterization,weighted version,nested weighted automaton,pebble weighted automaton,recognizable series,new class,weighted automaton,recognizable formal power series,weighted logic,transitive closure logic,first-order logic,formal power series,first order logic,transitive closure | Discrete mathematics,Combinatorics,Computer science,Automaton,Formal power series,Pebble,Transitive closure,Expressive power,Universal quantification,Bounded function | Conference |
Volume | ISSN | ISBN |
6199 | 0302-9743 | 3-642-14161-7 |
Citations | PageRank | References |
15 | 0.69 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benedikt Bollig | 1 | 427 | 35.02 |
| Paul Gastin | 2 | 1165 | 75.66 |
| Benjamin Monmege | 3 | 77 | 11.97 |
| Marc Zeitoun | 4 | 288 | 24.51 |