Conditional and Typed Rewriting Systems [[electronic resource] ] : 4th International Workshop, CTRS-94, Jerusalem, Israel, July 13 - 15, 1994. Proceedings / / edited by Nachum Dershowitz, Naomi Lindenstrauss |
Edizione | [1st ed. 1995.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1995 |
Descrizione fisica | 1 online resource (VIII, 384 p.) |
Disciplina | 005.13/1 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Mathematical logic
Computers Software engineering Programming languages (Electronic computers) Artificial intelligence Computer logic Mathematical Logic and Formal Languages Theory of Computation Software Engineering/Programming and Operating Systems Programming Languages, Compilers, Interpreters Artificial Intelligence Logics and Meanings of Programs |
ISBN | 3-540-45513-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Associative-commutative superposition -- A calculus for rippling -- Equation solving in geometrical theories -- LSE narrowing for decreasing conditional term rewrite systems -- Preserving confluence for rewrite systems with built-in operations -- Hierarchical termination -- Well-foundedness of term orderings -- A new characterisation of AC-termination and application -- Relative normalization in orthogonal expression reduction systems -- On termination and confluence of conditional rewrite systems -- How to transform canonical decreasing CTRSs into equivalent canonical TRSs -- Termination for restricted derivations and conditional rewrite systems -- Rewriting for preorder relations -- Strong sequentiality of left-linear overlapping rewrite systems -- A conflict between call-by-need computation and parallelism -- The complexity of testing ground reducibility for linear word rewriting systems with variables -- Coherence for cartesian closed categories: A sequential approach -- Modular properties of constructor-sharing conditional term rewriting systems -- Church-Rosser property and unique normal form property of non-duplicating term rewriting systems -- The transformation of term rewriting systems based on well-formedness preserving mappings -- Abstract notions and inference systems for proofs by mathematical induction. |
Record Nr. | UNISA-996466102703316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 1995 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Fields of Logic and Computation [[electronic resource] ] : Essays Dedicated to Yuri Gurevich on the Occasion of His 70th Birthday / / edited by Andreas Blass, Nachum Dershowitz, Wolfgang Reisig |
Edizione | [1st ed. 2010.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 |
Descrizione fisica | 1 online resource (XIII, 627 p. 49 illus.) |
Disciplina | 004.0151 |
Collana | Programming and Software Engineering |
Soggetto topico |
Computer programming
Computer logic Software engineering Mathematical logic Algorithms Computer communication systems Programming Techniques Logics and Meanings of Programs Software Engineering Mathematical Logic and Formal Languages Algorithm Analysis and Problem Complexity Computer Communication Networks |
ISBN |
1-280-38827-7
9786613566195 3-642-15025-X |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | On Yuri Gurevich -- Yuri, Logic, and Computer Science -- Database Theory, Yuri, and Me -- Technical Papers -- Tracking Evidence -- Strict Canonical Constructive Systems -- Decidable Expansions of Labelled Linear Orderings -- Existential Fixed-Point Logic, Universal Quantifiers, and Topoi -- Three Paths to Effectiveness -- The Quest for a Tight Translation of Büchi to co-Büchi Automata -- Normalization of Some Extended Abstract State Machines -- Finding Reductions Automatically -- On Complete Problems, Relativizations and Logics for Complexity Classes -- Effective Closed Subshifts in 1D Can Be Implemented in 2D -- The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey -- A Logic for PTIME and a Parameterized Halting Problem -- Inferring Loop Invariants Using Postconditions -- ASMs and Operational Algorithmic Completeness of Lambda Calculus -- Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs -- Ibn S?n? on Analysis: 1. Proof Search. Or: Abstract State Machines as a Tool for History of Logic -- Abstract State Machines and the Inquiry Process -- The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion -- Definability of Combinatorial Functions and Their Linear Recurrence Relations -- Halting and Equivalence of Program Schemes in Models of Arbitrary Theories -- Metrization Theorem for Space-Times: From Urysohn’s Problem towards Physically Useful Constructive Mathematics -- Thirteen Definitions of a Stable Model -- DKAL and Z3: A Logic Embedding Experiment -- Decidability of the Class E by Maslov’s Inverse Method -- Logics for Two Fragments beyond the Syllogistic Boundary -- Choiceless Computation and Symmetry -- Hereditary Zero-One Laws for Graphs -- On Monadic Theories of Monadic Predicates. |
Record Nr. | UNISA-996466291103316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2010 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Fields of logic and computation : essays dedicated to Yuri Gurevich on the occassion of his 70th birthday / / Andreas Blass, Nachum Dershowitz, Wolfgang Reisig (eds.) |
Edizione | [1st ed. 2010.] |
Pubbl/distr/stampa | Berlin ; ; New York, : Springer, c2010 |
Descrizione fisica | 1 online resource (XIII, 627 p. 49 illus.) |
Disciplina | 004.0151 |
Altri autori (Persone) |
BlassAndreas <1947->
DershowitzNachum ReisigWolfgang <1950-> |
Collana | Lecture notes in computer science |
Soggetto topico |
Computer algorithms
Logic, Symbolic and mathematical |
ISBN |
1-280-38827-7
9786613566195 3-642-15025-X |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | On Yuri Gurevich -- Yuri, Logic, and Computer Science -- Database Theory, Yuri, and Me -- Technical Papers -- Tracking Evidence -- Strict Canonical Constructive Systems -- Decidable Expansions of Labelled Linear Orderings -- Existential Fixed-Point Logic, Universal Quantifiers, and Topoi -- Three Paths to Effectiveness -- The Quest for a Tight Translation of Büchi to co-Büchi Automata -- Normalization of Some Extended Abstract State Machines -- Finding Reductions Automatically -- On Complete Problems, Relativizations and Logics for Complexity Classes -- Effective Closed Subshifts in 1D Can Be Implemented in 2D -- The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey -- A Logic for PTIME and a Parameterized Halting Problem -- Inferring Loop Invariants Using Postconditions -- ASMs and Operational Algorithmic Completeness of Lambda Calculus -- Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs -- Ibn S?n? on Analysis: 1. Proof Search. Or: Abstract State Machines as a Tool for History of Logic -- Abstract State Machines and the Inquiry Process -- The Algebra of Adjacency Patterns: Rees Matrix Semigroups with Reversion -- Definability of Combinatorial Functions and Their Linear Recurrence Relations -- Halting and Equivalence of Program Schemes in Models of Arbitrary Theories -- Metrization Theorem for Space-Times: From Urysohn’s Problem towards Physically Useful Constructive Mathematics -- Thirteen Definitions of a Stable Model -- DKAL and Z3: A Logic Embedding Experiment -- Decidability of the Class E by Maslov’s Inverse Method -- Logics for Two Fragments beyond the Syllogistic Boundary -- Choiceless Computation and Symmetry -- Hereditary Zero-One Laws for Graphs -- On Monadic Theories of Monadic Predicates. |
Record Nr. | UNINA-9910483367003321 |
Berlin ; ; New York, : Springer, c2010 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Fields of Logic and Computation II [[electronic resource] ] : Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday / / edited by Lev D. Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, Wolfram Schulte |
Edizione | [1st ed. 2015.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
Descrizione fisica | 1 online resource (X, 319 p. 15 illus.) |
Disciplina | 004.015113 |
Collana | Programming and Software Engineering |
Soggetto topico |
Computer programming
Programming Techniques |
ISBN | 3-319-23534-6 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Intro -- Preface -- Contents -- K-trivial, K-low and MLR-low Sequences: A Tutorial -- 1 Notation -- 2 K-trivial Sets: Definition and Existence -- 3 K-trivial and K-low Sequences -- 4 K-trivial Sequences Cannot Compute 0' -- 5 K-trivial Sequences Are K-low -- 6 K-low and MLR-low Oracles -- References -- Horn Clause Solvers for Program Verification -- 1 Introduction -- 1.1 Program Logics and Horn Clauses -- 1.2 Paper Outline -- 2 Horn Clause Basics -- 2.1 Existential Fixed-Point Logic and Horn Clauses -- 2.2 Derivations and Interpretations -- 2.3 Loose Semantics and Horn Clauses -- 3 From Programs to Clauses -- 3.1 State Machines -- 3.2 Procedural Languages -- 3.3 Proof Rules -- 4 Solving Horn Clauses -- 4.1 Magic Sets -- 4.2 Fold/Unfold -- 4.3 A Program Transformation for Inlining Assertions -- 5 Conclusions and Continuations -- References -- Existential Fixed-Point Logic as a Fragment of Second-Order Logic -- 1 Introduction -- 2 Preliminaries -- 2.1 Existential Fixed-Point Logic -- 2.2 Translation to Second-Order Logic -- 3 Model-Checking -- 4 Conjunctions -- 5 Satisfiability and Trimming -- 6 Trimming to Horn Form -- 7 Summary -- References -- On the Unpredictability of Individual Quantum Measurement Outcomes -- 1 Introduction -- 2 Models of Prediction -- 3 A Model for Prediction of Individual Physical Events -- 4 Computability Theoretic Notions of Unpredictability -- 5 Quantum Unpredictability -- 5.1 The Intuition of Quantum Indeterminism and Unpredictability -- 5.2 A Formal Basis for Quantum Indeterminism -- 5.3 Contextual Alternatives -- 5.4 Unpredictability of Individual Quantum Measurements -- 6 Incomputability, Unpredictability, and Quantum Randomness -- 7 Summary -- References -- The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture -- 1 Introduction -- 2 Preliminaries -- 3 The Ehrenfeucht-Fraïssé-method.
4 A Logical Reformulation of ¶=NP -- 5 On Random (3-Col,LFP)-Sequences -- 6 The Planted Clique Conjecture -- 7 The Planted Clique Conjecture and (3-Col,LFP)-sequences -- 8 Some Remarks on the Logic Version of the Planted Clique Conjecture -- 9 Further Results and Open Questions -- References -- Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations -- 1 Introduction -- 2 Preliminaries -- 2.1 Linear Orders -- 2.2 Logical Structures -- 3 Lifted Structure -- 3.1 The Semigroup "426830A P(L), "3222378 "526930B -- 3.2 A Characterization of the Operation "3222378 -- 3.3 The Partially Ordered Set "426830A P(L), "526930B -- 3.4 Final Segments -- 3.5 A Characterization of the Ordering -- 4 Defining Single Elements -- 4.1 Immediate Predecessors -- 4.2 Singleton Sets -- 4.3 Recovering the Linear Order -- 4.4 Pairs -- 5 Defining Membership -- 5.1 Defining Final Segments -- 5.2 Upwards Closure -- 5.3 Membership When L has a Minimum Element 0 -- 5.4 Membership in the General Case -- 6 Final Proofs -- 6.1 Defining the Downarrow Operation with Uparrow -- 6.2 Defining the Uparrow Operation with the Order -- 6.3 Equivalent First-Order Structures -- References -- Regularity Equals Monadic Second-Order Definability for Quasi-trees -- 1 Introduction -- 2 Definitions, Notation and Basic Facts -- 2.1 Finite and Infinite Terms -- 2.2 Arrangements -- 2.3 Trees and Rooted Trees -- 2.4 Join-Trees -- 2.5 The Rank-Width of a Countable Graph -- 3 The Algebra of Binary Join-Trees -- 4 Quasi-trees -- References -- Capturing MSO with One Quantifier -- 1 Introduction -- 2 Preliminaries -- 3 Satisfiability Quantifier -- 4 Capturing MSO -- 5 Unranked Trees -- 6 Conclusion -- References -- Logics for Weighted Timed Pushdown Automata -- 1 Introduction -- 2 Weighted Timed Pushdown Automata -- 3 Weighted Timed Matching Logic. 4 Visibly Pushdown Languages -- 5 Decomposition of Weighted Timed Pushdown Automata -- 6 Definability Equals Recognizability -- 7 Weighted Timed Pushdown Automata with Global Clocks -- 8 Conclusion -- References -- Inherent Vacuity in Lattice Automata -- 1 Introduction -- 2 Preliminaries -- 2.1 Lattices -- 2.2 Lattice Automata -- 3 Vacuity in Lattice Automata -- 4 Useful Observations on Tolerance and Flexibility -- 4.1 Full-Order LDFW -- 4.2 Full-Order LNFW -- 4.3 Partial-Order LDFW -- 4.4 Partial-Order LNFW -- 5 Complexity of the Decision Problems -- 6 Inherent Vacuity with Analogy to Temporal Logic -- References -- Is Polynomial Time Choiceless? -- 1 Introduction -- 2 Choiceless Polynomial Time -- 2.1 BGS-Logic -- 2.2 Definition of Choiceless Polynomial Time -- 2.3 Defining Properties of Small Substructures -- 2.4 Choiceless Polynomial Time Without Counting -- 3 Fixed-Point Logic with Counting -- 4 Structures of Bounded Colour Class Size -- 5 Symmetric Circuits -- 6 Interpretation Logic -- 7 Challenges for Future Research -- 7.1 A Characterization Without Explicit Polynomial Bounds -- 7.2 Polynomial-Time Properties of Small Definable Subgraphs -- 7.3 Isomorphism of CFI-Graphs and Graphs of Bounded Colour Class Size -- 7.4 Constraint Satisfaction Problems -- 7.5 A Notion of Symmetric Circuits for CPT -- 7.6 Choiceless Polynomial Time versus Rank Logic -- References -- Arithmetical Congruence Preservation: From Finite to Infinite -- 1 Introduction -- 2 Switching Between Finite and Infinite -- 2.1 Lifting Functions Z/nZZ/mZ to NN and ZZ -- 2.2 Representation of Congruence Preserving Functions Z/nZZ/mZ -- 2.3 Lifting Functions Z/nZZ/mZ to Z/rZZ/sZ -- 3 Congruence Preservation on p-adic/profinite Integers -- 3.1 Congruence Preserving Functions Are Continuous -- 3.2 Congruence Preserving Functions and Inverse Limits. 3.3 Extension of Congruence Preserving Functions NN -- 3.4 Representation of Congruence Preserving Functions ZpZp -- 4 Conclusion -- References -- An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers -- 1 Introduction -- 2 The Game -- 2.1 Description of the First Game -- 2.2 A Game Where Definability is Not Forced -- 2.3 A Game with Fixed Game-Board and Fixed Roles -- 3 Summary -- References -- Logics of Finite Hankel Rank -- 1 Introduction -- 1.1 Yuri's Quest for Logics for Computer Science -- 1.2 Preservation Theorems -- 1.3 Reduction Theorems -- 1.4 Purpose of This Paper -- 2 Background -- 2.1 Logics with Quantifier Rank -- 2.2 Sum-Like and Product-Like Operations on -structures -- 2.3 Abstract Lindström Logics -- 3 Hankel Matrices of -properties -- 3.1 Hankel Matrices -- 3.2 -Properties of Finite -rank -- 3.3 Proof of Theorem 5 -- 3.4 Properties of Finite S-rank and Finite P-rank -- 4 Hankel Matrices and the Feferman-Vaught Theorem -- 4.1 The FV-property -- 4.2 The FV-property and Finite Rank -- 5 The S-Closure of a Nice Logic -- 6 Conclusions and Open Problems -- References -- The Strategy of Campaigning -- 1 Introduction -- 2 A General Theorem -- 3 Ambiguity and Pessimism -- 4 The Logical Formalism of Dean and Parikh -- 5 Extension of the Framework -- 5.1 Candidate Beliefs -- 5.2 Stay-At-Home Voters -- 6 Conclusions and Future Work -- References -- On Almost Future Temporal Logics -- 1 Introduction -- 2 Preliminaries -- 2.1 First-Order Monadic Logic of Order -- 2.2 Propositional Temporal Logics -- 2.3 Kamp's and Stavi's Theorems -- 3 Future and Almost Future Formulas -- 4 No Finite Base for Almost Future Formulas -- 4.1 Proof of Lemma 4.3 -- 4.2 Proof of Lemma 4.4 -- 4.3 A Generalization -- References -- Minsky Machines and Algorithmic Problems -- 1 Introduction. 2 Turing Machines and Minsky Machines -- 2.1 Turing Machines -- 2.2 Minsky Machines -- 3 The Three Main Semigroups Simulating Minsky Machines -- 4 Varieties of Semigroups and the Word Problem -- 5 Gurevich's Theorem. The Uniform Word Problem for Finite Semigroups -- 6 The Uniform Word Problem for Finite Groups -- 6.1 Slobodskoi's Theorem -- 6.2 Some Applications of Slobodskoi's Theorem -- 7 Other Algorithmic Applications of Minsky Machines -- 7.1 Collatz Type Problems -- 7.2 Amalgams of Finite Semigroups -- 7.3 Complicated Residually Finite Semigroups -- References -- On Failure of 0-1 Laws -- References -- Composition Over the Natural Number Ordering with an Extra Binary Relation -- 1 Introduction -- 2 (N, <, P) with Monadic P -- 3 (N, <, R) with Binary R of Finite Valency -- 4 Applications -- 5 Conclusion -- References -- The Fundamental Nature of the Log Loss Function -- 1 Introduction -- 2 Loss Functions -- 3 Repetitive Predictions -- 4 A Simple Statement of Fundamentality -- 5 A Criterion of Fundamentality -- 6 Frequently Asked Questions -- 7 Conclusion -- References -- Erratum to: The Fundamental Natureof the Log Loss Function -- Author Index. |
Record Nr. | UNISA-996466457103316 |
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Fields of Logic and Computation II : Essays Dedicated to Yuri Gurevich on the Occasion of His 75th Birthday / / edited by Lev D. Beklemishev, Andreas Blass, Nachum Dershowitz, Bernd Finkbeiner, Wolfram Schulte |
Edizione | [1st ed. 2015.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
Descrizione fisica | 1 online resource (X, 319 p. 15 illus.) |
Disciplina | 004.015113 |
Collana | Programming and Software Engineering |
Soggetto topico |
Computer programming
Programming Techniques |
ISBN | 3-319-23534-6 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Intro -- Preface -- Contents -- K-trivial, K-low and MLR-low Sequences: A Tutorial -- 1 Notation -- 2 K-trivial Sets: Definition and Existence -- 3 K-trivial and K-low Sequences -- 4 K-trivial Sequences Cannot Compute 0' -- 5 K-trivial Sequences Are K-low -- 6 K-low and MLR-low Oracles -- References -- Horn Clause Solvers for Program Verification -- 1 Introduction -- 1.1 Program Logics and Horn Clauses -- 1.2 Paper Outline -- 2 Horn Clause Basics -- 2.1 Existential Fixed-Point Logic and Horn Clauses -- 2.2 Derivations and Interpretations -- 2.3 Loose Semantics and Horn Clauses -- 3 From Programs to Clauses -- 3.1 State Machines -- 3.2 Procedural Languages -- 3.3 Proof Rules -- 4 Solving Horn Clauses -- 4.1 Magic Sets -- 4.2 Fold/Unfold -- 4.3 A Program Transformation for Inlining Assertions -- 5 Conclusions and Continuations -- References -- Existential Fixed-Point Logic as a Fragment of Second-Order Logic -- 1 Introduction -- 2 Preliminaries -- 2.1 Existential Fixed-Point Logic -- 2.2 Translation to Second-Order Logic -- 3 Model-Checking -- 4 Conjunctions -- 5 Satisfiability and Trimming -- 6 Trimming to Horn Form -- 7 Summary -- References -- On the Unpredictability of Individual Quantum Measurement Outcomes -- 1 Introduction -- 2 Models of Prediction -- 3 A Model for Prediction of Individual Physical Events -- 4 Computability Theoretic Notions of Unpredictability -- 5 Quantum Unpredictability -- 5.1 The Intuition of Quantum Indeterminism and Unpredictability -- 5.2 A Formal Basis for Quantum Indeterminism -- 5.3 Contextual Alternatives -- 5.4 Unpredictability of Individual Quantum Measurements -- 6 Incomputability, Unpredictability, and Quantum Randomness -- 7 Summary -- References -- The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture -- 1 Introduction -- 2 Preliminaries -- 3 The Ehrenfeucht-Fraïssé-method.
4 A Logical Reformulation of ¶=NP -- 5 On Random (3-Col,LFP)-Sequences -- 6 The Planted Clique Conjecture -- 7 The Planted Clique Conjecture and (3-Col,LFP)-sequences -- 8 Some Remarks on the Logic Version of the Planted Clique Conjecture -- 9 Further Results and Open Questions -- References -- Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations -- 1 Introduction -- 2 Preliminaries -- 2.1 Linear Orders -- 2.2 Logical Structures -- 3 Lifted Structure -- 3.1 The Semigroup "426830A P(L), "3222378 "526930B -- 3.2 A Characterization of the Operation "3222378 -- 3.3 The Partially Ordered Set "426830A P(L), "526930B -- 3.4 Final Segments -- 3.5 A Characterization of the Ordering -- 4 Defining Single Elements -- 4.1 Immediate Predecessors -- 4.2 Singleton Sets -- 4.3 Recovering the Linear Order -- 4.4 Pairs -- 5 Defining Membership -- 5.1 Defining Final Segments -- 5.2 Upwards Closure -- 5.3 Membership When L has a Minimum Element 0 -- 5.4 Membership in the General Case -- 6 Final Proofs -- 6.1 Defining the Downarrow Operation with Uparrow -- 6.2 Defining the Uparrow Operation with the Order -- 6.3 Equivalent First-Order Structures -- References -- Regularity Equals Monadic Second-Order Definability for Quasi-trees -- 1 Introduction -- 2 Definitions, Notation and Basic Facts -- 2.1 Finite and Infinite Terms -- 2.2 Arrangements -- 2.3 Trees and Rooted Trees -- 2.4 Join-Trees -- 2.5 The Rank-Width of a Countable Graph -- 3 The Algebra of Binary Join-Trees -- 4 Quasi-trees -- References -- Capturing MSO with One Quantifier -- 1 Introduction -- 2 Preliminaries -- 3 Satisfiability Quantifier -- 4 Capturing MSO -- 5 Unranked Trees -- 6 Conclusion -- References -- Logics for Weighted Timed Pushdown Automata -- 1 Introduction -- 2 Weighted Timed Pushdown Automata -- 3 Weighted Timed Matching Logic. 4 Visibly Pushdown Languages -- 5 Decomposition of Weighted Timed Pushdown Automata -- 6 Definability Equals Recognizability -- 7 Weighted Timed Pushdown Automata with Global Clocks -- 8 Conclusion -- References -- Inherent Vacuity in Lattice Automata -- 1 Introduction -- 2 Preliminaries -- 2.1 Lattices -- 2.2 Lattice Automata -- 3 Vacuity in Lattice Automata -- 4 Useful Observations on Tolerance and Flexibility -- 4.1 Full-Order LDFW -- 4.2 Full-Order LNFW -- 4.3 Partial-Order LDFW -- 4.4 Partial-Order LNFW -- 5 Complexity of the Decision Problems -- 6 Inherent Vacuity with Analogy to Temporal Logic -- References -- Is Polynomial Time Choiceless? -- 1 Introduction -- 2 Choiceless Polynomial Time -- 2.1 BGS-Logic -- 2.2 Definition of Choiceless Polynomial Time -- 2.3 Defining Properties of Small Substructures -- 2.4 Choiceless Polynomial Time Without Counting -- 3 Fixed-Point Logic with Counting -- 4 Structures of Bounded Colour Class Size -- 5 Symmetric Circuits -- 6 Interpretation Logic -- 7 Challenges for Future Research -- 7.1 A Characterization Without Explicit Polynomial Bounds -- 7.2 Polynomial-Time Properties of Small Definable Subgraphs -- 7.3 Isomorphism of CFI-Graphs and Graphs of Bounded Colour Class Size -- 7.4 Constraint Satisfaction Problems -- 7.5 A Notion of Symmetric Circuits for CPT -- 7.6 Choiceless Polynomial Time versus Rank Logic -- References -- Arithmetical Congruence Preservation: From Finite to Infinite -- 1 Introduction -- 2 Switching Between Finite and Infinite -- 2.1 Lifting Functions Z/nZZ/mZ to NN and ZZ -- 2.2 Representation of Congruence Preserving Functions Z/nZZ/mZ -- 2.3 Lifting Functions Z/nZZ/mZ to Z/rZZ/sZ -- 3 Congruence Preservation on p-adic/profinite Integers -- 3.1 Congruence Preserving Functions Are Continuous -- 3.2 Congruence Preserving Functions and Inverse Limits. 3.3 Extension of Congruence Preserving Functions NN -- 3.4 Representation of Congruence Preserving Functions ZpZp -- 4 Conclusion -- References -- An Extension of the Ehrenfeucht-Fraïssé Game for First Order Logics Augmented with Lindström Quantifiers -- 1 Introduction -- 2 The Game -- 2.1 Description of the First Game -- 2.2 A Game Where Definability is Not Forced -- 2.3 A Game with Fixed Game-Board and Fixed Roles -- 3 Summary -- References -- Logics of Finite Hankel Rank -- 1 Introduction -- 1.1 Yuri's Quest for Logics for Computer Science -- 1.2 Preservation Theorems -- 1.3 Reduction Theorems -- 1.4 Purpose of This Paper -- 2 Background -- 2.1 Logics with Quantifier Rank -- 2.2 Sum-Like and Product-Like Operations on -structures -- 2.3 Abstract Lindström Logics -- 3 Hankel Matrices of -properties -- 3.1 Hankel Matrices -- 3.2 -Properties of Finite -rank -- 3.3 Proof of Theorem 5 -- 3.4 Properties of Finite S-rank and Finite P-rank -- 4 Hankel Matrices and the Feferman-Vaught Theorem -- 4.1 The FV-property -- 4.2 The FV-property and Finite Rank -- 5 The S-Closure of a Nice Logic -- 6 Conclusions and Open Problems -- References -- The Strategy of Campaigning -- 1 Introduction -- 2 A General Theorem -- 3 Ambiguity and Pessimism -- 4 The Logical Formalism of Dean and Parikh -- 5 Extension of the Framework -- 5.1 Candidate Beliefs -- 5.2 Stay-At-Home Voters -- 6 Conclusions and Future Work -- References -- On Almost Future Temporal Logics -- 1 Introduction -- 2 Preliminaries -- 2.1 First-Order Monadic Logic of Order -- 2.2 Propositional Temporal Logics -- 2.3 Kamp's and Stavi's Theorems -- 3 Future and Almost Future Formulas -- 4 No Finite Base for Almost Future Formulas -- 4.1 Proof of Lemma 4.3 -- 4.2 Proof of Lemma 4.4 -- 4.3 A Generalization -- References -- Minsky Machines and Algorithmic Problems -- 1 Introduction. 2 Turing Machines and Minsky Machines -- 2.1 Turing Machines -- 2.2 Minsky Machines -- 3 The Three Main Semigroups Simulating Minsky Machines -- 4 Varieties of Semigroups and the Word Problem -- 5 Gurevich's Theorem. The Uniform Word Problem for Finite Semigroups -- 6 The Uniform Word Problem for Finite Groups -- 6.1 Slobodskoi's Theorem -- 6.2 Some Applications of Slobodskoi's Theorem -- 7 Other Algorithmic Applications of Minsky Machines -- 7.1 Collatz Type Problems -- 7.2 Amalgams of Finite Semigroups -- 7.3 Complicated Residually Finite Semigroups -- References -- On Failure of 0-1 Laws -- References -- Composition Over the Natural Number Ordering with an Extra Binary Relation -- 1 Introduction -- 2 (N, <, P) with Monadic P -- 3 (N, <, R) with Binary R of Finite Valency -- 4 Applications -- 5 Conclusion -- References -- The Fundamental Nature of the Log Loss Function -- 1 Introduction -- 2 Loss Functions -- 3 Repetitive Predictions -- 4 A Simple Statement of Fundamentality -- 5 A Criterion of Fundamentality -- 6 Frequently Asked Questions -- 7 Conclusion -- References -- Erratum to: The Fundamental Natureof the Log Loss Function -- Author Index. |
Record Nr. | UNINA-9910484001403321 |
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Fields of Logic and Computation III [[electronic resource] ] : Essays Dedicated to Yuri Gurevich on the Occasion of His 80th Birthday / / edited by Andreas Blass, Patrick Cégielski, Nachum Dershowitz, Manfred Droste, Bernd Finkbeiner |
Edizione | [1st ed. 2020.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 |
Descrizione fisica | 1 online resource (x, 341 pages) |
Disciplina | 004.015113 |
Collana | Programming and Software Engineering |
Soggetto topico |
Computer programming
Data structures (Computer science) Computer communication systems Special purpose computers Artificial intelligence Computer logic Software engineering Programming Techniques Data Structures Computer Communication Networks Special Purpose and Application-Based Systems Logic in AI Software Engineering |
ISBN | 3-030-48006-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Computation -- Logic -- Verification -- Topos theory. -Parallel Computing -- Tree -- Gurevich conjecture -- Arabic algorithms -- Hyperbolic group -- Lattice-ordered group -- Temporal logic -- Metric logic -- Random convergence -- Knot theory -- Entropic convergence -- Random access machine, PTIME -- Algorithmic randomness. . |
Record Nr. | UNISA-996418286403316 |
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Fields of Logic and Computation III : Essays Dedicated to Yuri Gurevich on the Occasion of His 80th Birthday / / edited by Andreas Blass, Patrick Cégielski, Nachum Dershowitz, Manfred Droste, Bernd Finkbeiner |
Edizione | [1st ed. 2020.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 |
Descrizione fisica | 1 online resource (x, 341 pages) |
Disciplina |
004.015113
005.1015113 |
Collana | Programming and Software Engineering |
Soggetto topico |
Computer programming
Data structures (Computer science) Computer communication systems Special purpose computers Artificial intelligence Computer logic Software engineering Programming Techniques Data Structures Computer Communication Networks Special Purpose and Application-Based Systems Logic in AI Software Engineering |
ISBN | 3-030-48006-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Computation -- Logic -- Verification -- Topos theory. -Parallel Computing -- Tree -- Gurevich conjecture -- Arabic algorithms -- Hyperbolic group -- Lattice-ordered group -- Temporal logic -- Metric logic -- Random convergence -- Knot theory -- Entropic convergence -- Random access machine, PTIME -- Algorithmic randomness. . |
Record Nr. | UNINA-9910409668103321 |
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2020 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Language, Culture, Computation: Computational Linguistics and Linguistics [[electronic resource] ] : Essays Dedicated to Yaacov Choueka on the Occasion of His 75 Birthday, Part III / / edited by Nachum Dershowitz, Ephraim Nissan |
Edizione | [1st ed. 2014.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014 |
Descrizione fisica | 1 online resource (XVI, 868 p. 173 illus.) |
Disciplina | 006.35 |
Collana | Information Systems and Applications, incl. Internet/Web, and HCI |
Soggetto topico |
Artificial intelligence
Natural language processing (Computer science) Information storage and retrieval Computers Artificial Intelligence Natural Language Processing (NLP) Information Storage and Retrieval Theory of Computation |
ISBN | 3-642-45327-9 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Natural Language Processing -- Representing the Lexicon -- The Lexicon and Ontologies: Tools -- The Lexicon and Ontologies: Historical Linguistics -- Neologisation -- The Lexicon, Word Formation, and Neologisms.- Zoonymy, Neologised or Nativised. |
Record Nr. | UNISA-996211261803316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Language, Culture, Computation: Computational Linguistics and Linguistics : Essays Dedicated to Yaacov Choueka on the Occasion of His 75 Birthday, Part III / / edited by Nachum Dershowitz, Ephraim Nissan |
Edizione | [1st ed. 2014.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014 |
Descrizione fisica | 1 online resource (XVI, 868 p. 173 illus.) |
Disciplina | 006.35 |
Collana | Information Systems and Applications, incl. Internet/Web, and HCI |
Soggetto topico |
Artificial intelligence
Natural language processing (Computer science) Information storage and retrieval Computers Artificial Intelligence Natural Language Processing (NLP) Information Storage and Retrieval Theory of Computation |
ISBN | 3-642-45327-9 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Natural Language Processing -- Representing the Lexicon -- The Lexicon and Ontologies: Tools -- The Lexicon and Ontologies: Historical Linguistics -- Neologisation -- The Lexicon, Word Formation, and Neologisms.- Zoonymy, Neologised or Nativised. |
Record Nr. | UNINA-9910483378503321 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Language, Culture, Computation: Computing - Theory and Technology [[electronic resource] ] : Essays Dedicated to Yaacov Choueka on the Occasion of His 75 Birthday, Part I / / edited by Nachum Dershowitz, Ephraim Nissan |
Edizione | [1st ed. 2014.] |
Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014 |
Descrizione fisica | 1 online resource (XIV, 604 p. 101 illus.) |
Disciplina | 025.04072 |
Collana | Information Systems and Applications, incl. Internet/Web, and HCI |
Soggetto topico |
Artificial intelligence
Natural language processing (Computer science) Information storage and retrieval Computers Artificial Intelligence Natural Language Processing (NLP) Information Storage and Retrieval Theory of Computation |
ISBN | 3-642-45321-X |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | The Jubilarian: Yaacov and His Oeuvre -- Theory of Computation -- Science Computing and Tools for Engineering -- Information Retrieval. |
Record Nr. | UNISA-996211262003316 |
Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2014 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|