Automaticity. I: Properties of a measure of descriptional complexity
From MaRDI portal
Publication:1816738
DOI10.1006/jcss.1996.0046zbMath0859.68059OpenAlexW1969367179MaRDI QIDQ1816738
Yuri Breitbart, Jeffrey O. Shallit
Publication date: 13 March 1997
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.1996.0046
Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Formal languages and automata (68Q45) Automata sequences (11B85)
Related Items
Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds., Hartmanis-Stearns Conjecture on Real Time and Transcendence, Generalising automaticity to modal properties of finite structures, Regular Growth Automata: Properties of a Class of Finitely Induced Infinite Machines, STATE-SIZE HIERARCHY FOR FINITE-STATE COMPLEXITY, On a conjecture of J. Shallit, Automaticity. II: Descriptional complexity in the unary case, Algorithmic introduction of quantified cuts, Learning finite cover automata from queries, Finite Automata, Palindromes, Powers, and Patterns, Approximate Automata for Omega-Regular Languages, On the existence of regular approximations, Automaticity. IV: Sequences, sets, and diversity, Succinct representations of languages by DFA with different levels of reliability, Finite state complexity, Minimal cover-automata for finite languages, Remarks on Separating Words, The binomial equivalence classes of finite words, Enumerating regular expressions and their languages, Detecting palindromes, patterns and borders in regular languages, Compressibility of Finite Languages by Grammars
