Log in

Relevant bibliographies by topics / Undecidable / Journal articles

To see the other types of publications on this topic, follow the link: Undecidable.

Journal articles on the topic 'Undecidable'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Undecidable.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

da Costa, N. C. A., and F. A. Doria. "Undecidable hopf bifurcation with undecidable fixed point." International Journal of Theoretical Physics 33, no. 9 (September 1994): 1885–903. http://dx.doi.org/10.1007/bf00671031.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Bennett, Charles H. "Undecidable dynamics." Nature 346, no. 6285 (August 1990): 606–7. http://dx.doi.org/10.1038/346606a0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Myasnikov, Alexei G., and Alexander N. Rybalov. "Generic complexity of undecidable problems." Journal of Symbolic Logic 73, no. 2 (June 2008): 656–73. http://dx.doi.org/10.2178/jsl/1208359065.

Full text

Abstract:

AbstractIn this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets.

APA, Harvard, Vancouver, ISO, and other styles

4

Stewart, Ian. "Deciding the undecidable." Nature 352, no. 6337 (August 1991): 664–65. http://dx.doi.org/10.1038/352664a0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Kapovich, Michael. "Discreteness is undecidable." International Journal of Algebra and Computation 26, no. 03 (May 2016): 467–72. http://dx.doi.org/10.1142/s0218196716500193.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Maddux, Roger D. "Undecidable semiassociative relation algebras." Journal of Symbolic Logic 59, no. 2 (June 1994): 398–418. http://dx.doi.org/10.2307/2275397.

Full text

Abstract:

AbstractIf K is a class of semiassociative relation algebras and K contains the relation algebra of all binary relations on a denumerable set, then the word problem for the free algebra over K on one generator is unsolvable. This result implies that the set of sentences which are provable in the formalism ℒw× is an undecidable theory. A stronger algebraic result shows that the set of logically valid sentences in ℒw× forms a hereditarily undecidable theory in ℒw×. These results generalize similar theorems, due to Tarski, concerning relation algebras and the formalism ℒ×.

APA, Harvard, Vancouver, ISO, and other styles

7

Janicaud, Dominique. "Metamorphosis of the Undecidable." Graduate Faculty Philosophy Journal 13, no. 1 (1988): 125–40. http://dx.doi.org/10.5840/gfpj19881317.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Bokov, G. V. "Undecidable Iterative Propositional Calculus." Algebra and Logic 55, no. 4 (September 2016): 274–82. http://dx.doi.org/10.1007/s10469-016-9396-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Straßburger, Lutz. "System NEL is Undecidable." Electronic Notes in Theoretical Computer Science 84 (September 2003): 166–77. http://dx.doi.org/10.1016/s1571-0661(04)80853-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Saito, A., and K. Kaneko. "Geometry of Undecidable Systems." Progress of Theoretical Physics 99, no. 5 (May 1, 1998): 885–90. http://dx.doi.org/10.1143/ptp.99.885.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Scholte, Tom. "Heuristics for the Undecidable." She Ji: The Journal of Design, Economics, and Innovation 5, no. 4 (2019): 379–82. http://dx.doi.org/10.1016/j.sheji.2019.11.011.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Ben-David, Shai, Pavel Hrubeš, Shay Moran, Amir Shpilka, and Amir Yehudayoff. "Learnability can be undecidable." Nature Machine Intelligence 1, no. 1 (January 2019): 44–48. http://dx.doi.org/10.1038/s42256-018-0002-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Pierce, B. C. "Bounded Quantification Is Undecidable." Information and Computation 112, no. 1 (July 1994): 131–65. http://dx.doi.org/10.1006/inco.1994.1055.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Bennett, Tony. "Book Review: Undecidable dinosaurs." International Journal of Cultural Studies 2, no. 1 (April 1999): 133–36. http://dx.doi.org/10.1177/136787799900200107.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Magidor, Menachem, John W. Rosenthal, Mattiyahu Rubin, and Gabriel Srour. "Some highly undecidable lattices." Annals of Pure and Applied Logic 46, no. 1 (January 1990): 41–63. http://dx.doi.org/10.1016/0168-0072(90)90077-f.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Kuznetsov, Stepan. "Action Logic is Undecidable." ACM Transactions on Computational Logic 22, no. 2 (May 15, 2021): 1–26. http://dx.doi.org/10.1145/3445810.

