We study the decidability of the following problem: given affine functions over and two vectors , is reachable from by successive iterations of (in this given order)? We show that this question is decidable for and undecidable for some fixed .
We study the decidability of the following problem: given p affine functions ƒ1,...,ƒp over and two vectors , is v2 reachable from v1 by successive iterations of ƒ1,...,ƒp (in this given order)? We show that this question is decidable for p = 1, 2 and undecidable for some fixed p.
This paper is a contribution to the general tiling problem for the hyperbolic plane. It is an intermediary result between the result obtained by R. Robinson [Invent. Math.44 (1978) 259–264] and the conjecture that the problem is undecidable.
Educational content for abstract reduction systems concerning reduction, convertibility, normal forms, divergence and convergence, Church- Rosser property, term rewriting systems, and the idea of the Knuth-Bendix Completion Algorithm. The theory is based on [1].
We introduce adhesive categories, which are categories with structure ensuring that pushouts along monomorphisms are well-behaved, as well as quasiadhesive categories which restrict attention to regular monomorphisms. Many examples of graphical structures used in computer science are shown to be examples of adhesive and quasiadhesive categories. Double-pushout graph rewriting generalizes well to rewriting on arbitrary adhesive and quasiadhesive categories.
We introduce adhesive categories, which are categories with structure ensuring that pushouts along monomorphisms are well-behaved, as well as quasiadhesive categories which restrict attention to regular monomorphisms. Many examples of graphical structures used in computer science are shown to be examples of adhesive and quasiadhesive categories. Double-pushout graph rewriting generalizes well to rewriting on arbitrary adhesive and quasiadhesive categories.
Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our...
Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization....
The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA, that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters, that restricts the PA...
The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA, that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters, that restricts the PA by forcing any two transitions on the same letter...
The Parikh finite word automaton (PA) was introduced and studied in 2003 by Klaedtke and Rueß. Natural variants of the PA arise from viewing a PA equivalently as an automaton that keeps a count of its transitions and semilinearly constrains their numbers. Here we adopt this view and define the affine PA, that extends the PA by having each transition induce an affine transformation on the PA registers, and the PA on letters, that restricts the PA...
We define an agent-oriented abstraction formalism devoted to generalized theories of abstraction that have been proposed in Artificial Intelligence. The model we propose extends the abstraction capabilities of the existing Agent-Oriented Programming paradigm. This short note reviews first the existing attempts to define abstraction in AI and in agent systems. Then, our model is introduced in terms of six definitions covering the concepts of agents, annotated knowledge, utility and society of agents....
In this article we formalize negligible functions that play an essential role in cryptology [10], [2]. Generally, a cryptosystem is secure if the probability of succeeding any attacks against the cryptosystem is negligible. First, we formalize the algebra of polynomially bounded sequences [20]. Next, we formalize negligible functions and prove the set of negligible functions is a subset of the algebra of polynomially bounded sequences. Moreover, we then introduce equivalence relation between polynomially...