SSFLA 2011: Finite Automata, Football and Roller-Coasters

Last week, which was a Holy week before Easter, I was in a nice city in Spain – Tarragona, and attended lectures on computational complexity theory at Spring School in Formal Languages and Applications (SSFLA 2011).

That was the first time I’d been at such a school. Blue Spanish sky, sunny weather, nice fellows – everything left so many unforgettable impressions imprinted as almost a thousand of photos and videos, which are selectively published on Flickr.


Professors Holzer and Baader were great, delivering very interesting and not boring lectures. During brakes we were getting to know each other and discuss our research themes.

Formal Languages and Automata

A formal language for us was mathematics and computational theory.
So we could not help making photos with some mathematical interpretation:
Reflexive relation

Transitive relation

I also took a photo of myself. So, being in a symmetric, reflexive and transitive relation we were in the equivalence relation with each other 🙂

Informal Languages

Spring School was also a great cultural exchange event for all of us. We came from all parts of Europe and South America as well: Germany, Italy, France, Czech Republic, Denmark, Russia, Colombia, Argentina…
An informal language for us was English – the universal communication language for all people of the world. I’d completely realized its benefit in our life during the School.
We used a lot of informal English after lessons 🙂

Sea and Relax

One day Peter, Gil and I went to Salou, a famous resort city on the Mediterranean sea coast named “Costa Dorada”, which is “Gold Coast” from Spanish. Beautiful sea views and gold sand, a bit windy, but sunny weather were very relaxing.
We were basking in the sunshine and resting under Spanish palms. In that moment we were very far from the School in our thoughts, as if we’d escaped to unexpected vacations in the middle of workday.


Football Match and Salsa

One day we watched a match between Barcelona and Real Madrid football teams. That was very funny and enjoyable!
We’d been eating good Colombian food in a Colombian bar. I liked “Empanada” (a stuffed pastry), “Arepa” (pancake-like thin bread from corn meal) with meat and a milk shake with “Lulo” fruit were very tasty!
Two football fans were among us – Luis supporting Real Madrid, and Andres being for Barcelona. The game was very interesting, emotional, full of dramatic goal moments, and we were quite involved, even not being big football fans.

Next day we came to the Colombian bar again and had been dancing salsa till night. I love dancing, and I’d known basic steps of salsa. Andres turned out a good salsa dancer, he leaded well and showed me a real salsa drive. Andres is from Cali – the capital of salsa in Colombia. That was great and unforgettable to dance with a man, who knows what a real Colombian salsa is! Thank you, Andres!

Port Aventura’s Amusements

I had only 3 hours in the park, which is extremely short to try all available attractions. Also the ticket costs 44 euro, considerable price for a full day, but quite expensive for a couple of hours. I walked around the park, which was divided into several zones dedicated to different world parts and countries – China, Mexico, Far West, Europe. Each part was decorated in a special style – Far West is full of Saloons, has a condor in a cage and American food. In China’s part there is the longest roller-coaster – Dragon Khan, in Mexico – the most scariest one – Hurakan Condor.

Long queues for interesting attractions were annoying.  Fortunately, I managed to try Furious Baco in “Europe”. Baco’s worth it – very fast and breathtaking refreshment after 30 minutes waiting in a queue!


The last day, Holy Friday, Paula, Andres and I went to Barcelona. Barcelona was great! For me and Paula that was the first time to Barcelona, and of course, we visited Gaudi’s buildings – Sagrada Familia and La Pedrera.
But the most startling place for me was Gaudi’s park.  Fanciful trees and constructions, cookie-like buildings, plenty of mosaic – that was all amazing! We’d noticed that it takes only two steps toward the park, and you get a completely another view, full of new details and features you couldn’t see from the previous point.

The week passed very fast, left me with lots of impressions and inspired. That was the best trip I’d ever made.
For more photos, you can also view this Flickr set.


Leave a comment

Filed under events, trips

Funny English Words and Their Meanings