Full text

Abstract:

Action logic is the algebraic logic (inequational theory) of residuated Kleene lattices. One of the operations of this logic is the Kleene star, which is axiomatized by an induction scheme. For a stronger system that uses an -rule instead (infinitary action logic), Buszkowski and Palka (2007) proved -completeness (thus, undecidability). Decidability of action logic itself was an open question, raised by Kozen in 1994. In this article, we show that it is undecidable, more precisely, -complete. We also prove the same undecidability results for all recursively enumerable logics between action logic and infinitary action logic, for fragments of these logics with only one of the two lattice (additive) connectives, and for action logic extended with the law of distributivity.

APA, Harvard, Vancouver, ISO, and other styles

17

Gray, Robert D. "Undecidability of the word problem for one-relator inverse monoids via right-angled Artin subgroups of one-relator groups." Inventiones mathematicae 219, no. 3 (September 9, 2019): 987–1008. http://dx.doi.org/10.1007/s00222-019-00920-2.

Full text

Abstract:

Abstract We prove the following results: (1) There is a one-relator inverse monoid $$\mathrm {Inv}\langle A\,|\,w=1 \rangle $$Inv⟨A|w=1⟩ with undecidable word problem; and (2) There are one-relator groups with undecidable submonoid membership problem. The second of these results is proved by showing that for any finite forest the associated right-angled Artin group embeds into a one-relator group. Combining this with a result of Lohrey and Steinberg (J Algebra 320(2):728–755, 2008), we use this to prove that there is a one-relator group containing a fixed finitely generated submonoid in which the membership problem is undecidable. To prove (1) a new construction is introduced which uses the one-relator group and submonoid in which membership is undecidable from (2) to construct a one-relator inverse monoid $$\mathrm {Inv}\langle A\,|\,w=1 \rangle $$Inv⟨A|w=1⟩ with undecidable word problem. Furthermore, this method allows the construction of an E-unitary one-relator inverse monoid of this form with undecidable word problem. The results in this paper answer a problem originally posed by Margolis et al. (in: Semigroups and their applications, Reidel, Dordrecht, pp. 99–110, 1987).

APA, Harvard, Vancouver, ISO, and other styles

18

CHVALOVSKÝ, KAREL, and ROSTISLAV HORČÍK. "FULL LAMBEK CALCULUS WITH CONTRACTION IS UNDECIDABLE." Journal of Symbolic Logic 81, no. 2 (May 10, 2016): 524–40. http://dx.doi.org/10.1017/jsl.2015.18.

Full text

Abstract:

AbstractWe prove that the set of formulae provable in the full Lambek calculus with the structural rule of contraction is undecidable. In fact, we show that the positive fragment of this logic is undecidable.

APA, Harvard, Vancouver, ISO, and other styles

19

MARGENSTERN, MAURICE. "THE FINITE TILING PROBLEM IS UNDECIDABLE IN THE HYPERBOLIC PLANE." International Journal of Foundations of Computer Science 19, no. 04 (August 2008): 971–82. http://dx.doi.org/10.1142/s0129054108006078.

Full text

Abstract:

In this paper, we consider the finite tiling problem which was proved undecidable in the Euclidean plane by Jarkko Kari, see [5]. Here, we prove that the same problem for the hyperbolic plane is also undecidable.

APA, Harvard, Vancouver, ISO, and other styles

20

Dietrich, Eric, and Chris Fields. "Equivalence of the Frame and Halting Problems." Algorithms 13, no. 7 (July 20, 2020): 175. http://dx.doi.org/10.3390/a13070175.

Full text

Abstract:

The open-domain Frame Problem is the problem of determining what features of an open task environment need to be updated following an action. Here we prove that the open-domain Frame Problem is equivalent to the Halting Problem and is therefore undecidable. We discuss two other open-domain problems closely related to the Frame Problem, the system identification problem and the symbol-grounding problem, and show that they are similarly undecidable. We then reformulate the Frame Problem as a quantum decision problem, and show that it is undecidable by any finite quantum computer.

APA, Harvard, Vancouver, ISO, and other styles

21

Sigal, Ron. "Undecidable complexity statements in -arithmetic." Journal of Symbolic Logic 54, no. 2 (June 1989): 415–27. http://dx.doi.org/10.2307/2274857.

