Descriptional Complexity of Formal Systems
Springer International Publishing (Verlag)
978-3-319-60251-6 (ISBN)
Sensing as a Complexity Measure.- Avoiding Overlaps in Pictures.- Descriptional Complexity and Operations - Two non-Classical Cases.- Applications of Transducers in Independent Languages, Word Distances, Codes.- On the Degree of Nondeterminism of Tree Adjoining Languages and Head Grammar Languages.- On the Average Complexity of Strong Star Normal Form.- Most Complex Non-Returning Regular Languages.- Uncountable realtime probabilistic classes.- A Parametrized Analysis of Algorithms on Hierarchical Graphs.- Graph-Controlled Insertion-Deletion Systems Generating Language Classes Beyond Linearity.- Computational Completeness of Networks of Evolutionary Processors with Elementary Polarizations and a Small Number of Processors.- Recognizing Union-Find trees built up using union-by-rank strategy is NP-complete.- Self-attraction removal from oritatami systems.- One-Time Nondeterministic Computations.- Kuratowski Algebras Generated by Factor-, Subword-, and Suffix-Free Languages.- Branching Measures and Nearly Acyclic NFAs.- Square on Deterministic, Alternating, and Boolean Finite Automata.- A Pumping Lemma for Ordered Restarting Automata.- Concise Representations of Reversible Automata.- State Complexity of Unary SV-XNFA with Different Acceptance Conditions.- Reset Complexity of Ideal Languages Over a Binary Alphabet.- 2-state 2-symbol Turing machines with periodic support produce regular sets.- State Complexity of Suffix Distance.- The quotient operation on input-driven pushdown automata.
| Erscheinungsdatum | 06.07.2017 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science | Theoretical Computer Science and General Issues |
| Zusatzinfo | X, 311 p. 76 illus. |
| Verlagsort | Cham |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 498 g |
| Themenwelt | Mathematik / Informatik ► Informatik ► Software Entwicklung |
| Informatik ► Theorie / Studium ► Algorithmen | |
| Schlagworte | Algorithm analysis and problem complexity • algorithms • Algorithms & Data Structures • Algorithms & data structures • Automata extensions • Automata Theory • computational completeness • computation by abstract devices • computer architecture & logic design • Computer architecture & logic design • Computer programming / software engineering • Computer Science • context free languages • descriptional complexity • Formal Languages • graph-controlled systems • Information Theory • insertion-deletion systems • language • Logics and meanings of programs • Mathematical logic and formal languages • Mathematical theory of computation • Models of Computation • Operating Systems • quantitative automata • regular languages • Software engineering • Software Engineering/Programming and Operating Sys • State Complexity • syntactic complexity • Theory of Computation • Turing Machines • upper bounds • user interface design & usability • User interface design & usability |
| ISBN-10 | 3-319-60251-9 / 3319602519 |
| ISBN-13 | 978-3-319-60251-6 / 9783319602516 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
