A survey of graph and subgraph isomorphism problems

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

A survey of graph and subgraph isomorphism problems

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

The Borel Complexity of Isomorphism for Some First Order Theories

In this work we consider several instances of the following problem: "how complicated can the isomorphism relation for countable models be?"' Using the Borel reducibility framework, we investigate this question with regard to the space of countable models of particular complete first-order theories. We also investigate to what extent this complexity is mirrored in the number of back-and-forth inequivalent models of the theory. We consider this question for two large and related classes of theories. First, we consider o-minimal theories, showing that if T is o-minimal, then the isomorphism relation is either Borel complete or Borel. Further, if it is Borel, we characterize exactly which values can occur, and when they occur. In all cases Borel completeness implies lambda-Borel completeness for all lambda. Second, we consider colored linear orders, which are (complete theories of) a linear order expanded by countably many unary predicates. We discover the same characterization as with o-minimal theories, taking the same values, with the exception that all finite values are possible except two. We characterize exactly when each possibility occurs, which is similar to the o-minimal case. Additionally, we extend Schirrman's theorem, showing that if the language is finite, then T is countably categorical or Borel complete. As before, in all cases Borel completeness implies lambda-Borel completeness for all lambda.

ON ISOMORPHIC CLASSIFICATIONS OF SPACES OF COMPACT OPERATORS

We prove an extension of the classical isomorphic classification of Banach spaces of continuous functions on ordinals. As a consequence, we give complete isomorphic classifications of some Banach spaces K(X,Y(n)), eta >= omega, of compact operators from X to Y(eta), the space of all continuous Y-valued functions defined in the interval of ordinals [1, eta] and equipped with the supremum norm. In particular, under the Continuum Hypothesis, we extend a recent result of C. Samuel by classifying, up to isomorphism, the spaces K(X(xi), c(0)(Gamma)(eta)), where omega <= xi < omega(1,) eta >= omega, Gamma is a countable set, X contains no complemented copy of l(1), X* has the Mazur property and the density character of X** is less than or equal to N(1).

Gestão da Qualidade e sustentabilidade das organizações: o lado oculto da realidade

Este trabalho baseia-se num estudo de caso de uma organização do sector da construção civil e surge da minha preocupação em relação ao facto de que o sucesso das organizações depende da sua sustentabilidade e esta depende da regulação e da legitimidade organizacional. A certificação dos Sistemas de Gestão da Qualidade (SGQ) satisfaz estas duas condições, pois é vista como fonte de oportunidades para melhorar os processos e as práticas, reduzindo desperdícios operacionais, e para melhorar a identidade e a imagem organizacional junto das entidades interessadas, melhorando a aceitabilidade no mercado. Partindo deste pressuposto, adopto sistema teórico que focaliza a organização formal e a organização informal dos Sistemas de Gestão da Qualidade. Para isso, começo por convocar a teoria da burocracia de modo a analisar a dimensão formal da gestão e certificação dos Sistemas de Gestão da Qualidade. Posteriormente, e para melhor entender a organização burocrática da qualidade, convoco a teoria sobre disfunções da burocracia, de modo a identificar efeitos não intencionados, o modelo da anarquia organizada, para abordar a dimensão mais incerta e ambígua da Gestão da Qualidade e, por fim, a teoria institucional para captar a importância da isomorfização e da hipocrisia organizacional. Deste modo, abordando a dimensão formal e informal e a complexidade da Gestão da Qualidade, esta pesquisa oferece leitura interrogativa e preocupante acerca da sustentabilidade organizacional, mais concretamente a relação entre Gestão da Qualidade e sustentabilidade organizacional.

Práticas de contabilidade e controlo de gestão no setor automóvel

Dissertação apresentada para obtenção do Grau de Mestre em Contabilidade e Finanças, sob orientação de: Amélia Ferreira da Silva José António Fernandes Lopes Oliveira Vale

O ensino profissional de nível secundário em Portugal, 2000-2014

