Implementation and Application of Automata [[electronic resource] ] : 27th International Conference, CIAA 2023, Famagusta, North Cyprus, September 19–22, 2023, Proceedings / / edited by Benedek Nagy |
Edizione | [1st ed. 2023.] |
Pubbl/distr/stampa | Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2023 |
Descrizione fisica | 1 online resource (313 pages) |
Disciplina | 511.3 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computer science
Artificial intelligence Information storage and retrieval systems Algorithms Computer science - Mathematics Discrete mathematics Theory of Computation Computer Science Logic and Foundations of Programming Artificial Intelligence Information Storage and Retrieval Discrete Mathematics in Computer Science |
ISBN | 3-031-40247-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Finite automata as verifiers -- Binary Coded Unary Regular Languages -- A Survey on Automata with Translucent Letters -- Earliest Query Answering for Deterministic Stepwise Hedge Automata -- Constrained Multi-Tildes -- On the smallest synchronizing terms of finite tree automata -- Universal First-Order Quantification over Automata -- Average Complexity of Partial Derivatives for Synchronised Shuffle Expressions -- Sweep complexity revisited -- The Pumping Lemma for Regular Languages is Hard -- M-equivalence of Parikh Matrix over a Ternary Alphabet -- Operational Complexity in Subregular Classes -- When Is Context-Freeness Distinguishable from Regularity? An Extension of Parikh's Theorem -- Enhanced Ternary Fibonacci Codes -- Sweeping Input-Driven Pushdown Automata -- Verified Verifying: SMT-LIB for Strings in Isabelle -- Weighted Bottom-up and Top-down Tree Transformations Are Incomparable -- Deciding whether an Attributed Translation can be realized by a Top-Down Transducer -- A time to cast away stones -- Two-way Machines and de Bruijn Words -- Transduction of Automatic Sequences and Applications -- Measuring Power of Generalised Definite Languages -- Smaller Representation of Compiled Regular Expressions. |
Record Nr. | UNISA-996546854703316 |
Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2023 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Implementation and Application of Automata : 27th International Conference, CIAA 2023, Famagusta, North Cyprus, September 19–22, 2023, Proceedings / / edited by Benedek Nagy |
Edizione | [1st ed. 2023.] |
Pubbl/distr/stampa | Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2023 |
Descrizione fisica | 1 online resource (313 pages) |
Disciplina | 511.3 |
Collana | Lecture Notes in Computer Science |
Soggetto topico |
Computer science
Artificial intelligence Information storage and retrieval systems Algorithms Computer science - Mathematics Discrete mathematics Theory of Computation Computer Science Logic and Foundations of Programming Artificial Intelligence Information Storage and Retrieval Discrete Mathematics in Computer Science |
ISBN | 3-031-40247-2 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto | Finite automata as verifiers -- Binary Coded Unary Regular Languages -- A Survey on Automata with Translucent Letters -- Earliest Query Answering for Deterministic Stepwise Hedge Automata -- Constrained Multi-Tildes -- On the smallest synchronizing terms of finite tree automata -- Universal First-Order Quantification over Automata -- Average Complexity of Partial Derivatives for Synchronised Shuffle Expressions -- Sweep complexity revisited -- The Pumping Lemma for Regular Languages is Hard -- M-equivalence of Parikh Matrix over a Ternary Alphabet -- Operational Complexity in Subregular Classes -- When Is Context-Freeness Distinguishable from Regularity? An Extension of Parikh's Theorem -- Enhanced Ternary Fibonacci Codes -- Sweeping Input-Driven Pushdown Automata -- Verified Verifying: SMT-LIB for Strings in Isabelle -- Weighted Bottom-up and Top-down Tree Transformations Are Incomparable -- Deciding whether an Attributed Translation can be realized by a Top-Down Transducer -- A time to cast away stones -- Two-way Machines and de Bruijn Words -- Transduction of Automatic Sequences and Applications -- Measuring Power of Generalised Definite Languages -- Smaller Representation of Compiled Regular Expressions. |
Record Nr. | UNINA-9910741154203321 |
Cham : , : Springer Nature Switzerland : , : Imprint : Springer, , 2023 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|
Machines, Computations, and Universality [[electronic resource] ] : 7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings / / edited by Jerome Durand-Lose, Benedek Nagy |
Edizione | [1st ed. 2015.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
Descrizione fisica | 1 online resource (XX, 199 p. 41 illus.) |
Disciplina | 004 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science Machine theory Computer science—Mathematics Discrete mathematics Theory of Computation Formal Languages and Automata Theory Computer Science Logic and Foundations of Programming Discrete Mathematics in Computer Science |
ISBN | 3-319-23111-1 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Intro -- Preface -- Organization -- Invited Talks -- Decidability Problems for Self-induced Systems Generated by a Substitution -- Concurrency, Histories, and Nets -- Spiking Neural P Systems: A Class of Parallel Computing Models Inspired by Neurons -- Towards Formal Verification of Computations and Hypercomputations in Relativistic Physics -- Contents -- Invited Papers -- Decidability Problems for Self-induced Systems Generated by a Substitution -- 1 Substitutions Among Mathematics and Computer Science -- 2 The Geometry of One-Dimensional Substitutions -- 3 Undecidability of GIFS Topological Properties -- 4 Decidability of Rauzy Fractals Properties -- 5 Extending the Framework of Rauzy Fractals -- References -- Towards Formal Verification of Computations and Hypercomputations in Relativistic Physics -- 1 Introduction -- 1.1 Geometrical Boosting of Computational Power -- 1.2 Geometrical Reduction of Computational Power -- 1.3 Geometrical Effects on Computational Complexity -- 2 Modelling Relativity Theory in Isabelle/HOL -- 2.1 First-Order Relativity Theory -- 2.2 Generating Verifiable Proofs -- 3 Next Steps -- References -- Regular Papers -- A Connection Between Red-Green Turing Machines and Watson-Crick T0L Systems -- 1 Introduction -- 2 Preliminaries -- 2.1 Red-Green Turing Machines -- 2.2 Watson-Crick L Systems -- 3 Results -- 4 Conclusions -- References -- Tight Bounds for Cut-Operations on Deterministic Finite Automata -- 1 Introduction -- 2 Preliminaries -- 3 The Descriptional Complexity of the Cut Operation -- 4 The Descriptional Complexity of the Iterated-Cut Operation -- 5 Conclusions -- References -- Non-isometric Contextual Array Grammars with Regular Control and Local Selectors -- 1 Introduction -- 2 Definitions -- 3 Isometric Contextual Array Grammars -- 3.1 The Basic Variant -- 3.2 Contextual Array Grammars with Regular Control.
4 Non-isometric Contextual Array Grammars -- 4.1 Non-isometric Contextual Array Grammars with Regular Control -- 4.2 Non-isometric Contextual Array Grammars with Regular Control and Local Selectors -- 5 A Characterization of Linear String Languages -- 6 More-Dimensional Non-isometric Contextual Array Grammars with Regular Control and Local Selectors -- 7 Conclusions -- References -- Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States -- 1 Introduction -- 2 Preliminaries -- 3 Universality Results -- 4 Conclusions -- References -- Tinput-Driven Pushdown Automata -- 1 Introduction -- 2 Preliminaries -- 3 Computational Capacity -- 4 Closure Properties -- 5 Decidability Questions -- 6 Representation Theorems -- 7 Conclusion -- References -- Reversible Limited Automata -- 1 Introduction -- 2 Preliminaries -- 3 Sweeping Reversible k-Limited Automata -- 4 A Hierarchy of Reversible Limited Automata -- 5 Limited Automata and Church-Rosser Languages -- References -- An Intrinsically Universal Family of Causal Graph Dynamics -- 1 Introduction -- 2 Graphs and Localizable Dynamics -- 3 Intrinsic Simulation and Universality -- 4 Preliminary Results -- 5 A Family of Intrinsically Universal Local Rules -- 5.1 Graph Encoding -- 5.2 Local Rule Encoding -- 5.3 Description of an Intrinsically Universal Rule -- 5.4 On the (non) Existence of a Single Universal Rule -- 6 Conclusion -- References -- The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems -- 1 Introduction -- 2 Definitions -- 2.1 Informal Definition of the 2HAM -- 2.2 Definitions for Simulation -- 2.3 Intrinsic Universality -- 3 Uniform Mappings -- 4 Strong Simulation via Uniform Mappings -- 5 Impossibility of Strong Simulation at Higher Temperatures -- 6 Simulating Arbitrary Lower Temperature Ladder Systems -- References. A Characterization of NP Within Interval-Valued Computing -- 1 Introduction -- 1.1 Computing Paradigms -- 1.2 A Brief History of Interval-Valued Computing -- 2 Preliminaries -- 3 Interval-Valued Computations: Definitions -- 4 Results -- 5 Example -- 6 Conclusions, Further Remarks -- References -- Universality in Infinite Petri Nets -- 1 Introduction -- 2 Petri Nets and Linear Cellular Automata -- 3 Simulating Separate Cell -- 4 Simulating Cellular Automaton -- 5 Simulating TMs Which Simulate Rule 110 -- 6 Some Remarks on Universal Constructs -- 7 Conclusions -- References -- Author Index. |
Record Nr. | UNISA-996200366603316 |
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
![]() | ||
Lo trovi qui: Univ. di Salerno | ||
|
Machines, Computations, and Universality : 7th International Conference, MCU 2015, Famagusta, North Cyprus, September 9-11, 2015, Proceedings / / edited by Jerome Durand-Lose, Benedek Nagy |
Edizione | [1st ed. 2015.] |
Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 |
Descrizione fisica | 1 online resource (XX, 199 p. 41 illus.) |
Disciplina | 004 |
Collana | Theoretical Computer Science and General Issues |
Soggetto topico |
Algorithms
Computer science Machine theory Computer science—Mathematics Discrete mathematics Theory of Computation Formal Languages and Automata Theory Computer Science Logic and Foundations of Programming Discrete Mathematics in Computer Science |
ISBN | 3-319-23111-1 |
Formato | Materiale a stampa ![]() |
Livello bibliografico | Monografia |
Lingua di pubblicazione | eng |
Nota di contenuto |
Intro -- Preface -- Organization -- Invited Talks -- Decidability Problems for Self-induced Systems Generated by a Substitution -- Concurrency, Histories, and Nets -- Spiking Neural P Systems: A Class of Parallel Computing Models Inspired by Neurons -- Towards Formal Verification of Computations and Hypercomputations in Relativistic Physics -- Contents -- Invited Papers -- Decidability Problems for Self-induced Systems Generated by a Substitution -- 1 Substitutions Among Mathematics and Computer Science -- 2 The Geometry of One-Dimensional Substitutions -- 3 Undecidability of GIFS Topological Properties -- 4 Decidability of Rauzy Fractals Properties -- 5 Extending the Framework of Rauzy Fractals -- References -- Towards Formal Verification of Computations and Hypercomputations in Relativistic Physics -- 1 Introduction -- 1.1 Geometrical Boosting of Computational Power -- 1.2 Geometrical Reduction of Computational Power -- 1.3 Geometrical Effects on Computational Complexity -- 2 Modelling Relativity Theory in Isabelle/HOL -- 2.1 First-Order Relativity Theory -- 2.2 Generating Verifiable Proofs -- 3 Next Steps -- References -- Regular Papers -- A Connection Between Red-Green Turing Machines and Watson-Crick T0L Systems -- 1 Introduction -- 2 Preliminaries -- 2.1 Red-Green Turing Machines -- 2.2 Watson-Crick L Systems -- 3 Results -- 4 Conclusions -- References -- Tight Bounds for Cut-Operations on Deterministic Finite Automata -- 1 Introduction -- 2 Preliminaries -- 3 The Descriptional Complexity of the Cut Operation -- 4 The Descriptional Complexity of the Iterated-Cut Operation -- 5 Conclusions -- References -- Non-isometric Contextual Array Grammars with Regular Control and Local Selectors -- 1 Introduction -- 2 Definitions -- 3 Isometric Contextual Array Grammars -- 3.1 The Basic Variant -- 3.2 Contextual Array Grammars with Regular Control.
4 Non-isometric Contextual Array Grammars -- 4.1 Non-isometric Contextual Array Grammars with Regular Control -- 4.2 Non-isometric Contextual Array Grammars with Regular Control and Local Selectors -- 5 A Characterization of Linear String Languages -- 6 More-Dimensional Non-isometric Contextual Array Grammars with Regular Control and Local Selectors -- 7 Conclusions -- References -- Universality of Graph-controlled Leftist Insertion-deletion Systems with Two States -- 1 Introduction -- 2 Preliminaries -- 3 Universality Results -- 4 Conclusions -- References -- Tinput-Driven Pushdown Automata -- 1 Introduction -- 2 Preliminaries -- 3 Computational Capacity -- 4 Closure Properties -- 5 Decidability Questions -- 6 Representation Theorems -- 7 Conclusion -- References -- Reversible Limited Automata -- 1 Introduction -- 2 Preliminaries -- 3 Sweeping Reversible k-Limited Automata -- 4 A Hierarchy of Reversible Limited Automata -- 5 Limited Automata and Church-Rosser Languages -- References -- An Intrinsically Universal Family of Causal Graph Dynamics -- 1 Introduction -- 2 Graphs and Localizable Dynamics -- 3 Intrinsic Simulation and Universality -- 4 Preliminary Results -- 5 A Family of Intrinsically Universal Local Rules -- 5.1 Graph Encoding -- 5.2 Local Rule Encoding -- 5.3 Description of an Intrinsically Universal Rule -- 5.4 On the (non) Existence of a Single Universal Rule -- 6 Conclusion -- References -- The Simulation Powers and Limitations of Hierarchical Self-Assembly Systems -- 1 Introduction -- 2 Definitions -- 2.1 Informal Definition of the 2HAM -- 2.2 Definitions for Simulation -- 2.3 Intrinsic Universality -- 3 Uniform Mappings -- 4 Strong Simulation via Uniform Mappings -- 5 Impossibility of Strong Simulation at Higher Temperatures -- 6 Simulating Arbitrary Lower Temperature Ladder Systems -- References. A Characterization of NP Within Interval-Valued Computing -- 1 Introduction -- 1.1 Computing Paradigms -- 1.2 A Brief History of Interval-Valued Computing -- 2 Preliminaries -- 3 Interval-Valued Computations: Definitions -- 4 Results -- 5 Example -- 6 Conclusions, Further Remarks -- References -- Universality in Infinite Petri Nets -- 1 Introduction -- 2 Petri Nets and Linear Cellular Automata -- 3 Simulating Separate Cell -- 4 Simulating Cellular Automaton -- 5 Simulating TMs Which Simulate Rule 110 -- 6 Some Remarks on Universal Constructs -- 7 Conclusions -- References -- Author Index. |
Record Nr. | UNINA-9910484374203321 |
Cham : , : Springer International Publishing : , : Imprint : Springer, , 2015 | ||
![]() | ||
Lo trovi qui: Univ. Federico II | ||
|