Full text

Abstract:

The failure of a large and diverse body of work to settle some of the now-classical questions of computational complexity (notably P =? NP) suggests that they might not, in fact, be resolvable by established proof techniques.Hartmanis and Hopcroft [HH] raised the issue of independent statements about computational complexity in 1976, constructing, for any consistent r.e. theory T capable of expressing statements about Turing machines, a Turing machine MT such that statements which intuitively express the computational complexity of MT are independent of T. Their technique involves a simple diagonalizing search over the theorems of T. In this paper we prove a constructive version of their independence result in the context of a generalization of a hierarchy of free variable logics defined by Rose [R1]. These logics are based on an axiomatized treatment of an extension by Löb and Wainer [LW] of Grzegorczyk's [G] hierarchy into the transfinite. Associated with each extended Grzegorczyk class (relative to an ordinal notation system S satisfying certain conditions) is the logic -arithmetic.Free variable logics are interesting from the perspective of theoretical computer science. We may construe the equational definition of functions as a form of programming system. Each -arithmetic, then, has the nice property of containing both a programming system and a logic for stating and proving facts about programs.

APA, Harvard, Vancouver, ISO, and other styles

22

Bès, Alexis, and Denis Richard. "Undecidable extensions of Skolem arithmetic." Journal of Symbolic Logic 63, no. 2 (June 1998): 379–401. http://dx.doi.org/10.2307/2586837.

Full text

Abstract:

AbstractLet be the restriction of usual order relation to integers which are primes or squares of primes, and let ⊥ denote the coprimeness predicate. The elementary theory of is undecidable. Now denote by <π the restriction of order to primary numbers. All arithmetical relations restricted to primary numbers are definable in the structure (ℕ; ⊥, <π). Furthermore, the structures (ℕ; ∣, <π) (ℕ; =, ×, <π) and (ℕ; =, +, ×) are interdefinable.

APA, Harvard, Vancouver, ISO, and other styles

23

Siomau, Michael. "Undecidable, Unrecognizable, and Quantum Computing." Quantum Reports 2, no. 3 (July 1, 2020): 337–42. http://dx.doi.org/10.3390/quantum2030023.

Full text

Abstract:

Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.

APA, Harvard, Vancouver, ISO, and other styles

24

Mayr, Richard. "Undecidable problems in unreliable computations." Theoretical Computer Science 297, no. 1-3 (March 2003): 337–54. http://dx.doi.org/10.1016/s0304-3975(02)00646-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Moore, Matthew. "Finite degree clones are undecidable." Theoretical Computer Science 796 (December 2019): 237–71. http://dx.doi.org/10.1016/j.tcs.2019.09.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Stebletsova, Vera, and Yde Venema. "Undecidable theories of Lyndon algebras." Journal of Symbolic Logic 66, no. 1 (March 2001): 207–24. http://dx.doi.org/10.2307/2694918.

Full text

Abstract:

AbstractWith each projective geometry we can associate a Lyndon algebra. Such an algebra always satisfies Tarski's axioms for relation algebras and Lyndon algebras thus form an interesting connection between the fields of projective geometry and algebraic logic. In this paper we prove that if G is a class of projective geometries which contains an infinite projective geometry of dimension at least three, then the class L(G) of Lyndon algebras associated with projective geometries in G has an undecidable equational theory. In our proof we develop and use a connection between projective geometries and diagonal-free cylindric algebras.

APA, Harvard, Vancouver, ISO, and other styles

27

Frank, Manfred, and Barry Allen. "Are There Rationally Undecidable Arguments?" Common Knowledge 25, no. 1-3 (April 1, 2019): 63–75. http://dx.doi.org/10.1215/0961754x-7299126.

Full text

Abstract:

