the proceedings contain 51 papers. the topics discussed include: complexity in convex languages;three learnable models for the description of language;arbology: trees and pushdown automata;complexity of the satisfiabi...
ISBN:
(纸本)3642130887
the proceedings contain 51 papers. the topics discussed include: complexity in convex languages;three learnable models for the description of language;arbology: trees and pushdown automata;complexity of the satisfiability problem for a class of propositional schemata;a simple n-dimensional intrinsically universal quantum cellular automaton;a fast longest common subsequence algorithm for similar strings;equivalence and inclusion problem for strongly unambiguous Büchi automata;pregroup grammars with letter promotions;a hierarchical classification of first-order recurrent neural networks;choosing word occurrences for the smallest grammar problem;finding consistent categorial grammars of bounded value: a parameterized approach;operator precedence and the visibly pushdown property;on the maximal number of cubic runs in a string;and simplifying regular expressions: a quantitative perspective.
the proceedings contain 31 papers. the special focus in this conference is on language and automatatheory and applications. the topics include: Boolean monadic recursive schemes as a logical characterization of the s...
ISBN:
(纸本)9783030406073
the proceedings contain 31 papers. the special focus in this conference is on language and automatatheory and applications. the topics include: Boolean monadic recursive schemes as a logical characterization of the subsequential functions;expressiveness and conciseness of timed automata for the verification of stochastic models;Windable heads and recognizing NL with constant randomness;alternating finite automata with limited universal branching;Pebble-intervals automata and FO2 with Two Orders;limited two-way deterministic finite automata with advice;on the size of depth-two threshold circuits for the inner product mod 2 function;complexity issues of string to graph approximate matching;complexity of automatic sequences;context-sensitive fusion grammars are universal;containment and equivalence of weighted automata: Probabilistic and max-plus cases;cyclic shift on multi-component grammars;the automatic baire property and an effective property of ω-Rational Functions;the power of programs over monoids in J;geometrically closed positive varieties of star-free languages;intersection and union hierarchies of deterministic context-free languages and pumping lemmas;on the weisfeiler-leman dimension of fractional packing;input strictly local tree transducers;lyndon words versus inverse lyndon words: Queries on suffixes and bordered words;reducing the ambiguity of parikh matrices;on collapsing prefix normal words;approaching arithmetic theories with finite-state automata;simplified parsing expression derivatives;complete variable-length codes: An excursion into word edit operations;recompression: Technique for word equations and compressed data;how to prove that a language is regular or star-free?;deciding classes of regular languages: the covering approach;is decidable in .
the proceedings contain 33 papers. the special focus in this conference is on language and automatatheory and applications. the topics include: Logic, languages, and rules for web data extraction and reasoning over d...
ISBN:
(纸本)9783319537320
the proceedings contain 33 papers. the special focus in this conference is on language and automatatheory and applications. the topics include: Logic, languages, and rules for web data extraction and reasoning over data;a stable non-interleaving early operational semantics for the pi-calculus;efficient learning of tier-based strictly k-local languages;the strong, weak, and very weak finite context and kernel properties;an automata view to goal-directed methods;a calculus of cyber-physical systems;efficient pattern matching in elastic-degenerate texts;integrated encryption in dynamic arithmetic compression;two-dimensional palindromes and their properties;on the complexity of hard enumeration problems;consensus string problem for multiple regular languages;the weight in enumeration;derivatives and finite automata of expressions in star normal form;finding DFAs with maximal shortest synchronizing word length;linear parsing expression grammars;on finite-index indexed grammars and their restrictions;a derivational model of discontinuous parsing;cut languages in rational bases;a way to compact Petri nets’ behaviors uniformly;partitioning graphs into induced subgraphs;space complexity of reachability testing in labelled graphs;most general property-preserving updates;cellular automata with majority-rule;on the computational power of affine automata;detecting useless transitions in pushdown automata;hardness results for coverability problem of well-structured pushdown systems and reachability analysis of pushdown systems with an upper stack.
the proceedings contain 49 papers. the topics discussed include: computing optimal reachability costs in priced dense-timed pushdown automata;formulae for polyominoes on twisted cylinders;picture codes with finite dec...
ISBN:
(纸本)9783319049205
the proceedings contain 49 papers. the topics discussed include: computing optimal reachability costs in priced dense-timed pushdown automata;formulae for polyominoes on twisted cylinders;picture codes with finite deciphering delay;networks of polarized evolutionary processors are computationally complete;two double-exponential gaps for automata with a limited pushdown;efficient list-based computation of the string subsequence kernel;characterisation of the state spaces of live and bounded marked graph Petri nets;computing depths of patterns;solving equations on words with morphisms and antimorphisms;shift-reduce parsers for transition networks;satisfiability for MTL and TPTL over non-monotonic data words;(k,l)-unambiguity and quasi-deterministic structures: an alternative for the determinization;solutions to the multi-dimensional equal powers problem constructed by composition of rectangular morphisms;and extremal combinatorics of reaction systems.
the proceedings contain 34 papers. the special focus in this conference is on language and automatatheory and applications. the topics include: Equivalence Checking of Prefix-Free Transducers and Deterministic Two-Ta...
ISBN:
(纸本)9783030134341
the proceedings contain 34 papers. the special focus in this conference is on language and automatatheory and applications. the topics include: Equivalence Checking of Prefix-Free Transducers and Deterministic Two-Tape automata;Efficient Symmetry Breaking for SAT-Based Minimum DFA Inference;closure and Nonclosure Properties of the Compressible and Rankable Sets;the Range of State Complexities of languages Resulting from the Cut Operation;state Complexity of Pseudocatenation;complexity of Regex Crosswords;generalized Predictive Shift-Reduce Parsing for Hyperedge Replacement Graph Grammars;transformation of Petri Nets into Context-Dependent Fusion Grammars;generalized Register Context-Free Grammars;observation and Interaction: Invited Paper;logic and Rational languages of Scattered and Countable Series-Parallel Posets;toroidal Codes and Conjugate Pictures;geometrical Closure of Binary V3/2 languages;deterministic Biautomata and Subclasses of Deterministic Linear languages;learning Unions of k-Testable languages;regular Matching and Inclusion on Compressed Tree Patterns with Context Variables;rule-Based Unification in Combined theories and the Finite Variant Property;extensions of the Caucal Hierarchy?;tight Bounds on the Minimum Size of a Dynamic Monopoly;recurrence in Multidimensional Words;from Words to Graphs, and Back;a Note with Computer Exploration on the Triangle Conjecture;efficient Representation and Counting of Antipower Factors in Words;on the Maximum Number of Distinct Palindromic Sub-arrays;syntactic View of Sigma-Tau Generation of Permutations;palindromic Subsequences in Finite Words;an Oracle Hierarchy for Small One-Way Finite automata;orbits of Abelian Automaton Groups;Bounded automata Groups are co-ET0L;decidability of Sensitivity and Equicontinuity for Linear Higher-Order Cellular automata;on Varieties of Ordered automata.
the proceedings contain 46 papers. the special focus in this conference is on automata and Logic. the topics include: Non-zero sum games for reactive synthesis;tangles and connectivity in graphs;restricted turing mach...
ISBN:
(纸本)9783319299990
the proceedings contain 46 papers. the special focus in this conference is on automata and Logic. the topics include: Non-zero sum games for reactive synthesis;tangles and connectivity in graphs;restricted turing machines and language recognition;automata for ontologies;a logical characterization for dense-time visibly pushdown automata;a complexity measure on buchi automata;compositional bisimulation minimization for interval Markov decision processes;a weighted MSO logic with storage behaviour and its Buchi-Elgot-Trakhtenbrot theorem;colored nested words;input-driven queue automata with internal transductions;periodic generalized automata over the reals;minimal separating sequences for all pairs of states;forkable regular expressions;on the Levenshtein automaton and the size of the neighbourhood of a word;parallelogram morphisms and circular codes;on del-robust primitive partial words with one hole;on XOR lemma for polynomial threshold weight and length;walking and searching from an inner point of a line;using duality in circuit complexity;the minimum entropy submodular set cover problem;on the capacity of capacitated automata;on limited nondeterminism and ACC circuit lower bounds;the complexity of induced tree reconfiguration problems;the missing case in Chomsky-Schutzenberger theorem;homomorphic characterizations of indexed languages;steganography based on pattern languages;inferring a relax NG schema from XML documents;noise free multi-armed bandit game;properties of regular DAG languages;normal form on linear tree-to-word transducers;a kleene theorem for weighted tree automata over tree valuation monoids and hankel matrices for weighted visibly pushdown automata.
the proceedings contain 67 papers. the special focus in this conference is on Algorithms, automata, Logic, Concurrency, Codes, Semigroups, and Symbolic Dynamics. the topics include: Automated synthesis of application-...
ISBN:
(纸本)9783319155784
the proceedings contain 67 papers. the special focus in this conference is on Algorithms, automata, Logic, Concurrency, Codes, Semigroups, and Symbolic Dynamics. the topics include: Automated synthesis of application-layer connectors from automata-based specifications;average-case optimal approximate circular string matching;an efficient best-trees algorithm for weighted tree automata over the tropical semiring;construction of a de bruijn graph for assembly from a truncated suffix tree;a parallel algorithm for finding all minimal maximum subsequences via random walk;complexity of road coloring with prescribed reset words;logics for unordered trees with data constraints on siblings;insertion operations on deterministic reversal-bounded counter machines;on observability of automata networks via computational algebra;derivatives for regular shuffle expressions;quotient of acceptance specifications under reachability constraints;structure and measure of a decidable class of two-dimensional codes;preset distinguishing sequences and diameter of transformation semigroups;on the number of closed factors in a word;on the language of primitive partial words;a nonuniform circuit class with multilayer of threshold gates having super quasi polynomial size lower bounds against NEXP;parameterized enumeration for modification problems;compressed data structures for range searching;bfs-based symmetry breaking predicates for DFA identification;learning conjunctive grammars and contextual binary feature grammars;towards more precise rewriting approximations;order structures for subclasses of generalised traces;a nivat theorem for weighted picture automata and weighted MSO logic and a hierarchy of transducing observer systems.
this special issue of the journal Information and Computation contains extended versions of some of the best papers presented at the 8thinternationalconference on language and automatatheory and applications (LATA ...
详细信息
this special issue of the journal Information and Computation contains extended versions of some of the best papers presented at the 8thinternationalconference on language and automatatheory and applications (LATA 2014), held in Madrid, Spain, on March 10–14, 2014. In the paper Picture Codes and Deciphering Delay by Marcella Anselmo, Dora Giammarresi, and Maria Madonia, the authors are interested in the theory of variable length codes. they extend the concept of finite deciphering delay to pictures in two dimensions and they prove that a set of pictures with finite deciphering delay is a code. Fernando Arroyo, Sandra GoÁmez Canaval, Victor Mitrana, and Stefan Popescu introduce a new variant of networks of evolutionary processors in their paper On the Computational Power of Networks of Polarized Evolutionary Processors. Whereas in the literature the communication of the processors is controlled by filters attached to the processors or to the channels between them, here the communication is regulated by the compatibility between the polarization of words and nodes. In the paper Two Double-Exponential Gaps for automata with a Limited Pushdown, the authors Zuzana BednaÁrovaÁ and Viliam Geffert present a variant of pushdown automata with a stack height bounded by a constant that recognize only regular languages but can be more succinct than finite automata. the paper On the List Update Problem with Advice by Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro LoÁpez-Ortiz considers the list accessing problem in the model of online computations with advice. the authors investigate a well-known class of online algorithms and give tight upper and lower bounds on the competitive ratio of these algorithms, thus clarifying the picture since some false claims have been around in the literature. In the paper CNF and DNF Succinct Graph Encodings by Bireswar Das, Patrick Scharpfenecker, and Jacobo Tora Án, the authors investigate the effect of different kinds of succinct en
暂无评论