- Monadic Decomposition
2017/04/30 by Margus Veanes, Nikolaj Bjørner, Lev Nachmanson +1 · 3 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Automaton #Boolean satisfiability problem #Computer science #Decidability #Decision problem #Decomposition #Discrete mathematics #Formal Methods in Verification #Logic, programming, and type systems #Mathematics #Monadic predicate calculus #Quantifier (linguistics) #Satisfiability #Theoretical computer science #semigroups and automata theory
- Thermodynamical cost of some interpretations of quantum theory
2015/09/11 by Adán Cabello, Mile Gu, Otfried Gühne +2 · 1 voice · 6 citations
Arts and Humanities · Mathematics · Physics and Astronomy · #Advanced Thermodynamics and Statistical Mechanics #Calculus (dental) #Computer science #Consistent histories #Decidability #Discrete mathematics #Epistemology #Erasure #Interpretation (philosophy) #Linguistics #Mathematical economics #Mathematics #Metaphysics #Observer (physics) #Philosophy #Philosophy and History of Science #Philosophy of language #Physics #Pure mathematics #Quantum #Quantum Mechanics and Applications #Quantum dynamics #Quantum mechanics #Quantum process #Quantum system #Theoretical physics #Type (biology) #quant-ph
- Recursive Markov Decision Processes and Recursive Stochastic Games
2015/05/06 by Kousha Etessami, Mihalis Yannakakis · 2 citations
Computer Science · Mathematics · #Algorithm #Complexity and Algorithms in Graphs #Computer science #Context (archaeology) #Decidability #Decision problem #Discrete mathematics #Distributed systems and fault tolerance #Formal Methods in Verification #Markov chain #Markov decision process #Markov process #Mathematical economics #Mathematical optimization #Mathematics #Recursion (computer science) #Undecidable problem
- Ranking Functions for Linear-Constraint Loops
2014/07/01 by Amir M. Ben-Amram, Samir Genaim · 3 citations
Computer Science · Mathematics · #Advanced Algebra and Logic #Combinatorics #Computer science #Data Management and Algorithms #Decidability #Discrete mathematics #Formal Methods in Verification #Lexicographical order #Mathematics #P #Range (aeronautics) #Ranking (information retrieval) #Time complexity
- Uncertainty, incompleteness, chance, and design
2013/01/29 by Fernando Sols, Sols, Fernando · 1 voice
Arts and Humanities · Mathematics · Physics and Astronomy · #Calculus (dental) #Character (mathematics) #Computer science #Decidability #Discrete mathematics #Epistemology #Gödel #Gödel's incompleteness theorems #Indeterminacy (philosophy) #Mathematical economics #Mathematics #Philosophy #Philosophy and History of Science #Pure mathematics #Randomness #Scope (computer science) #Sequence (biology) #Undecidable problem #physics.hist-ph
- On rules with existential variables: Walking the decidability line
2011/04/19 by Jean-François Baget, Michel Leclère, Marie-Laure Mugnier +2 · 19 citations
Computer Science · Mathematics · #Advanced Database Systems and Queries #Artificial intelligence #Backward chaining #Chaining #Class (philosophy) #Computer science #Decidability #Discrete mathematics #Expert system #Forward chaining #Logical consequence #Mathematics #Semantic Web and Ontologies #Theoretical computer science #Undecidable problem
- Analyzing ambiguity of context-free grammars
2009/11/16 by Claus Brabrand, Robert Giegerich, Anders Møller · 1 citation
Biochemistry, Genetics and Molecular Biology · #Ambiguity #Artificial intelligence #Computer science #Context (archaeology) #Context-free grammar #Decidability #Definite clause grammar #Genomics and Chromatin Dynamics #Grammar #L-attributed grammar #Linguistics #Natural language processing #Parsing #Programming language #RNA and protein synthesis mechanisms #RNA modifications and cancer #Rule-based machine translation #Stochastic context-free grammar #Theoretical computer science #Tree-adjoining grammar #Undecidable problem
- Analyzing Context-Free Grammars Using an Incremental SAT Solver
2008/08/12 by Roland Axelsson, Keijo Heljanko, Martin Lange · 1 citation
Computer Science · Mathematics · #Algorithm #Ambiguity #Artificial intelligence #Boolean satisfiability problem #Bounded function #Computer science #Constraint Satisfaction and Optimization #Correctness #Decidability #Description logic #Discrete mathematics #Equivalence (formal languages) #Formal Methods in Verification #Intermediate logic #Logic, Reasoning, and Knowledge #Mathematics #Programming language #Propositional calculus #Propositional formula #Propositional variable #Rule-based machine translation #Satisfiability #Theoretical computer science #Undecidable problem #Universality (dynamical systems)
- Elementary theory of free non-abelian groups
2006/06/07 by Olga Kharlampovich, Alexei Myasnikov · 2 citations
Computer Science · Mathematics · #Abelian group #Advanced Topology and Set Theory #Algebra over a field #Computer science #Decidability #Discrete mathematics #Elementary abelian group #Elementary theory #Geometric and Algebraic Topology #Mathematics #Pure mathematics #semigroups and automata theory
- Consistency of a counterexample to Naimark's problem
2003/12/06 by Charles A. Akemann, Charles Akemann, Nik Weaver · 2 citations
Mathematics · #Advanced Operator Algebra Research #Advanced Topics in Algebra #Advanced Topology and Set Theory #Algebra over a field #Axiom #Computer science #Counterexample #Decidability #Discrete mathematics #Equivalence (formal languages) #Hilbert space #Mathematics #Pure mathematics #Set (abstract data type) #Statement (logic) #Undecidable problem #math.FA #math.LO #math.OA
- The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics
2000/05/01 by S. Tobies · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Axiom #Biomedical Text Mining and Ontologies #Boolean satisfiability problem #Cardinality (data modeling) #Decidability #Description logic #Extension (predicate logic) #Formalism (music) #Logic, Reasoning, and Knowledge #Predicate (mathematical logic) #Satisfiability #Semantic Web and Ontologies #cs.AI
- Tarski’s problem about the elementary theory of free groups has a positive solution
1998/12/14 by Olga Kharlampovich, Alexei Myasnikov · 1 citation
Mathematics · #Geometric and Algebraic Topology #Algebraic Geometry and Number Theory #Homotopy and Cohomology in Algebraic Topology #Elementary theory #Mathematics #Decidability #Group (periodic table) #Elementary proof #Model theory #Infinite group #Free group #Group theory #Pure mathematics #Algebra over a field #Discrete mathematics #Quantum mechanics #Physics #Computer science
- Mathematical Foundations of Computer Science 1997
1997/01/01 by PrÃvara, Igor, RužiÄka, Peter, Igor Prívara +1 · 1 citation
Computer Science · Engineering · Mathematics · #Computability, Logic, AI Algorithms #Computer science #Decidability #Discrete mathematics #Engineering #Management science #Mathematics #Nondeterministic algorithm #Teaching and Learning Programming #Theoretical computer science #Transition system
- Computability and Recursion
1996/09/01 by Robert I. Soare · 3 citations
Computer Science · Mathematics · #Algorithm #Cellular Automata and Applications #Computability #Computability theory #Computability, Logic, AI Algorithms #Computable function #Computation #Computer science #Decidability #Discrete mathematics #Function (biology) #Mathematics #Programming language #Recursion (computer science) #Theoretical computer science #Turing #Turing machine #semigroups and automata theory
- Undecidable boundedness problems for datalog programs
1995/11/01 by Gerd G. Hillebrand, Gerd G Hillebrand, Paris C Kanellakis +5 · 1 citation
Computer Science · Mathematics · #Algorithm #Arity #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Datalog #Decidability #Discrete mathematics #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics #Partition (number theory) #Predicate (mathematical logic) #Programming language #Turing machine #Undecidable problem
- Reversibility and surjectivity problems of cellular automata
1994/02/01 by Jarkko Kari · 3 citations
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #Cellular Automata and Applications #DNA and Biological Computing #semigroups and automata theory #Undecidable problem #Injective function #Mathematics #Surjective function #Decidability #Mathematical proof #Discrete mathematics #Decision problem #Cellular automaton #Function (biology) #Combinatorics #Domino #Algorithm
- A generalized notion of weak interpretability and the corresponding modal logic
1993/05/01 by Giorgie Dzhaparidze · 1 citation
Computer Science · Mathematics · #Algebra over a field #Artificial intelligence #Computer science #Decidability #Discrete mathematics #Interpretability #Logic, Reasoning, and Knowledge #Mathematics #Modal #Modal logic #Multi-Agent Systems and Negotiation #Pure mathematics #Semantic Web and Ontologies
- Reasoning about systems with many processes
1992/07/01 by Steven M. German, A. Prasad Sistla · 27 citations
Computer Science · #Algorithm #Computer science #Decidability #Distributed computing #Finite-state machine #Formal Methods in Verification #Linear temporal logic #Logic, programming, and type systems #Mutual exclusion #Petri Nets in System Modeling #Process (computing) #Programming language #State (computer science) #Temporal logic #Theoretical computer science
- Reversibility of 2D cellular automata is undecidable
1990/09/01 by Jarkko Kari · 6 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithm #Asynchronous cellular automaton #Automata theory #Automaton #Block cellular automaton #Cellular Automata and Applications #Cellular automaton #Computability, Logic, AI Algorithms #Computer science #Continuous automaton #Continuous spatial automaton #DNA and Biological Computing #Decidability #Deterministic automaton #Discrete mathematics #Mathematics #Mobile automaton #Quantum finite automata #Reversible cellular automaton #Stochastic cellular automaton #Theoretical computer science #Timed automaton #Two-way deterministic finite automaton #Undecidable problem
- Nonconstructive tools for proving polynomial-time decidability
1988/06/01 by Michael R. Fellows, Michael A. Langston · 5 citations
Computer Science · Mathematics · #Formal Methods in Verification #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Decidability #Time complexity #Computer science #Decision problem #Graph #Set (abstract data type) #Theoretical computer science #Graph theory #Mathematics #Discrete mathematics #Algorithm #Combinatorics
- An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebras
1985/01/01 by Äbdelilah Kandri-Rody, Abdelilah Kandri-Rody, Deepak Kapur +1 · 2 citations
Computer Science · Mathematics · #Algebra over a field #Arithmetic #Commutative property #Computer science #Decidability #Discrete mathematics #Formal Methods in Verification #Gröbner basis #Ideal (ethics) #Logic, programming, and type systems #Mathematics #Modulo #Polynomial #Polynomial and algebraic computation #Polynomial ring #Pure mathematics #Unification #Word problem (mathematics education)
- An inductive theory for free products of groups
1979/12/01 by Verena Huber-Dyson · 1 citation
Arts and Humanities · Computer Science · Mathematics · #Adjunction #Algebra over a field #Arity #Computer science #Decidability #Discrete mathematics #Elementary theory #Free product #Geometric and Algebraic Topology #Group (periodic table) #Linguistics and Discourse Analysis #Mathematics #Morphism #Programming language #Pure mathematics #Unary operation #Undecidable problem #semigroups and automata theory
- Some decision problems related to the reachability problem for Petri nets
1976/10/01 by Toshiro Araki, Tadao Kasami · 1 citation
Computer Science · Mathematics · #Algorithm #Computer science #Decidability #Decision problem #Discrete mathematics #Equivalence (formal languages) #Formal Methods in Verification #Mathematics #Petri Nets in System Modeling #Petri net #Process architecture #Reachability #Reachability problem #Stochastic Petri net #Theoretical computer science #Undecidable problem #semigroups and automata theory
- Some undecidable problems involving elementary functions of a real variable
1969/01/01 by Daniel Richardson · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Numerical Methods and Algorithms #Polynomial and algebraic computation #Multiplication (music) #Undecidable problem #Mathematics #Elementary function #Variable (mathematics) #Expression (computer science) #Constant (computer programming) #Identity (music) #Function (biology) #Subtraction #Set (abstract data type) #Real number #Discrete mathematics #Algebra over a field #Arithmetic #Pure mathematics #Combinatorics #Computer science #Mathematical analysis #Decidability #Physics