Frank in this article treats the disagreement between François Lyotard and Jürgen Habermas over whether there are arguments that cannot be decided rationally. Lyotard identifies rational undecidability as the “postmodern condition.” Habermas objects that reasonable procedures do exist that are adequate for the resolution of any argument among reasonable participants. Frank judges Lyotard’s argument as unpersuasive yet blames Habermas for dismissing altogether the idea of rationally undecidable disagreements. Frank then turns from contemporary philosophy to early German Romantic hermeneutics and literary theory to substantiate a claim that unresolvable disagreement exists even amid consensus. “Every consensus,” Frank writes in explication of Friedrich Schleiermacher, “contains a residual misunderstanding that will never entirely go away, and this is why no consensus as to either the meaning or the interpretation of the world can ever be final or universally valid.” Frank moreover cites the even more radical position of Friedrich Schlegel: “All truth is relative—but together with that proposition another must be coordinated: there is essentially no such thing as error.” Frank’s own conclusion, reached after comparing these Romantic notions with Jacques Derrida’s concept of différance, is that “the shaping of consensus will never lead us to a universal symbolism that everyone must make use of in the same way.”

APA, Harvard, Vancouver, ISO, and other styles

28

Gafni, Eli, and Elias Koutsoupias. "Three-Processor Tasks Are Undecidable." SIAM Journal on Computing 28, no. 3 (January 1998): 970–83. http://dx.doi.org/10.1137/s0097539796305766.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Schmidt-Schauss, Manfred. "Implication of clauses is undecidable." Theoretical Computer Science 59, no. 3 (August 1988): 287–96. http://dx.doi.org/10.1016/0304-3975(88)90146-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Frank, M. "ARE THERE RATIONALLY UNDECIDABLE ARGUMENTS?" Common Knowledge 9, no. 1 (January 1, 2003): 119–31. http://dx.doi.org/10.1215/0961754x-9-1-119.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Loader, R. "Higher Order Matching is Undecidable." Logic Journal of IGPL 11, no. 1 (January 1, 2003): 51–68. http://dx.doi.org/10.1093/jigpal/11.1.51.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

McNulty, George F. "Alfred Tarski and undecidable theories." Journal of Symbolic Logic 51, no. 4 (December 1986): 890–98. http://dx.doi.org/10.2307/2273902.

Full text

Abstract:

Alfred Tarski identified decidability within various logical formalisms as one of the principal themes for investigation in mathematical logic. This is evident already in the focus of the seminar he organized in Warsaw in 1926. Over the ensuing fifty-five years, Tarski put forth a steady stream of theorems concerning decidability, many with far-reaching consequences. Just as the work of the 1926 seminar reflected Tarski's profound early interest in decidability, so does his last work, A formalization of set theory without variables, a monograph written in collaboration with S. Givant [8−m]. An account of the Warsaw seminar can be found in Vaught [1986].Tarski's work on decidability falls into four broad areas: elementary theories which are decidable, elementary theories which are undecidable, the undecidability of theories of various restricted kinds, and what might be called decision problems of the second degree. An account of Tarski's work with decidable elementary theories can be found in Doner and van den Dries [1987] and in Monk [1986] (for Boolean algebras). Vaught [1986] discusses Tarski's contributions to the method of quantifier elimination. Our principal concern here is Tarski's work in the remaining three areas.We will say that a set of elementary sentences is a theory provided it is closed with respect to logical consequence and we will say that a theory is decidable or undecidable depending on whether it is a recursive or nonrecursive set. The notion of a theory may be restricted in a number of interesting ways. For example, an equational theory is just the set of all universal sentences, belonging to some elementary theory, whose quantifier-free parts are equations between terms.

APA, Harvard, Vancouver, ISO, and other styles

33

Nies, A. "Undecidable fragments of elementary theories." Algebra Universalis 35, no. 1 (March 1996): 8–33. http://dx.doi.org/10.1007/bf01190967.

Full text

APA, Harvard, Vancouver, ISO, and other styles

34

Aerts, Sven. "Undecidable Classical Properties of Observers." International Journal of Theoretical Physics 44, no. 12 (December 2005): 2113–25. http://dx.doi.org/10.1007/s10773-005-9008-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Nutt, Werner. "The unification hierarchy is undecidable." Journal of Automated Reasoning 7, no. 3 (1991): 369–81. http://dx.doi.org/10.1007/bf00249020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Ketema, Jeroen. "Some Undecidable Approximations of TRSs." Electronic Notes in Theoretical Computer Science 124, no. 2 (April 2005): 51–63. http://dx.doi.org/10.1016/j.entcs.2004.11.024.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Dolan, Peter. "Undecidable statements and random graphs." Annals of Mathematics and Artificial Intelligence 6, no. 1-3 (March 1992): 17–25. http://dx.doi.org/10.1007/bf01531021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

