Search

The HOM-problem asks whether the image of a regular tree language under a given tree homomorphism is again regular. It was recently shown to be decidable by Godoy, Giménez, Ramos, and Àlvarez. In this paper, the ℕ-weighted version of this problem is considered and its decidability is proved. More precisely, it is decidable in polynomial time whether the image of a regular ℕ-weighted tree language under a nondeleting, nonerasing tree homomorphism is regular.

The “somewhat vague, intuitive” notion from computability theory of an effective procedure (method) or algorithm can be fairly precisely defined, even if it does not have a purely mathematical definition—and even if (as many have asserted) for that reason, the Church–Turing thesis (that the effectively calculable functions on natural numbers are exactly the general recursive functions), cannot be proved. However, it is logically provable from the notion of an effective procedure, without reliance on any (partially) mathematical thesis or conjecture concerning effective procedures, such as the Church–Turing thesis, that the class of effective procedures is undecidable, i.e., that there is no effective procedure for ascertaining whether a given procedure is effective. The proof does not even appeal to a precise definition of ‘effective procedure’. Instead, it relies solely and entirely on a basic grasp of the intuitive notion of such a procedure. Though the result itself is not surprising, it is also not without significance. It has the consequence, for example, that the solution to a decision problem, if it is to be complete, must be accompanied by a separate argument that the proposed ascertainment procedure is, in fact, a decision procedure, i.e., effective—for example, that it invariably terminates with the correct verdict.

Diplomová práce se zabývá softwarovými nástroji pro podporu manažerského rozhodování v podniku. V rámci práce je definováno manažerské rozhodování v podniku na všech jeho úrovních a dále jsou se zohledněním těchto úrovní formulovány požadavky na softwarové nástroje pro podporu manažerského rozhodování. V rámci práce je provedeno šetření, jaké softwarové nástroje jsou v současné době využívány a na základě stanovených kritérií jsou tyto jednotlivé nástroje porovnány., The diploma thesis deals with software tools to support managerial decision making in the company. The thesis defines managerial decision making in the company at all its levels. According to these levels, requierements for software tools to support managerial decision making, are formulated. A survey is conducted of which software tools are currently used and based on that these individual tools are compared., Fakulta ekonomicko-správní, Studentka přednesla obhajobu práce s názvem: Softwarové nástroje pro podporu manažerského rozhodování v podniku. Cílem práce bylo formulovat požadavky na softwarové nástroje pro podporu manažerského rozhodování v podniku a provést komparaci stávajících softwarových produktů. Během rozpravy byly položeny dotazy dle posudku vedoucího diplomové práce: O1.: V současné době společností rezonuje technologie ChatGPT a její budoucí pozitivní i negativní dopady na společnost. Jakým způsobem může tato technologie ovlivnit budoucí manažerské rozhodování v podniku? Dotazy dle posudku oponenta diplomové práce: O1.: Zvažovala jste pro hodnocení variant mimo Saatyho metody i využití jiných metod na podporu vícekriteriálního rozhodování, např. PROMETHEE, AGREPREF, ELECTRE, TOPSIS? Proč ano, proč ne? Následně byly během rozpravy položeny doplňující dotazy: O1.: V příloze D své DP máte jednotlivé váhy rozděleny pro 3 úrovně řízení v podniku; finální rozhodnutí bylo uděleno separátně? Studentka na otázky reagovala., Dokončená práce s úspěšnou obhajobou

