Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Descriptional Complexity of Formal Systems [[electronic resource] ] : 13 International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings / / edited by Markus Holzer, Martin Kutrib, Giovanni Pighizzini
| Descriptional Complexity of Formal Systems [[electronic resource] ] : 13 International Workshop, DCFS 2011, Gießen/Limburg, Germany, July 25-27, 2011. Proceedings / / edited by Markus Holzer, Martin Kutrib, Giovanni Pighizzini |
| Edizione | [1st ed. 2011.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 |
| Descrizione fisica | 1 online resource (X, 329 p. 59 illus., 1 illus. in color.) |
| Disciplina | 004.0151 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science
Software engineering Machine theory Theory of Computation Software Engineering Formal Languages and Automata Theory Computer Science Logic and Foundations of Programming |
| ISBN | 3-642-22600-0 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNISA-996465750903316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2011 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Implementation and Application of Automata [[electronic resource] ] : 19th International Conference, CIAA 2014, Giessen, Germany, July 30 -- August 2, 2014, Proceedings / / edited by Markus Holzer, Martin Kutrib
| Implementation and Application of Automata [[electronic resource] ] : 19th International Conference, CIAA 2014, Giessen, Germany, July 30 -- August 2, 2014, Proceedings / / edited by Markus Holzer, Martin Kutrib |
| Edizione | [1st ed. 2014.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014 |
| Descrizione fisica | 1 online resource (X, 347 p. 76 illus.) |
| Disciplina | 511.3 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science
Algorithms Machine theory Bioinformatics Artificial intelligence—Data processing Information storage and retrieval systems Theory of Computation Formal Languages and Automata Theory Computational and Systems Biology Data Science Information Storage and Retrieval |
| ISBN | 3-319-08846-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Table of Contents -- Invited Papers -- FPsolve: A Generic Solver for Fixpoint Equations over Semirings -- 1 Introduction -- 2 Scenario: A Recommendation System -- 3 Algorithms and Data Structures -- 3.1 Solving Linear Equations -- 3.2 Decomposition into Strongly-Connected Components -- 4 Implementation -- 4.1 Invocation of the Standalone Solver -- 4.2 Custom Semirings and Extensions -- 5 Conclusions and Related Tools -- References -- Restarting Automata for Picture Languages: A Survey on Recent Developments -- 1 Introduction -- 2 Pictures and Picture Languages -- 3 Sgraffito Automata -- 4 Deterministic Sgraffito Automata -- 5 Restarting Tiling Automata -- 6 Ordered Restarting Automata -- 7 Deterministic Three-Way ORWW-Automata -- 8 Deterministic Two-Way ORWW-Automata -- 9 Conclusion -- References -- Investigations on Automata and Languages over a Unary Alphabet -- 1 Introduction -- 2 Unary Finite Automata: Optimal Simulations -- 3 Unary Two-Way Automata -- 4 Beyond Finite Automata -- 5 Beyond Regular Languages -- 6 Final Remarks -- References -- Cellular Automata for Crowd Dynamics -- 1 Introduction -- 2 CA Models for Crowd Dynamics -- 3 Conclusions -- References -- Regular Papers -- Counting Equivalent Linear Finite Transducers Using a Canonical Form -- 1 Introduction -- 2 Basic Concepts -- 3 Testing the Equivalence of LFTs -- 4 Canonical LFTs -- 5 On the Size of Equivalence Classes of LFTs -- 6 Conclusion -- References -- On the Power of One-Way Automata with Quantum and Classical States -- 1 Introduction -- 2 Preliminaries -- 2.1 Linear Algebra -- 2.2 Languages and Formal Power Series -- 2.3 Finite Automata -- 3 Characterizing the Power of qcfas -- 4 Size-Cost of Language Operations on qcfas -- References -- On Comparing Deterministic Finite Automata and the Shuffle of Words -- 1 Introduction.
2 Preliminaries -- 3 Fixed-Length Skeleton Polynomial Algorithm -- 4 General coNP-Completeness -- References -- Minimal Partial Languages and Automata -- 1 Introduction -- 2 Approximating Minimal -DFAs -- 3 Computing Minimal -DFAs -- 3.1 Our Minlang Algorithm -- 3.2 Our Redundancy Check Algorithm -- 3.3 Our Partial Language Check Algorithm -- 4 Adapting Minlang for Infinite Languages -- 5 Conclusion and Open Problems -- References -- Large Aperiodic Semigroups -- 1 Introduction -- 2 Terminology and Notation -- 3 Unitary and Semiconstant DFAs -- 4 Unitary Semigroups -- 5 Semiconstant Semigroups -- References -- On the Square of Regular Languages -- 1 Introduction -- 2 Square for Automata with k Final States -- 2.1 An Application -- 3 Square of Languages over Unary Alphabet -- 3.1 Finite Unary Languages -- 3.2 General Unary Languages -- 4 Conclusions -- References -- Unary Languages Recognized by Two-Way One-Counter Automata -- 1 Introduction -- 2 Background -- 3 Main Results -- 3.1 Simulation of Multi-counter Automata on Unary Alphabet -- 3.2 Simulation of Turing Machines on Binary and General Alphabets -- 3.3 A Quantum Simplification -- 3.4 Unary 2D1CAs versus Two-Counter Machines -- References -- A Type System for Weighted Automata and Rational Expressions -- 1 Introduction -- 2 Typing Automata and Rational Expressions -- 2.1 Weighted Automata -- 2.2 Rational Expressions -- 3 The Type System -- 3.1 Operations on Automata -- 3.2 The Hierarchy of Types -- 3.3 Type Restriction -- 4 Implementation Facet -- 4.1 The Value/ValueSet Design Principle -- 4.2 Computations on Types -- 4.3 On-the-Fly Compilation -- 5 Future Work and Improvements -- 5.1 Syntactic and Semantic Improvements of Contexts -- 5.2 Dynamic Compilation Granularity -- 6 Conclusion -- References -- Bounded Prefix-Suffix Duplication -- 1 Introduction -- 2 Preliminaries. 3 Bounded Prefix-Suffix Duplication as a Formal Operation on Languages -- 3.1 Membership Problem -- 4 Bounded Prefix-Suffix Duplication Distances -- References -- Recognition of Labeled Multidigraphs by Spanning Tree Automata -- 1 Introduction -- 2 Preliminaries -- 3 Spanning Tree Automaton -- 3.1 Definition -- 3.2 Basic Properties -- 4 Membership Problem -- 4.1 NP-Completeness -- 4.2 Linear-Time Solvability of the Membership Problem for Graphs of Bounded Tree-Width -- 5 Conclusion and Future Work -- References -- Reset Thresholds of Automata with Two Cycle Lengths -- 1 Introduction -- 2 Wielandt-Type Automata -- 3 Dulmage-Mendelsohn-Type Automata -- References -- On the Ambiguity, Finite-Valuedness, and Lossiness Problems in Acceptors and Transducers -- 1 Introduction -- 2 Ambiguity in Acceptors -- 3 Finite-Valuedness in Transducers -- 4 Lossiness in Transducers -- 5 Finite-Valuedness in Context-Free Transducers -- 6 Undecidable Problems Concerning 2-Tape NFAs -- 7 Conclusion -- References -- Kleene Closure on Regular and Prefix-Free Languages -- 1 Introduction -- 2 Kleene Closure on Regular Languages: Contiguous Range of Complexities for Linear Alphabet -- 3 Kleene Closure on Prefix-Free Languages -- 4 Conclusions -- References -- Left is Better than Right for Reducing Nondeterminism of NFAs -- 1 Introduction -- 2 Preliminaries -- 3 NFA Constructions from Regular Expressions -- 4 NFA Reduction by Invariant Equivalences -- 5 Nondeterminism of NFAs -- 6 Experimental Results -- 6.1 Size Reduction of NFAs -- 6.2 Reduction of Nondeterminism -- 7 Conclusions -- References -- Analytic Functions Computable by Finite State Transducers -- 1 Introduction -- 2 Subshifts -- 3 Finite Accepting Automata -- 4 M¨obius Transformations -- 5 M¨obius Number Systems -- 6 Finite State Transducers -- 7 Analytic Functions -- 8 Rational Transformations and Intervals. 9 The Binary Signed System -- 10 Bimodular Systems -- 11 Conclusions -- References -- Partial Derivative and Position Bisimilarity Automata -- 1 Introduction -- 2 Regular Expressions and Automata -- 2.1 Position Automaton -- 2.2 Partial Derivative Automaton -- 3 Apd Characterizations and Bisimilarity -- 3.1 Linear Regular Expressions -- 3.2 Finite Languages -- 3.3 Comparing -- 3.4 General Regular Languages -- References -- The Power of Regularity-Preserving Multi Bottom-up Tree Transducers -- 1 Introduction -- 2 Notation -- 3 Formal Models -- 4 Main Results -- References -- Pushdown Machines for Weighted Context-Free Tree Translation -- 1 Introduction -- 2 Preliminaries -- 3 Weighted Synchronous Context-Free Tree Grammar -- 4 Weighted Pushdown Extended Tree Transducers -- 5 Main Result -- 6 Conclusion -- References -- Weighted Variable Automata over Infinite Alphabets -- 1 Introduction -- 2 Preliminaries -- 3 Weighted Variable Automata -- 4 Closure Properties of the Class VRec (K,Σ). -- 5 Rational Series over Infinite Alphabets -- 6 Application to Variable Finite Automata -- Conclusion -- References -- Implications of Quantum Automata for Contextuality -- 1 Preliminaries -- 1.1 Promise Problems -- 1.2 Quantum Automata -- 2 Quantum Automata for Promise Problems -- 2.1 Exact Rational (Sweeping) 2QCFA Algorithm -- 2.2 Exact Rational Restarting rtQCFA Algorithm -- 2.3 Las Vegas Rational rtQCFA Algorithm -- 2.4 Succinctness of Realtime QFAs -- 3 Noncontextual Inequalities from Automata -- 4 Discussion -- References -- Pairwise Rational Kernels Obtained by Automaton Operations -- 1 Introduction -- 2 Related Works -- 3 Background -- 3.1 Automata, Finite-State Transducers -- 3.2 Kernels and Rational Kernels -- 3.3 n-gram Kernel as a Rational Kernel -- 3.4 Pairwise Rational Kernels -- 4 New Pairwise Rational Kernels as Automaton Operations. 4.1 General Definitions -- 4.2 Automata Operations -- 4.3 New Pairwise Rational Kernels -- 4.4 Algorithms -- 5 Methods -- 5.1 Dataset and Kernels -- 5.2 Learning Procedure -- 6 Results -- 7 Conclusion -- References -- Author Index. |
| Record Nr. | UNISA-996213698703316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Implementation and Application of Automata : 19th International Conference, CIAA 2014, Giessen, Germany, July 30 -- August 2, 2014, Proceedings / / edited by Markus Holzer, Martin Kutrib
| Implementation and Application of Automata : 19th International Conference, CIAA 2014, Giessen, Germany, July 30 -- August 2, 2014, Proceedings / / edited by Markus Holzer, Martin Kutrib |
| Edizione | [1st ed. 2014.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014 |
| Descrizione fisica | 1 online resource (X, 347 p. 76 illus.) |
| Disciplina | 511.3 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science
Algorithms Machine theory Bioinformatics Artificial intelligence - Data processing Information storage and retrieval systems Theory of Computation Formal Languages and Automata Theory Computational and Systems Biology Data Science Information Storage and Retrieval |
| ISBN | 3-319-08846-7 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Table of Contents -- Invited Papers -- FPsolve: A Generic Solver for Fixpoint Equations over Semirings -- 1 Introduction -- 2 Scenario: A Recommendation System -- 3 Algorithms and Data Structures -- 3.1 Solving Linear Equations -- 3.2 Decomposition into Strongly-Connected Components -- 4 Implementation -- 4.1 Invocation of the Standalone Solver -- 4.2 Custom Semirings and Extensions -- 5 Conclusions and Related Tools -- References -- Restarting Automata for Picture Languages: A Survey on Recent Developments -- 1 Introduction -- 2 Pictures and Picture Languages -- 3 Sgraffito Automata -- 4 Deterministic Sgraffito Automata -- 5 Restarting Tiling Automata -- 6 Ordered Restarting Automata -- 7 Deterministic Three-Way ORWW-Automata -- 8 Deterministic Two-Way ORWW-Automata -- 9 Conclusion -- References -- Investigations on Automata and Languages over a Unary Alphabet -- 1 Introduction -- 2 Unary Finite Automata: Optimal Simulations -- 3 Unary Two-Way Automata -- 4 Beyond Finite Automata -- 5 Beyond Regular Languages -- 6 Final Remarks -- References -- Cellular Automata for Crowd Dynamics -- 1 Introduction -- 2 CA Models for Crowd Dynamics -- 3 Conclusions -- References -- Regular Papers -- Counting Equivalent Linear Finite Transducers Using a Canonical Form -- 1 Introduction -- 2 Basic Concepts -- 3 Testing the Equivalence of LFTs -- 4 Canonical LFTs -- 5 On the Size of Equivalence Classes of LFTs -- 6 Conclusion -- References -- On the Power of One-Way Automata with Quantum and Classical States -- 1 Introduction -- 2 Preliminaries -- 2.1 Linear Algebra -- 2.2 Languages and Formal Power Series -- 2.3 Finite Automata -- 3 Characterizing the Power of qcfas -- 4 Size-Cost of Language Operations on qcfas -- References -- On Comparing Deterministic Finite Automata and the Shuffle of Words -- 1 Introduction.
2 Preliminaries -- 3 Fixed-Length Skeleton Polynomial Algorithm -- 4 General coNP-Completeness -- References -- Minimal Partial Languages and Automata -- 1 Introduction -- 2 Approximating Minimal -DFAs -- 3 Computing Minimal -DFAs -- 3.1 Our Minlang Algorithm -- 3.2 Our Redundancy Check Algorithm -- 3.3 Our Partial Language Check Algorithm -- 4 Adapting Minlang for Infinite Languages -- 5 Conclusion and Open Problems -- References -- Large Aperiodic Semigroups -- 1 Introduction -- 2 Terminology and Notation -- 3 Unitary and Semiconstant DFAs -- 4 Unitary Semigroups -- 5 Semiconstant Semigroups -- References -- On the Square of Regular Languages -- 1 Introduction -- 2 Square for Automata with k Final States -- 2.1 An Application -- 3 Square of Languages over Unary Alphabet -- 3.1 Finite Unary Languages -- 3.2 General Unary Languages -- 4 Conclusions -- References -- Unary Languages Recognized by Two-Way One-Counter Automata -- 1 Introduction -- 2 Background -- 3 Main Results -- 3.1 Simulation of Multi-counter Automata on Unary Alphabet -- 3.2 Simulation of Turing Machines on Binary and General Alphabets -- 3.3 A Quantum Simplification -- 3.4 Unary 2D1CAs versus Two-Counter Machines -- References -- A Type System for Weighted Automata and Rational Expressions -- 1 Introduction -- 2 Typing Automata and Rational Expressions -- 2.1 Weighted Automata -- 2.2 Rational Expressions -- 3 The Type System -- 3.1 Operations on Automata -- 3.2 The Hierarchy of Types -- 3.3 Type Restriction -- 4 Implementation Facet -- 4.1 The Value/ValueSet Design Principle -- 4.2 Computations on Types -- 4.3 On-the-Fly Compilation -- 5 Future Work and Improvements -- 5.1 Syntactic and Semantic Improvements of Contexts -- 5.2 Dynamic Compilation Granularity -- 6 Conclusion -- References -- Bounded Prefix-Suffix Duplication -- 1 Introduction -- 2 Preliminaries. 3 Bounded Prefix-Suffix Duplication as a Formal Operation on Languages -- 3.1 Membership Problem -- 4 Bounded Prefix-Suffix Duplication Distances -- References -- Recognition of Labeled Multidigraphs by Spanning Tree Automata -- 1 Introduction -- 2 Preliminaries -- 3 Spanning Tree Automaton -- 3.1 Definition -- 3.2 Basic Properties -- 4 Membership Problem -- 4.1 NP-Completeness -- 4.2 Linear-Time Solvability of the Membership Problem for Graphs of Bounded Tree-Width -- 5 Conclusion and Future Work -- References -- Reset Thresholds of Automata with Two Cycle Lengths -- 1 Introduction -- 2 Wielandt-Type Automata -- 3 Dulmage-Mendelsohn-Type Automata -- References -- On the Ambiguity, Finite-Valuedness, and Lossiness Problems in Acceptors and Transducers -- 1 Introduction -- 2 Ambiguity in Acceptors -- 3 Finite-Valuedness in Transducers -- 4 Lossiness in Transducers -- 5 Finite-Valuedness in Context-Free Transducers -- 6 Undecidable Problems Concerning 2-Tape NFAs -- 7 Conclusion -- References -- Kleene Closure on Regular and Prefix-Free Languages -- 1 Introduction -- 2 Kleene Closure on Regular Languages: Contiguous Range of Complexities for Linear Alphabet -- 3 Kleene Closure on Prefix-Free Languages -- 4 Conclusions -- References -- Left is Better than Right for Reducing Nondeterminism of NFAs -- 1 Introduction -- 2 Preliminaries -- 3 NFA Constructions from Regular Expressions -- 4 NFA Reduction by Invariant Equivalences -- 5 Nondeterminism of NFAs -- 6 Experimental Results -- 6.1 Size Reduction of NFAs -- 6.2 Reduction of Nondeterminism -- 7 Conclusions -- References -- Analytic Functions Computable by Finite State Transducers -- 1 Introduction -- 2 Subshifts -- 3 Finite Accepting Automata -- 4 M¨obius Transformations -- 5 M¨obius Number Systems -- 6 Finite State Transducers -- 7 Analytic Functions -- 8 Rational Transformations and Intervals. 9 The Binary Signed System -- 10 Bimodular Systems -- 11 Conclusions -- References -- Partial Derivative and Position Bisimilarity Automata -- 1 Introduction -- 2 Regular Expressions and Automata -- 2.1 Position Automaton -- 2.2 Partial Derivative Automaton -- 3 Apd Characterizations and Bisimilarity -- 3.1 Linear Regular Expressions -- 3.2 Finite Languages -- 3.3 Comparing -- 3.4 General Regular Languages -- References -- The Power of Regularity-Preserving Multi Bottom-up Tree Transducers -- 1 Introduction -- 2 Notation -- 3 Formal Models -- 4 Main Results -- References -- Pushdown Machines for Weighted Context-Free Tree Translation -- 1 Introduction -- 2 Preliminaries -- 3 Weighted Synchronous Context-Free Tree Grammar -- 4 Weighted Pushdown Extended Tree Transducers -- 5 Main Result -- 6 Conclusion -- References -- Weighted Variable Automata over Infinite Alphabets -- 1 Introduction -- 2 Preliminaries -- 3 Weighted Variable Automata -- 4 Closure Properties of the Class VRec (K,Σ). -- 5 Rational Series over Infinite Alphabets -- 6 Application to Variable Finite Automata -- Conclusion -- References -- Implications of Quantum Automata for Contextuality -- 1 Preliminaries -- 1.1 Promise Problems -- 1.2 Quantum Automata -- 2 Quantum Automata for Promise Problems -- 2.1 Exact Rational (Sweeping) 2QCFA Algorithm -- 2.2 Exact Rational Restarting rtQCFA Algorithm -- 2.3 Las Vegas Rational rtQCFA Algorithm -- 2.4 Succinctness of Realtime QFAs -- 3 Noncontextual Inequalities from Automata -- 4 Discussion -- References -- Pairwise Rational Kernels Obtained by Automaton Operations -- 1 Introduction -- 2 Related Works -- 3 Background -- 3.1 Automata, Finite-State Transducers -- 3.2 Kernels and Rational Kernels -- 3.3 n-gram Kernel as a Rational Kernel -- 3.4 Pairwise Rational Kernels -- 4 New Pairwise Rational Kernels as Automaton Operations. 4.1 General Definitions -- 4.2 Automata Operations -- 4.3 New Pairwise Rational Kernels -- 4.4 Algorithms -- 5 Methods -- 5.1 Dataset and Kernels -- 5.2 Learning Procedure -- 6 Results -- 7 Conclusion -- References -- Author Index. |
| Record Nr. | UNINA-9910483916603321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2014 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||