38

Schewe, Sven. "Distributed synthesis is simply undecidable." Information Processing Letters 114, no. 4 (April 2014): 203–7. http://dx.doi.org/10.1016/j.ipl.2013.11.012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

39

Robinson, E. J., and P. Mitchell. "Children's Failure to Make Judgements of Undecidability when they are Ignorant." International Journal of Behavioral Development 13, no. 4 (December 1990): 467–88. http://dx.doi.org/10.1177/016502549001300405.

Full text

Abstract:

In five investigations we tested 5 to 7-year-olds' ability to make appropriate judgements of "undecidable". Children pointed at the picture they thought might be a named familiar or unfamiliar cartoon character from a set of 5, and were asked if they knew or didn't know their chosen picture was the target. Judgements about familiar targets were accurate, but children often failed to make correct "don't know" judgements ("undecidable") about unfamiliar targets. This was not simply because children felt "don't know" was too negative an expression, given that their chosen picture might have been the target, since varying the wording had little effect: "just think" and "just hope" contrasted with "know"; "hard" contrasted with "easy"; "don't know" contrasted with "is it [target name] or isn't it". Further results showed that children were not simply avoiding loss of face caused by admitting to ignorance, nor were they simply committed to their chosen picture. Finally, asking children if they had ever heard of the target before, increased the likelihood of their subsequently making correct "undecidable" judgements. We discuss why "undecidable" judgements might be difficult for children to make, and why alerting them to lack of past experience via their correct judgements of "never heard of.." was beneficial to their making correct judgements of "undecidable".

APA, Harvard, Vancouver, ISO, and other styles

40

Kontchakov, Roman, Agi Kurucz, and Michael Zakharyaschev. "Undecidability of First-Order Intuitionistic and Modal Logics with Two variables." Bulletin of Symbolic Logic 11, no. 3 (September 2005): 428–38. http://dx.doi.org/10.2178/bsl/1122038996.

Full text

Abstract:

AbstractWe prove that the two-variable fragment of first-order intuitionistic logic is undecidable, even without constants and equality. We also show that the two-variable fragment of a quantified modal logic L with expanding first-order domains is undecidable whenever there is a Kripke frame for L with a point having infinitely many successors (such are, in particular, the first-order extensions of practically all standard modal logics like K, K4, GL, S4, S5, K4.1, S4.2, GL.3, etc.). For many quantified modal logics, including those in the standard nomenclature above, even the monadic two-variable fragments turn out to be undecidable.

APA, Harvard, Vancouver, ISO, and other styles

41

Kent, Thomas F. "The Π3-theory of the -enumeration degrees is undecidable." Journal of Symbolic Logic 71, no. 4 (December 2006): 1284–302. http://dx.doi.org/10.2178/jsl/1164060455.

Full text

Abstract:

AbstractWe show that in the language of { ≤ }. the Π3-fragment of the first order theory of the -enumeration degrees is undecidable. We then extend this result to show that the Π3-theory of any substructure of the enumeration degrees which contains the -degrees is undecidable.

APA, Harvard, Vancouver, ISO, and other styles

42

GILLIBERT, PIERRE. "THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE." International Journal of Algebra and Computation 24, no. 01 (February 2014): 1–9. http://dx.doi.org/10.1142/s0218196714500015.

Full text

Abstract:

The finiteness problem for automaton groups and semigroups has been widely studied, several partial positive results are known. However, we prove that, in the most general case, the problem is undecidable. We study the case of automaton semigroups. Given a NW-deterministic Wang tile set, we construct a Mealy automaton, such that the plane admits a valid Wang tiling if and only if the Mealy automaton generates a infinite semigroup. The construction is similar to a construction by Kari for proving that the nilpotency problem for cellular automata is unsolvable. Moreover, Kari proves that the tiling of the plane is undecidable for NW-deterministic Wang tile set. It follows that the finiteness problem for automaton semigroups is undecidable.

APA, Harvard, Vancouver, ISO, and other styles

43

CHVALOVSKÝ, KAREL. "UNDECIDABILITY OF CONSEQUENCE RELATION IN FULL NON-ASSOCIATIVE LAMBEK CALCULUS." Journal of Symbolic Logic 80, no. 2 (April 22, 2015): 567–86. http://dx.doi.org/10.1017/jsl.2014.39.