Some time ago I started to collect interesting English words and phrases, which have different and tricky meanings and should be used carefully to avoid comic and awkward situations. That is specially important for non-native English speakers and everyone who studies and continues studying the language. A few of these words are in this post.

Here is my list of notable words:

  • Probation
  • Facilities
  • Ruth
  • Goggle – this word is more fun than can be ridiculously used


If you want to say that you’ve come for a temporary practice, to get some useful experience and then you’ll go back to your country/work/university – don’t use this tricky word ‘probation’. Though, you can find it within the Lingvo dictionary by searching for ‘стажировка’.
Look up inversely, search for ‘probation’. One of possible meanings is to be currently released from a prison for a trial period.
So if you’ve said that you are on a probation here, don’t wonder why your new mates have become alert, reserved and unfriendly with you, and try to avoid contacting you later.


There are a lot of synonyms for opportunities and possibilities in English. But be careful to use ‘facilities’ in this meaning!
One ‘facility’ in the singular form may be used as an ‘opportunity’, though there are some meaning shades. But do not use this noun in plural to denote opportunities – ‘facilities’ may also mean WC 🙂


A woman’s name, a part of the Holy Bible – the Ruth. But that is not all.
Ruth is also a pity, compassion and mercy.
However, what a surprise it is that if you say something like “Excuse me, where is the Ruth?”, nobody’ll help you with the Bible. Instead, people can pass you toward the woman’s WC 🙂 Strange riddle. It is interesting, how does this word start being used in such a manner?

Beer Goggles

This word also has plenty of meanings. But one of them is the funniest, denoting a whole phrase in Russian at once.
Look up in Lingvo:
beer goggles – состояние алкогольного опьянения, при котором представители противоположного пола начинают казаться более привлекательными (сравни русское “не бывает некрасивых женщин, бывает мало водки”) I couldn’t date her without my beer goggles on. — Она была такая уродина, что каждый раз, прежде чем идти на свидание, мне надо было как следует принять.

Strong phrase, we should add it to our armoury 🙂  Note that double ‘g’ and not double ‘o’ – goggle. It’s none of Google’s doing 🙂

That’s all now. The vocabulary will be continued. I’ll much appreciate any of your comments 🙂

1 Comment

Filed under Uncategorized – Best English Dictionary and Thesaurus

Our English tutor has recommended an on-line dictionary and thesaurus –

I like it! It is really comprehensive and full of clear explanations of words and meaning shades.
Macmillan has an awesome intelligent thesaurus, which shows only words related to the needed meaning, and does not overwhelm the search result. Also Macmillan regularly publishes new English words based on the constant research of live and trustworthy spoken and written language examples.

Nice service! Worth adding to Favourite links, I think.

Leave a comment

Filed under Uncategorized


В ноябре прошлого года я писала об OWL и синтаксисе описаний онтологий. В этой статье рассказывается о теоретических основах представления знаний в виде онтологий, о проблеме хранения данных и задаче ODBA.
* * *

Задача ODBA

С развитием концептуального моделирования (ООП, UML) и усложнения систем возникает необходимость обеспечения информационной системы высокоуровневым интерфейсом для работы с большими объемами данных. Такой интерфейс можно обеспечить за счет представления знаний о предметной области в форме онтологического описания (базы знаний). Задача доступа к данным через высокоуровневый интерфейс онтологии называется ontology-based data access (ODBA). Решение должно удовлетворять следующим требованиям: 1) эффективное выполнение запросов, которые в идеале должны выполняться с той же скоростью, что и SQL-запросы над существующими РБД, и 2) обработка запросов должна использовать все преимущества реляционных технологий, уже используемых для хранения данных.

База знаний и задачи логического вывода