O presente estudo aborda a forma como as escolas secundárias públicas com ensino profissional (cursos profissionais) de qualificação profissional de nível 4, se têm vindo a adaptar às novas configurações do sistema educativo, na integração desta oferta educativa. Esta via de ensino tem contribuído de forma expressiva para o aumento da escolarização do ensino secundário nos últimos anos em Portugal. Tendo presentes estas novas configurações institucionais que resultaram em mudanças no sistema educativo, o Estado parece agora legitimar e apelar ao comportamento competitivo, numa ação conduzida por lógicas de mercado (quase-mercado). Destacamos aspetos fundamentais como os reflexos da crise económica e financeira no desemprego e na formulação de quadros de incerteza, o reforço do regime de autonomia, a imposição de condições de administração e gestão participativa, a estrutura e organização desta via de ensino, e o planeamento da oferta formativa como contextos centrais para a reflexão e identificação da ação estratégica. Recorremos ao conceito de instituição, o qual define o ambiente organizacional como um espaço de trocas de recursos económicos e simbólicos, e enfatiza que as estruturas organizacionais são o resultado de pressões exercidas pelo ambiente institucional em que estão inseridas, e não entidades passivas, pois desenvolvem práticas e estratégias consideradas apropriadas para assegurar o seu poder, legitimidade e sobrevivência. Através da análise da evolução das ofertas de cursos às escalas nacional e regional e de entrevistas com escolas públicas e municípios da rede EXCEL, bem como de escolas privadas dos mesmos concelhos, concluímos que numa primeira fase as escolas públicas pautaram as suas ofertas por estratégias defensivas, face à dependência de recursos, à procura de estabilidade organizativa e de afetação do corpo docente instalado e à perceção duvidosa sobre a autonomia. A segunda fase, a partir de 2011, carateriza-se pelo reforço da centralidade do Estado que passou a determinar as ofertas agindo como representante único da procura pública, ao mesmo tempo que se manteve a pressão concorrencial sobre as escolas como atores da oferta, estruturando um quase-mercado aproximado a um monopsónio.

Curry-Howard for sequent calculus at last!

This paper tries to remove what seems to be the remaining stumbling blocks in the way to a full understanding of the Curry-Howard isomorphism for sequent calculus, namely the questions: What do variables in proof terms stand for? What is co-control and a co-continuation? How to define the dual of Parigot's mu-operator so that it is a co-control operator? Answering these questions leads to the interpretation that sequent calculus is a formal vector notation with first-class co-control. But this is just the "internal" interpretation, which has to be developed simultaneously with, and is justified by, an "external" one, offered by natural deduction: the sequent calculus corresponds to a bi-directional, agnostic (w.r.t. the call strategy), computational lambda-calculus. Next, the duality between control and co-control is studied and proved in the context of classical logic, where one discovers that the classical sequent calculus has a distortion towards control, and that sequent calculus is the de Morgan dual of natural deduction.

Abordagem histórica e institucional da mudança em contabilidade de gestão: o caso da normalização nos hospitais públicos portugueses

A teoria institucional constituiu o enquadramento no qual foi suportada a pergunta geral desta investigação: como e porquê a Normalização da Contabilidade de Gestão (NCG) nos hospitais públicos portugueses surgiu e evoluiu? O objetivo geral foi compreender de forma profunda o surgimento e a mudança nas regras de NCG dos hospitais públicos portugueses no período histórico 1954-2011. Face ao enquadramento institucional que justificou uma investigação interpretativa, foi usado como método de investigação um estudo de caso explanatório. A evidência sobre o caso da NCG nos hospitais públicos portugueses foi recolhida em documentos e através de 58 entrevistas realizadas em 47 unidades de análise (nos serviços centrais de contabilidade do Ministério da Saúde e em 46 hospitais públicos, num total de 53 existentes). Quanto aos principais resultados obtidos, no período 1954-1974, as regras criadas pelo poder político para controlo dos gastos públicos e a contabilidade orçamental de base de caixa estiveram na génese dos primeiros conceitos de Contabilidade de Gestão (CG) para os serviços públicos de saúde portugueses. A transição de um regime ditatorial para um regime democrático (25 de Abril de 1974), a criação do Plano Oficial de Contabilidade (POC/77) e a implementação de um estado social com Serviço Nacional de Saúde (SNS) criaram a conjuntura crítica necessária para o surgimento de um Plano Oficial de Contabilidade para os Serviços de Saúde (POCSS/80) que incluiu regras de CG. A primeira edição do Plano de Contabilidade Analítica dos Hospitais (PCAH), aprovada em 1996, não foi uma construção de raiz, mas antes uma adaptação para os hospitais das regras de CG incluídas no POCSS/91 que havia revisto o POCSS/80. Após o início da implementação do PCAH, em 1998, ocorreram sequências de autorreforço institucionalizadoras destas normas, no período 1998-2011, por influência de pressões isomórficas coercivas que delinearam um processo de evolução incremental cujo resultado foi uma reprodução por adaptação, num contexto de dependência de recursos. Vários agentes internos e externos pressionaram, no período 2003-2011, através de sequências reativas para a desinstitucionalização do PCAH em resposta ao persistente fenómeno de loose coupling. Mas o PCAH só foi descontinuado nos hospitais com privatização da governação e rejeição dos anteriores sistemas de informação. Ao nível da extensão da teoria, este estudo de caso adotou o institucionalismo histórico na investigação em CG, quanto se sabe pela primeira vez, que se mostra útil na interpretação dos processos e dos resultados da criação e evolução de instituições de CG num determinado contexto histórico. Na condição de dependência de recursos, as sequências de autorreforço, via isomorfismo coercivo, tendem para uma institucionalização com fenómeno de loose coupling. Como resposta a este fenómeno, ocorrem sequências reativas no sentido da desinstitucionalização. Perante as pressões (políticas, funcionais, sociais e tecnológicas) desinstitucionalizadoras, o fator governação privada acelera o processo de desinstitucionalização, enquanto o fator governação pública impede ou abranda esse processo.

