Selected publications at LSV: 2005

M. Droste and P. Gastin. Weighted Automata and Weighted Logics. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lisboa, Portugal, July 2005, LNCS 3580, pages 513-525. Springer. ( PDF | PS | PS.GZ | PDF (long version) | PS (long version) | PS.GZ (long version) )
doi: 10.1007/11523468_42

Abstract:: Weighted automata are used to describe quantitative properties in various areas such as probabilistic systems, image compression, speech-to-text processing. The behaviour of such an automaton is a mapping, called a formal power series, assigning to each word a weight in some semiring. We generalize Büchi's and Elgot's fundamental theorems to this quantitative setting. We introduce a weighted version of MSO logic and prove that, for commutative semirings, the behaviours of weighted automata are precisely the formal power series definable with our weighted logic. We also consider weighted first-order logic and show that aperiodic series coincide with the first-order definable ones, if the semiring is locally finite, commutative and has some aperiodicity property.

`@inproceedings{Gastin-ICALP2005,`
	`address =`	`{Lisboa, Portugal},`
	`author =`	`{Droste, Manfred and Gastin, Paul},`
	`booktitle =`	`{{P}roceedings of the 32nd {I}nternational {C}olloquium on {A}utomata, {L}anguages and {P}rogramming ({ICALP}'05)},`
	`DOI =`	`{10.1007/11523468_42},`
	`editor =`	`{Caires, Lu{\'\i}s and Italiano, Giuseppe F. and Monteiro, Lu{\'\i}s and Palamidessi, Catuscia and Yung, Moti},`
	`month =`	`jul,`
	`pages =`	`{513-525},`
	`publisher =`	`{Springer},`
	`series =`	`{Lecture Notes in Computer Science},`
	`title =`	`{Weighted Automata and Weighted Logics},`
	`url =`	`{http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/icalp05dg-final.pdf},`
	`volume =`	`{3580},`
	`year =`	`{2005},`
`}`

About LSV