We consider a natural generalization of the concept of order of an element in a group: an element g ¿ G is said to have order k in a subgroup H (resp., in a coset Hu) of a group G if k is the first strictly positive integer such that gk ¿ H (resp., gk ¿ Hu). We study this notion and its algorithmic properties in the realm of free groups and some related families. Both positive and negative (algorithmic) results emerge in this setting. On the positive side, among other results, we prove that the order of elements, the set of orders (called spectrum), and the set of preorders (i.e., the set of elements of a given order) w.r.t. finitely generated subgroups are always computable in free and free times free-abelian groups. On the negative side, we provide examples of groups and subgroups having essentially any subset of natural numbers as relative spectrum; in particular, non-recursive and even non-recursively enumerable sets of natural numbers. Also, we take advantage of Mikhailova’s construction to see that the spectrum membership problem is unsolvable for direct products of nonabelian free groups., The first named author was partially supported by MINECO grant PID2019-107444GA-I00 and the Basque Government grant IT974-16. The second named author acknowledges partial support from the Spanish Agencia Estatal de Investigación, through grant MTM2017-82740-P (AEI/ FEDER, UE), and also from the Graduate School of Mathematics through the María de Maeztu Programme for Units of Excellence in R&D (MDM-2014-0445). The third named author was partially supported by (Polish) Narodowe Centrum Nauki, grant UMO-2018/31/G/ST1/02681., Peer Reviewed, Postprint (author's final draft)

This report describes a case study where a multi criteria decision model is used to make decisions regarding asset interventions for four social housing complexes, similar in terms of issues and possible interventions, at Christchurch City Council. The value judgements from the decision makers and their advisors that were necessary for creating the decision model were elicited through three workshops; selecting aspects, weighting and rating and lastly reviewing the output. An analysis performed shows that the decision model is logically consistent and does not suffer from the rank reversal phenomenon. The validation of the model also included creating four individual decision models, one for each social housing complex, comparing the results of applying the joint model and the individual models, and revisiting and reconsidering the value judgments made in the different models when discrepancies were found. This included utility difference analysis and asking trade-off questions to the decision makers. Part of the validation was also to get acceptance of the output of the joint model from the social housing team. Applying the decision model on the four social housing complexes and receiving an output which is accepted by the social housing team suggests that the aggregated model can be used for future decision problems of the same kind, provided that they are within the set level ranges of the aspects. Since the decision model is transparent in terms of which values or priorities have been applied and which prerequisites must be met in order to apply the model to future decisions, it is possible to use the decision model as a ‘live model’ with adjustment being made to it when required.

This report describes a case study where a multi criteria decision model is used to make decisions regarding asset interventions for four social housing complexes, similar in terms of issues and possible interventions, at Christchurch City Council. The value judgements from the decision makers and their advisors that were necessary for creating the decision model were elicited through three workshops; selecting aspects, weighting and rating and lastly reviewing the output. An analysis performed shows that the decision model is logically consistent and does not suffer from the rank reversal phenomenon. The validation of the model also included creating four individual decision models, one for each social housing complex, comparing the results of applying the joint model and the individual models, and revisiting and reconsidering the value judgments made in the different models when discrepancies were found. This included utility difference analysis and asking trade-off questions to the decision makers. Part of the validation was also to get acceptance of the output of the joint model from the social housing team. Applying the decision model on the four social housing complexes and receiving an output which is accepted by the social housing team suggests that the aggregated model can be used for future decision problems of the same kind, provided that they are within the set level ranges of the aspects. Since the decision model is transparent in terms of which values or priorities have been applied and which prerequisites must be met in order to apply the model to future decisions, it is possible to use the decision model as a ‘live model’ with adjustment being made to it when required.

The topic of this article is Hilbert’s axiom of solvability, that is, his conviction of the solvability of every mathematical problem by means of a finite number of operations. The question of solvability is commonly identified with the decision problem. Given this identification, there is not the slightest doubt that Hilbert’s conviction was falsified by Gödel’s proof and by the negative results for the decision problem. On the other hand, Gödel’s theorems do offer a solution, albeit a negative one, in the form of an impossibility proof. In this sense, Hilbert’s optimism may still be justified. Here I argue that Gödel’s theorems opened the door to proof theory and to the remarkably successful development of generalized as well as relativized realizations of Hilbert’s program. Thus, the fall of absolute certainty came hand in hand with the rise of partially secure and reliable foundations of mathematical knowledge. Not all was lost and much was gained.

In this dissertation, it is argued that the same mathematical object can be interpreted in different ways. For example, it can be a game, but it can also be a decision problem. Accordingly, the following question it raised: ‘Is it possible for a person to be perfectly rational in every situation?’ It is shown that a person can be simultaneously rational and irrational, which leads to a paradoxical situation. For example, while an individual can be perfectly rational with respect to financial decisions, the individual can make irrational decisions in his or her private life.

In this dissertation, it is argued that the same mathematical object can be interpreted in different ways. For example, it can be a game, but it can also be a decision problem. Accordingly, the following question it raised: ‘Is it possible for a person to be perfectly rational in every situation?’ It is shown that a person can be simultaneously rational and irrational, which leads to a paradoxical situation. For example, while an individual can be perfectly rational with respect to financial decisions, the individual can make irrational decisions in his or her private life.

We prove that one cannot algorithmically decide whether a finitely presented Z-extension admits a finitely generated base group, and we use this fact to prove the undecidability of the BNS invariant. Furthermore, we show the equivalence between the isomorphism problem within the subclass of unique Z-extensions, and the semi-conjugacy problem for deranged outer automorphisms., Peer Reviewed, Postprint (author's final draft)

It is known that a language of finite words is definable in monadic second-order logic - MSO - (resp. first-order logic - FO -) iff it is recognized by some finite automaton (resp. some aperiodic finite automaton). Deciding whether an automaton A is equivalent to an aperiodic one is known to be PSPACE-complete. This problem has an important application in logic: it allows one to decide whether a given MSO formula is equivalent to some FO formula. In this paper, we address the aperiodicity problem for functions from finite words to finite words (transductions), defined by finite transducers, or equivalently by bimachines, a transducer model studied by Schützenberger and Reutenauer. Precisely, we show that the problem of deciding whether a given bimachine is equivalent to some aperiodic one is PSPACE-complete.

We study direct products of free-abelian and free groups with special emphasis on algorithmic problems. After giving natural extensions of standard notions into that family, we find an explicit expression for an arbitrary endomorphism of Zm×Fn. These tools are used to solve several algorithmic problems for Zm×Fn: the membership problem, the isomorphism problem, the finite index problem, the subgroup and coset intersection problems, the fixed point problem, and the Whitehead problem., Peer Reviewed, Postprint (author’s final draft)

The HOM problem questions whether the image of a given regular tree language through a given tree homomorphism is also regular. Decidability of HOM is an important theoretical question which was open for a long time. Recently, HOM has been proved decidable with a triple exponential time algorithm. In this paper we obtain an exponential time algorithm for this problem, and conclude that it is EXPTIME-complete. The proof builds upon previous results and techniques on tree automata with constraints., Postprint (published version)

Decision‐makers in organisations and businesses make numerous decisions every day, and these decisions are expected to be based on facts and carried out in a rational manner. However, most decisions are not based on precise information or careful analysis due to several reasons. People are, e.g., unable to behave rationally as a result of their experiences, socialisation, and additionally, because humans possess fairly limited capacities for processing information in an objective manner. In order to circumvent this human incapacity to handle decision situations in a rational manner, especially those involving risk and uncertainty, a widespread suggestion, at least in managerial decision making, is to take advantage of support in the form of decision support systems. One possibility involves decision analytical tools, but they are, almost without exception, not efficiently employed in organisations and businesses. It appears that one reason for this is the high demands the tools place on the decision‐maker in a variety of ways, e.g., by presupposing that reliable input data is obtainable by an exogenous process. Even though the reliability of current decision analytic tools is highly dependent on the quality of the input data, they rarely contain methods for eliciting data from the users. The problem focused on in this thesis is the unavailability and inefficiency of methods for eliciting decision information from the users. The aim is to identify problem areas regarding the elicitation of decision data in real decision making processes, and to propose elicitation methods that take people’s natural choice strategies and natural behaviour into account. In this effort, we have identified a conceptual gap between the decision‐makers, the decision models, and the decision analytical tools, consisting of seven gap components. The gap components are of three main categories (of which elicitation is one). In order to study elicitation problems, a number of empirical studies

Decision‐makers in organisations and businesses make numerous decisions every day, and these decisions are expected to be based on facts and carried out in a rational manner. However, most decisions are not based on precise information or careful analysis due to several reasons. People are, e.g., unable to behave rationally as a result of their experiences, socialisation, and additionally, because humans possess fairly limited capacities for processing information in an objective manner. In order to circumvent this human incapacity to handle decision situations in a rational manner, especially those involving risk and uncertainty, a widespread suggestion, at least in managerial decision making, is to take advantage of support in the form of decision support systems. One possibility involves decision analytical tools, but they are, almost without exception, not efficiently employed in organisations and businesses. It appears that one reason for this is the high demands the tools place on the decision‐maker in a variety of ways, e.g., by presupposing that reliable input data is obtainable by an exogenous process. Even though the reliability of current decision analytic tools is highly dependent on the quality of the input data, they rarely contain methods for eliciting data from the users. The problem focused on in this thesis is the unavailability and inefficiency of methods for eliciting decision information from the users. The aim is to identify problem areas regarding the elicitation of decision data in real decision making processes, and to propose elicitation methods that take people’s natural choice strategies and natural behaviour into account. In this effort, we have identified a conceptual gap between the decision‐makers, the decision models, and the decision analytical tools, consisting of seven gap components. The gap components are of three main categories (of which elicitation is one). In order to study elicitation problems, a number of empirical studies

Decision‐makers in organisations and businesses make numerous decisions every day, and these decisions are expected to be based on facts and carried out in a rational manner. However, most decisions are not based on precise information or careful analysis due to several reasons. People are, e.g., unable to behave rationally as a result of their experiences, socialisation, and additionally, because humans possess fairly limited capacities for processing information in an objective manner. In order to circumvent this human incapacity to handle decision situations in a rational manner, especially those involving risk and uncertainty, a widespread suggestion, at least in managerial decision making, is to take advantage of support in the form of decision support systems. One possibility involves decision analytical tools, but they are, almost without exception, not efficiently employed in organisations and businesses. It appears that one reason for this is the high demands the tools place on the decision‐maker in a variety of ways, e.g., by presupposing that reliable input data is obtainable by an exogenous process. Even though the reliability of current decision analytic tools is highly dependent on the quality of the input data, they rarely contain methods for eliciting data from the users. The problem focused on in this thesis is the unavailability and inefficiency of methods for eliciting decision information from the users. The aim is to identify problem areas regarding the elicitation of decision data in real decision making processes, and to propose elicitation methods that take people’s natural choice strategies and natural behaviour into account. In this effort, we have identified a conceptual gap between the decision‐makers, the decision models, and the decision analytical tools, consisting of seven gap components. The gap components are of three main categories (of which elicitation is one). In order to study elicitation problems, a number of empirical studies

Decision‐makers in organisations and businesses make numerous decisions every day, and these decisions are expected to be based on facts and carried out in a rational manner. However, most decisions are not based on precise information or careful analysis due to several reasons. People are, e.g., unable to behave rationally as a result of their experiences, socialisation, and additionally, because humans possess fairly limited capacities for processing information in an objective manner. In order to circumvent this human incapacity to handle decision situations in a rational manner, especially those involving risk and uncertainty, a widespread suggestion, at least in managerial decision making, is to take advantage of support in the form of decision support systems. One possibility involves decision analytical tools, but they are, almost without exception, not efficiently employed in organisations and businesses. It appears that one reason for this is the high demands the tools place on the decision‐maker in a variety of ways, e.g., by presupposing that reliable input data is obtainable by an exogenous process. Even though the reliability of current decision analytic tools is highly dependent on the quality of the input data, they rarely contain methods for eliciting data from the users. The problem focused on in this thesis is the unavailability and inefficiency of methods for eliciting decision information from the users. The aim is to identify problem areas regarding the elicitation of decision data in real decision making processes, and to propose elicitation methods that take people’s natural choice strategies and natural behaviour into account. In this effort, we have identified a conceptual gap between the decision‐makers, the decision models, and the decision analytical tools, consisting of seven gap components. The gap components are of three main categories (of which elicitation is one). In order to study elicitation problems, a number of empirical studies

We will consider here the splicing systems, generative devicesinspired by cut and paste phenomena on DNA molecules under the actionof restriction and ligase enzymes. A DNA strand can be viewed as a stringover a four letter alphabet (the four deoxyribonucleotides), therefore wecan model DNA computation within the framework of formal languagetheory. In spite of a vast literature on splicing systems, briefly surveyedhere, a few problems related to their computational power are still open.We intend to evidence how classical techniques and concepts in automatatheory are a legitimate tool for investigating some of these problems.