Streaming transducers for algorithmic verification of single-pass list-processing programs

DOI10.1145/1926385.1926454zbMath1284.68159arXiv1007.4958OpenAlexW4251691259MaRDI QIDQ5408580

Pavol Černý, Rajeev Alur

Publication date: 10 April 2014

Published in: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.4958

zbMATH Keywords

transducerslistsalgorithmic software verification

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items

Bidirectional Runtime Enforcement of First-Order Branching-Time Properties, Semantic Foundations for Deterministic Dataflow and Stream Processing, Efficient Equivalence Checking Technique for Some Classes of Finite-State Machines, On the Model Checking Problem for Some Extension of CTL*, Equivalence Checking Problem for Finite State Transducers over Semigroups, On first-order runtime enforcement of branching-time properties, Complexity of regular functions, Unnamed Item, An automata-theoretic approach to the verification of distributed algorithms, Simple linear string constraints, Copyless cost-register automata: structure, expressiveness, and closure properties, Nondeterministic Streaming String Transducers, Better complexity bounds for cost register automata, Unnamed Item, Unnamed Item, Unnamed Item, Streamable regular transductions, Regular Programming for Quantitative Properties of Data Streams, Streaming ranked-tree-to-string transducers, Regular Transformations of Data Words Through Origin Information, Shortest Paths in One-Counter Systems, Extended symbolic finite automata and transducers, Copyful Streaming String Transducers, Better complexity bounds for cost register automata, Non-deterministic transducer models of retransmission protocols over noisy channels, On bidirectional runtime enforcement, Pattern eliminating transformations