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
• 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.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
• 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.