База знаний (knowledge base, KB) – описание предметной области в виде онтологии – позволяет извлекать данные (ABox), хранящиеся в БД, с учетом ограничений, накладываемых на более высоком концептуальном уровне (TBox):
KB = ABox+TBox,
Где ABox – assertional box – Множество данных, хранящихся в БД;
TBox – terminological box – Концептуальная модель данных, например, Entity-Relationship.
В качестве языка представления знаний используется дискриптивная логика (ДЛ) определенного уровня выразительности. Уровень выразительности определяется как набор аксиом, разрешенных в TBox и ABox. С одной стороны, язык должен быть как можно более выразительным, чтобы полностью описать предметную область; с другой стороны, задачи логического вывода над KB должны иметь приемлемую вычислительную сложность.
Пусть дана KB K=(T,A). Фундаментальными задачами логического вывода (reasoning) являются:

  • Выполнимость (satisfiability). Требуется проверить, существует ли модель K.
  • Проверка экземпляра (instance checking). Пусть даны объект a и класс C. Требуется определить, что K⊨C(a), или является ли a^I∈C^I для каждой модели I KB K.
  • Ответ на запрос (query answering). Пусть дан запрос q(x ⃗ ) и кортеж a ⃗ объектов из A. Требуется определить, что K⊨q(a ⃗), или a ⃗ является ответом на запрос q(x ⃗ ) относительно K.
  • Вычислительная сложность задач зависит от переменного и некоторого фиксированного числа входных параметров. Входными параметрами являются: размер TBox, |T|,размер ABox, |A|, размер K=(T,A), размер запроса – число параметров запроса q(x ⃗ ), |x ⃗ |=N.
    Для задач логического вывода различают комбинированную сложность (combined complexity) и сложность по объему данных (data complexity). В контексте задачи ODBA рассматривают сложность по объему данных, считая размер TBox фиксированным и размер запроса пренебрежимо малым, по сравнению с объемом данных ABox.

    Представление знаний в DL-Lite

    Для концептуального моделирования наряду с UML и ER предложены языки семейства DL-Lite. Общими чертами логик семейства DL-Lite являются следующие – 1) нет возможности привязки ролей к конкретным концептам, все роли могут быть применены ко всем концептам (∃R.C),C=⊺; 2) нет возможности определения покрытия предметной области в виде дизъюнкции концептов.
    Максимально выразительным языком для концептуального моделирования, для которого вычислительная сложность query answering не будет превосходить P, является 〖DL-Lite〗_horn^HF. Если ввести дополнительное ограничение UNA (unique name assumption): a_i^I≠a_j^I,i≠j, то query answering в 〖DL-Lite〗_horn^((HF)|(HN)) будет иметь наименьшую вычислительную сложность по объему данных – AC^0 . Следствием этого является важное свойство:

  • Пусть дана база знаний K=(T,A), удовлетворяющая 〖DL-Lite〗_horn^((HF)) с UNA, конъюнктивный (не содержащий дизъюнкций) запрос q(x ⃗ ). Тогда q(x ⃗ ) и TBox могут быть переписаны в виде объединения конъюнктивных запросов SQL(q(x ⃗ )) только над ABox, и ответ на этот запрос будет непротиворечивым (sound) и полным (complete).
  • На этом свойстве основано переписывание запросов (query rewriting), которое позволяет получить базу знаний на основе традиционной БД, работать с данными на концептуальном уровне независимо от конкретной схемы БД, эффективно используя все преимущества современных реляционных СУБД.
    Для систем, работающих с большими объемами данных, для которых основной задачей является query answering, консорциумом W3C предложен стандарт OWL 2 QL, который основан на еще менее выразительном, чем 〖DL-Lite〗_horn^((HF)), подмножестве аксиом 〖DL-Lite〗_core^H (другое обозначение – 〖DL-Lite〗_R^ ). Сложность всех задач логического вывода над онтологиями 〖DL-Lite〗_core^H не превосходит полиномиальной. Такое существенное ограничение было введено потому, что в OWL вместо UNA используется прямое обозначение равенства либо неравенства имен. Чтобы сложность задач логического вывода на онтологиях по стандарту OWL 2 QL оставалась постоянной, было решено не включать возможности определения функциональных зависимостей и числовых ограничений между концептами, при которых вычислительная сложность зависит от принятия/непринятия UNA.

    Переписывание запросов для высокоуровневого интерфейса доступа к данным

    Для OWL 2 QL активно разрабатываются алгоритмы переписывания запросов (query rewriting), которые позволят выполнять концептуальный query answering над имеющимися БД.
    В настоящий момент известно 2 алгоритма переписывания запросов. Алгоритм CGLLR для DL-Lite реализован в нескольких системах QuOnto, Owlgres, ROWLKit, алгоритм RQR для DL-Lite+ был представлен в 2009-м году и реализован в REQUIEM. Алгоритмы CGLLR и RQR возвращают одинаковые результаты переписывания запросов. В процессе переписывания каждый алгоритм порождает большое количество – порядка нескольких тысяч – UCQ (unique conjunctive query). Это приводит к формированию сложных SQL-запросов с большим количеством объединений (UNION), которые могут быть практически невыполнимы для СУБД.
    Ведется активная работа по оптимизации этих алгоритмов в следующих направлениях:

  • Упрощение первичного запроса q(x ⃗ ) с помощью резолюций;
  • Исключение UCQ, для которых не задано отображение (OWL->RDB mapping).
  • Оптимизированный RQR генерирует меньше UCQ, чем CGLLR, его можно использовать для более выразительных языков ДЛ, чем DL-Lite. Однако RQR все еще демонстрирует низкую эффективность на больших реальных объемах данных, не защищен от зацикливания и требует дополнительной информации для повышения скорости переписывания запросов.


  • Franconi. Propositional logic.
  • The DL-Lite Family and Relations
  • OWL 2 Web Ontology Language
    Profiles – W3C Recommendation, actual October 27, 2009
  • H.ector P.erez-Urbina, Ian Horrocks, and Boris Motik. Practical Aspects of Query Rewriting for OWL 2
  • Leave a comment

    Filed under Uncategorized

    One Year With WordPress!

    Full year passed so fast!
    Today I’ve noticed that the first posts published here are created long since a year ago.
    What are the results and conclusions?
    Blogging is useful. It really helps me not only note my impressions from visiting IT events, but also post pieces of information on various subjects, which are also may be interesting to my colleagues and friends.
    Finally, I refer to my blog in messages to my friends when speaking about upcoming events. So the message comes out short, and if the news is really interesting the addressee can follow the link and find out more information from my post.
    I like WordPress and will stay my blog on this engine. It is powerful, convenient, social-integrated and well indexed by popular Searchers.
    Try “Как я поступал в Вышку” at Google and see the results -)

    Leave a comment

    Filed under Uncategorized

    Техническая коммуникация и документирование ПО

    Сегодня второй день Зимней Школы по программной инженерии для выпускников ВУЗов’11, на которой я представила свой доклад о технической коммуникации и документировании ПО. Презентацию можно посмотреть здесь:
    Техническая коммуникация и документирование ПО.pps (PowerPoint 2003 file)

    Leave a comment

    Filed under CMS, Confluence, Документация, документирование ПО, единый источник документации, управление проектами, technical communication, technical writing, Wiki

    Готовится учебник по управлению программными проектами

    Максим Дорофеев, Сергей Архипенков и другие эксперты в области управления проектами готовят учебник, не пропустите!
    Вот ссылка на блог Максима:

    Учебник по управлению программными проектами.

    Авторы учебника проводят очень интересные лекции и семинары, я была на них. Очень жду книжки от мастеров своего дела, а не от унылых профессоров ВБД.

    По поводу интересных книжек от современных интересных авторов хочется еще отметить учебное пособие по теории сложности вычислений и алгоритмов, соавтором которого является Стас Фомин. Стас всегда представляет какие-нибудь ноу-хау и бросает вызов слушателям его докладов.

    Leave a comment

    Filed under управление проектами, project management, software lifecycle