Full text

Abstract:

AbstractWe prove that the consequence relation in the Full Non-associative Lambek Calculus is undecidable. An encoding of the halting problem for 2-tag systems using finitely many sequents in the language {⋅,∨} is presented. Therefore already the consequence relation in this fragment is undecidable. Moreover, the construction works even when the structural rules of exchange and contraction are added.

APA, Harvard, Vancouver, ISO, and other styles

44

Hirsch, Robin, and Marcel Jackson. "Undecidability of representability as binary relations." Journal of Symbolic Logic 77, no. 4 (December 2012): 1211–44. http://dx.doi.org/10.2178/jsl.7704090.

Full text

Abstract:

AbstractIn this article we establish the undecidability of representability and of finite representability as algebras of binary relations in a wide range of signatures. In particular, representability and finite representability are undecidable for Boolean monoids and lattice ordered monoids, while representability is undecidable for Jónsson's relation algebra. We also establish a number of undecidability results for representability as algebras of injective functions.

APA, Harvard, Vancouver, ISO, and other styles

45

BELL, PAUL C., and IGOR POTAPOV. "ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS." International Journal of Foundations of Computer Science 21, no. 06 (December 2010): 963–78. http://dx.doi.org/10.1142/s0129054110007660.

Full text

Abstract:

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. In the second part of the paper we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup S of integral square matrices whether or not the identity matrix belongs to S?". We show that the problem is undecidable starting from dimension four even when the number of matrices in the generator is 48. From this fact, we can immediately derive that the fundamental problem of whether a finite set of matrices generates a group is also undecidable. We also answer several questions for matrices over different number fields. Apart from the application to matrix problems, we believe that the Identity Correspondence Problem will also be useful in identifying new areas of undecidable problems in abstract algebra, computational questions in logic and combinatorics on words.

APA, Harvard, Vancouver, ISO, and other styles

46

Chagrova, L. A. "An undecidable problem in correspondence theory." Journal of Symbolic Logic 56, no. 4 (December 1991): 1261–72. http://dx.doi.org/10.2307/2275473.

Full text

Abstract:

In this paper we prove undecidability of first-order definability of propositional formulas. The main result is proved for intuitionistic formulas, but it remains valid for other kinds of propositional formulas by analogous arguments or with the help of various translations.For general background on correspondence theory the reader is referred to van Benthem [1], [2] (see [3] for a survey of recent results).The method for the proofs of undecidability in this paper will be to simulate calculations of a Minsky machine by intuitionistic formulas. §3 concerns this simulation. Effective procedures for the construction of simulating modal formulas can be found in the literature (cf. [4]).The principal results of the paper are in §4. §5 gives some further undecidability results, that will be proved in another paper by modification of the method of this paper.I am indebted to the referee for drawing my attention to some errors in an earlier version of this paper.

APA, Harvard, Vancouver, ISO, and other styles

47

Mikulás, Szabolcs, and Maarten Marx. "Undecidable relativizations of algebras of relations." Journal of Symbolic Logic 64, no. 2 (June 1999): 747–60. http://dx.doi.org/10.2307/2586497.

Full text

Abstract:

AbstractIn this paper we show that relativized versions of relation set algebras and cylindric set algebras have undecidable equational theories if we include coordinatewise versions of the counting operations into the similarity type. We apply these results to the guarded fragment of first-order logic.

APA, Harvard, Vancouver, ISO, and other styles

48

Plump, Detlef. "Termination of Graph Rewriting is Undecidable." Fundamenta Informaticae 33, no. 2 (1998): 201–9. http://dx.doi.org/10.3233/fi-1998-33204.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Culik, Hugh. "Our Lady, Queen of Undecidable Propositions." Journal of Humanistic Mathematics 6, no. 2 (July 2016): 230–40. http://dx.doi.org/10.5642/jhummath.201602.21.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Seynhaeve, Franck, Sophie Tison, Marc Tommasi, and Ralf Treinen. "Grid structures and undecidable constraint theories." Theoretical Computer Science 258, no. 1-2 (May 2001): 453–90. http://dx.doi.org/10.1016/s0304-3975(00)00032-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!