- A Unified Translation of Linear Temporal Logic to ω-Automata
2020/10/17 by Javier Esparza, Jan Křetínský, Salomon Sickert · 7 citations
Computer Science · Mathematics · #Algorithm #Automata theory #Automaton #Computer science #Discrete mathematics #Formal Methods in Verification #Linear temporal logic #Logic, programming, and type systems #Mathematics #Nondeterministic algorithm #Quantum finite automata #Theoretical computer science #semigroups and automata theory #ω-automaton
- Memcomputing NP -complete problems in polynomial time using polynomial resources and collective states
2014/11/18 by Fabio L. Traversa, Chiara Ramella, Fabrizio Bonani +1 · 1 voice · 7 citations
Computer Science · Engineering · Mathematics · #Advanced Memory and Neural Computing #Algorithm #Architecture #Computation #Computer science #Ferroelectric and Negative Capacitance Devices #Mathematics #NP #NSPACE #Non-deterministic Turing machine #Nondeterministic algorithm #Overhead (engineering) #Polynomial #Programming language #Quantum Computing Algorithms and Architecture #State (computer science) #Theoretical computer science #Time hierarchy theorem #Turing machine #Universal Turing machine #Von Neumann architecture #cs.ET #cs.NE
- NON-UNIQUENESS AND RADIUS OF CYCLIC UNARY NFAs
2005/10/01 by Michael Domaratzki, Keith Ellul, JEFFREY SHALLIT +1 · 2 citations
Computer Science · Mathematics · #semigroups and automata theory #Algorithms and Data Compression #Cellular Automata and Applications #Unary operation #Nondeterministic algorithm #RADIUS #Mathematics #Uniqueness #Regular language #Diophantine equation #Class (philosophy) #Combinatorics #Discrete mathematics #Computer science #Mathematical analysis #Theoretical computer science #Automaton #Artificial intelligence
- Domain theory for concurrency
2004/02/27 by Mikkel Nygaard, Glynn Winskel · 2 citations
Computer Science · Mathematics · #Algebra over a field #Bisimulation #Computer science #Concurrency #Denotational semantics #Discrete mathematics #Domain theory #Formal Methods in Verification #Linear logic #Logic, programming, and type systems #Mathematical proof #Mathematics #Nondeterministic algorithm #Operational semantics #Programming language #Pure mathematics #Semantics (computer science) #Soundness #Theoretical computer science #semigroups and automata theory
- A second-order theory for NL
2004/01/01 by Simon Cook, Antonina Kolokolova · 1 citation
Computer Science · Mathematics · #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Advanced Algebra and Logic #Mathematics #Nondeterministic algorithm #Order (exchange) #Discrete mathematics #Horn clause #Bounded function #Set theory #Quantifier (linguistics) #Polynomial #Set (abstract data type) #Combinatorics #Algebra over a field #Pure mathematics #Computer science #Artificial intelligence
- A study of the applicability of existing exception-handling techniques to component-based real-time software technology
1998/03/01 by Jun Lang, David B. Stewart · 1 citation
Computer Science · #Advanced Software Engineering Methodologies #Algorithm #Component (thermodynamics) #Component-based software engineering #Computer science #Embedded Systems Design Techniques #Nondeterministic algorithm #Operating system #Real-Time Systems Scheduling #Reliability (semiconductor) #Reliability engineering #Software #Software construction #Software development #Software engineering #Software quality #Software reliability testing #Software sizing #Software system
- Mathematical Foundations of Computer Science 1997
1997/01/01 by PrÃvara, Igor, RužiÄka, Peter, Igor Prívara +1 · 2 citations
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
- Self-improving reactive agents based on reinforcement learning, planning and teaching
1992/05/01 by Long-Ji Lin · 5 citations
Computer Science · Mathematics · #Adaptive Dynamic Programming Control #Artificial intelligence #Computer science #Evolutionary Algorithms and Applications #Generalization #Heuristic #Learning classifier system #Machine learning #Mathematics #Nondeterministic algorithm #Reinforcement Learning in Robotics #Reinforcement learning #Testbed #Theoretical computer science
- Petri nets are monoids
1990/10/01 by José Meseguer, Ugo Montanari · 1 citation
Computer Science · Mathematics · #Algebra over a field #Computer science #Concurrency #Conservative extension #Distributed systems and fault tolerance #Distributive property #Formal Methods in Verification #Mathematics #Nondeterministic algorithm #Petri Nets in System Modeling #Petri net #Programming language #Pure mathematics #Theoretical computer science
- On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape turing machines
1989/02/01 by Zvi Galil, Ravi Kannan, Endre Szemerédi · 1 citation
Computer Science · Mathematics · #Advanced Data Storage Technologies #Algorithm #Cellular Automata and Applications #Combinatorics #Computation #Discrete mathematics #Mathematics #NSPACE #Non-deterministic Turing machine #Nondeterministic algorithm #Probabilistic Turing machine #Quantum Computing Algorithms and Architecture #Sublinear function #Time hierarchy theorem #Turing machine #Upper and lower bounds
- On the complexity of omega -automata
1988/01/01 by Muli Safra · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · Mathematics · #semigroups and automata theory #Chemical Synthesis and Analysis #Formal Methods in Verification #Nondeterministic algorithm #Büchi automaton #Automaton #Discrete mathematics #Automata theory #Computer science #Quantum finite automata #Successor cardinal #ω-automaton #Order (exchange) #Omega #Exponential function #Upper and lower bounds #Mathematics #Theoretical computer science #Combinatorics #Deterministic automaton
- Algebraic laws for nondeterminism and concurrency
1985/01/01 by Matthew Hennessy, Robin Milner · 46 citations
Computer Science · Mathematics · #Algebra over a field #Bisimulation #Computer science #Concurrency #Congruence (geometry) #Denotational semantics #Extension (predicate logic) #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics #Nondeterministic algorithm #Operational semantics #Programming language #Pure mathematics #Recursion (computer science) #Semantics (computer science) #Simple (philosophy) #Theoretical computer science
- Black-white pebbles and graph separation
1981/12/01 by Thomas Lengauer · 9 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computation #Computer science #Feedback vertex set #Graph #Graph Labeling and Dimension Problems #Mathematics #Nondeterministic algorithm #Pebble #Theoretical computer science #Theory of computation #Vertex (graph theory)
- NP-Complete decision problems for binary quadratics
1978/04/01 by Kenneth L. Manders, Leonard M. Adleman, Leonard Adleman · 1 citation
Computer Science · Mathematics · #Algorithm #Combinatorics #Complexity class #Computability, Logic, AI Algorithms #Computational complexity theory #Decision problem #Degree (music) #Discrete mathematics #Logic, programming, and type systems #Mathematics #Modulo #NP #Natural number #Nondeterministic algorithm #P versus NP problem #PSPACE #Time complexity #Turing machine #Variable (mathematics) #semigroups and automata theory
- New problems complete for nondeterministic log space
1976/12/01 by Neil D. Jones, Y. Edmund Lien, William T. Laaser · 1 citation
Computer Science · Mathematics · #Associative property #Combinatorics #Discrete mathematics #Equivalence (formal languages) #Logic, Reasoning, and Knowledge #Mathematics #Natural Language Processing Techniques #Nondeterministic algorithm #Pure mathematics #Reachability #Reachability problem #Satisfiability #Semantic Web and Ontologies
- A Powerdomain Construction
1976/09/01 by Gordon Plotkin · 11 citations
Computer Science · Mathematics · #Logic, programming, and type systems #Formal Methods in Verification #Logic, Reasoning, and Knowledge #Nondeterministic algorithm #Exponentiation #Class (philosophy) #Domain (mathematical analysis) #Mathematics #Product (mathematics) #Semantics (computer science) #Discrete mathematics #Algebraic number #Combinatorics #Computer science #Programming language
- Tessellations with local transformations
1972/10/01 by Daniel Richardson, D. Richardson · 5 citations
Business, Management and Accounting · Engineering · Materials Science · Mathematics · #Advanced Theoretical and Applied Studies in Material Sciences and Geometry #Algebra over a field #Combinatorics #Compact space #Discrete mathematics #Domain (mathematical analysis) #Function (biology) #Geometry #Inverse #Mathematical analysis #Mathematics #Nondeterministic algorithm #Optics and Image Analysis #Product (mathematics) #Pure mathematics #Quasicrystal Structures and Properties #Topology (electrical circuits) #Transformation (genetics) #Translation (biology)
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
1971/10/01 by Frank R. Moore · 1 citation
Computer Science · Mathematics · #semigroups and automata theory #Machine Learning and Algorithms #Computability, Logic, AI Algorithms #Mathematical proof #Nondeterministic algorithm #Deterministic finite automaton #Nondeterministic finite automaton #Finite-state machine #Equivalence (formal languages) #Quantum finite automata #Discrete mathematics #Automaton #DFA minimization #Deterministic automaton #Mathematics #Finite set #Finite state #Set (abstract data type) #Automata theory #Computer science #Theoretical computer science #Algorithm
- General properties of star height of regular events
1970/06/01 by Rina Cohen, Rina S. Cohen, Janusz Brzozowski +1 · 2 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Combinatorics #Complement (music) #Computability, Logic, AI Algorithms #Concatenation (mathematics) #Discrete mathematics #Mathematical analysis #Mathematics #Nondeterministic algorithm #Quotient #Star (game theory) #Upper and lower bounds #semigroups and automata theory