PL
 |
EN
Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl
Ograniczanie wyników
Czasopisma help
  1. 32 Fundamenta Informaticae
  2. 5 Logic and Logical Philosophy
  3. 2 Bulletin of the Section of Logic
  4. 2 International Journal of Applied Mathematics and Computer Science
  5. 2 Teologia w Polsce
Więcej...
Lata help
  1. 2 2022
  2. 2 2021
  3. 2 2020
  4. 1 2019
  5. 6 2018
Więcej...
Autorzy help
  1. 3 Honkala J.
  2. 3 Rosa-Velardo F.
  3. 2 Clempner J.
  4. 2 Frutos-Escrig D. d.
  5. 2 Lomazova I. A.
Więcej...
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 48

Liczba wyników na stronie
first rewind previous Strona / 3 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  decidability
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 3 next fast forward last
1
Content available remote On the Problem Whether the Image of an N-Rational Series Equals N
100%
Honkala J.
Fundamenta Informaticae
|
2006
|
tom Vol. 73, nr 1-2
127-132
EN
We show that it is undecidable whether or not a given N-rational series assumes all nonnegative values. As a consequence we see that it is undecidable whether the image of a given N-rational series equals the image of a given N-rational sequence. We discuss also related results concerning DT0L and D0L length sets.
2
Content available remote The Sequence Equivalence Problem for Marked DT0L Systems
80%
Honkala J.
Fundamenta Informaticae
|
2011
|
tom Vol. 110, nr 1-4
175-182
EN
We study the DT0L sequence equivalence problem for marked morphisms. We show that to decide this problem it is enough to consider initial terms involving at most 2n morphisms where n is the cardinality of the underlying alphabet.
3
Content available remote Membrane computing with external output
80%
Paun G. , Rozenberg G. , Salomaa A.
Fundamenta Informaticae
|
2000
|
tom Vol. 41, Nr 3
313-340
EN
A membrane computing system (also called P system) consists of computing cells which are organized hierarchically by the inclusion relation: cells may include cells, which again may include cells, etc. Each cell is enclosed by its membrane. Each cell is an independent computing agent with its own computing program, which produces objects. The interaction between cells consists of the exchange of objects through membranes. The output of a computation is a partially ordered set of objects which leave the system through its external membrane. The fundamental properties of computations in such P systems with external output are investigated. These include the computing power, normal forms, and basic decision problems.
4
Content available remote The equivalence problem of DOL and DFOL power series
80%
Honkala J.
Fundamenta Informaticae
|
1999
|
tom Vol. 38, Nr 1,2
201-208
EN
We show that it is decidable whether or not a given D0L power series and a given DF0L power series over a computable field are equal. This generalizes to power series the result of Ruohonen stating that DF0L-D0L language equivalence is decidable.
5
Content available remote Nested Petri nets - a formalism for specification and verification of multi-agent distributed systems
80%
Lomazova I. A.
Fundamenta Informaticae
|
2000
|
tom Vol. 43, Nr 1-4
195-214
EN
Nested Petri nets is a formalism for modeling hierarchical multi-agent systems. Tokens in nested Petri nets are elements represented by nets themselves. Decidability of some crucial for verification problems shows that, in spite of their "unflat" structure, nested Petri nets maintain significant properties of ordinary Petri nets. A comparison with some other Petri net models is given. The formalism allows generalization to a recursive case, when a nested Petri net may generate its own copy as its element. Two simple examples illustrate the approach.
6
Content available remote Freeness Problem for Matrix Semigroups of Parikh Matrices
80%
Teh W. C. , Atanasiu A. , Wong D. C. K.
Fundamenta Informaticae
|
2021
|
tom Vol. 179, nr 4
385--397
EN
Since the undecidability of the mortality problem for 3 × 3 matrices over integers was proved using the Post Correspondence Problem, various studies on decision problems of matrix semigroups have emerged. The freeness problem in particular has received much attention but decidability remains open even for 2 × 2 upper triangular matrices over nonnegative integers. Parikh matrices are upper triangular matrices introduced as a generalization of Parikh vectors and have become useful tools in studying of subword occurrences. In this work, we focus on semigroups of Parikh matrices and study the freeness problem in this context.
7
Content available Simple Decision Procedure for S5 in Standard Cut-Free Sequent Calculus
80%
Indrzejczak A.
Bulletin of the Section of Logic
|
2016
|
tom 45
|
nr 2
EN
In the paper a decision procedure for S5 is presented which uses a cut-free sequent calculus with additional rules allowing a reduction to normal modal forms. It utilizes the fact that in S5 every formula is equivalent to some 1-degree formula, i.e. a modally-flat formula with modal functors having only boolean formulas in its scope. In contrast to many sequent calculi (SC) for S5 the presented system does not introduce any extra devices. Thus it is a standard version of SC but with some additional simple rewrite rules. The procedure combines the proces of saturation of sequents with reduction of their elements to some normal modal form.
8
Propositions, Possible Worlds, and Recursion
80%
Wiśniewski A.
Logic and Logical Philosophy
|
2011
|
tom 20
|
nr 1-2
73-79
EN
The issue of reduction of propositions to sets of possible worlds is addressed. It is shown that, under some natural assumptions, there always exist recursive propositions, i.e. decidable sets of possible worlds, which are not assigned to any sentence of a language. Some consequences of this result are discussed.
9
Content available remote Soundness of Timed-Arc Workflow Nets in Discrete and Continuous-Time Semantics
80%
Mateo J. A. , Srba J. , Sørensen M. G.
Fundamenta Informaticae
|
2015
|
tom Vol. 140, nr 1
89--121
EN
Analysis of workflow processes with quantitative aspects like timing is of interest in numerous time-critical applications. We suggest a workflow model based on timed-arc Petri nets and study the foundational problems of soundness and strong (time-bounded) soundness. We first consider the discrete-time semantics (integer delays) and explore the decidability of the soundness problems and show, among others, that soundness is decidable for monotonic workflow nets while reachability is undecidable. For general timed-arc workflow nets soundness and strong soundness become undecidable, though we can design efficient verification algorithms for the subclass of bounded nets. We also discuss the soundness problem in the continuous-time semantics (real-number delays) and show that for nets with nonstrict guards (where the reachability question coincides for both semantics) the soundness checking problem does not in general follow the approach for the discrete semantics and different zone-based techniques are needed for introducing its decidability in the bounded case. Finally, we demonstrate the usability of our theory on the case studies of a Brake System Control Unit used in aircraft certification, the MPEG2 encoding algorithm, and a blood transfusion workflow. The implementation of the algorithms is freely available as a part of the model checker TAPAAL (www.tapaal.net).
10
Content available remote From One-dimensional to Two-dimensional Cellular Automata
80%
Dennunzio A.
Fundamenta Informaticae
|
2012
|
tom Vol. 115, nr 1
87-105
EN
We enlighten the differences between one-dimensional and two-dimensional cellular automata by considering both the dynamical and decidability aspects. We also show a canonical representation theorem for the slicing constructions, a tool allowing to give the 2D version of important 1D CA notions as closing and positive expansivity and lift 1D results to the 2D settings.
11
Content available remote Composition Theorem for Generalized Sum
80%
Rabinovich A.
Fundamenta Informaticae
|
2007
|
tom Vol. 79, nr 1-2
137-167
EN
Composition theorems are tools which reduce sentences about some compound structure to sentences about its parts. A seminal example of such a theorem is the Feferman-Vaught Theorem [3] which reduces the first-order theory of generalized products to the first order theory of its factors and the monadic second-order theory of index structure. Shelah [23] used the composition theorem for linear orders as one of the main tools for obtaining very strong decidability results for the monadic second-order theory of linear orders. The main technical contribution of our paper is (1) a definition of a generalized sum of structures and (2) a composition theorem for first-order logic over the generalized sum. One of our objectives is to emphasize the work-out of the composition method.
12
Content available remote The Reachability Problem for Object Nets
80%
Köhler M.
Fundamenta Informaticae
|
2007
|
tom Vol. 79, nr 3-4
401-413
EN
In this article I will prove undecidability results for elementary object net systems ( EOS). Object nets are Petri nets which have Petri nets as tokens - an approach which is called the "nets-within-nets" paradigm. EOS are special object net systems which have a two leveled structure.
13
Content available remote Undecidability Results for Timed Automata with Silent Transitions
80%
Bouyer P. , Haddad S. , Reynier P.-A.
Fundamenta Informaticae
|
2009
|
tom Vol. 92, nr 1-2
1-25
EN
In this work, we study decision problems related to timed automata with silent transitions (TAε) which strictly extend the expressiveness of timed automata (TA). We first answer negatively a central question raised by the introduction of silent transitions: can we decide whether the language recognized by a TAε can be recognized by some TA? Then we establish in the framework of TAε some old open conjectures that O. Finkel has recently solved for TA. His proofs follow a generic scheme which relies on the fact that only a finite number of configurations can be reached by a TA while reading a timed word. This property does not hold for TAε , the proofs in the framework of TAε thus require more elaborated arguments. We establish undecidability of complementability, minimization of the number of clocks, and closure under shuffle. We also show these results in the framework of infinite timed languages.
14
Content available remote On the Branching Complexity of P Systems
80%
Ciobanu G. , Paun G. , Pérez-Jiménez M. J.
Fundamenta Informaticae
|
2006
|
tom Vol. 73, nr 1-2
27-36
EN
We consider two complexity parameters related to the graph of reachable configurations of a given P system, namely the outdegree as a measure of the degree of non-determinism, and the indegree as a measure of the degree of confluence. These parameters can be defined for both the generative and the accepting mode of using a P system. We investigate here these parameters in what concerns hierarchies and decidability issues. We prove that all hierarchies have only two levels and that all considered decidability problems have a negative answer.
15
Content available remote Decidability Analysis of Self-Stabilization for Infinite-State Systems
80%
Yen H.-C. , Yu L.-P.
Fundamenta Informaticae
|
2006
|
tom Vol. 70, nr 4
387-402
EN
For a variety of infinite-state systems, the problem of deciding whether a given system is self-stabilizing or not is investigated from the decidability viewpoint. We develop a unified strategy through which checking self-stabilization is shown to be decidable for lossy vector addition systems with states, one-counter machines, and conflict-free Petri nets. For lossy counter machines and lossy channel systems, in contrast, the self-stabilization problem is shown to be undecidable.
16
Content available remote Definability within structures related to Pascal’s triangle modulo an integer
80%
Bès A. , Korec I.
Fundamenta Mathematicae
|
1998
|
tom 156
|
nr 2
111-129
EN
Let Sq denote the set of squares, and let $SQ_n$ be the squaring function restricted to powers of n; let ⊥ denote the coprimeness relation. Let $B_n(x,y)=({x+y \atop x}) MOD n$. For every integer n ≥ 2 addition and multiplication are definable in the structures ⟨ℕ; B_n,⊥⟩ and ⟨ℕ; B_n,Sq⟩; thus their elementary theories are undecidable. On the other hand, for every prime p the elementary theory of ⟨ℕ; B_p,SQ_p⟩ is decidable.
17
Content available remote On Axiomatizability of the Multiplicative Theory of Numbers
80%
Salehi S.
Fundamenta Informaticae
|
2018
|
tom Vol. 159, nr 3
279--296
EN
The multiplicative theory of a set of numbers (which could be natural, integer, rational, real or complex numbers) is the first-order theory of the structure of that set with (solely) the multiplication operation (that set is taken to be multiplicative, i.e., closed under multiplication). In this paper we study the multiplicative theories of the complex, real and (positive) rational numbers. These theories (and also the multiplicative theories of natural and integer numbers) are known to be decidable (i.e., there exists an algorithm that decides whether a given sentence is derivable form the theory); here we present explicit axiomatizations for them and show that they are not finitely axiomatizable. For each of these sets (of complex, real and [positive] rational numbers) a language, including the multiplication operation, is introduced in a way that it allows quantifier elimination (for the theory of that set).
18
Content available remote On the decidability of some problems concerning morphisms, regular sets, and post correspondence problem
70%
Turakainen P.
Fundamenta Informaticae
|
1999
|
tom Vol. 38, Nr 1,2
209-221
EN
Regular languages are divided into equivalence classes according to the lengths of the words and both the universal and the existential equivalence of rational transductions on the set of these classes is studied. It is shown that the cardinality equivalence problem is undecidable for e-free finite substitutions. The morphic replication equivalence problem is arithmetized and an application to word equations is presented. Finally, the generalized Post correspondence problem is modified by using a single inverse morphism or a single finite substitution or its inverse instead of two morphisms.
19
More on The Decidability of Mereological Theories
70%
Tsai H.-c.
Logic and Logical Philosophy
|
2011
|
tom 20
|
nr 3
251-265
EN
Quite a few results concerning the decidability of mereological theories have been given in my previous paper. But many mereological theories are still left unaccounted for. In this paper I will refine a general method for proving the undecidability of a theory and then by making use of it, I will show that most mereological theories that are strictly weaker than CEM are finitely inseparable and hence undecidable. The same results might be carried over to some extensions of those weak theories by adding the fusion axiom schema. Most of the proofs to be presented in this paper take finite lattices as the base models when applying the refined method. However, I shall also point out the limitation of this kind of reduction and make some observations and conjectures concerning the decidability of stronger mereological theories.
20
Content available Decidability of addition and Frobenius map for polynomials and rational functions
70%
Chompitaki D. , Kamarianakis M. , Pheidas T.
Reports on Mathematical Logic
|
2022
|
tom Vol. 57
53--60
EN
Let p be a prime number, Fp a finite field with p elements, F an algebraic extension of Fp and z a variable. We consider the structure of addition and the Frobenius map (i.e., x 7→ x p ) in the polynomial rings F[z] and in fields F(z) of rational functions. We prove that any question about F[z] in the structure of addition and Frobenius map may be effectively reduced to questions about the similar structure of the field F. Furthermore, we provide an example which shows that a fact which is true for addition and the Frobenius map in the polynomial rings F[z] fails to be true in F(z). As a consequence, certain methods used to prove model completeness for polynomials do not suffice to prove model completeness for similar structures for fields of rational functions F(z), a problem that remains open even for F = Fp
first rewind previous Strona / 3 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.