On complexity of Ehrenfeucht-Fraïssé games
| aut.researcher | Liu, Jiamou | |
| dc.contributor.author | Khoussainov, B | |
| dc.contributor.author | Liu, J | |
| dc.contributor.editor | Artemov, S | |
| dc.contributor.editor | Nerode, A | |
| dc.date.accessioned | 2011-11-27T03:57:03Z | |
| dc.date.available | 2011-11-27T03:57:03Z | |
| dc.date.copyright | 2007-06-10 | |
| dc.date.issued | 2007-06-10 | |
| dc.description.abstract | In this paper we initiate the study of Ehrenfeucht-Fraïssé games for some standard finite structures. Examples of such standard structures are equivalence relations, trees, unary relation structures, Boolean algebras, and some of their natural expansions. The paper concerns the following question that we call Ehrenfeucht-Fraïssé problem. Given n ϵ ω as a parameter, two relational structures A and B from one of the classes of structures mentioned above. How efficient is it to decide if Duplicator wins the n-round EF game G_n (A,B)? We provide algorithms for solving the Ehrenfeucht-Fraïssé problem for the mentioned classes of structures. The running times of all the algorithms are bounded by constants. We obtain the values of these constants as functions of n. | |
| dc.format.medium | paper and online | |
| dc.identifier.citation | Computer Science: Logical Foundations of Computer Science: proceedings from the International Symposium (LFCS'07), New York, NY, USA, vol.4514, pp. 293 - 309 | |
| dc.identifier.doi | 10.1007/978-3-540-72734-7_21 | |
| dc.identifier.isbn | 978-3-540-72732-3 | |
| dc.identifier.issn | 0302-9743 (Print) 1611-3349 (Online) | |
| dc.identifier.uri | https://hdl.handle.net/10292/2814 | |
| dc.publisher | Springer Berlin / Heidelberg | |
| dc.relation.uri | http://dx.doi.org/10.1007/978-3-540-72734-7_21 | |
| dc.rights | An author may self-archive an author-created version of his/her article on his/her own website and or in his/her institutional repository. He/she may also deposit this version on his/her funder’s or funder’s designated repository at the funder’s request or as a result of a legal obligation, provided it is not made publicly available until 12 months after official publication. He/ she may not use the publisher's PDF version, which is posted on www.springerlink.com, for the purpose of self-archiving or deposit. Furthermore, the author may only post his/her version provided acknowledgement is given to the original source of publication and a link is inserted to the published article on Springer's website. The link must be accompanied by the following text: "The final publication is available at www.springerlink.com”. (Please also see Publisher’s Version and Citation) | |
| dc.rights.accessrights | OpenAccess | |
| dc.title | On complexity of Ehrenfeucht-Fraïssé games | |
| dc.type | Conference Contribution | |
| pubs.organisational-data | /AUT | |
| pubs.organisational-data | /AUT/Design & Creative Technologies | |
| pubs.organisational-data | /AUT/Design & Creative Technologies/School of Computing & Mathematical Science | |
| pubs.organisational-data | /AUT/PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers | |
| pubs.organisational-data | /AUT/PBRF Researchers/Design & Creative Technologies PBRF Researchers/DCT C & M Computing |