Explaining Variation in Organizational Change: The Reform of Human Resource Management in the European Commission and the OECD

In this article we investigate the reforms of human resource management in the European Commission and the OECD by analyzing comparatively to what extent both organizations have adjusted their respective structures towards the ideal type of the so-called New Public Management (NPM). The empirical findings show that reforms towards NPM are more pronounced in the Commission than in the OECD. These findings are surprising for two reasons: First, it seems rather paradoxical that the OECD as central promoter of NPM at the international level lags behind the global trend when it comes to reforming its own structures. Second, this result is in contradiction with theoretical expectations, as they can be derived from theories of institutional isomorphism. To nevertheless account for the surprising results, it is necessary to modify and complement existing theories especially with regard to the scope conditions of their causal mechanisms.

Generalized descriptive set theory and classification theory

Descriptive set theory is mainly concerned with studying subsets of the space of all countable binary sequences. In this paper we study the generalization where countable is replaced by uncountable. We explore properties of generalized Baire and Cantor spaces, equivalence relations and their Borel reducibility. The study shows that the descriptive set theory looks very different in this generalized setting compared to the classical, countable case. We also draw the connection between the stability theoretic complexity of first-order theories and the descriptive set theoretic complexity of their isomorphism relations. Our results suggest that Borel reducibility on uncountable structures is a model theoretically natural way to compare the complexity of isomorphism relations.

Legal europeanization as legal transformation : some insights from Swiss 'outer Europe'

The "Europeanization" of non-EU countries' laws is predominantly seen as an "export" of the EU acquis, especially in the case of so-called "quasi-member" states such as Switzerland. Based on an examination of the Swiss experience, this paper highlights the flaws of this conceptualization: the Europeanization of Swiss Law is a highly differentiated phenomenon, encompassing several forms of approximation to EU Law. All of these forms fall short of an "export" of norms, and result in the creation of something new: a "Europeanized law" that is similar to, but qualitatively different from, EU Law. Another drawback of the "export" metaphor is the emphasis it places on the isomorphism of positive legislation. Europeanization goes deeper than that. As shown in this paper, it is a process of transformation involving not only positive law, but also legal thinking. The Swiss case demonstrates how significant such deeper transformations can be: the Europeanization of positive law has induced an alteration of the traditional canon of legal interpretation. It also demonstrates how problematic such transformations can be: the above-mentioned alteration has not given rise to a new and universally accepted canon of interpretation. This reflects the tension between the need for clear "rules of reference" for EU legal materials - which are required in order to restore coherence and predictability to an extensively Europeanized legal system - and the reluctance to give a legal value to foreign legal materials - which is rooted in a traditional understanding of the concept of "law". Such tension, in turn, shows what deep and difficult transformations are required in order to establish a viable model of legal integration outside supranational structures.

Vertical Syndication-Proof Competitive Prices in Multilateral Markets

[eng] A multi-sided Böhm-Bawerk assignment game (Tejada, to appear) is a model for a multilateral market with a finite number of perfectly complementary indivisible commodities owned by different sellers, and inflexible demand and support functions. We show that for each such market game there is a unique vector of competitive prices for the commodities that is vertical syndication-proof, in the sense that, at those prices, syndication of sellers each owning a different commodity is neither beneficial nor detrimental for the buyers. Since, moreover, the benefits obtained by the agents at those prices correspond to the nucleolus of the market game, we provide a syndication-based foundation for the nucleolus as an appropriate solution concept for market games. For different solution concepts a syndicate can be disadvantageous and there is no escape to Aumman’s paradox (Aumann, 1973). We further show that vertical syndicationproofness and horizontal syndication-proofness – in which sellers of the same commodity collude – are incompatible requirements under some mild assumptions. Our results build on a self-interesting link between multi-sided Böhm-Bawerk assignment games and bankruptcy games (O’Neill, 1982). We identify a particular subset of Böhm-Bawerk assignment games and we show that it is isomorphic to the whole class of bankruptcy games. This isomorphism enables us to show the uniqueness of the vector of vertical syndication-proof prices for the whole class of Böhm-Bawerk assignment market using well-known results of bankruptcy problems.

