Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings /: 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings. (2015)
- Record Type:
- Book
- Title:
- Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings /: 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings. (2015)
- Main Title:
- Fundamentals of computation theory : 20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings
- Other Titles:
- FCT 2015
- Further Information:
- Note: Adrian Kosowski, Igor Walukiewicz (eds.).
- Editors:
- Kosowski, Adrian
Walukiewicz, Igor - Other Names:
- FCT (Symposium), 20th
- Contents:
- Intro; Preface; Conference Organization; Invited Talks; It is Better to be Vaguely Right Than Exactly Wrong; Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies; On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS; Contents; Invited talks; Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies; 1 Introduction; 2 Underlying Idea; 3 TSP and Related Problems; 4 Bounded Occurrence Optimization Problems; 5 Bi-wheel Amplifier Graphs; 6 Preparation Lemma; 7 Instances of Metric TSP 8 Instances of Asymmetric TSP (ATSP)9 A Role of Weights; 10 Graphic TSP; 11 Some Applications; 12 Summary of Main Results; 13 Further Research; References; On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS; 1 Introduction; 2 Preliminaries; 2.1 Probabilistic Vector Addition Systems with States; 2.2 Patterns and Pattern Frequencies; 3 Pattern Frequency in One-Counter pVASS; 3.1 Approximating [p↓q] and [p↑]; 3.2 Approximating E R↓s and E#t r↓s; 4 Pattern Frequency in Two-Counter pVASS; 5 Future Research; References; Geometry, Combinatorics, Text Algorithms Longest -Gapped Repeat and Palindrome1 Introduction; 2 Preliminaries; 3 Our Solution; References; On the Enumeration of Permutominoes; 1 Introduction; 2 Preliminaries; 3 The Inflate-Paste Technique; 4 Direct Enumeration of Permutominoes; 5 Tailoring the Algorithm to Specific Subclasses; 5.1 Convex Permutominoes; 5.2Intro; Preface; Conference Organization; Invited Talks; It is Better to be Vaguely Right Than Exactly Wrong; Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies; On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS; Contents; Invited talks; Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies; 1 Introduction; 2 Underlying Idea; 3 TSP and Related Problems; 4 Bounded Occurrence Optimization Problems; 5 Bi-wheel Amplifier Graphs; 6 Preparation Lemma; 7 Instances of Metric TSP 8 Instances of Asymmetric TSP (ATSP)9 A Role of Weights; 10 Graphic TSP; 11 Some Applications; 12 Summary of Main Results; 13 Further Research; References; On the Existence and Computability of Long-Run Average Properties in Probabilistic VASS; 1 Introduction; 2 Preliminaries; 2.1 Probabilistic Vector Addition Systems with States; 2.2 Patterns and Pattern Frequencies; 3 Pattern Frequency in One-Counter pVASS; 3.1 Approximating [p↓q] and [p↑]; 3.2 Approximating E R↓s and E#t r↓s; 4 Pattern Frequency in Two-Counter pVASS; 5 Future Research; References; Geometry, Combinatorics, Text Algorithms Longest -Gapped Repeat and Palindrome1 Introduction; 2 Preliminaries; 3 Our Solution; References; On the Enumeration of Permutominoes; 1 Introduction; 2 Preliminaries; 3 The Inflate-Paste Technique; 4 Direct Enumeration of Permutominoes; 5 Tailoring the Algorithm to Specific Subclasses; 5.1 Convex Permutominoes; 5.2 Row-Convex Permutominoes; 6 Conclusion; References; Stabbing Segments with Rectilinear Objects; 1 Introduction; 2 Stabbing with One or Two Halfplanes; 2.1 Stabbing Halfplane; 2.2 Stabbing Strips; 2.3 Stabbing Quadrants; 3 Stabbing with Three Halfplanes 4.2 Depth Implies Highness or DNR4.3 A Low Deep Set; 4.4 No K-Trivial is O(1)-deepK; 5 Infinitely Often Depth and Conditional Depth; 6 Conclusion; References; On the Expressive Power of Read-Once Determinants; 1 Introduction; 2 Basic Observations; 3 Elementary Symmetric Polynomials and Permanent; 3.1 Elementary Symmetric Polynomials; 3.2 Non-expressibility of Permanent as ROD; 4 Non-expressible Monomial Sets; 5 Discussion and Open Problems; References; Constructive Relationships Between Algebraic Thickness and Normality; 1 Introduction and Known Results; 2 Preliminaries and Known Results … (more)
- Publisher Details:
- Cham : Springer
- Publication Date:
- 2015
- Extent:
- 1 online resource (xix, 395 pages), illustrations
- Subjects:
- 004
Computer science
Computer science -- Congresses
Computer science
Computers -- Hardware -- Network Hardware
Computers -- Programming -- General
Computers -- Data Processing
Computers -- Software Development & Engineering -- General
Network hardware
Computer programming / software development
Discrete mathematics
Software Engineering
Computer software
Computer Communication Networks
Logic design
Computational complexity
Software engineering
Computers -- Programming -- Algorithms
Algorithms & data structures
Electronic books
Conference papers and proceedings
Electronic books - Languages:
- English
- ISBNs:
- 9783319221779
3319221779
3319221760
9783319221762 - Related ISBNs:
- 9783319221762
- Notes:
- Note: Online resource; title from PDF title page (SpringerLink, viewed August 14, 2015).
- Access Rights:
- Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
- Access Usage:
- Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library HMNTS - ELD.DS.354825
- Ingest File:
- 01_314.xml