java -Xmx6000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data ./data --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -tc ../../../trunk/examples/toolchains/AutomizerC.xml -s ../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf -i ../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i -------------------------------------------------------------------------------- This is Ultimate 0.1.23-1cceb4a [2018-01-29 22:37:01,943 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-01-29 22:37:01,944 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-01-29 22:37:01,959 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-01-29 22:37:01,959 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-01-29 22:37:01,960 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-01-29 22:37:01,961 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-01-29 22:37:01,962 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-01-29 22:37:01,964 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-01-29 22:37:01,965 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-01-29 22:37:01,966 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-01-29 22:37:01,966 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-01-29 22:37:01,967 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-01-29 22:37:01,968 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-01-29 22:37:01,969 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-01-29 22:37:01,972 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-01-29 22:37:01,974 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-01-29 22:37:01,976 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-01-29 22:37:01,977 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-01-29 22:37:01,978 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-01-29 22:37:01,980 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-01-29 22:37:01,981 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-01-29 22:37:01,981 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-01-29 22:37:01,982 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-01-29 22:37:01,983 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-01-29 22:37:01,984 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-01-29 22:37:01,984 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-01-29 22:37:01,985 INFO L177 SettingsManager]: PEA to Boogie provides no preferences, ignoring... [2018-01-29 22:37:01,985 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-01-29 22:37:01,985 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-01-29 22:37:01,986 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-01-29 22:37:01,986 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/ai/eq-bench/svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf [2018-01-29 22:37:01,994 INFO L110 SettingsManager]: Loading preferences was successful [2018-01-29 22:37:01,994 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-01-29 22:37:01,995 INFO L131 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2018-01-29 22:37:01,995 INFO L133 SettingsManager]: * to procedures, called more than once=true [2018-01-29 22:37:01,995 INFO L131 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2018-01-29 22:37:01,996 INFO L133 SettingsManager]: * Abstract domain for RCFG-of-the-future=VPDomain [2018-01-29 22:37:01,996 INFO L133 SettingsManager]: * Use the RCFG-of-the-future interface=true [2018-01-29 22:37:01,996 INFO L131 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2018-01-29 22:37:01,996 INFO L133 SettingsManager]: * sizeof long=4 [2018-01-29 22:37:01,996 INFO L133 SettingsManager]: * Check unreachability of error function in SV-COMP mode=false [2018-01-29 22:37:01,996 INFO L133 SettingsManager]: * Overapproximate operations on floating types=true [2018-01-29 22:37:01,997 INFO L133 SettingsManager]: * sizeof POINTER=4 [2018-01-29 22:37:01,997 INFO L133 SettingsManager]: * Check division by zero=IGNORE [2018-01-29 22:37:01,997 INFO L133 SettingsManager]: * Check for the main procedure if all allocated memory was freed=true [2018-01-29 22:37:01,997 INFO L133 SettingsManager]: * Bitprecise bitfields=true [2018-01-29 22:37:01,997 INFO L133 SettingsManager]: * SV-COMP memtrack compatibility mode=true [2018-01-29 22:37:01,997 INFO L133 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2018-01-29 22:37:01,997 INFO L133 SettingsManager]: * sizeof long double=12 [2018-01-29 22:37:01,998 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-01-29 22:37:01,998 INFO L133 SettingsManager]: * Size of a code block=SingleStatement [2018-01-29 22:37:01,998 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-01-29 22:37:01,998 INFO L133 SettingsManager]: * Add additional assume for each assert=false [2018-01-29 22:37:01,998 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-01-29 22:37:01,998 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-29 22:37:01,999 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-01-29 22:37:01,999 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-01-29 22:37:01,999 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-01-29 22:37:01,999 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-01-29 22:37:01,999 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-01-29 22:37:01,999 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-01-29 22:37:01,999 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-01-29 22:37:02,000 INFO L133 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2018-01-29 22:37:02,000 INFO L131 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2018-01-29 22:37:02,000 INFO L133 SettingsManager]: * TransformationType=HEAP_SEPARATOR [2018-01-29 22:37:02,032 INFO L81 nceAwareModelManager]: Repository-Root is: /tmp [2018-01-29 22:37:02,042 INFO L266 ainManager$Toolchain]: [Toolchain 1]: Parser(s) successfully initialized [2018-01-29 22:37:02,045 INFO L222 ainManager$Toolchain]: [Toolchain 1]: Toolchain data selected. [2018-01-29 22:37:02,046 INFO L271 PluginConnector]: Initializing CDTParser... [2018-01-29 22:37:02,046 INFO L276 PluginConnector]: CDTParser initialized [2018-01-29 22:37:02,047 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/array-memsafety/cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-29 22:37:02,192 INFO L304 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2018-01-29 22:37:02,199 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2018-01-29 22:37:02,200 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2018-01-29 22:37:02,200 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2018-01-29 22:37:02,207 INFO L276 PluginConnector]: CACSL2BoogieTranslator initialized [2018-01-29 22:37:02,208 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,211 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@51fea89f and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02, skipping insertion in model container [2018-01-29 22:37:02,212 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,226 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-29 22:37:02,263 INFO L153 Dispatcher]: Using SV-COMP mode [2018-01-29 22:37:02,381 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-29 22:37:02,397 INFO L450 PostProcessor]: Settings: Checked method=main [2018-01-29 22:37:02,404 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02 WrapperNode [2018-01-29 22:37:02,404 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2018-01-29 22:37:02,405 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2018-01-29 22:37:02,405 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2018-01-29 22:37:02,405 INFO L276 PluginConnector]: Boogie Preprocessor initialized [2018-01-29 22:37:02,421 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,421 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,432 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,433 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,437 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,440 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,441 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... [2018-01-29 22:37:02,443 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2018-01-29 22:37:02,443 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2018-01-29 22:37:02,443 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2018-01-29 22:37:02,443 INFO L276 PluginConnector]: RCFGBuilder initialized [2018-01-29 22:37:02,444 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-01-29 22:37:02,487 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2018-01-29 22:37:02,488 INFO L136 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2018-01-29 22:37:02,488 INFO L136 BoogieDeclarations]: Found implementation of procedure cstrncat [2018-01-29 22:37:02,488 INFO L136 BoogieDeclarations]: Found implementation of procedure main [2018-01-29 22:37:02,488 INFO L128 BoogieDeclarations]: Found specification of procedure write~int [2018-01-29 22:37:02,488 INFO L128 BoogieDeclarations]: Found specification of procedure read~int [2018-01-29 22:37:02,488 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.free [2018-01-29 22:37:02,488 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2018-01-29 22:37:02,488 INFO L128 BoogieDeclarations]: Found specification of procedure #Ultimate.alloc [2018-01-29 22:37:02,489 INFO L128 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2018-01-29 22:37:02,489 INFO L128 BoogieDeclarations]: Found specification of procedure cstrncat [2018-01-29 22:37:02,489 INFO L128 BoogieDeclarations]: Found specification of procedure main [2018-01-29 22:37:02,489 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2018-01-29 22:37:02,489 INFO L128 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2018-01-29 22:37:02,764 INFO L257 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2018-01-29 22:37:02,765 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.01 10:37:02 BoogieIcfgContainer [2018-01-29 22:37:02,765 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2018-01-29 22:37:02,766 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2018-01-29 22:37:02,766 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2018-01-29 22:37:02,769 INFO L276 PluginConnector]: TraceAbstraction initialized [2018-01-29 22:37:02,769 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 29.01 10:37:02" (1/3) ... [2018-01-29 22:37:02,770 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@295046da and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.01 10:37:02, skipping insertion in model container [2018-01-29 22:37:02,770 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 29.01 10:37:02" (2/3) ... [2018-01-29 22:37:02,770 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@295046da and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 29.01 10:37:02, skipping insertion in model container [2018-01-29 22:37:02,770 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 29.01 10:37:02" (3/3) ... [2018-01-29 22:37:02,772 INFO L107 eAbstractionObserver]: Analyzing ICFG cstrncat-alloca_true-valid-memsafety_true-termination.i [2018-01-29 22:37:02,780 INFO L128 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-01-29 22:37:02,787 INFO L140 ceAbstractionStarter]: Appying trace abstraction to program that has 15 error locations. [2018-01-29 22:37:02,826 INFO L322 AbstractCegarLoop]: Interprodecural is true [2018-01-29 22:37:02,826 INFO L323 AbstractCegarLoop]: Hoare is true [2018-01-29 22:37:02,826 INFO L324 AbstractCegarLoop]: Compute interpolants for FPandBP [2018-01-29 22:37:02,826 INFO L325 AbstractCegarLoop]: Backedges is TWOTRACK [2018-01-29 22:37:02,827 INFO L326 AbstractCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2018-01-29 22:37:02,827 INFO L327 AbstractCegarLoop]: Difference is false [2018-01-29 22:37:02,827 INFO L328 AbstractCegarLoop]: Minimize is MINIMIZE_SEVPA [2018-01-29 22:37:02,827 INFO L333 AbstractCegarLoop]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-01-29 22:37:02,828 INFO L87 2NestedWordAutomaton]: Mode: main mode - execution starts in main procedure [2018-01-29 22:37:02,849 INFO L276 IsEmpty]: Start isEmpty. Operand 96 states. [2018-01-29 22:37:02,856 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 22 [2018-01-29 22:37:02,856 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:02,857 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:02,857 INFO L371 AbstractCegarLoop]: === Iteration 1 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:02,863 INFO L82 PathProgramCache]: Analyzing trace with hash 533934611, now seen corresponding path program 1 times [2018-01-29 22:37:02,865 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:02,865 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:02,908 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:02,908 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:02,908 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:02,955 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:02,963 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:03,024 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:03,027 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:03,028 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2018-01-29 22:37:03,030 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-29 22:37:03,041 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-29 22:37:03,042 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-29 22:37:03,044 INFO L87 Difference]: Start difference. First operand 96 states. Second operand 3 states. [2018-01-29 22:37:03,195 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:03,196 INFO L93 Difference]: Finished difference Result 145 states and 158 transitions. [2018-01-29 22:37:03,196 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-29 22:37:03,197 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 21 [2018-01-29 22:37:03,197 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:03,208 INFO L225 Difference]: With dead ends: 145 [2018-01-29 22:37:03,209 INFO L226 Difference]: Without dead ends: 92 [2018-01-29 22:37:03,212 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-29 22:37:03,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 92 states. [2018-01-29 22:37:03,243 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 92 to 92. [2018-01-29 22:37:03,244 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 92 states. [2018-01-29 22:37:03,246 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 92 states to 92 states and 98 transitions. [2018-01-29 22:37:03,248 INFO L78 Accepts]: Start accepts. Automaton has 92 states and 98 transitions. Word has length 21 [2018-01-29 22:37:03,248 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:03,248 INFO L432 AbstractCegarLoop]: Abstraction has 92 states and 98 transitions. [2018-01-29 22:37:03,248 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-29 22:37:03,248 INFO L276 IsEmpty]: Start isEmpty. Operand 92 states and 98 transitions. [2018-01-29 22:37:03,249 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-29 22:37:03,249 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:03,249 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:03,249 INFO L371 AbstractCegarLoop]: === Iteration 2 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:03,250 INFO L82 PathProgramCache]: Analyzing trace with hash -2054226453, now seen corresponding path program 1 times [2018-01-29 22:37:03,250 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:03,250 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:03,251 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,251 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:03,251 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:03,275 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:03,341 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:03,341 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:03,341 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-29 22:37:03,343 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-29 22:37:03,343 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-29 22:37:03,343 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-29 22:37:03,344 INFO L87 Difference]: Start difference. First operand 92 states and 98 transitions. Second operand 4 states. [2018-01-29 22:37:03,435 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:03,436 INFO L93 Difference]: Finished difference Result 92 states and 98 transitions. [2018-01-29 22:37:03,436 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-29 22:37:03,436 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 24 [2018-01-29 22:37:03,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:03,438 INFO L225 Difference]: With dead ends: 92 [2018-01-29 22:37:03,438 INFO L226 Difference]: Without dead ends: 91 [2018-01-29 22:37:03,439 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-29 22:37:03,439 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states. [2018-01-29 22:37:03,446 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 91. [2018-01-29 22:37:03,446 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 91 states. [2018-01-29 22:37:03,448 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 91 states to 91 states and 97 transitions. [2018-01-29 22:37:03,449 INFO L78 Accepts]: Start accepts. Automaton has 91 states and 97 transitions. Word has length 24 [2018-01-29 22:37:03,449 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:03,449 INFO L432 AbstractCegarLoop]: Abstraction has 91 states and 97 transitions. [2018-01-29 22:37:03,449 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-29 22:37:03,449 INFO L276 IsEmpty]: Start isEmpty. Operand 91 states and 97 transitions. [2018-01-29 22:37:03,450 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2018-01-29 22:37:03,450 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:03,450 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:03,451 INFO L371 AbstractCegarLoop]: === Iteration 3 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:03,451 INFO L82 PathProgramCache]: Analyzing trace with hash -2054226452, now seen corresponding path program 1 times [2018-01-29 22:37:03,451 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:03,451 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:03,452 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,452 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:03,452 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,472 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:03,473 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:03,666 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:03,667 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:03,667 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2018-01-29 22:37:03,667 INFO L409 AbstractCegarLoop]: Interpolant automaton has 8 states [2018-01-29 22:37:03,668 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2018-01-29 22:37:03,668 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=38, Unknown=0, NotChecked=0, Total=56 [2018-01-29 22:37:03,668 INFO L87 Difference]: Start difference. First operand 91 states and 97 transitions. Second operand 8 states. [2018-01-29 22:37:03,791 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:03,792 INFO L93 Difference]: Finished difference Result 91 states and 97 transitions. [2018-01-29 22:37:03,792 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-29 22:37:03,792 INFO L78 Accepts]: Start accepts. Automaton has 8 states. Word has length 24 [2018-01-29 22:37:03,792 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:03,793 INFO L225 Difference]: With dead ends: 91 [2018-01-29 22:37:03,793 INFO L226 Difference]: Without dead ends: 90 [2018-01-29 22:37:03,793 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 10 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=48, Invalid=84, Unknown=0, NotChecked=0, Total=132 [2018-01-29 22:37:03,794 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states. [2018-01-29 22:37:03,798 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 90. [2018-01-29 22:37:03,798 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 90 states. [2018-01-29 22:37:03,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 90 states to 90 states and 96 transitions. [2018-01-29 22:37:03,800 INFO L78 Accepts]: Start accepts. Automaton has 90 states and 96 transitions. Word has length 24 [2018-01-29 22:37:03,800 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:03,800 INFO L432 AbstractCegarLoop]: Abstraction has 90 states and 96 transitions. [2018-01-29 22:37:03,800 INFO L433 AbstractCegarLoop]: Interpolant automaton has 8 states. [2018-01-29 22:37:03,800 INFO L276 IsEmpty]: Start isEmpty. Operand 90 states and 96 transitions. [2018-01-29 22:37:03,801 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-29 22:37:03,801 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:03,801 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:03,801 INFO L371 AbstractCegarLoop]: === Iteration 4 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:03,802 INFO L82 PathProgramCache]: Analyzing trace with hash 743489415, now seen corresponding path program 1 times [2018-01-29 22:37:03,802 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:03,802 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:03,803 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,803 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:03,803 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,816 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:03,817 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:03,849 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:03,850 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:03,850 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-29 22:37:03,850 INFO L409 AbstractCegarLoop]: Interpolant automaton has 4 states [2018-01-29 22:37:03,850 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2018-01-29 22:37:03,850 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2018-01-29 22:37:03,851 INFO L87 Difference]: Start difference. First operand 90 states and 96 transitions. Second operand 4 states. [2018-01-29 22:37:03,906 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:03,906 INFO L93 Difference]: Finished difference Result 90 states and 96 transitions. [2018-01-29 22:37:03,907 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-01-29 22:37:03,907 INFO L78 Accepts]: Start accepts. Automaton has 4 states. Word has length 25 [2018-01-29 22:37:03,907 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:03,908 INFO L225 Difference]: With dead ends: 90 [2018-01-29 22:37:03,908 INFO L226 Difference]: Without dead ends: 89 [2018-01-29 22:37:03,909 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-29 22:37:03,909 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 89 states. [2018-01-29 22:37:03,914 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 89 to 89. [2018-01-29 22:37:03,914 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 89 states. [2018-01-29 22:37:03,915 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 89 states to 89 states and 95 transitions. [2018-01-29 22:37:03,915 INFO L78 Accepts]: Start accepts. Automaton has 89 states and 95 transitions. Word has length 25 [2018-01-29 22:37:03,916 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:03,916 INFO L432 AbstractCegarLoop]: Abstraction has 89 states and 95 transitions. [2018-01-29 22:37:03,916 INFO L433 AbstractCegarLoop]: Interpolant automaton has 4 states. [2018-01-29 22:37:03,916 INFO L276 IsEmpty]: Start isEmpty. Operand 89 states and 95 transitions. [2018-01-29 22:37:03,916 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2018-01-29 22:37:03,917 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:03,917 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:03,917 INFO L371 AbstractCegarLoop]: === Iteration 5 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:03,917 INFO L82 PathProgramCache]: Analyzing trace with hash 743489416, now seen corresponding path program 1 times [2018-01-29 22:37:03,917 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:03,917 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:03,918 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,918 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:03,919 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:03,932 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:03,933 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:04,012 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:04,012 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:04,013 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2018-01-29 22:37:04,013 INFO L409 AbstractCegarLoop]: Interpolant automaton has 5 states [2018-01-29 22:37:04,013 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2018-01-29 22:37:04,013 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-01-29 22:37:04,013 INFO L87 Difference]: Start difference. First operand 89 states and 95 transitions. Second operand 5 states. [2018-01-29 22:37:04,075 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:04,075 INFO L93 Difference]: Finished difference Result 89 states and 95 transitions. [2018-01-29 22:37:04,076 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-29 22:37:04,076 INFO L78 Accepts]: Start accepts. Automaton has 5 states. Word has length 25 [2018-01-29 22:37:04,076 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:04,077 INFO L225 Difference]: With dead ends: 89 [2018-01-29 22:37:04,077 INFO L226 Difference]: Without dead ends: 88 [2018-01-29 22:37:04,078 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-01-29 22:37:04,078 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 88 states. [2018-01-29 22:37:04,083 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 88 to 88. [2018-01-29 22:37:04,083 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 88 states. [2018-01-29 22:37:04,085 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 88 states to 88 states and 94 transitions. [2018-01-29 22:37:04,085 INFO L78 Accepts]: Start accepts. Automaton has 88 states and 94 transitions. Word has length 25 [2018-01-29 22:37:04,085 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:04,085 INFO L432 AbstractCegarLoop]: Abstraction has 88 states and 94 transitions. [2018-01-29 22:37:04,085 INFO L433 AbstractCegarLoop]: Interpolant automaton has 5 states. [2018-01-29 22:37:04,086 INFO L276 IsEmpty]: Start isEmpty. Operand 88 states and 94 transitions. [2018-01-29 22:37:04,086 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-29 22:37:04,086 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:04,087 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:04,087 INFO L371 AbstractCegarLoop]: === Iteration 6 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:04,087 INFO L82 PathProgramCache]: Analyzing trace with hash 441118832, now seen corresponding path program 1 times [2018-01-29 22:37:04,087 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:04,087 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:04,088 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:04,088 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:04,088 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:04,103 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:04,104 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:04,150 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:04,150 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:04,151 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-29 22:37:04,151 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-29 22:37:04,151 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-29 22:37:04,151 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-29 22:37:04,151 INFO L87 Difference]: Start difference. First operand 88 states and 94 transitions. Second operand 6 states. [2018-01-29 22:37:04,281 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:04,281 INFO L93 Difference]: Finished difference Result 118 states and 126 transitions. [2018-01-29 22:37:04,281 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-29 22:37:04,281 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 32 [2018-01-29 22:37:04,282 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:04,283 INFO L225 Difference]: With dead ends: 118 [2018-01-29 22:37:04,283 INFO L226 Difference]: Without dead ends: 114 [2018-01-29 22:37:04,283 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-01-29 22:37:04,284 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 114 states. [2018-01-29 22:37:04,291 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 114 to 101. [2018-01-29 22:37:04,292 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 101 states. [2018-01-29 22:37:04,293 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 114 transitions. [2018-01-29 22:37:04,293 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 114 transitions. Word has length 32 [2018-01-29 22:37:04,293 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:04,294 INFO L432 AbstractCegarLoop]: Abstraction has 101 states and 114 transitions. [2018-01-29 22:37:04,294 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-29 22:37:04,294 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 114 transitions. [2018-01-29 22:37:04,295 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2018-01-29 22:37:04,295 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:04,295 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:04,295 INFO L371 AbstractCegarLoop]: === Iteration 7 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:04,295 INFO L82 PathProgramCache]: Analyzing trace with hash 441118833, now seen corresponding path program 1 times [2018-01-29 22:37:04,296 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:04,296 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:04,296 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:04,297 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:04,297 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:04,310 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:04,311 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:04,475 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:04,476 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:04,476 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [9] imperfect sequences [] total 9 [2018-01-29 22:37:04,476 INFO L409 AbstractCegarLoop]: Interpolant automaton has 10 states [2018-01-29 22:37:04,477 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2018-01-29 22:37:04,477 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=19, Invalid=71, Unknown=0, NotChecked=0, Total=90 [2018-01-29 22:37:04,477 INFO L87 Difference]: Start difference. First operand 101 states and 114 transitions. Second operand 10 states. [2018-01-29 22:37:04,742 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:04,742 INFO L93 Difference]: Finished difference Result 140 states and 156 transitions. [2018-01-29 22:37:04,742 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-01-29 22:37:04,742 INFO L78 Accepts]: Start accepts. Automaton has 10 states. Word has length 32 [2018-01-29 22:37:04,743 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:04,746 INFO L225 Difference]: With dead ends: 140 [2018-01-29 22:37:04,746 INFO L226 Difference]: Without dead ends: 136 [2018-01-29 22:37:04,747 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 25 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2018-01-29 22:37:04,747 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2018-01-29 22:37:04,755 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 119. [2018-01-29 22:37:04,755 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 119 states. [2018-01-29 22:37:04,757 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 119 states to 119 states and 137 transitions. [2018-01-29 22:37:04,757 INFO L78 Accepts]: Start accepts. Automaton has 119 states and 137 transitions. Word has length 32 [2018-01-29 22:37:04,757 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:04,757 INFO L432 AbstractCegarLoop]: Abstraction has 119 states and 137 transitions. [2018-01-29 22:37:04,758 INFO L433 AbstractCegarLoop]: Interpolant automaton has 10 states. [2018-01-29 22:37:04,758 INFO L276 IsEmpty]: Start isEmpty. Operand 119 states and 137 transitions. [2018-01-29 22:37:04,759 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-29 22:37:04,759 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:04,759 INFO L350 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:04,760 INFO L371 AbstractCegarLoop]: === Iteration 8 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:04,760 INFO L82 PathProgramCache]: Analyzing trace with hash 906112675, now seen corresponding path program 1 times [2018-01-29 22:37:04,760 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:04,760 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:04,761 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:04,761 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:04,761 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:04,774 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:04,775 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:04,825 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2018-01-29 22:37:04,825 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:04,825 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-29 22:37:04,826 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-29 22:37:04,826 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-29 22:37:04,826 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-29 22:37:04,826 INFO L87 Difference]: Start difference. First operand 119 states and 137 transitions. Second operand 7 states. [2018-01-29 22:37:05,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:05,006 INFO L93 Difference]: Finished difference Result 131 states and 145 transitions. [2018-01-29 22:37:05,006 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-29 22:37:05,007 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 39 [2018-01-29 22:37:05,007 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:05,008 INFO L225 Difference]: With dead ends: 131 [2018-01-29 22:37:05,008 INFO L226 Difference]: Without dead ends: 130 [2018-01-29 22:37:05,009 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-01-29 22:37:05,009 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2018-01-29 22:37:05,016 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 118. [2018-01-29 22:37:05,016 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 118 states. [2018-01-29 22:37:05,017 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 136 transitions. [2018-01-29 22:37:05,017 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 136 transitions. Word has length 39 [2018-01-29 22:37:05,018 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:05,018 INFO L432 AbstractCegarLoop]: Abstraction has 118 states and 136 transitions. [2018-01-29 22:37:05,018 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-29 22:37:05,018 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 136 transitions. [2018-01-29 22:37:05,018 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2018-01-29 22:37:05,019 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:05,019 INFO L350 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:05,019 INFO L371 AbstractCegarLoop]: === Iteration 9 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:05,019 INFO L82 PathProgramCache]: Analyzing trace with hash 906112676, now seen corresponding path program 1 times [2018-01-29 22:37:05,019 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:05,019 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:05,020 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:05,020 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:05,020 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:05,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:05,033 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:05,200 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:05,201 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:05,201 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 2 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:05,207 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:05,236 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:05,244 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:05,325 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:05,327 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:05,355 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:05,356 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:05,361 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:05,362 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-29 22:37:05,408 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:05,409 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:05,412 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-29 22:37:05,413 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:05,426 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:05,427 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:05,427 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:37:05,428 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:05,436 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:05,436 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-29 22:37:05,651 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:05,672 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:05,672 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 24 [2018-01-29 22:37:05,673 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-29 22:37:05,673 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-29 22:37:05,673 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=532, Unknown=0, NotChecked=0, Total=600 [2018-01-29 22:37:05,673 INFO L87 Difference]: Start difference. First operand 118 states and 136 transitions. Second operand 25 states. [2018-01-29 22:37:06,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:06,333 INFO L93 Difference]: Finished difference Result 177 states and 197 transitions. [2018-01-29 22:37:06,333 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2018-01-29 22:37:06,334 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 39 [2018-01-29 22:37:06,334 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:06,335 INFO L225 Difference]: With dead ends: 177 [2018-01-29 22:37:06,335 INFO L226 Difference]: Without dead ends: 173 [2018-01-29 22:37:06,336 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 62 GetRequests, 28 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 270 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=192, Invalid=1068, Unknown=0, NotChecked=0, Total=1260 [2018-01-29 22:37:06,337 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 173 states. [2018-01-29 22:37:06,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 173 to 125. [2018-01-29 22:37:06,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 125 states. [2018-01-29 22:37:06,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 125 states to 125 states and 144 transitions. [2018-01-29 22:37:06,347 INFO L78 Accepts]: Start accepts. Automaton has 125 states and 144 transitions. Word has length 39 [2018-01-29 22:37:06,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:06,348 INFO L432 AbstractCegarLoop]: Abstraction has 125 states and 144 transitions. [2018-01-29 22:37:06,348 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-29 22:37:06,348 INFO L276 IsEmpty]: Start isEmpty. Operand 125 states and 144 transitions. [2018-01-29 22:37:06,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-29 22:37:06,350 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:06,350 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:06,350 INFO L371 AbstractCegarLoop]: === Iteration 10 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:06,350 INFO L82 PathProgramCache]: Analyzing trace with hash -1038587179, now seen corresponding path program 1 times [2018-01-29 22:37:06,350 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:06,350 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:06,352 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:06,352 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:06,352 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:06,365 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:06,366 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:06,455 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:06,455 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:06,455 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-29 22:37:06,456 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-29 22:37:06,456 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-29 22:37:06,456 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-29 22:37:06,457 INFO L87 Difference]: Start difference. First operand 125 states and 144 transitions. Second operand 6 states. [2018-01-29 22:37:06,532 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:06,532 INFO L93 Difference]: Finished difference Result 130 states and 151 transitions. [2018-01-29 22:37:06,533 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-01-29 22:37:06,533 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 40 [2018-01-29 22:37:06,533 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:06,534 INFO L225 Difference]: With dead ends: 130 [2018-01-29 22:37:06,534 INFO L226 Difference]: Without dead ends: 129 [2018-01-29 22:37:06,535 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=19, Invalid=37, Unknown=0, NotChecked=0, Total=56 [2018-01-29 22:37:06,535 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2018-01-29 22:37:06,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 124. [2018-01-29 22:37:06,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 124 states. [2018-01-29 22:37:06,544 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 141 transitions. [2018-01-29 22:37:06,544 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 141 transitions. Word has length 40 [2018-01-29 22:37:06,544 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:06,544 INFO L432 AbstractCegarLoop]: Abstraction has 124 states and 141 transitions. [2018-01-29 22:37:06,545 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-29 22:37:06,545 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 141 transitions. [2018-01-29 22:37:06,546 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 41 [2018-01-29 22:37:06,546 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:06,546 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:06,546 INFO L371 AbstractCegarLoop]: === Iteration 11 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:06,546 INFO L82 PathProgramCache]: Analyzing trace with hash -1038587178, now seen corresponding path program 1 times [2018-01-29 22:37:06,546 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:06,547 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:06,547 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:06,547 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:06,548 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:06,559 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:06,560 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:06,682 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:06,683 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:06,683 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2018-01-29 22:37:06,683 INFO L409 AbstractCegarLoop]: Interpolant automaton has 9 states [2018-01-29 22:37:06,683 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2018-01-29 22:37:06,684 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2018-01-29 22:37:06,684 INFO L87 Difference]: Start difference. First operand 124 states and 141 transitions. Second operand 9 states. [2018-01-29 22:37:06,854 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:06,854 INFO L93 Difference]: Finished difference Result 175 states and 200 transitions. [2018-01-29 22:37:06,854 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-01-29 22:37:06,854 INFO L78 Accepts]: Start accepts. Automaton has 9 states. Word has length 40 [2018-01-29 22:37:06,855 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:06,855 INFO L225 Difference]: With dead ends: 175 [2018-01-29 22:37:06,855 INFO L226 Difference]: Without dead ends: 174 [2018-01-29 22:37:06,856 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 22 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2018-01-29 22:37:06,856 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2018-01-29 22:37:06,862 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 142. [2018-01-29 22:37:06,863 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 142 states. [2018-01-29 22:37:06,864 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 142 states to 142 states and 161 transitions. [2018-01-29 22:37:06,864 INFO L78 Accepts]: Start accepts. Automaton has 142 states and 161 transitions. Word has length 40 [2018-01-29 22:37:06,864 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:06,864 INFO L432 AbstractCegarLoop]: Abstraction has 142 states and 161 transitions. [2018-01-29 22:37:06,865 INFO L433 AbstractCegarLoop]: Interpolant automaton has 9 states. [2018-01-29 22:37:06,865 INFO L276 IsEmpty]: Start isEmpty. Operand 142 states and 161 transitions. [2018-01-29 22:37:06,866 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2018-01-29 22:37:06,866 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:06,866 INFO L350 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:06,866 INFO L371 AbstractCegarLoop]: === Iteration 12 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:06,866 INFO L82 PathProgramCache]: Analyzing trace with hash 153428241, now seen corresponding path program 2 times [2018-01-29 22:37:06,866 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:06,867 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:06,867 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:06,867 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:06,868 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:06,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:06,884 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:07,266 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:07,267 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:07,267 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:07,272 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-29 22:37:07,287 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:37:07,294 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:37:07,297 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-29 22:37:07,301 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:07,383 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:07,383 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,390 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:07,390 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,396 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,396 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-29 22:37:07,455 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:07,455 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:07,456 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:37:07,456 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,466 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:07,467 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-01-29 22:37:07,467 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,476 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,476 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:28 [2018-01-29 22:37:07,538 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-29 22:37:07,540 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-29 22:37:07,540 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,541 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,550 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-29 22:37:07,550 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:40 [2018-01-29 22:37:07,584 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:07,587 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 32 [2018-01-29 22:37:07,589 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-29 22:37:07,590 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,594 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,602 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-29 22:37:07,602 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:51, output treesize:47 [2018-01-29 22:37:07,792 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:07,794 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 33 treesize of output 31 [2018-01-29 22:37:07,803 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 18 treesize of output 19 [2018-01-29 22:37:07,803 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-29 22:37:07,814 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 1 [2018-01-29 22:37:07,815 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:07,818 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:37:07,828 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 2 xjuncts. [2018-01-29 22:37:07,828 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 3 variables, input treesize:53, output treesize:69 [2018-01-29 22:37:08,131 INFO L134 CoverageAnalysis]: Checked inductivity of 11 backedges. 0 proven. 11 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:08,152 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:08,152 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 19] total 34 [2018-01-29 22:37:08,152 INFO L409 AbstractCegarLoop]: Interpolant automaton has 35 states [2018-01-29 22:37:08,152 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2018-01-29 22:37:08,153 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=109, Invalid=1081, Unknown=0, NotChecked=0, Total=1190 [2018-01-29 22:37:08,153 INFO L87 Difference]: Start difference. First operand 142 states and 161 transitions. Second operand 35 states. [2018-01-29 22:37:08,730 WARN L143 SmtUtils]: Spent 320ms on a formula simplification that was a NOOP. DAG size: 55 [2018-01-29 22:37:10,408 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:10,408 INFO L93 Difference]: Finished difference Result 344 states and 380 transitions. [2018-01-29 22:37:10,446 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 33 states. [2018-01-29 22:37:10,446 INFO L78 Accepts]: Start accepts. Automaton has 35 states. Word has length 46 [2018-01-29 22:37:10,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:10,448 INFO L225 Difference]: With dead ends: 344 [2018-01-29 22:37:10,448 INFO L226 Difference]: Without dead ends: 340 [2018-01-29 22:37:10,449 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 87 GetRequests, 28 SyntacticMatches, 1 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 785 ImplicationChecksByTransitivity, 2.2s TimeCoverageRelationStatistics Valid=452, Invalid=3088, Unknown=0, NotChecked=0, Total=3540 [2018-01-29 22:37:10,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 340 states. [2018-01-29 22:37:10,459 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 340 to 149. [2018-01-29 22:37:10,459 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 149 states. [2018-01-29 22:37:10,460 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 149 states to 149 states and 169 transitions. [2018-01-29 22:37:10,460 INFO L78 Accepts]: Start accepts. Automaton has 149 states and 169 transitions. Word has length 46 [2018-01-29 22:37:10,461 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:10,461 INFO L432 AbstractCegarLoop]: Abstraction has 149 states and 169 transitions. [2018-01-29 22:37:10,461 INFO L433 AbstractCegarLoop]: Interpolant automaton has 35 states. [2018-01-29 22:37:10,461 INFO L276 IsEmpty]: Start isEmpty. Operand 149 states and 169 transitions. [2018-01-29 22:37:10,462 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2018-01-29 22:37:10,462 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:10,463 INFO L350 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:10,463 INFO L371 AbstractCegarLoop]: === Iteration 13 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:10,463 INFO L82 PathProgramCache]: Analyzing trace with hash -485619196, now seen corresponding path program 3 times [2018-01-29 22:37:10,463 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:10,463 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:10,464 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:10,464 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-29 22:37:10,464 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:10,481 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:10,482 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:10,753 WARN L146 SmtUtils]: Spent 118ms on a formula simplification. DAG size of input: 36 DAG size of output 26 [2018-01-29 22:37:11,170 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:11,170 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:11,170 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:11,178 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-01-29 22:37:11,193 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-29 22:37:11,197 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-29 22:37:11,201 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-29 22:37:11,205 INFO L254 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued a check-sat command [2018-01-29 22:37:11,206 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-29 22:37:11,211 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:11,272 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:11,272 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,285 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:11,286 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,293 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,294 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-29 22:37:11,361 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:11,362 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:11,362 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:37:11,362 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,373 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:11,373 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-01-29 22:37:11,373 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,384 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,384 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:39, output treesize:28 [2018-01-29 22:37:11,445 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-29 22:37:11,447 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-29 22:37:11,447 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,448 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,456 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-29 22:37:11,457 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:44, output treesize:40 [2018-01-29 22:37:11,494 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:11,498 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 32 [2018-01-29 22:37:11,499 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2018-01-29 22:37:11,500 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,503 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,511 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-29 22:37:11,511 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:51, output treesize:47 [2018-01-29 22:37:11,894 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:11,896 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 37 [2018-01-29 22:37:11,907 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 24 treesize of output 39 [2018-01-29 22:37:11,908 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 3 xjuncts. [2018-01-29 22:37:11,925 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 9 treesize of output 1 [2018-01-29 22:37:11,926 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:11,935 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:37:11,960 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 7 dim-0 vars, and 2 xjuncts. [2018-01-29 22:37:11,960 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:66, output treesize:227 [2018-01-29 22:37:12,349 INFO L134 CoverageAnalysis]: Checked inductivity of 27 backedges. 0 proven. 27 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:12,369 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:12,369 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [21, 24] total 44 [2018-01-29 22:37:12,369 INFO L409 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-01-29 22:37:12,370 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-01-29 22:37:12,370 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=1823, Unknown=0, NotChecked=0, Total=1980 [2018-01-29 22:37:12,370 INFO L87 Difference]: Start difference. First operand 149 states and 169 transitions. Second operand 45 states. [2018-01-29 22:37:15,344 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:15,344 INFO L93 Difference]: Finished difference Result 349 states and 387 transitions. [2018-01-29 22:37:15,344 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2018-01-29 22:37:15,344 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 53 [2018-01-29 22:37:15,344 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:15,346 INFO L225 Difference]: With dead ends: 349 [2018-01-29 22:37:15,346 INFO L226 Difference]: Without dead ends: 345 [2018-01-29 22:37:15,348 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 101 GetRequests, 30 SyntacticMatches, 1 SemanticMatches, 70 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1165 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=641, Invalid=4471, Unknown=0, NotChecked=0, Total=5112 [2018-01-29 22:37:15,348 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 345 states. [2018-01-29 22:37:15,357 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 345 to 156. [2018-01-29 22:37:15,357 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 156 states. [2018-01-29 22:37:15,358 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 156 states to 156 states and 177 transitions. [2018-01-29 22:37:15,359 INFO L78 Accepts]: Start accepts. Automaton has 156 states and 177 transitions. Word has length 53 [2018-01-29 22:37:15,359 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:15,359 INFO L432 AbstractCegarLoop]: Abstraction has 156 states and 177 transitions. [2018-01-29 22:37:15,359 INFO L433 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-01-29 22:37:15,359 INFO L276 IsEmpty]: Start isEmpty. Operand 156 states and 177 transitions. [2018-01-29 22:37:15,360 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-01-29 22:37:15,360 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:15,360 INFO L350 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:15,361 INFO L371 AbstractCegarLoop]: === Iteration 14 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:15,361 INFO L82 PathProgramCache]: Analyzing trace with hash -1033741019, now seen corresponding path program 1 times [2018-01-29 22:37:15,361 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:15,361 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:15,362 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:15,362 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-29 22:37:15,362 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:15,372 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:15,373 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:15,410 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 3 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:15,410 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:15,448 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-01-29 22:37:15,448 INFO L409 AbstractCegarLoop]: Interpolant automaton has 3 states [2018-01-29 22:37:15,449 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2018-01-29 22:37:15,449 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-29 22:37:15,449 INFO L87 Difference]: Start difference. First operand 156 states and 177 transitions. Second operand 3 states. [2018-01-29 22:37:15,460 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:15,460 INFO L93 Difference]: Finished difference Result 204 states and 229 transitions. [2018-01-29 22:37:15,461 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-01-29 22:37:15,461 INFO L78 Accepts]: Start accepts. Automaton has 3 states. Word has length 54 [2018-01-29 22:37:15,461 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:15,462 INFO L225 Difference]: With dead ends: 204 [2018-01-29 22:37:15,462 INFO L226 Difference]: Without dead ends: 140 [2018-01-29 22:37:15,462 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-01-29 22:37:15,462 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 140 states. [2018-01-29 22:37:15,470 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 140 to 140. [2018-01-29 22:37:15,470 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 140 states. [2018-01-29 22:37:15,471 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 140 states to 140 states and 156 transitions. [2018-01-29 22:37:15,471 INFO L78 Accepts]: Start accepts. Automaton has 140 states and 156 transitions. Word has length 54 [2018-01-29 22:37:15,471 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:15,472 INFO L432 AbstractCegarLoop]: Abstraction has 140 states and 156 transitions. [2018-01-29 22:37:15,472 INFO L433 AbstractCegarLoop]: Interpolant automaton has 3 states. [2018-01-29 22:37:15,472 INFO L276 IsEmpty]: Start isEmpty. Operand 140 states and 156 transitions. [2018-01-29 22:37:15,472 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 55 [2018-01-29 22:37:15,472 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:15,473 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:15,473 INFO L371 AbstractCegarLoop]: === Iteration 15 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:15,473 INFO L82 PathProgramCache]: Analyzing trace with hash -211914578, now seen corresponding path program 1 times [2018-01-29 22:37:15,473 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:15,473 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:15,474 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:15,474 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:15,474 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:15,482 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:15,483 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:15,563 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:15,563 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:15,563 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-29 22:37:15,563 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-29 22:37:15,564 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-29 22:37:15,564 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2018-01-29 22:37:15,564 INFO L87 Difference]: Start difference. First operand 140 states and 156 transitions. Second operand 6 states. [2018-01-29 22:37:15,608 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:15,608 INFO L93 Difference]: Finished difference Result 189 states and 207 transitions. [2018-01-29 22:37:15,609 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-29 22:37:15,609 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 54 [2018-01-29 22:37:15,609 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:15,610 INFO L225 Difference]: With dead ends: 189 [2018-01-29 22:37:15,610 INFO L226 Difference]: Without dead ends: 169 [2018-01-29 22:37:15,610 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=36, Unknown=0, NotChecked=0, Total=56 [2018-01-29 22:37:15,611 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 169 states. [2018-01-29 22:37:15,622 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 169 to 146. [2018-01-29 22:37:15,623 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 146 states. [2018-01-29 22:37:15,624 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 146 states to 146 states and 162 transitions. [2018-01-29 22:37:15,624 INFO L78 Accepts]: Start accepts. Automaton has 146 states and 162 transitions. Word has length 54 [2018-01-29 22:37:15,624 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:15,624 INFO L432 AbstractCegarLoop]: Abstraction has 146 states and 162 transitions. [2018-01-29 22:37:15,624 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-29 22:37:15,625 INFO L276 IsEmpty]: Start isEmpty. Operand 146 states and 162 transitions. [2018-01-29 22:37:15,625 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 59 [2018-01-29 22:37:15,625 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:15,626 INFO L350 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:15,626 INFO L371 AbstractCegarLoop]: === Iteration 16 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:15,626 INFO L82 PathProgramCache]: Analyzing trace with hash -899211454, now seen corresponding path program 1 times [2018-01-29 22:37:15,626 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:15,626 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:15,627 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:15,628 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:15,628 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:15,641 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:15,642 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:15,879 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:15,879 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:15,879 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:15,885 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:15,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:15,913 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:15,920 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 11 [2018-01-29 22:37:15,923 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 10 [2018-01-29 22:37:15,923 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:15,926 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:15,934 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-29 22:37:15,934 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:25, output treesize:21 [2018-01-29 22:37:16,087 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 16 [2018-01-29 22:37:16,092 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 16 treesize of output 13 [2018-01-29 22:37:16,093 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-29 22:37:16,096 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:37:16,104 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:37:16,104 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:38, output treesize:29 [2018-01-29 22:37:16,187 INFO L134 CoverageAnalysis]: Checked inductivity of 6 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:16,207 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:16,208 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 11] total 20 [2018-01-29 22:37:16,208 INFO L409 AbstractCegarLoop]: Interpolant automaton has 21 states [2018-01-29 22:37:16,208 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2018-01-29 22:37:16,208 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=48, Invalid=372, Unknown=0, NotChecked=0, Total=420 [2018-01-29 22:37:16,208 INFO L87 Difference]: Start difference. First operand 146 states and 162 transitions. Second operand 21 states. [2018-01-29 22:37:16,934 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:16,934 INFO L93 Difference]: Finished difference Result 192 states and 209 transitions. [2018-01-29 22:37:16,935 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2018-01-29 22:37:16,935 INFO L78 Accepts]: Start accepts. Automaton has 21 states. Word has length 58 [2018-01-29 22:37:16,935 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:16,936 INFO L225 Difference]: With dead ends: 192 [2018-01-29 22:37:16,936 INFO L226 Difference]: Without dead ends: 191 [2018-01-29 22:37:16,936 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 51 SyntacticMatches, 0 SemanticMatches, 31 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 150 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=148, Invalid=908, Unknown=0, NotChecked=0, Total=1056 [2018-01-29 22:37:16,936 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 191 states. [2018-01-29 22:37:16,942 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 191 to 163. [2018-01-29 22:37:16,942 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 163 states. [2018-01-29 22:37:16,943 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 181 transitions. [2018-01-29 22:37:16,943 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 181 transitions. Word has length 58 [2018-01-29 22:37:16,943 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:16,943 INFO L432 AbstractCegarLoop]: Abstraction has 163 states and 181 transitions. [2018-01-29 22:37:16,943 INFO L433 AbstractCegarLoop]: Interpolant automaton has 21 states. [2018-01-29 22:37:16,944 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 181 transitions. [2018-01-29 22:37:16,944 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-29 22:37:16,944 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:16,944 INFO L350 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:16,944 INFO L371 AbstractCegarLoop]: === Iteration 17 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:16,944 INFO L82 PathProgramCache]: Analyzing trace with hash -2105751261, now seen corresponding path program 1 times [2018-01-29 22:37:16,944 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:16,945 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:16,945 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:16,945 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:16,945 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:16,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:16,954 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:17,012 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2018-01-29 22:37:17,012 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:17,013 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2018-01-29 22:37:17,013 INFO L409 AbstractCegarLoop]: Interpolant automaton has 7 states [2018-01-29 22:37:17,013 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2018-01-29 22:37:17,013 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2018-01-29 22:37:17,013 INFO L87 Difference]: Start difference. First operand 163 states and 181 transitions. Second operand 7 states. [2018-01-29 22:37:17,106 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:17,106 INFO L93 Difference]: Finished difference Result 163 states and 181 transitions. [2018-01-29 22:37:17,106 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2018-01-29 22:37:17,106 INFO L78 Accepts]: Start accepts. Automaton has 7 states. Word has length 59 [2018-01-29 22:37:17,107 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:17,107 INFO L225 Difference]: With dead ends: 163 [2018-01-29 22:37:17,107 INFO L226 Difference]: Without dead ends: 161 [2018-01-29 22:37:17,107 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=29, Invalid=61, Unknown=0, NotChecked=0, Total=90 [2018-01-29 22:37:17,108 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2018-01-29 22:37:17,116 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 157. [2018-01-29 22:37:17,116 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 157 states. [2018-01-29 22:37:17,117 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 157 states to 157 states and 174 transitions. [2018-01-29 22:37:17,118 INFO L78 Accepts]: Start accepts. Automaton has 157 states and 174 transitions. Word has length 59 [2018-01-29 22:37:17,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:17,118 INFO L432 AbstractCegarLoop]: Abstraction has 157 states and 174 transitions. [2018-01-29 22:37:17,118 INFO L433 AbstractCegarLoop]: Interpolant automaton has 7 states. [2018-01-29 22:37:17,118 INFO L276 IsEmpty]: Start isEmpty. Operand 157 states and 174 transitions. [2018-01-29 22:37:17,119 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-29 22:37:17,119 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:17,119 INFO L350 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:17,119 INFO L371 AbstractCegarLoop]: === Iteration 18 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:17,120 INFO L82 PathProgramCache]: Analyzing trace with hash -2105751260, now seen corresponding path program 1 times [2018-01-29 22:37:17,120 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:17,120 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:17,121 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:17,121 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:17,121 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:17,132 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:17,133 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:17,473 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:17,474 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:17,474 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:17,483 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:17,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:17,508 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:17,565 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:17,565 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:17,570 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:17,570 INFO L202 ElimStorePlain]: Needed 2 recursive calls to eliminate 2 variables, input treesize:15, output treesize:11 [2018-01-29 22:37:17,867 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:17,887 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:17,887 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [19, 18] total 35 [2018-01-29 22:37:17,887 INFO L409 AbstractCegarLoop]: Interpolant automaton has 36 states [2018-01-29 22:37:17,887 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 36 interpolants. [2018-01-29 22:37:17,888 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=1163, Unknown=0, NotChecked=0, Total=1260 [2018-01-29 22:37:17,888 INFO L87 Difference]: Start difference. First operand 157 states and 174 transitions. Second operand 36 states. [2018-01-29 22:37:18,832 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:18,833 INFO L93 Difference]: Finished difference Result 233 states and 255 transitions. [2018-01-29 22:37:18,833 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2018-01-29 22:37:18,833 INFO L78 Accepts]: Start accepts. Automaton has 36 states. Word has length 59 [2018-01-29 22:37:18,833 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:18,834 INFO L225 Difference]: With dead ends: 233 [2018-01-29 22:37:18,834 INFO L226 Difference]: Without dead ends: 230 [2018-01-29 22:37:18,835 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 96 GetRequests, 43 SyntacticMatches, 0 SemanticMatches, 53 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 599 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=323, Invalid=2647, Unknown=0, NotChecked=0, Total=2970 [2018-01-29 22:37:18,835 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 230 states. [2018-01-29 22:37:18,841 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 230 to 190. [2018-01-29 22:37:18,841 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 190 states. [2018-01-29 22:37:18,842 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 190 states to 190 states and 211 transitions. [2018-01-29 22:37:18,842 INFO L78 Accepts]: Start accepts. Automaton has 190 states and 211 transitions. Word has length 59 [2018-01-29 22:37:18,842 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:18,843 INFO L432 AbstractCegarLoop]: Abstraction has 190 states and 211 transitions. [2018-01-29 22:37:18,843 INFO L433 AbstractCegarLoop]: Interpolant automaton has 36 states. [2018-01-29 22:37:18,843 INFO L276 IsEmpty]: Start isEmpty. Operand 190 states and 211 transitions. [2018-01-29 22:37:18,843 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2018-01-29 22:37:18,843 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:18,843 INFO L350 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:18,843 INFO L371 AbstractCegarLoop]: === Iteration 19 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:18,844 INFO L82 PathProgramCache]: Analyzing trace with hash -1283924820, now seen corresponding path program 1 times [2018-01-29 22:37:18,844 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:18,844 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:18,844 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:18,845 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:18,845 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:18,856 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:18,857 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:18,960 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:18,960 INFO L320 seRefinementStrategy]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-01-29 22:37:18,960 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2018-01-29 22:37:18,961 INFO L409 AbstractCegarLoop]: Interpolant automaton has 6 states [2018-01-29 22:37:18,961 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2018-01-29 22:37:18,961 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2018-01-29 22:37:18,961 INFO L87 Difference]: Start difference. First operand 190 states and 211 transitions. Second operand 6 states. [2018-01-29 22:37:19,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:19,098 INFO L93 Difference]: Finished difference Result 190 states and 211 transitions. [2018-01-29 22:37:19,098 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2018-01-29 22:37:19,098 INFO L78 Accepts]: Start accepts. Automaton has 6 states. Word has length 59 [2018-01-29 22:37:19,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:19,099 INFO L225 Difference]: With dead ends: 190 [2018-01-29 22:37:19,099 INFO L226 Difference]: Without dead ends: 171 [2018-01-29 22:37:19,099 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2018-01-29 22:37:19,099 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 171 states. [2018-01-29 22:37:19,105 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 171 to 163. [2018-01-29 22:37:19,105 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 163 states. [2018-01-29 22:37:19,106 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 163 states to 163 states and 177 transitions. [2018-01-29 22:37:19,106 INFO L78 Accepts]: Start accepts. Automaton has 163 states and 177 transitions. Word has length 59 [2018-01-29 22:37:19,106 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:19,106 INFO L432 AbstractCegarLoop]: Abstraction has 163 states and 177 transitions. [2018-01-29 22:37:19,106 INFO L433 AbstractCegarLoop]: Interpolant automaton has 6 states. [2018-01-29 22:37:19,106 INFO L276 IsEmpty]: Start isEmpty. Operand 163 states and 177 transitions. [2018-01-29 22:37:19,107 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-29 22:37:19,107 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:19,107 INFO L350 BasicCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:19,108 INFO L371 AbstractCegarLoop]: === Iteration 20 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:19,108 INFO L82 PathProgramCache]: Analyzing trace with hash -525498700, now seen corresponding path program 1 times [2018-01-29 22:37:19,108 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:19,108 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:19,109 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:19,109 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:19,109 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:19,120 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:19,121 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:19,272 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:19,272 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:19,272 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:19,277 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:19,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:19,297 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:19,329 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:19,329 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:19,336 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:19,336 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:19,341 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:19,342 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-29 22:37:19,373 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:19,374 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:19,374 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:37:19,374 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:19,381 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:19,382 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-29 22:37:19,382 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:19,388 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:19,389 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:18 [2018-01-29 22:37:19,559 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:19,580 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:19,580 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 24 [2018-01-29 22:37:19,581 INFO L409 AbstractCegarLoop]: Interpolant automaton has 25 states [2018-01-29 22:37:19,581 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2018-01-29 22:37:19,581 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=68, Invalid=532, Unknown=0, NotChecked=0, Total=600 [2018-01-29 22:37:19,581 INFO L87 Difference]: Start difference. First operand 163 states and 177 transitions. Second operand 25 states. [2018-01-29 22:37:20,032 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:20,032 INFO L93 Difference]: Finished difference Result 172 states and 185 transitions. [2018-01-29 22:37:20,032 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-01-29 22:37:20,033 INFO L78 Accepts]: Start accepts. Automaton has 25 states. Word has length 60 [2018-01-29 22:37:20,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:20,033 INFO L225 Difference]: With dead ends: 172 [2018-01-29 22:37:20,033 INFO L226 Difference]: Without dead ends: 166 [2018-01-29 22:37:20,034 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 81 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 32 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 243 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=166, Invalid=956, Unknown=0, NotChecked=0, Total=1122 [2018-01-29 22:37:20,034 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2018-01-29 22:37:20,040 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 158. [2018-01-29 22:37:20,040 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 158 states. [2018-01-29 22:37:20,040 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 171 transitions. [2018-01-29 22:37:20,041 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 171 transitions. Word has length 60 [2018-01-29 22:37:20,041 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:20,041 INFO L432 AbstractCegarLoop]: Abstraction has 158 states and 171 transitions. [2018-01-29 22:37:20,041 INFO L433 AbstractCegarLoop]: Interpolant automaton has 25 states. [2018-01-29 22:37:20,041 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 171 transitions. [2018-01-29 22:37:20,041 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2018-01-29 22:37:20,041 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:20,041 INFO L350 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:20,042 INFO L371 AbstractCegarLoop]: === Iteration 21 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:20,042 INFO L82 PathProgramCache]: Analyzing trace with hash 1066252721, now seen corresponding path program 4 times [2018-01-29 22:37:20,042 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:20,042 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:20,042 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:20,043 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:20,043 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:20,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:20,055 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:20,902 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:20,902 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:20,902 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:20,907 INFO L101 rtionOrderModulation]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-01-29 22:37:20,927 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-29 22:37:20,931 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:21,002 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:21,003 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,010 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:21,010 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,016 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,016 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-29 22:37:21,080 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,080 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,081 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-01-29 22:37:21,081 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,094 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,094 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,095 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:37:21,095 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,102 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,102 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-29 22:37:21,170 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-29 22:37:21,172 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-29 22:37:21,172 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,174 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,181 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-29 22:37:21,181 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-29 22:37:21,220 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,223 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 33 [2018-01-29 22:37:21,225 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-29 22:37:21,225 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,229 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,237 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-29 22:37:21,237 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-29 22:37:21,975 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,980 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 55 treesize of output 49 [2018-01-29 22:37:21,982 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-29 22:37:21,983 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:21,992 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,992 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:21,993 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:22,001 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 4 select indices, 4 select index equivalence classes, 7 disjoint index pairs (out of 6 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 73 [2018-01-29 22:37:22,002 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 2 xjuncts. [2018-01-29 22:37:22,021 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:37:22,041 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-29 22:37:22,041 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:83, output treesize:146 [2018-01-29 22:37:22,459 INFO L134 CoverageAnalysis]: Checked inductivity of 50 backedges. 0 proven. 50 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:22,479 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:22,479 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [24, 27] total 50 [2018-01-29 22:37:22,479 INFO L409 AbstractCegarLoop]: Interpolant automaton has 51 states [2018-01-29 22:37:22,479 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2018-01-29 22:37:22,480 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=157, Invalid=2393, Unknown=0, NotChecked=0, Total=2550 [2018-01-29 22:37:22,480 INFO L87 Difference]: Start difference. First operand 158 states and 171 transitions. Second operand 51 states. [2018-01-29 22:37:23,306 WARN L146 SmtUtils]: Spent 358ms on a formula simplification. DAG size of input: 91 DAG size of output 52 [2018-01-29 22:37:38,693 WARN L146 SmtUtils]: Spent 120ms on a formula simplification. DAG size of input: 115 DAG size of output 87 [2018-01-29 22:37:50,185 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:50,185 INFO L93 Difference]: Finished difference Result 261 states and 275 transitions. [2018-01-29 22:37:50,186 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 37 states. [2018-01-29 22:37:50,186 INFO L78 Accepts]: Start accepts. Automaton has 51 states. Word has length 60 [2018-01-29 22:37:50,186 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:50,187 INFO L225 Difference]: With dead ends: 261 [2018-01-29 22:37:50,187 INFO L226 Difference]: Without dead ends: 242 [2018-01-29 22:37:50,188 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1635 ImplicationChecksByTransitivity, 26.8s TimeCoverageRelationStatistics Valid=587, Invalid=6216, Unknown=3, NotChecked=0, Total=6806 [2018-01-29 22:37:50,188 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2018-01-29 22:37:50,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 165. [2018-01-29 22:37:50,196 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 165 states. [2018-01-29 22:37:50,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 165 states to 165 states and 179 transitions. [2018-01-29 22:37:50,196 INFO L78 Accepts]: Start accepts. Automaton has 165 states and 179 transitions. Word has length 60 [2018-01-29 22:37:50,197 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:50,197 INFO L432 AbstractCegarLoop]: Abstraction has 165 states and 179 transitions. [2018-01-29 22:37:50,197 INFO L433 AbstractCegarLoop]: Interpolant automaton has 51 states. [2018-01-29 22:37:50,197 INFO L276 IsEmpty]: Start isEmpty. Operand 165 states and 179 transitions. [2018-01-29 22:37:50,197 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2018-01-29 22:37:50,197 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:50,197 INFO L350 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:50,197 INFO L371 AbstractCegarLoop]: === Iteration 22 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:50,198 INFO L82 PathProgramCache]: Analyzing trace with hash 1708344081, now seen corresponding path program 1 times [2018-01-29 22:37:50,198 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:50,198 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:50,198 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:50,198 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-29 22:37:50,198 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:50,207 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:50,208 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:50,938 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:50,939 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:50,939 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:50,944 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:50,964 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:50,969 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:50,999 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:50,999 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:51,007 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:51,007 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:51,014 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:51,015 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-29 22:37:51,069 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:51,069 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:51,070 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-29 22:37:51,070 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:51,080 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:51,080 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:51,081 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:37:51,081 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:51,086 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:51,086 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:16 [2018-01-29 22:37:51,772 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:51,794 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:51,794 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 24] total 44 [2018-01-29 22:37:51,794 INFO L409 AbstractCegarLoop]: Interpolant automaton has 45 states [2018-01-29 22:37:51,794 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 45 interpolants. [2018-01-29 22:37:51,795 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=1867, Unknown=0, NotChecked=0, Total=1980 [2018-01-29 22:37:51,795 INFO L87 Difference]: Start difference. First operand 165 states and 179 transitions. Second operand 45 states. [2018-01-29 22:37:54,604 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:54,604 INFO L93 Difference]: Finished difference Result 265 states and 283 transitions. [2018-01-29 22:37:54,605 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 39 states. [2018-01-29 22:37:54,605 INFO L78 Accepts]: Start accepts. Automaton has 45 states. Word has length 66 [2018-01-29 22:37:54,605 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:54,606 INFO L225 Difference]: With dead ends: 265 [2018-01-29 22:37:54,606 INFO L226 Difference]: Without dead ends: 242 [2018-01-29 22:37:54,607 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 122 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 78 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1394 ImplicationChecksByTransitivity, 3.3s TimeCoverageRelationStatistics Valid=602, Invalid=5718, Unknown=0, NotChecked=0, Total=6320 [2018-01-29 22:37:54,607 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 242 states. [2018-01-29 22:37:54,615 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 242 to 213. [2018-01-29 22:37:54,615 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-01-29 22:37:54,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 230 transitions. [2018-01-29 22:37:54,616 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 230 transitions. Word has length 66 [2018-01-29 22:37:54,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:54,616 INFO L432 AbstractCegarLoop]: Abstraction has 213 states and 230 transitions. [2018-01-29 22:37:54,616 INFO L433 AbstractCegarLoop]: Interpolant automaton has 45 states. [2018-01-29 22:37:54,616 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 230 transitions. [2018-01-29 22:37:54,616 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2018-01-29 22:37:54,617 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:54,617 INFO L350 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:54,617 INFO L371 AbstractCegarLoop]: === Iteration 23 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:54,617 INFO L82 PathProgramCache]: Analyzing trace with hash 1747339879, now seen corresponding path program 1 times [2018-01-29 22:37:54,617 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:54,617 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:54,618 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:54,618 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:54,618 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:54,627 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:54,628 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:37:55,103 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:55,104 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:37:55,110 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 10 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:37:55,115 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:55,135 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:55,138 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:37:55,144 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:55,144 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,151 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:37:55,152 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,158 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,158 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-29 22:37:55,209 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:55,209 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:55,210 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:37:55,210 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,219 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:37:55,220 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-29 22:37:55,220 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,226 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,227 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:30, output treesize:19 [2018-01-29 22:37:55,278 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 13 [2018-01-29 22:37:55,279 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-29 22:37:55,280 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,281 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,286 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:37:55,286 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:34, output treesize:30 [2018-01-29 22:37:55,564 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 20 treesize of output 16 [2018-01-29 22:37:55,573 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 16 treesize of output 13 [2018-01-29 22:37:55,573 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-29 22:37:55,576 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:37:55,585 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 2 xjuncts. [2018-01-29 22:37:55,585 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:40, output treesize:55 [2018-01-29 22:37:55,805 INFO L134 CoverageAnalysis]: Checked inductivity of 7 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:37:55,825 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:37:55,825 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [22, 22] total 40 [2018-01-29 22:37:55,826 INFO L409 AbstractCegarLoop]: Interpolant automaton has 41 states [2018-01-29 22:37:55,826 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 41 interpolants. [2018-01-29 22:37:55,826 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=116, Invalid=1524, Unknown=0, NotChecked=0, Total=1640 [2018-01-29 22:37:55,827 INFO L87 Difference]: Start difference. First operand 213 states and 230 transitions. Second operand 41 states. [2018-01-29 22:37:59,523 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:37:59,524 INFO L93 Difference]: Finished difference Result 241 states and 255 transitions. [2018-01-29 22:37:59,524 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2018-01-29 22:37:59,524 INFO L78 Accepts]: Start accepts. Automaton has 41 states. Word has length 67 [2018-01-29 22:37:59,524 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:37:59,525 INFO L225 Difference]: With dead ends: 241 [2018-01-29 22:37:59,525 INFO L226 Difference]: Without dead ends: 235 [2018-01-29 22:37:59,526 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 112 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 63 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1007 ImplicationChecksByTransitivity, 2.0s TimeCoverageRelationStatistics Valid=400, Invalid=3760, Unknown=0, NotChecked=0, Total=4160 [2018-01-29 22:37:59,526 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 235 states. [2018-01-29 22:37:59,533 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 235 to 213. [2018-01-29 22:37:59,533 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 213 states. [2018-01-29 22:37:59,534 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 213 states to 213 states and 229 transitions. [2018-01-29 22:37:59,534 INFO L78 Accepts]: Start accepts. Automaton has 213 states and 229 transitions. Word has length 67 [2018-01-29 22:37:59,534 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:37:59,534 INFO L432 AbstractCegarLoop]: Abstraction has 213 states and 229 transitions. [2018-01-29 22:37:59,534 INFO L433 AbstractCegarLoop]: Interpolant automaton has 41 states. [2018-01-29 22:37:59,534 INFO L276 IsEmpty]: Start isEmpty. Operand 213 states and 229 transitions. [2018-01-29 22:37:59,535 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2018-01-29 22:37:59,535 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:37:59,535 INFO L350 BasicCegarLoop]: trace histogram [6, 5, 5, 5, 5, 5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:37:59,535 INFO L371 AbstractCegarLoop]: === Iteration 24 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:37:59,535 INFO L82 PathProgramCache]: Analyzing trace with hash -955875996, now seen corresponding path program 5 times [2018-01-29 22:37:59,536 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:37:59,536 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:37:59,536 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:59,537 INFO L101 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2018-01-29 22:37:59,537 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:37:59,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:37:59,552 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:38:00,758 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 80 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:38:00,758 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:38:00,772 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 11 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:38:00,777 INFO L101 rtionOrderModulation]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-01-29 22:38:00,783 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:00,785 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:00,787 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:00,788 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:00,790 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:00,797 INFO L278 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:00,800 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-29 22:38:00,803 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:38:00,869 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:38:00,869 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:00,876 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:38:00,877 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:00,883 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:00,883 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:27, output treesize:25 [2018-01-29 22:38:00,953 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:00,953 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:00,954 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:38:00,954 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:00,963 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:00,964 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 21 [2018-01-29 22:38:00,964 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:00,972 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:00,972 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:36, output treesize:25 [2018-01-29 22:38:01,043 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-29 22:38:01,044 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-29 22:38:01,044 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:01,045 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:01,052 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 1 dim-2 vars, End of recursive call: 1 dim-0 vars, and 1 xjuncts. [2018-01-29 22:38:01,052 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:41, output treesize:37 [2018-01-29 22:38:01,091 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:01,094 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 33 [2018-01-29 22:38:01,095 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-29 22:38:01,096 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:01,100 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:01,110 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: 3 dim-0 vars, and 1 xjuncts. [2018-01-29 22:38:01,110 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 4 variables, input treesize:52, output treesize:48 [2018-01-29 22:38:02,169 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:02,170 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 57 [2018-01-29 22:38:02,181 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:02,181 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:02,182 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:02,184 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:02,184 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:02,185 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:02,194 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 5 select indices, 5 select index equivalence classes, 12 disjoint index pairs (out of 10 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 43 treesize of output 113 [2018-01-29 22:38:02,195 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-29 22:38:02,228 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-29 22:38:02,229 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:02,242 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:38:02,267 INFO L267 ElimStorePlain]: Start of recursive call 1: 4 dim-0 vars, 1 dim-2 vars, End of recursive call: 4 dim-0 vars, and 2 xjuncts. [2018-01-29 22:38:02,268 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 5 variables, input treesize:93, output treesize:166 [2018-01-29 22:38:02,686 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 0 proven. 80 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:38:02,706 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:38:02,706 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 31] total 59 [2018-01-29 22:38:02,706 INFO L409 AbstractCegarLoop]: Interpolant automaton has 60 states [2018-01-29 22:38:02,706 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2018-01-29 22:38:02,707 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=288, Invalid=3252, Unknown=0, NotChecked=0, Total=3540 [2018-01-29 22:38:02,707 INFO L87 Difference]: Start difference. First operand 213 states and 229 transitions. Second operand 60 states. [2018-01-29 22:38:04,139 WARN L146 SmtUtils]: Spent 172ms on a formula simplification. DAG size of input: 98 DAG size of output 59 [2018-01-29 22:38:08,908 WARN L146 SmtUtils]: Spent 228ms on a formula simplification. DAG size of input: 113 DAG size of output 74 [2018-01-29 22:38:09,571 WARN L146 SmtUtils]: Spent 102ms on a formula simplification. DAG size of input: 115 DAG size of output 76 [2018-01-29 22:38:14,928 WARN L146 SmtUtils]: Spent 109ms on a formula simplification. DAG size of input: 103 DAG size of output 64 [2018-01-29 22:38:20,117 WARN L146 SmtUtils]: Spent 103ms on a formula simplification. DAG size of input: 122 DAG size of output 83 [2018-01-29 22:38:20,783 WARN L146 SmtUtils]: Spent 102ms on a formula simplification. DAG size of input: 126 DAG size of output 87 [2018-01-29 22:38:24,944 WARN L146 SmtUtils]: Spent 136ms on a formula simplification. DAG size of input: 132 DAG size of output 93 [2018-01-29 22:38:26,938 WARN L146 SmtUtils]: Spent 208ms on a formula simplification. DAG size of input: 135 DAG size of output 97 [2018-01-29 22:38:29,314 WARN L146 SmtUtils]: Spent 213ms on a formula simplification. DAG size of input: 148 DAG size of output 88 [2018-01-29 22:38:37,110 WARN L146 SmtUtils]: Spent 205ms on a formula simplification. DAG size of input: 145 DAG size of output 104 [2018-01-29 22:38:39,331 WARN L146 SmtUtils]: Spent 121ms on a formula simplification. DAG size of input: 115 DAG size of output 98 [2018-01-29 22:38:48,890 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:38:48,891 INFO L93 Difference]: Finished difference Result 364 states and 388 transitions. [2018-01-29 22:38:48,891 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2018-01-29 22:38:48,891 INFO L78 Accepts]: Start accepts. Automaton has 60 states. Word has length 67 [2018-01-29 22:38:48,891 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:38:48,892 INFO L225 Difference]: With dead ends: 364 [2018-01-29 22:38:48,892 INFO L226 Difference]: Without dead ends: 330 [2018-01-29 22:38:48,895 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 141 GetRequests, 37 SyntacticMatches, 1 SemanticMatches, 103 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3284 ImplicationChecksByTransitivity, 42.9s TimeCoverageRelationStatistics Valid=1149, Invalid=9766, Unknown=5, NotChecked=0, Total=10920 [2018-01-29 22:38:48,896 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 330 states. [2018-01-29 22:38:48,912 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 330 to 227. [2018-01-29 22:38:48,913 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 227 states. [2018-01-29 22:38:48,913 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 227 states to 227 states and 245 transitions. [2018-01-29 22:38:48,913 INFO L78 Accepts]: Start accepts. Automaton has 227 states and 245 transitions. Word has length 67 [2018-01-29 22:38:48,914 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:38:48,914 INFO L432 AbstractCegarLoop]: Abstraction has 227 states and 245 transitions. [2018-01-29 22:38:48,914 INFO L433 AbstractCegarLoop]: Interpolant automaton has 60 states. [2018-01-29 22:38:48,914 INFO L276 IsEmpty]: Start isEmpty. Operand 227 states and 245 transitions. [2018-01-29 22:38:48,915 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 74 [2018-01-29 22:38:48,915 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:38:48,915 INFO L350 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:38:48,915 INFO L371 AbstractCegarLoop]: === Iteration 25 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:38:48,915 INFO L82 PathProgramCache]: Analyzing trace with hash -815188860, now seen corresponding path program 2 times [2018-01-29 22:38:48,915 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:38:48,916 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:38:48,916 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:38:48,916 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-29 22:38:48,916 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:38:48,929 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:38:48,930 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:38:49,612 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:38:49,613 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:38:49,613 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 12 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:38:49,618 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-29 22:38:49,630 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:49,638 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:49,640 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-29 22:38:49,643 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:38:49,646 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:38:49,646 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:49,653 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:38:49,654 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:49,659 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:49,659 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:24, output treesize:19 [2018-01-29 22:38:49,718 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:49,719 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:49,719 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:38:49,719 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:49,731 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:49,732 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 23 [2018-01-29 22:38:49,732 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:49,738 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-0 vars, 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:49,738 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:30, output treesize:16 [2018-01-29 22:38:50,453 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 20 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:38:50,474 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:38:50,474 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [29, 27] total 53 [2018-01-29 22:38:50,474 INFO L409 AbstractCegarLoop]: Interpolant automaton has 54 states [2018-01-29 22:38:50,474 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 54 interpolants. [2018-01-29 22:38:50,475 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=150, Invalid=2712, Unknown=0, NotChecked=0, Total=2862 [2018-01-29 22:38:50,475 INFO L87 Difference]: Start difference. First operand 227 states and 245 transitions. Second operand 54 states. [2018-01-29 22:38:52,597 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2018-01-29 22:38:52,598 INFO L93 Difference]: Finished difference Result 292 states and 310 transitions. [2018-01-29 22:38:52,598 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 35 states. [2018-01-29 22:38:52,598 INFO L78 Accepts]: Start accepts. Automaton has 54 states. Word has length 73 [2018-01-29 22:38:52,598 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2018-01-29 22:38:52,599 INFO L225 Difference]: With dead ends: 292 [2018-01-29 22:38:52,599 INFO L226 Difference]: Without dead ends: 279 [2018-01-29 22:38:52,600 INFO L553 BasicCegarLoop]: 0 DeclaredPredicates, 130 GetRequests, 49 SyntacticMatches, 0 SemanticMatches, 81 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1662 ImplicationChecksByTransitivity, 2.4s TimeCoverageRelationStatistics Valid=539, Invalid=6267, Unknown=0, NotChecked=0, Total=6806 [2018-01-29 22:38:52,600 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 279 states. [2018-01-29 22:38:52,610 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 279 to 249. [2018-01-29 22:38:52,610 INFO L82 GeneralOperation]: Start removeUnreachable. Operand 249 states. [2018-01-29 22:38:52,610 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 249 states to 249 states and 268 transitions. [2018-01-29 22:38:52,610 INFO L78 Accepts]: Start accepts. Automaton has 249 states and 268 transitions. Word has length 73 [2018-01-29 22:38:52,610 INFO L84 Accepts]: Finished accepts. word is rejected. [2018-01-29 22:38:52,611 INFO L432 AbstractCegarLoop]: Abstraction has 249 states and 268 transitions. [2018-01-29 22:38:52,611 INFO L433 AbstractCegarLoop]: Interpolant automaton has 54 states. [2018-01-29 22:38:52,611 INFO L276 IsEmpty]: Start isEmpty. Operand 249 states and 268 transitions. [2018-01-29 22:38:52,611 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 75 [2018-01-29 22:38:52,611 INFO L342 BasicCegarLoop]: Found error trace [2018-01-29 22:38:52,611 INFO L350 BasicCegarLoop]: trace histogram [3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2018-01-29 22:38:52,611 INFO L371 AbstractCegarLoop]: === Iteration 26 === [mainErr3RequiresViolation, mainErr1RequiresViolation, mainErr2RequiresViolation, mainErr0RequiresViolation, mainErr4EnsuresViolation, cstrncatErr7RequiresViolation, cstrncatErr5RequiresViolation, cstrncatErr0RequiresViolation, cstrncatErr3RequiresViolation, cstrncatErr9RequiresViolation, cstrncatErr1RequiresViolation, cstrncatErr2RequiresViolation, cstrncatErr8RequiresViolation, cstrncatErr6RequiresViolation, cstrncatErr4RequiresViolation]=== [2018-01-29 22:38:52,611 INFO L82 PathProgramCache]: Analyzing trace with hash 827230036, now seen corresponding path program 2 times [2018-01-29 22:38:52,611 INFO L209 onRefinementStrategy]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-01-29 22:38:52,612 INFO L67 tionRefinementEngine]: Using refinement strategy CamelRefinementStrategy [2018-01-29 22:38:52,612 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:38:52,612 INFO L99 rtionOrderModulation]: Changing assertion order to NOT_INCREMENTALLY [2018-01-29 22:38:52,612 INFO L117 rtionOrderModulation]: Craig nested/tree interpolation forces the following order [2018-01-29 22:38:52,620 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2018-01-29 22:38:52,621 WARN L137 erpolLogProxyWrapper]: Using partial proofs (cut at CNF-level). Set option :produce-proofs to true to get complete proofs. [2018-01-29 22:38:53,407 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:38:53,408 INFO L308 seRefinementStrategy]: The current sequences of interpolants are not accepted, trying to find more. [2018-01-29 22:38:53,408 INFO L209 onRefinementStrategy]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 13 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-01-29 22:38:53,412 INFO L101 rtionOrderModulation]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-01-29 22:38:53,424 INFO L201 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:53,431 INFO L214 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued a check-sat command [2018-01-29 22:38:53,433 INFO L239 tOrderPrioritization]: Conjunction of SSA is unsat [2018-01-29 22:38:53,436 INFO L270 TraceCheckSpWp]: Computing forward predicates... [2018-01-29 22:38:53,459 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:38:53,459 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,465 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 6 treesize of output 5 [2018-01-29 22:38:53,465 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,469 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,469 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:19, output treesize:17 [2018-01-29 22:38:53,526 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:53,527 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 15 [2018-01-29 22:38:53,527 INFO L267 ElimStorePlain]: Start of recursive call 2: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,535 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:53,536 INFO L700 Elim1Store]: detected not equals via solver [2018-01-29 22:38:53,536 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 4 [2018-01-29 22:38:53,536 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,541 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,541 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 2 variables, input treesize:28, output treesize:21 [2018-01-29 22:38:53,602 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 16 [2018-01-29 22:38:53,603 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 15 [2018-01-29 22:38:53,603 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,605 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,610 INFO L267 ElimStorePlain]: Start of recursive call 1: 1 dim-2 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,611 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 1 variables, input treesize:35, output treesize:31 [2018-01-29 22:38:53,652 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 33 [2018-01-29 22:38:53,653 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 12 [2018-01-29 22:38:53,654 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,658 INFO L267 ElimStorePlain]: Start of recursive call 2: 1 dim-1 vars, End of recursive call: and 1 xjuncts. [2018-01-29 22:38:53,664 INFO L267 ElimStorePlain]: Start of recursive call 1: 2 dim-0 vars, 1 dim-2 vars, End of recursive call: 2 dim-0 vars, and 1 xjuncts. [2018-01-29 22:38:53,664 INFO L202 ElimStorePlain]: Needed 3 recursive calls to eliminate 3 variables, input treesize:42, output treesize:38 [2018-01-29 22:38:54,058 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 34 treesize of output 32 [2018-01-29 22:38:54,063 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 18 treesize of output 15 [2018-01-29 22:38:54,093 INFO L267 ElimStorePlain]: Start of recursive call 3: End of recursive call: and 2 xjuncts. [2018-01-29 22:38:54,099 INFO L477 Elim1Store]: Elim1 did not use preprocessing eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 1 [2018-01-29 22:38:54,100 INFO L267 ElimStorePlain]: Start of recursive call 4: End of recursive call: and 1 xjuncts. [2018-01-29 22:38:54,102 INFO L267 ElimStorePlain]: Start of recursive call 2: 2 dim-1 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:38:54,110 INFO L267 ElimStorePlain]: Start of recursive call 1: 3 dim-0 vars, 1 dim-2 vars, End of recursive call: and 2 xjuncts. [2018-01-29 22:38:54,110 INFO L202 ElimStorePlain]: Needed 4 recursive calls to eliminate 4 variables, input treesize:47, output treesize:38 [2018-01-29 22:38:54,702 INFO L134 CoverageAnalysis]: Checked inductivity of 17 backedges. 2 proven. 15 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-01-29 22:38:54,722 INFO L320 seRefinementStrategy]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-01-29 22:38:54,722 INFO L335 seRefinementStrategy]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25] total 51 [2018-01-29 22:38:54,723 INFO L409 AbstractCegarLoop]: Interpolant automaton has 52 states [2018-01-29 22:38:54,723 INFO L132 InterpolantAutomaton]: Constructing interpolant automaton starting with 52 interpolants. [2018-01-29 22:38:54,723 INFO L133 InterpolantAutomaton]: CoverageRelationStatistics Valid=136, Invalid=2516, Unknown=0, NotChecked=0, Total=2652 [2018-01-29 22:38:54,723 INFO L87 Difference]: Start difference. First operand 249 states and 268 transitions. Second operand 52 states. [2018-01-29 22:38:59,472 WARN L146 SmtUtils]: Spent 4060ms on a formula simplification. DAG size of input: 62 DAG size of output 56 [2018-01-29 22:38:59,629 WARN L146 SmtUtils]: Spent 105ms on a formula simplification. DAG size of input: 68 DAG size of output 62 [2018-01-29 22:39:03,960 WARN L146 SmtUtils]: Spent 4127ms on a formula simplification. DAG size of input: 91 DAG size of output 80 [2018-01-29 22:39:08,248 WARN L146 SmtUtils]: Spent 4195ms on a formula simplification. DAG size of input: 110 DAG size of output 94 [2018-01-29 22:39:12,508 WARN L146 SmtUtils]: Spent 4167ms on a formula simplification. DAG size of input: 113 DAG size of output 98 [2018-01-29 22:39:12,751 WARN L146 SmtUtils]: Spent 132ms on a formula simplification. DAG size of input: 94 DAG size of output 84 [2018-01-29 22:39:17,812 WARN L146 SmtUtils]: Spent 4126ms on a formula simplification. DAG size of input: 80 DAG size of output 70 [2018-01-29 22:39:18,142 WARN L146 SmtUtils]: Spent 252ms on a formula simplification. DAG size of input: 108 DAG size of output 93 [2018-01-29 22:39:18,478 WARN L146 SmtUtils]: Spent 232ms on a formula simplification. DAG size of input: 104 DAG size of output 85 [2018-01-29 22:39:18,723 WARN L146 SmtUtils]: Spent 145ms on a formula simplification. DAG size of input: 96 DAG size of output 86 [2018-01-29 22:39:19,004 WARN L146 SmtUtils]: Spent 206ms on a formula simplification. DAG size of input: 127 DAG size of output 103 [2018-01-29 22:39:19,531 WARN L146 SmtUtils]: Spent 432ms on a formula simplification. DAG size of input: 124 DAG size of output 105 [2018-01-29 22:39:22,339 WARN L146 SmtUtils]: Spent 2747ms on a formula simplification. DAG size of input: 100 DAG size of output 86 [2018-01-29 22:39:26,650 WARN L146 SmtUtils]: Spent 4110ms on a formula simplification. DAG size of input: 82 DAG size of output 72 Received shutdown request... [2018-01-29 22:39:28,771 INFO L142 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 27 states. [2018-01-29 22:39:28,771 WARN L491 AbstractCegarLoop]: Verification canceled [2018-01-29 22:39:28,776 WARN L185 ceAbstractionStarter]: Timeout [2018-01-29 22:39:28,776 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 29.01 10:39:28 BoogieIcfgContainer [2018-01-29 22:39:28,776 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2018-01-29 22:39:28,777 INFO L168 Benchmark]: Toolchain (without parser) took 146584.12 ms. Allocated memory was 306.7 MB in the beginning and 601.9 MB in the end (delta: 295.2 MB). Free memory was 266.7 MB in the beginning and 362.6 MB in the end (delta: -95.8 MB). Peak memory consumption was 199.3 MB. Max. memory is 5.3 GB. [2018-01-29 22:39:28,778 INFO L168 Benchmark]: CDTParser took 0.17 ms. Allocated memory is still 306.7 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 5.3 GB. [2018-01-29 22:39:28,778 INFO L168 Benchmark]: CACSL2BoogieTranslator took 204.29 ms. Allocated memory is still 306.7 MB. Free memory was 265.7 MB in the beginning and 255.5 MB in the end (delta: 10.2 MB). Peak memory consumption was 10.2 MB. Max. memory is 5.3 GB. [2018-01-29 22:39:28,779 INFO L168 Benchmark]: Boogie Preprocessor took 37.76 ms. Allocated memory is still 306.7 MB. Free memory was 255.5 MB in the beginning and 253.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. [2018-01-29 22:39:28,779 INFO L168 Benchmark]: RCFGBuilder took 322.20 ms. Allocated memory is still 306.7 MB. Free memory was 253.5 MB in the beginning and 229.8 MB in the end (delta: 23.7 MB). Peak memory consumption was 23.7 MB. Max. memory is 5.3 GB. [2018-01-29 22:39:28,779 INFO L168 Benchmark]: TraceAbstraction took 146010.18 ms. Allocated memory was 306.7 MB in the beginning and 601.9 MB in the end (delta: 295.2 MB). Free memory was 229.8 MB in the beginning and 362.6 MB in the end (delta: -132.8 MB). Peak memory consumption was 162.4 MB. Max. memory is 5.3 GB. [2018-01-29 22:39:28,781 INFO L344 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.17 ms. Allocated memory is still 306.7 MB. Free memory is still 272.7 MB. There was no memory consumed. Max. memory is 5.3 GB. * CACSL2BoogieTranslator took 204.29 ms. Allocated memory is still 306.7 MB. Free memory was 265.7 MB in the beginning and 255.5 MB in the end (delta: 10.2 MB). Peak memory consumption was 10.2 MB. Max. memory is 5.3 GB. * Boogie Preprocessor took 37.76 ms. Allocated memory is still 306.7 MB. Free memory was 255.5 MB in the beginning and 253.5 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 5.3 GB. * RCFGBuilder took 322.20 ms. Allocated memory is still 306.7 MB. Free memory was 253.5 MB in the beginning and 229.8 MB in the end (delta: 23.7 MB). Peak memory consumption was 23.7 MB. Max. memory is 5.3 GB. * TraceAbstraction took 146010.18 ms. Allocated memory was 306.7 MB in the beginning and 601.9 MB in the end (delta: 295.2 MB). Free memory was 229.8 MB in the beginning and 362.6 MB in the end (delta: -132.8 MB). Peak memory consumption was 162.4 MB. Max. memory is 5.3 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 570). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 569). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 553]: Timeout (TraceAbstraction) Unable to prove that all allocated memory was freed (line 553). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 543). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 550). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 549). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - TimeoutResultAtElement [Line: 1]: Timeout (TraceAbstraction) Unable to prove that pointer dereference always succeeds (line 545). Cancelled while BasicCegarLoop was constructing difference of abstraction (249states) and interpolant automaton (currently 27 states, 52 states before enhancement), while PredicateUnifier was unifying predicates, while SimplifyDDAWithTimeout was simplifying term of DAG size 114. - StatisticsResult: Ultimate Automizer benchmark data CFG has 4 procedures, 96 locations, 15 error locations. TIMEOUT Result, 145.9s OverallTime, 26 OverallIterations, 6 TraceHistogramMax, 126.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 2309 SDtfs, 8962 SDslu, 24669 SDs, 0 SdLazy, 13320 SolverSat, 788 SolverUnsat, 3 SolverUnknown, 0 SolverNotchecked, 16.5s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 1360 GetRequests, 512 SyntacticMatches, 4 SemanticMatches, 843 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 13209 ImplicationChecksByTransitivity, 120.4s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=249occurred in iteration=25, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 25 MinimizatonAttempts, 879 StatesRemovedByMinimization, 19 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 18.0s InterpolantComputationTime, 1972 NumberOfCodeBlocks, 1969 NumberOfCodeBlocksAsserted, 49 NumberOfCheckSat, 1934 ConstructedInterpolants, 235 QuantifiedInterpolants, 1580625 SizeOfPredicates, 310 NumberOfNonLiveVariables, 2089 ConjunctsInSsa, 670 ConjunctsInUnsatCore, 38 InterpolantComputations, 14 PerfectInterpolantSequences, 14/494 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf_AutomizerC.xml/Csv-Benchmark-0-2018-01-29_22-39-28-788.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/cstrncat-alloca_true-valid-memsafety_true-termination.i_svcomp-DerefFreeMemtrack-32bit-Automizer_Camel+AI_EQ_SS.epf_AutomizerC.xml/Csv-TraceAbstractionBenchmarks-0-2018-01-29_22-39-28-788.csv Completed graceful shutdown