Vertical Syndication-Proof Competitive Prices in Multilateral Markets

[eng] A multi-sided Böhm-Bawerk assignment game (Tejada, to appear) is a model for a multilateral market with a finite number of perfectly complementary indivisible commodities owned by different sellers, and inflexible demand and support functions. We show that for each such market game there is a unique vector of competitive prices for the commodities that is vertical syndication-proof, in the sense that, at those prices, syndication of sellers each owning a different commodity is neither beneficial nor detrimental for the buyers. Since, moreover, the benefits obtained by the agents at those prices correspond to the nucleolus of the market game, we provide a syndication-based foundation for the nucleolus as an appropriate solution concept for market games. For different solution concepts a syndicate can be disadvantageous and there is no escape to Aumman’s paradox (Aumann, 1973). We further show that vertical syndicationproofness and horizontal syndication-proofness – in which sellers of the same commodity collude – are incompatible requirements under some mild assumptions. Our results build on a self-interesting link between multi-sided Böhm-Bawerk assignment games and bankruptcy games (O’Neill, 1982). We identify a particular subset of Böhm-Bawerk assignment games and we show that it is isomorphic to the whole class of bankruptcy games. This isomorphism enables us to show the uniqueness of the vector of vertical syndication-proof prices for the whole class of Böhm-Bawerk assignment market using well-known results of bankruptcy problems.

The social disembedding of business theory and practice. A (neo-)institutional analysis of the homo economicus and corporate social responsibility, and the inherent responsibility of business scholars

Aim Structure of the Thesis In the first article, I focus on the context in which the Homo Economicus was constructed - i.e., the conception of economic actors as fully rational, informed, egocentric, and profit-maximizing. I argue that the Homo Economicus theory was developed in a specific societal context with specific (partly tacit) values and norms. These norms have implicitly influenced the behavior of economic actors and have framed the interpretation of the Homo Economicus. Different factors however have weakened this implicit influence of the broader societal values and norms on economic actors. The result is an unbridled interpretation and application of the values and norms of the Homo Economicus in the business environment, and perhaps also in the broader society. In the second article, I show that the morality of many economic actors relies on isomorphism, i.e., the attempt to fit into the group by adopting the moral norms surrounding them. In consequence, if the norms prevailing in a specific group or context (such as a specific region or a specific industry) change, it can be expected that actors with an 'isomorphism morality' will also adapt their ethical thinking and their behavior -for the 'better' or for the 'worse'. The article further describes the process through which corporations could emancipate from the ethical norms prevailing in the broader society, and therefore develop an institution with specific norms and values. These norms mainly rely on mainstream business theories praising the economic actor's self-interest and neglecting moral reasoning. Moreover, because of isomorphism morality, many economic actors have changed their perception of ethics, and have abandoned the values prevailing in the broader society in order to adopt those of the economic theory. Finally, isomorphism morality also implies that these economic actors will change their morality again if the institutional context changes. The third article highlights the role and responsibility of business scholars in promoting a systematic reflection and self-critique of the business system and develops alternative models to fill the moral void of the business institution and its inherent legitimacy crisis. Indeed, the current business institution relies on assumptions such as scientific neutrality and specialization, which seem at least partly challenged by two factors. First, self-fulfilling prophecy provides scholars with an important (even if sometimes undesired) normative influence over practical life. Second, the increasing complexity of today's (socio-political) world and interactions between the different elements constituting our society question the strong specialization of science. For instance, economic theories are not unrelated to psychology or sociology, and economic actors influence socio-political structures and processes, e.g., through lobbying (Dobbs, 2006; Rondinelli, 2002), or through marketing which changes not only the way we consume, but more generally tries to instill a specific lifestyle (Cova, 2004; M. K. Hogg & Michell, 1996; McCracken, 1988; Muniz & O'Guinn, 2001). In consequence, business scholars are key actors in shaping both tomorrow's economic world and its broader context. A greater awareness of this influence might be a first step toward an increased feeling of civic responsibility and accountability for the models and theories developed or taught in business schools.